基于传统遗传算法的改进与研究

周文荣

（湖北大学，湖北 武汉 430062）

基于传统遗传算法的改进与研究

周文荣

（湖北大学，湖北 武汉 430062）

遗传算法是一种采用启发式的模拟自然界的进化论过程来解决现实生活中复杂非线性问题的算法，该算法常用于解决组合问题的最优化。在计算过程中通过对传统的交叉过程进行分析和改进，使用反转交叉的交叉方法，可以很好地解决在交叉过程中产生的“不良基因”问题。文章对基于传统遗传算法的改进进行了研究。

遗传算法；交叉算子；不良基因

1 遗传算法基本思想及流程

1.1 遗传算法的基本思想

遗传算法的基本原理就是对适者生存不适者淘汰规则的模拟，通过对个体中染色体进行处理，然后再进行目标选择，最终达到求解全局最优的问题。

传统的遗传算法的作用流程如图1所示。

图1 传统遗传算法作用流程

1.2 遗传算法的实现

传统遗传算法的实现主要包含以下几个部分。

1.2.1 编码方法

遗传算法实现的最开始的操作是对种群进行初始化，得到的一系列串。获得这些串的方法叫作编码。

在具体问题中，如何编码出容易理解并且清晰的字符串是算法的关键所在。

1.2.2 求适应度函数

在具体情况下适应度函数能够成为目标函数。例如在TSP问题中，适应度函数就是使路程最短的函数。把目标函数称为适应度函数是为了更加贴近自然环境下适者生存原则。在遗传算法中，根据适应度函数求得适应值。求解个体适应度的大小的代码叫作适应度函数[1]。遗传算法根据目标函数值来选择下一代，而目标函数值由适应度来表示。

1.2.3 选择算子

选择操作是在编码之后，该操作不会产生新的染色体，选择操作的主要目标是将适应度比较合适的个体选出来并保留下来，并将适应度不合适的个体进行淘汰，即选择操作在保证染色体上基因完整的同时，使高性能的个体保存下来继续进行迭代。最常用的选择方法为：

（1）精英选择，顾名思义精英选择就是选择精英。精英选择的过程首先是找到此次迭代中适应度最合适的染色体和最不合适的染色体，然后比较此染色体的适应度与之前适应度最合适的个体适应度的大小[2]。如果大于，则被选择保留。并将此个体当成目前适应度最好的个体，并用此个体去替代适应度最不好的个体，提高平均适应度。

（2）锦标赛选择，所谓竞标赛选择，就是从种群中选择一部分个体进行比赛，得胜者被选择[3]。假设整个种群的大小为N，运用到遗传算法中可以解释为从种群中选择N/2个个体，然后比较这N/2个个体的适应度，适应度最合适的被保留，最不合适的被淘汰。

（3）轮盘选择，轮盘选择是用一个轮盘不停进行旋转，每次旋转的时候，轮盘停下时，指针指向几号，这个号就被选择。

设种群大小是N，种群里编号为i的个体适应度为fi，那么该个体被选择保留的可能性为：

通过pi知道个体被选择到的概率就是此个体的适应度与种群适应度之和的比。解决方法是首先随机产生一个0到1之间的数，然后将个体编号为1到N，设定一个选择算子，一般情况下选择算子的大小为0.7，根据编号从小到大的顺序计算累计概率，当累计概率第一次大于或者等于选择算子时，对应的编号就是被选中的个体。

1.2.4 交叉算子

交叉算法是让两个父代染色体上的基因进行替换，得到新个体。交叉操作主要方法为：

（1）单点交叉。在单点交叉中，随机找到两个父代，再根据交叉算子随机找到一个基因位，将两个父代的该基因位置后面的基因进行替换。

（2）双点交叉。在双点交叉中，唯一和单点不同的是双点交叉会选取两个点来进行替换。

（3）部分映射交叉（Part Mapped Cross，PMX）。和单点交叉一样，部分映射交叉算法第一步选定两个父代，然后在两个父代上的基因随机选取交叉点，然后根对应的映射关系产生两个新的个体。

