软件设计与体系结构（慕晨）遗传算法入门到掌握.pdfVIP

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