下载掌阅APP，畅读海量书库
立即打开
遗传算法的实现在于遗传算法的算法流程和参数设置。算法流程可以帮助我们理解算法思想和实现过程，但实现了算法后，参数设置也很重要，差的参数会使算法陷入局部最优或无法收敛等情况。
遗传算法流程图如图1.1所示。具体可以表述为，遗传算法的输入和执行对象是一群个体组成的种群， t 代表算法执行代数，种群中的每个个体代表问题的一种解。首先根据某种机制创建初始种群，对初始种群进行适应度评估，保留初始种群中最优适应度解作为当前最优解。然后对种群中的个体进行选择、交叉（crossover）和变异（mutation），得到新的种群，若新种群中的最优解优于父代的最优解（Best中的个体），则替换。重复上述操作，直到满足算法终止条件。
图1.1 遗传算法流程图
遗传算法对应伪代码如表1.1所示。
表1.1 遗传算法伪代码
由流程图和伪代码可以看出遗传算法有6个基础组成部分（与Michalewicz归纳的相一致）：
（1）问题解的遗传表示。
（2）创建初始种群的方法。
（3）用来评估个体适应度值高低优劣的评价函数。
（4）改变后代基因的遗传算子（选择、交叉、变异）。
（5）算法终止条件。
（6）影响遗传算法效果的参数值（种群大小、迭代次数、算子应用的概率）。
解的遗传表示称为遗传编码，因为遗传算法不能直接处理问题空间的决策变量，必须转换成由基因按一定结构组成的染色体，所以就有了编码操作。反之将编码空间向问题空间的映射称为译码。如图1.2所示即为编码和译码。在对染色体进行译码时，若译码后得到的解映射到解空间中的可行域，则认为该染色体是可行解，否则就会出现非法解和不可行解。如图1.2所示非法解指的就是染色体解码出来的解在给定问题的解空间之外，不可行解指的是染色体译码后的解属于解空间，但不属于可行域。
图1.2 编码和译码解析图
编码的方式有很多种。根据采用的符号，可以分为二进制编码、实数编码和整数编码等；根据编码采用的结构，可以分为一维编码和多维编码；根据编码采用的长度，可以分为固定长度的编码和可变长度的编码；根据编码内容，可以分为仅包含解的编码和包含解和参数的编码。
对于不同的优化问题，要选择合适的编码方式，其评价原则有以下几个性质。
（1）不冗余：从编码到解码的映射是1对1的。 n 对1的映射会导致资源的浪费和算法的提前收敛，1对 n 的映射则还需要另外的设计方法，在解空间中的许多可能解中确定一个。
（2）合法性：对编码的任意排列都对应着一个解。该性质确保大多数的遗传操作可以应用到该编码上。
（3）完备性：任意解都对应着一个编码。该性质确保解空间中的任意解在算法搜索过程中都是可达的。
（4）Lamarckian性质：某个基因的等位基因的含义不依赖于其他基因，该性质考虑了一个染色体能否将其价值通过常用的遗传操作传到种群中。
（5）因果性：变异带来的基因型空间中的小扰动对应到表现型空间中也是小扰动。该性质确保了解中的有用信息的保留。
产生初始种群的方法通常有两种：一种是由完全随机的方法产生的，它适合于对问题的解无任何先验知识的情况；另一种是根据某些先验知识转变为必须满足的一组要求，然后在满足这些要求的解中再随机地选取样本。
评价函数也称适应度函数（fitness function），用来评价个体的适应度值，适应度值越大的个体越符合算法对解的要求，所以评价函数至关重要，指引解进化的方向。同时，适应度函数的选择会直接影响遗传算法的收敛速度以及能否找到全局最优解。
选择操作的原理本质上是基于达尔文的自然选择学说，它的作用是将遗传搜索引导到搜索空间中有前途的区域。通常采用的选择方法有轮盘赌选择（roulette wheel selection）、随机采样（stochastic sampling）、确定性选择（deterministic sampling）、混合选择（mixed sampling）和锦标赛选择（tournament selection）。
所谓交叉是指把两个父代个体的部分结构加以替换生成新个体的操作，这样可以提高搜索力。在交叉运算之前必须对群体中的个体进行配对。目前常用的配对策略是随机配对，即将群体中的个体以随机方式两两配对，交叉操作是在配对个体之间进行的。
交叉算子主要有1-断点交叉（不易破坏好的模型）、双断点交叉、多断点交叉（又称广义交叉，一般不使用，随着交叉点的增多，个体结构被破坏的可能性逐渐增大，影响算法的性能）、算术交叉、模拟二进制交叉、单峰正态交叉等。目前各种交叉操作形式上的区别是交叉位置的选取方式。
变异就是将染色体编码串中的某些基因用其他的基因来替换。它是遗传算法中不可缺少的部分，目的就是改善遗传算法的局部搜索能力，维持群体的多样性，防止出现早熟现象。
设计变异算子需要确定变异点的位置和基因值的替换，最常用的是基本位变异，它只改变编码串中个别位的基因值，变异发生的概率也小，发挥作用比较慢，效果不明显。变异算子主要包括4种。
（1）均匀变异，它特别适于算法的初期阶段，增加群体的多样性。
（2）非均匀变异，随着算法的运行，它使搜索过程更集中在某一个重点区域。
（3）边界变异，适用于最优点位于或接近可行解边界的问题。
（4）高斯变异，改进了算法对重点搜索区域的局部搜索性能。
遗传算法终止条件通常有两种：一是设定迭代次数，当算法迭代次数达到设定值时，算法停止；二是当解的变化小于某一设定的较小值时，认为结果收敛，算法停止。
遗传算法的实现除了要有一个详细的算法流程，还需要对参数进行设定。参数大小的选择对遗传算法执行的结果有很大影响，好的参数设置会加速算法收敛到全局最优解，反之，差的参数选择将会使结果得到局部最优解，甚至会导致结果无法收敛。一般地，需要设置的参数有以下几种。
（1）种群规模 N 影响算法的搜索能力和运行效率，一般设置为20～100。 N 设置较大时，一次所覆盖的模式较多，增大了种群多样性和算法搜索能力，但也增加了计算量，降低了算法运行效率。 N 设置较小时（群体内个体的多样性减小），容易造成局部收敛。
（2）染色体长度 L 影响算法的计算量和交配变异操作的效果。 L 的设置一般由问题定义的解的形式和选择的编码方式决定。例如，在二进制编码方法中， L 就根据解的取值范围和规定精度计算得到；在浮点数编码方法中， L 与问题定义的解的维数相同。此外 L 还可以是可变的，即染色体长度在算法执行中是不固定的，如Goldberg等提出的一种边长度染色体遗传算法Messy GA。
（3）基因取值范围 R 由采用的染色体编码方式而定。对于二进制编码方法， R ={0，1}；对于浮点数编码方法， R 与优化问题定义的解在每一维上的取值范围相同。
（4）交配概率 P c 决定了进化过程中种群内参加交配的染色体的平均数目，取值一般为0.4～0.99，也可以使用自适应方法在算法运行过程中调整交配概率。
（5）变异概率 P m 决定了进化过程中全体发生变异基因的平均个数，取值一般为0.001～0.1。变异操作增加了群体进化的多样性。但 P m 值不宜过大，否则会对已找到的较优解有一定的破坏作用，使搜索状态倒退回原来较差的情况。
在终止条件中，需要设定的有最大进化代数和收敛误差值。最大进化代数一般可设为100～1000，需要根据实际问题来设定，合理的进化代数可以防止算法因不收敛而一直运行。
在以上参数中，有部分参数在算法运行中可以是动态设定的，这更符合算法本身对动态和适应性的追求。动态参数的实现方法有：采用一种规则；获取当前搜索的状态信息进行反馈；采用自适应机制。Hinterding、Michalewicz和Eiben将适应性分为3类：确定性的、有适应能力的、自适应的。