其具体操作流程为：第一步随机选取一个交叉点，第二步 对对应单点之前的基因进行替换。第三步根据替换的对应性，找到内部的映射关系。根据映射关系将基因全部替换，得到新的个体。

部分映射交叉具体过程的流程如图2所示。

图2 部分映射交叉

遗传的目的就是获得与父代相比基因更加优良的个体。交配为自然进化的关键，而交叉也就自然成为遗传算法的关键。因为具有随机性，所有可能产生适应环境的新个体。也会在一定情况下产生不良基因，比如新产生的个体可能会破坏染色体中的基因重复性的规则。

1.2.5 变异算子

在生物学上，生物的变异是指染色体上的某些位上的基因发生了改变，主要有翻转、增加、减少等途径。

变异主要采用的方法是确定染色体上某一位的基因，然后与其他位上的基因发生替换。基因发生了变化，导致产生了新的个体，具有新的解决方案。变异效果如图3所示。

图3 变异操作

在不确定随机的问题下，遗传算法在执行时可能出现过快收敛。变异算子的出现减少了该情况出现的可能性。

2 对传统遗传算法的改进

本文对遗传算法过程所作的改进是对算法执行过程中的交叉操作进行改进。交叉操作可以产生新的基因组合的个体。单点交叉和双点交叉方法在产生新个体的同时，可能会导致不良基因的出现，所谓的不良基因是指个体上的染色体上出现不符合实际情况的基因，这样就必须对每次变异产生的基因进行查询，将含有不良基因的个体除去或者将其错误基因修正。针对这一问题，本文提出反转交叉的思想。

在交叉操作发生之前，第一步是进行编码。例如在求解货郎担问题时的编码采用自然数编码，每一座城市作为一个顶点，使用从1开始的自然数依次对顶点进行编号，于是城市的编号不会重复。

单点交叉和双点交叉产生“不良基因”的实例如图4所示。

由图4可知，在A1中4出现了两次，B1中5也出现了两次，单点交叉重复的基因较多。

虽然在实际的遗传中染色体上能存在重复的基因，但是在求解货郎担问题时，每座城市只有唯一的编号，父代的染色体代表路径，染色体上的基因代表了顶点的标号，顶点的标号不可以重复，通过对单点交叉和双点交叉的改进，之前研究者得到了部分映射交叉，可是在部分交叉映射中也可能同样存在重复的基因。

在部分映射交叉重复的例子如图5所示。

图4 单点双点交叉重复

图5 部分交叉映射重复

通过图5可知S2和T2中的编号存在重复。部分交叉映射第一步是进行单点交叉，第二步是产生映射关系，图7产生的映射关系为1与2对应、2与3对应、3与4对应。对于中间染色体S1和T1的单点交叉位置之后的基因进行映射，因为此映射存在过度的传递性，对S1中的4进行替换，首先用3替换，然后再用2替换，因为替换具有随机性，最后可能会停止替换，于是S2中出现两个2，以此对基因4之后的基因进行判断，观测各个基因是否具有映射关系，如果有映射关系就进行判断，没有映射关系则进行下一次循环，对T1也采用了同样的操作。可知此时遍历的时间复杂度为O(n2)。

由图5可知部分交叉映射虽然比单点交叉和双点交叉的交叉效果要好，但也可能存在重复。

在产生重复之后，存在以下几种方法可以尽量避免“重复基因”造成的重大影响：

（1）第一种方法是削弱含有重复基因的个体的地位。这种方法允许含有重复基因的染色体继续进行下一次迭代，但是赋给这些特殊个体较不合适的适应度，于是在选择操作时，这样特殊的染色体被淘汰。这种方法利用下一次的选择操作将正常染色体保留下来，方法的实现非常简单，但非常费时，因为遗传算法在迭代过程中会花费大量的时间产生无效染色体，再花费大量的时间淘汰无效染色体，效率较低。

