遗传算法存在问题分析

孙俊丽

摘要：基于遗传算法，分析了遗传算法中早熟现象和重复基因问题出现的原因，归纳了传统的解决办法，提出了有效的解决办法。

关键词：遗传算法；早熟现象；重复基因

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2015）17-0163-02

1 遗传算法存在问题

1.1早熟现象

遗传算法实质上就是在基因上进行的一系列的相关操作，即选择、交叉和变异操作，通过选择操作，将本代种群中适应度较高的个体遗传到下一代，交叉操作可以实现基因的重组，探索适应度更高的个体，变异操作主要实现基因的突变。通过一系列的操作之后，按照进化论中的优胜劣汰原则，较好的个体逐渐地被进化，较差的个体逐渐地被淘汰，得到遗传算法所寻找的最优解。随着遗传算法的进行，部分较高适应度的个体将会保留下来，如此进行下去，种群中个体大部分的基因将会趋于一致，种群中也会存在很多相似的个体，减小了种群的多样性。从遗传理论上分析，遗传算法能够保证操作的精确度，而且算法中的群体规模可以随机选取，通过一系列操作之后，种群中个体的优秀基因肯定能够遗传到下一代，种群最终能够得出最优解。但实际上，遗传算法实现是有时间限制的，而且实现资源也是有限的，所以实现过程中要考虑到群体规模的大小，遗传算法中的这些限制可能会使群体中的个体过早地丧失多样性。

综上所述，遗传算法的早熟现象指在遗传算法实现过程中，丧失了种群个体的多样性，使个体中的基因趋于一致，导致算法的搜索停止在局部，无法实现在全局的搜索，最终得到的是局部最优解。

1.2重复基因问题

遗传算法在实现时，编码方案如果采用了实数编码，容易出现重复基因的问题。重复基因主要是指在进行交叉操作的两个染色体中存在相同的基因，选择交叉点进行交叉之后，产生的新的染色体中有两个相同的基因。

以自动组卷问题为例，重复基因问题就是指在同一套试卷中有完全相同试题的出现。在实现遗传算法时，首先要进行初始化群体，初始群体中每个个体的产生都是随机的，所以每个个体选中的试题也是随机的，不同的个体可能会选中同一道试题。当两套试卷进行交叉操作时，如果两套试卷中含有相同的试题，而且该试题在试卷中的位置不同，或是试题在两个个体的基因位不同，交叉点选在两个基因位之间，交叉操作之后产生的新个体中必定会出现两个相同的基因。

2 早熟现象原因分析及解决

遗传算法在实际应用中经常出现早熟现象，出现早熟现象的原因主要有以下三点：

1） 群体规模

群体规模主要是指种群中的个体数量，其取值的大小影响着遗传算法早熟现象的发生。当群体规模取值较小时，虽然算法的收敛速度会很快，但是生成的具有较高适应度的个体的数量会很少，容易造成早熟现象的发生；当群体规模取值较大时，保证了参加遗传算法的群体的多样性，能够产生具有较高适应度的个体，增大了得到全局最优解的可能性，但是增大了算法的计算量，降低了收敛速度。综合考虑，群体规模的取值可以在50-100之间。

2） 选择操作

在自然界中，选择过程遵循着优胜劣汰的规律，在遗传算法中，这种规律是通过选择算子来实现的。选择操作主要是在本代种群中选择适应度较高的个体保留到下一代，保证遗传算法得到最优解。选择操作通常使用轮盘赌选择方法，增大了较高适应度值的个体被遗传的概率，但是这样有可能淘汰掉本代种群中的最佳个体，也有可能本代中的最佳个体通过交叉和变异操作之后，以前良好的基因组合被破坏，容易出现早熟现象。

3） 交叉概率和变异概率

在遗传算法中，通过交叉和变异的操作，保证了种群个体的多样性。传统的遗传算法中，交叉概率和变异概率采用了固定值。如果交叉概率取值较大，提高了交叉操作的速度，同时也破坏了原来个体，算法的寻优速度就会降低；如果交叉概率取值较小，会降低遗传个体的破坏性，但是算法可能会过早地得到局部最优解。如果变异概率较小，通过变异操作产生的新个体的数量也会变小，随着遗传操作的进行，适应度较高个体就会在群体中快速繁殖，从而出现局部最优解，出现早熟现象。因此，在遗传算法实现中的交叉和变异概率采用自适应遗传算法中的动态交叉概率和动态变异概率，这样会降低早熟现象出现的概率。

3 重复基因问题解决

解决重复基因问题的传统方法有两种：

第一种方法是在创建数据表时，在试题表中增加一个字段，在初始化群体时，用该字段标志试题是否被某个个体选中，已经被选中的试题不能再次被选中，这样在种群个体中避免了重复题的出现。但是这样做违背了初始化的随机性原则。

第二种方法是移动交叉点，即在进行交叉时，先判断两个个体中是否有重复基因出现，如果有重复基因的出现，将交叉点选在两个重复基因的基因位区间之外，如果区间选在了重复基因的基因位之内，则通过左移交叉点，将交叉点移到两个重复基因的基因位范围之外。

使用移动交叉点的方法存在以下问题：一是交叉操作的交叉点具有不确定性，如果控制交叉点的位置，则对交叉算子产生一定的破坏性；二是在本次遗传操作中，通过移动交叉点的位置避免了重复基因的出现，但是当产生的新个体再次进行交叉操作时，可能还会出现重复基因，所以此种方法对以后的交叉操作没有作用，在以后生成的子代之间进行交叉时，重复基因问题还会出现。

在本文中，根据遗传学中等位基因的知识，提出了一种等位基因法解决交叉操作中重复基因问题，在进行交叉操作时，判断出现重复基因之后，将出现的

的重复基因换到两个个体中相同的基因位，然后再进行交叉操作，这样就避免了新生成的子代中出现重复基因，可以不用考虑交叉点的位置，在任何交叉点都可以进行交叉操作，等值基因法对个体的适应度的值也没有影响，解决了重复基因的问题。

4 结束语

本文主要介绍了遗传算法中经常出现的早熟现象和重复基因问题，从多方面分析了出现这些问题的原因，归纳了传统的解决办法，提出了新的解决办法，通过这些办法，能有效地降低遗传算法早熟现象和重复基因问题的出现概率。

参考文献：

[1] 毛秉毅.基于遗传算法的智能组卷系统数据库结构的研究[J].计算机工程与应用， 2003（28）：230-232.

[2] 王小平，曹立明.遗传算法—理论、应用与软件实现[M].西安：西安交通大学出版社， 2002：37-38.

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

[4] 陈宇，陈治平.遗传算法中编码方案研究[J].计算机技术与自动化，2006，25（1）：50-52.

[5] 熊伟清，魏平，赵杰退.遗传算法的早熟现象研究[J].计算机应用研究，2001（9）：83-87.