遗传算法：基本原理及应用

遗传算法[5 7]（简称GA）是一种根据达尔文进化论思想，借鉴生物界自然选择和自然遗传机制的高度并行、随机和自适应搜索的全局优化和智能搜索算法。它模拟了生物进化过程中的“优胜劣汰、适者生存”的法则，将选择、杂交和变异等概念引入算法中，通过构造一组初始可行解群体并对其操作，使其逐渐朝着最优解的方向进化。它能克服传统方法易陷入局部最优解的缺点，可以较快地搜索到全局最优解，对目标函数的形态没有具体的要求，以适应度函数指导随机化搜索方向。适应值类似于自然选择的力量；选择算子根据父代中个体适应值的大小进行选择或淘汰，保证了最优搜索方向；交叉算子模拟基因重组及随机信息交换，保证了GA的搜索范围；变异算子模拟基因突变，保证了GA的全局搜索能力。遗传算法基本求解步骤如下。

（1）编码方法及个体评价方法。一般采用的是浮点编码方法。适应值函数为f（Xi）=

（2）个体选择：可采用以标准化集合分布规律对种群中的染色体进行选择，该方法以最佳染色体的选择概率ps作为基本参数，结合随机升序数rs按染色体的排列序号相对位置，确定其累计概率。概率机理仍然是适应值越大的染色体被选择的概率越大，适应值越小的染色体被选择的概率越小。

（3）交叉及变异运算。采用启发式交叉这一独特的交叉算子，其特点为：①以目标函数值确定搜索方向；②产生一个后代或者可能根本不产生后代。

假定从种群中选择的双亲为x 1、x 2，则由双亲产生的后代为：(www.xing528.com)

这里要求双亲中x 2不比x 1差，即对于求最大值问题，f（x 2）≥f（x 1）；对于最小值问题f（x 2）≤f（x 1）。r为0～1的一个随机数。该算子有可能产生不可行解向量，在这种情况下，重新产生随机数r和后代x 3。如果经过多次尝试后，没有发现新的满足约束条件的后代，算子终止并不再产生后代。启发式交叉更有利于搜索到精确解，主要用于小范围的精确搜索。

（4）最后采用非均匀变异操作。即各代参与变异操作的染色体变异量是非均匀变化的，变异量d（x）是染色体x、取值区间左右边界bl与br、当前进化代数gc、最大进化代数gm和形状参数b等参量的函数。变异量函数的公式表达为：d（x）=y[r（1-gc/gm）]b。式中y为参与变异操作的染色体到取值区域边界的距离，按式（10.67）计算：

变异后的基因个体表示为：

至此，计算过程完成了一次进化搜索，模型记录下种群的适应度以便后续搜索进行比较，同时初始种群通过一次进化后得到新的种群，对新的种群进行下一次进化计算，直至得出符合收敛条件的结果为止。