遗传算法的改进——IGA

吴伟

摘要：针对基本遗传算法（SGA）存在的缺点，分别从参数编码，采用三层递阶结构的染色体编码；适应度函数的选取，适应值指数比例系数自适应调整；遗传操作，采用最优保存策略，自适应选择和交叉概率。提出了改进的遗传算法（IGA）。

关键词：遗传算法；编码；适应度函数；遗传操作

中图分类号：TP301文献标识码：A文章编号：1009-3044(2012)01-0123-03

Improved Genetic Algorithm—IGA

WU Wei1,2

(1.School of Computer Science & Technology, Soochow University, Suzhou 215104, China; 2.Suzhou Vocational University, Suzhou 215104, China)

Abstract: For the genetic algorithm deficiencies, Separately from the coding parameters, using three layers of hierarchical structure coding; fitness function selection, fitness index proportion coefficient adaptive adjustment; genetic operation, the elitist strategy, adaptive selection and the crossover probability. proposes an improved genetic algorithm(IGA).

Key words: Genetic Algorithm; coding parameters; fitness function; genetic operation

遗传算法是一种模拟生物界自然遗传操作的算法，该算法通过模拟生物界自然选择、遗传机理，在群体中进行随机搜索。遗传算法的核心思想是生物界的“生存竞争，优胜劣汰，适者生存”的机制，算法的主要特征是：遗传操作不依赖于任何梯度信息，适合于一些传统优化算法不能解决的多目标优化问题和复杂优化问题，它可以实现群体中个体之间的信息融合，优胜劣汰。通过不断的迭代，从初始种群进化到最终的种群，从而寻找到最优解或次优解。遗传算法被认为是21世纪最为优秀的智能优化算法之一。

1基本遗传算法(SGA)

SGA最主要的思想是“适者生存”，群体中适应度值大的个体进行选择、遗传操作的可能性大，群体中适应度值小的个体就容易被淘汰，群体中的个体通过不停的进行选择、遗传操作直到达到设定的迭代次数或达到设置的阈值，则结束遗传操作，保存结果为其解或次优解。SGA中包含如下几个基本要素：1)染色体编码；2)适应度函数的设计；3)遗传操作设计。

群体的染色体编码是遗传算法中第一个要解决的问题，因为它直接决定着算法的迭代次数、是否收敛、训练学习的效率等问题。传统的二进制编码随着问题加深码串加长降低了算法的效率，而且二进制编码本身也不直观、精度也不高。符号编码不太容易实现交叉和变异操作。

群体适应度函数的确定问题是一个关键问题，因为它的好坏直接决定遗传算法的成功与否，即寻找到最优解或次优解。一般做法是将所要进行求解的目标函数作为适应度函数，此法简单易实现，但有一部分求解问题很难给出目标函数的具体函数关系，即使能表达，有的函数值域分布跨度大，平均适应度小，群体的整体适应度低，从而增加遗传迭代的次数，增加计算量。

遗传操作主要是选择、交叉和变异的设置。选择操作是把最适应环境的个体保存下来，遗传给下一代来保证种群的整体适应性。目前所采用的方法的主要思想是：若个体适应度值越大则被选中遗传给下一代的的概率就越大，相反个体适应度值越小则被遗传给下一代的的概率就越小，但此方法有可能破坏群体新个体的产生。遗传操作包括交叉和变异两项操作，其中两者是相辅相成的关系，其中交叉是主要的操作，变异是次要的。但传统的交叉和变异都是事先设定好的，不具有个体的交叉和变异概率随适应度值的变化而自动调节的能力。

2改进的遗传算法(IGA)

遗传算法的参数编码、适应度函数的设计、遗传操作，每个环节的实现策略的改变都会对整个遗传算法的寻优性能产生重要影响，而且需要其它环节做出相应的调整，才能达到比较理想的提高遗传算法寻优能力的目的。

2.1编码方案:将染色体设计成三层递阶结构

在生物医学领域，染色体是由控制基因和序列基因组成，控制基因来表明此染色体的作用和功能，而序列基因来实现它的作用和功能。我们借用此想法来实现遗传算法中染色体的编码，控制基因一般采用二进制编码，“1”表示下层基因被激活，其中的序列基因参加遗传操作。“0”表示下层基因未被激活，其中的序列基因不参加任何遗传操作。序列基因一般采用实数编码，可根据具体

2.3遗传操作

2.3.1最优保存策略

采取优秀个体策略(elitist strategy)，每代都保留几个最为优秀的个体不参与选择和变异操作，但参与交叉操作。这样能保证优秀基因传递给下一代，从而群体整体性能得到提升。

遗传算法是一个不断迭代产生新个体的过程，在这个过程中可以产生优秀个体，但传统遗传操作随机性很大，可能破坏群体中最为优秀的个体，导致整体性能下降。采取优秀个体策略可以避免这个问题的出现，它可以把当代中适应度最大的个体保存下来，直接传递到下一代，用它来替换下一代中适应度最小的个体。

具体操作过程如下：

第一步：当前群体按适应度大小进行排序，找到适应度最大和最小的个体。

第二步：若当代中适应度最大的个体比迄今为止的个体的适应度大,则以当代适应度最大的个体作为新的适应度最大的个体。第三步：用迄今为止适应度最大的个体替代掉群体中适应度最小的个体。

3结论

本文针对基本遗传算法，分别从参数编码，采用三层递阶结构的染色体编码；适应度函数的选取，适应值指数比例系数自适应调整；遗传操作，采用最优保存策略，自适应选择和交叉概率。提出了改进的遗传算法（IGA）。后序工作是把IGA算法应用到实际工作中去，来检验此算法的性能。

参考文献：

[1] John H.Holland.Adaptation in Natural and Artificial Systems[M].MIT Press,1975

[2]王凌.智能优化算法及其应用[M].北京:清华大学出版社施普林格出版社.2001.

[3]李伟超，宋大猛，陈斌，基于遗传算法的人工神经网络[J].计算机工程与设计，2006，27(2):316-318.

[4]赵宏伟,藏雪柏,王立江,凌兴宏.用于神经网络结构优化的改进遗传算法[J].计算机研究与发展(增刊).2000,37(10):244-248.

[5]李方方,赵英凯,许必熙.基于递阶遗传算法优化神经网络的研究[J].机械与电子，2006，(2):41-44.

[6]赵淑海,邱洪泽,马自谦.基于伪并行混合遗传算法的神经网络优化[J].计算机工程与设计,2006,27(13):2345-2347.

[7]王清,马广富,弥曼.一种基于遗传算法的神经网络控制方法研究[J].系统真学报，2006，18(4):1070-1077.

[8]何燕,肖芳,何小苑.基于自适应递阶遗传算法的洪水预报模型[J].微计算机信息,2007,23(16):311-313.

[9]何小娟,曾建潮,徐玉斌.基于思维进化算法的神经网络权值与结构优化[J].计算机工程与科学,2004,26(5):38-42.