龙源期刊网 http://www.qikan.com.cn
遗传算法中交叉算法的改进
作者：姜 薇
来源：《中国科技博览》2009年第01期
[摘要]遗传算法是模拟达尔文的自然选择学说和自然界的生物进化过程的一种计算模型。它采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。遗传算法的操作对象是一群二进制串(称为染色体、个体)，即种群。这里每一个染色体都对应问题的一个解。从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个体，使用杂交和变异来产生下一代种群。如此模仿生命的进化一代代演化下去，直到满足期望的终止条件为止。 一般应用于在一个问题的解集中查找最优解情况，如是一个问题有多个答案，但是想查找一个最优答案的话，那么使用遗传算法可以达到更快更好的效果。本文就遗传算法中的交叉算法的改进进行讨论与研究。 [关键词]遗传算法 交叉算法 改进
中图分类号:O224 文献标识码：A 文章编号: 1009-914X(2009)01(a)-0044-01
自然界的生物进化是按“适者生存，优胜劣汰”规律进行的，Michigan大学Holland教授根据这一规律于1975年首次提出了遗传算法（Genetic Algorithm，GA），其基本思想是力求充分模仿这一自然寻优过程的随机性、鲁棒性和全局性，借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现个体的适应性的提高，这一点体现了自然界中“物竞天择、适者生存”进化过程，从而吸引了大批的研究者，迅速推广到优化、搜索、机器学习等方面，并奠定了坚实的理论基础。这是一种新型的全局优化搜索算法，因为其直接对结构对象进行操作，不存在求导和函数连续性的限定，适于并行处理，已广泛应用于神经网络、计算机科学、优化调度、运输问题、组合优化、机器学习、信号处理、自适应控制和人工生命等领域，并且遗传算法在实际应用中也取得了巨大成功。
一、遗传算法简介
遗传算法摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工进化的方式对目标空间进行随机化搜索。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，模拟达尔文的遗传选择和自然淘汰的生物进化过程，对群体反复进行基于遗传学的操作（遗传，交叉和变异），根据预定的目标适应度函数对每个个体进行评价，依据
龙源期刊网 http://www.qikan.com.cn
适者生存、优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。
遗传算法包括三个基本遗传算子：选择（select）、交叉（crossover）、变异（mutation）。遗传算法中最重要的过程就是选择和交叉。这三个遗传算子有如下特点： 1.它们的操作都是在随机扰动情况下进行的，即遗传操作是随机化操作，而且是一种高效有向的搜索。
2.遗传操作的效果除了与编码方法、群体规模、初始群体以及适应度函数的设定有关外，还与上述三个遗传算子所取的操作概率密切相关。
3.三个遗传算子的操作方法随具体求解问题的不同而异，它们和个体的编码方式直接相关。
二、遗传算法中的交叉算子
（一）交叉算子
遗传算法中起核心作用的是遗传操作的交叉算子。交叉是反映对两个父代个体的部分结构进行重组而生成新个体的操作。交叉算子的设计应与编码设计协调进行，使之满足交叉算了的评估准则，即交叉算子需保证前一代中优秀个体的性状能在下一代的新个体中尽可能得到遗传和继承。
交叉算子包括两个基本内容：一是从由选择操作形成的配对库（mating pool）中，对个体随机配对，并按预先设定的交叉概率Pc决定每对是否需要交叉操作。二是设定对个体的交叉点（cross site）并对配对个体在这些交叉点前后的部分结构进行交换。目前常用的几种交叉算法如下：
（1）单点交叉：在个体串中随机设定一个交叉点，交叉时对两个个体在该点前或后的部分进行互换，生成两个新的个体。
（2）二点交叉：在个体串中随机设定两个交叉点，交叉时对两个个体在这两点间的部分进行互换，生成两个新的个体。
（3）多点交叉：是上述两种交叉的推广。
（4）一致交叉：根据设定的屏蔽字来决定两个个体的哪些位进行互换。
龙源期刊网 http://www.qikan.com.cn
（二）二点交叉
在交叉算子中常用的是二点交叉。
邮递员路径问题（TSP）属于NP完全问题，近年来，基于遗传算法求解TSP问题的研究十分活跃。解决TSP约束问题的一种有效的处理方法就是对交叉、变异等遗传操作做适当的修正，使其自动满足TSP的约束条件，常用的交叉算法有如下几点：
（1）部分匹配交叉：在此方法中，依据均匀随机分布产生的两个父串交叉点，定义这两点之间的区域为一匹配区域，并使用位置交换操作交换两个父串的匹配区域；然后再对两子串中匹配区域以外出现的遍历重复，依据匹配区域内的位置映射关系，逐一进行交换。 （2）顺序交叉法：选择一个匹配区域，根据匹配区域的映射关系，在其区域外的相应位置标记为H，再移动匹配区域至起点位置，且在其后预留相等于匹配区域的空间（H的数目），然后将其余码按相对次序排列在预留区后面，最后将父串的匹配区域相互交换，并放置到预留区内，即可得到两个子代。
（3）改进的顺序交叉法之一：选择一个匹配区域，将对方匹配区域内的子串加到自身子串的前面，在区配区后依次删除与匹配区相同的城市码，即可得到新的子串。 （三）改进的顺序交叉法之二
在2.（3）的基础上，设计一个新的顺序交叉法；方法2.（3）中的交换区域改变了位置，从原位置交换移到了子串的开头；如果想在相同位置交换，按2.（3）方法则会丢失部分代码；因此本方法原则是：选择一个匹配区域，将自身匹配区域内的子串复制到自身子串的后面，交换匹配内子串代码，删除匹配区域外与匹配区域内复制的代码。具体步骤如下： （1）设两父串及匹配区域为：A=91 |456|7832B=68 |123|9457
（2）将A的匹配区域加到A的后面，将B的匹配区域加到B的后面：A'=91 |456| 7832456B'=68 |123| 9457123
（3）将A'和B'的交换区域进行交换：A”=91 |123| 7832456 B”=68 | 456 | 9457123 （4）删除A”和B”匹配区域外的重复代码：A'”=9 |123| 78456B'”=8 | 456 | 97123 此方法一是保留了相同位置交换；二是保存了自己要交换出去的代码，避免了代码的丢失；三是将代码复制到父串的后面，在程序代码设计方面比较容易实现。 三、总结
遗传算法中交叉算法的改进
