数学建模策略方法之遗传算法入门到精通内附源程序源码.pdf

遗传算法的通俗解释之2 ——来自网络，感谢一切为之付出的人们 遗传算法的有趣应用很多，诸如寻路问题，8数码问题，囚犯困境，动作控制， 找圆心问题（这是一个国外网友的建议：在一个不规则的多边形 中，寻找一个 包含在该多边形内的最大圆圈的圆心。），TSP 问题（在以后的章节里面将做 详细介绍。），生产调度问题，人工生命模拟等。直到最后看到一个非 常有趣 的比喻，觉得由此引出的袋鼠跳问题 （暂且这么叫它吧），既有趣直观又直达遗 传算法的本质，确实非常适合作为初学者入门的例子。 问题的提出与解决方案 让我们先来考虑考虑下面这个问题的解决办法。 已知一元函数： 现在要求在既定的区间内找出函数的最大值 极大值、最大值、局部最优解、全局最优解 在解决上面提出的问题之前我们有必要先澄清几个以后将常常会碰到的概 念：极 大值、最大值、局部最优解、全局最优解。学过高中数学的人都知道极 2.1 大值在一个小邻域里面左边的函数值递增，右边的函数值递减，在图 里面的 表现就是一 个“山峰”。当然，在图上有很多个“山峰”，所以这个函数有很多个极 大值。而对于一个函数来说，最大值就是在所有极大值当中，最大的那个。所以 极大值具有局部性，而最大值则具有全局性。 因为遗传算法中每一条染色体，对应着遗传算法的一个 解决方案，一般我 们用适应性函数 （fitnessfunction）来衡量这个解决方案的优劣。所以从一个基 因组到其解的适应度形成一个映射。所以也可以把遗传算法的过程看作是一个在 多元函数里面求最优解的过程。在这个多维曲面里面也有数不清的“山峰”，而这 些最优解所对应的就是局部最优解。而其中也会有一个“山峰”的海拔最高的，那 么这个就是全局最优 解。而遗传算法的任务就是尽量爬到最高峰，而不是陷落 在一些小山峰。 （另外，值得注意的是遗传算法不一定要找“最高的山峰”，如果 问题的适应度评价越小越好的话，那么全局最优解就是函数的最小值，对应的， 遗传算法所要找的就是“最深的谷底”）如果至今你还不太理解的话，那么你先往 下看。本章的示例程序将会 非常形象的表现出这个情景。 “袋鼠跳”问题 既然我们把 函数曲线理解成一个一个山峰和山谷组成的山脉。那么我们可 以设想所得到的每一个解就是一只袋鼠，我们希望它们不断的向着更高处跳去， 直到跳到最高的山峰 （尽管袋鼠本身不见得愿意那么做）。所以求最大值的过程 就转化成一个“袋鼠跳”的过程。下面介绍介绍“袋鼠跳”的几种方式。 爬山法、模拟退火和遗传算法 解决寻找最大值问题的几种常见的算法： 1. 爬山法（最速上升爬山法）： 从有哪些信誉好的足球投注网站空间中随机产生邻近的点，从中选择对应解最优的个体，替换原来 “ ” “ ” 的个体，不断 重复上述过程。因为只对邻近 的点作比较，所以目光比较 短浅 ， 常常只能收敛到离开初始位置比较近的局部最优解上面。对于存在很多局部最优 点的问题，通过一个简单的迭代找出全局最优解的机会非常渺茫。（在爬山法中， 袋鼠最有希望到达最靠近它出发点的山顶，但不能保证该山顶是珠穆朗玛峰，或 者是一个非常 高的山峰。因为一路上它只顾上坡，没有下坡。） 2. 模拟退火： 这个方法来自金属热加工过程的启发。在金属热加工过程中，当金属的温 MeltingPoint 度超过它的熔点 （ ）时，原子就会激烈地随机运动。与所有的其它 的物理系统相类似，原子的这种运动趋向于寻找其能量的极小状态。在这个能量 的变迁过程中，开始时。温度非常高， 使得原子具有很高的能量。随着温度不 断降低，金属逐渐冷却，金属中的原子的能量就越来越小，最后达到所有可能的 最低点。利用模拟退火的时候，让算法从较大的跳跃开始，使到它有足够的 能“ 量”逃离可能“路过”的局部最优解而不至于限制在其中，当它停在全局最优解附近 的时候，逐渐的减小跳跃量，以便使其落脚 到全局最优解上。（在模拟退火“ ” 中，袋鼠喝醉了，而且随机地大跳