（2）第二种方法对无效染色体直接进行修复。当碰到重复的基因时，会将重复的基因用此染色体缺少的基因进行替换，即直接将无效染色体经过修复变成有效染色体。修复本身将消耗大量的时间。

为了有效避免出现重复基因的情况，本文在总结前文的交叉方法的基础上，提出了新的交叉方法—反转交叉。

反转序列进行交叉的过程描述为：

假设i∈{1,2,…,N}，此时N=7，a表示一条染色体，此染色体上的基因为{a1,a2,a3,a4,a5,a6,a7}={4,6,2,7,3,1,5}，设有一个变量m∈{1,2,…,N}表示下标，一个数组inv来表示得到的反转序列，初始时变量m为1，数组inv的元素都为0。

第一步是求出反转序列。反转序列的求法是给出一个编号ifalse，然后求出在数组a中等于编号i的元素的前面大于此元素的个数，并将这个数目赋值给inv[i]。例如在{a1,a2, a3,a4,a5,a6,a7}={4,6,2,7,3,1,5}中，当m=1时，a中为1的为第6号元素，a前五号元素都比1大，于是inv[1]=5；当m=2时，a中为2的为第3号元素，a前两号元素都比1大，于是inv[2]=2；当m=3时，a中为3的为第5号元素，ae前四号元素有3个元素比3大，于是inv[3]=3，以此类推，得到反转数组的元素分别为inv={5,2,3,0,2,0,0}。最后可知反转数组中的元素的大于介于0和n-1之间。

运用此方法，假设父代S={5,7,1,3,6,4,2}，父代T={4,6,2,7,3,1,5}，得到的反转序列为S1={2,5,2,3,0,1,0}和T1={5,2,3,0,2,0,0}。

第二步是对反转序列进行单点交叉，可以得S2={2,5,2,0,2,0,0}，T2={5,2,3,3,0,1,0}。

第三步是对S2和T2进行还原，得到子代。在求出反转数列并进行单点交叉之后，再使用以下代码进行还原。

//a表示为得到的子代数组，inv表示已得到的单点交叉之后的中间数组

还原之后得到的S3={4,6,1,3,7,5,2}，T3={5,7,2,6,3,1,4}。从S2还原得到S3的过程如表1所示。

表1 还原得到S3的过程

根据以上描述，可知反转交叉主要分为3步，对整个过程进行简化，其流程如图6所示。

图6 反转交叉过程

由图6可知反转交叉的性能要比部分交叉映射的性能好。反转交叉有效地处理了可能存在重复基因即不良染色体的情况，为后面的操作打下了坚实的基础。通过反转和还原可知，本算法的时间复杂度与部分交叉映射的时间复杂度一样都为O(n2)，但因反转交叉不会产生重复的基因，最后也不需要修复，而部分交叉映射可能会产生重复的基因，部分交叉映射在产生重复基因之后需要花费较多的时间进行修复或者进行淘汰。

[1]周明，孙树栋.遗传算法原理及应用[M].北京：国防工业出版社，2005.

[2]ALP O, ERKUT E, DREZNER Z. An ef fi cient genetic algorithm for p-median problem[J].Annals of Operations Research, 2003（4）：21-42.

[3]薛富强，葛临东.用于调制信号特征选择的改进遗传算法[J].计算机工程，2008（3）：213-214.

Research and improvement based on the traditional genetic algorithm

Zhou Wenrong
（Hubei University, Wuhan 430062, China）

Genetic algorithm is a kind of heuristic algorithm that adopts heuristics mode to simulate the natural evolution process to solve optimization of combinatorial problem. Through analysis and improvement of the traditional cross process in the calculation process, using the method of cross cross inversion. Based on that the traditional crossover process is analyzed and improved in the process of calculation, reverse-crossover method is put forward to solve the “bad genes” problem in the process of cross.

genetic algorithm; crossover operator; bad genes

周文荣（1989— ），女，湖北天门。