[科普中国]-遗传操作算子

遗传算法

遗传算法是一种基于“适者生存、优胜劣汰”的高度并行、随机搜索、自适应的优化算法，问题的求解过程被模拟为“染色体”适者生存的过程，通过“染色体”复制、交叉、变异等遗传操作，群体一代一代进化，收敛到“最适应环境”的个体，即求得问题的最优解或者较满意解。

遗传算法作为一种应用比较广泛、影响比较大的优化算法，与其他优化算法相比，它主要具有下述若干独特的性能。（1）遗传算法以参数的编码集作为运算对象，并且在执行搜索过程中，不受优化函数连续性及其导数求解的限制，因而具有很强的通用性。（2）遗传算法直接使用由目标函数确定的适应度函数信息，以群体为单位执行搜索过程，加快搜索到适应度较好的搜索空间，因而具有较强的全局搜索能力。（3）遗传算法简单通用，普适性强，易于与其他算法结合构成混合智能算法，并且该算法具有很强的鲁棒性，因而在众多领域得到了广泛的应用。鉴于以上特征，遗传算法受到了越来越广泛的重视1。

遗传操作算子基本遗传算法包括有三种遗传算子：选择算子，杂交算子，变异算子。在进行寻优的过程中，如果事先很难得知问题的求解步骤，在解空间进行搜索这一办法就成为更为广泛的策略之一。现下有两种具有代表性的搜索行为一种是随机搜索，一种是有向搜索。随机搜索以整个解空间作为搜索范围，广泛搜索并能从局部最优中跳离；有向搜索深度探索最优解，能够向着局部最优解进行有向爬山。遗传算法结合了随机和有向两种搜索能力，它可以在深度搜索和广度搜索之间维持适当的平衡2。在遗传算法中，由选择算子负责深度搜索累积的信息，杂交算子和变异算子负责广度搜索解空间中新的区域。下面我们逐一进行介绍：

选择在生物的遗传和自然进化过程中，对生存环境适应程度较高的物种将有更多的机会遗传到下一代；而对生存环境适应程度较低的物种遗传到下一代的机会就相对较少。模仿这个过程，遗传算法使用选择算子或称复制算子来对种群中的个体进行优胜劣汰操作：适应度较高的个体被遗传到下一代种群中的概率较大；适应度较低的个体被遗传到下一代种群中的概率较小。遗传运算中的选择操作就是用来确定从亲代种群中按某种方法选取哪些个体遗传到下一代种群中的一种遗传运算。选择操作建立在对个体的适应度进行评价的基础之上。选择操作的主要目的是在保持种群大小恒定的情况下复制种群中适应度高的个体，去除种群中适应度低的个体。首先计算适应度，适应度计算之后按照适应度进行父代个体的选择。

杂交或基因重组在生物的自然进化过程中，两个同源染色体通过交配而重组，形成新的染色体，从而产生出新的个体或物种。交配重组是生物遗传和进化过程中的一个主要环节。模仿这个环节，在遗传算法中也使用杂交算子来产生新的个体。遗传算法中的所谓杂交运算，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。前面介绍的选择算子不能在种群中建立任何新的个体，它只能以不复制适应度较差的个体为代价复制多个适应较高的个体，新个体的建立只能通过交叉算子和变异算子来实现。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起着关键作用，是产生新个体的主要方法在遗传算法中，在杂交运算之前还必须先对种群中的个体进行配对。目前常用的配对策略是随机配对，即将种群中的个个体以随机的方式组成对配对个体组，交叉操作是在这些配对个体组中的两个个体之间进行的。交叉算子的设计和实现与所研究的问题密切相关，一般要求它既不要太多地破坏个体编码串中表示优良性状的优良模式，又要能够有效地产生出一些较好的新个体模式。

变异在生物的遗传和自然进化过程中，其细胞分裂复制环节有可能会因为某些偶然因素的影响而产生一些复制差错，这样就会导致生物的某些基因发生某种变异，从而产生出新的染色体，表现出新的生物性状。虽然发生这种变异的可能性比较小，但它也是产生新物种的一个不可忽视的原因。模仿生物遗传和进化过程中的这种变异环节，在遗传算法中也引入了变异算子来产生新的个体。遗传算法中的所谓变异运算，是指将个体染色体编码串中某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。终止条件。终止条件就是一串进化结束的条件，一般依据问题的不同有不同的确定方法。运行参数。基本遗传算法主要山群体规模N、杂交概率Pc、变异概率Pm。