改进的快速遗传算法在函数优化中的应用

周勇 胡中功

摘 要： 遗传算法作为一种模仿生物自然进化过程的全局随机优化算法，在工程中已得到广泛应用。但普通遗传算法易存在早熟及收敛速度慢等缺点。提出一种快速收敛的改进遗传算法，该算法从全局出发，对初始群体生成、遗传选择、交叉和变异算子操作等几个方面做出改进，其中重点对交叉率和变异率进行优化，实现交叉率和变异率按个体适应度以S曲线和高斯分布曲线形式进行非线性自适应调整。通过案例仿真分析，证明了该方法的可行性和有效性，且具有更快的收敛速度和更可靠的稳定性。

关键词： 遗传算法； 高斯分布； 自适应； 收敛； 性能仿真； 函数优化

中图分类号： TN911.1?34； TP18 文献标识码： A 文章编号： 1004?373X（2018）17?0153?05

Abstract： Genetic algorithm （GA）， as a global stochastic optimization algorithm to simulate the natural evolution process of biology， has been widely used in engineering field， but the common GA has slow convergence speed and is easy to fall into premature convergence. Therefore， an improved fast?convergence GA is proposed to improve the items of initial population generation， genetic selection， operators crossover and operators mutation proceeding from the overall situation. The crossover rate and mutation rate are optimized emphatically to realize the nonlinear adaptive adjustment in the forms of the S curve and Gaussian distribution curve according to individual fitness. The analysis results of case simulation show that the method is feasible and effective， and has fast convergence speed and high stability.

Keywords： genetic algorithm； Gaussian distribution； adaptation； convergence； performance simulation； function optimization

0 引 言

遗传算法（Genetic Algorithm，GA）是美国Holland教授于1975年首先提出来的一种借鉴生物进化理论和门德尔基因遗传理论的高度并行、随机的优化方法[1]。它模拟自然界生物“优胜劣汰，适者生存”的自然进化过程，将研究的解空间映射为遗传空间[2]，主要特点是整体搜索策略和优化搜索方法在计算时不依赖于梯度信息或其他辅助知识，也不依赖于问题的具体领域[3]。近年來，从简单的PID控制，到复杂的最优控制、自适应控制等遗传算法在各种工程控制问题中都有成功的应用案例。特别是目前人工智能的蓬勃发展，因而极具潜力的遗传算法一直是研究的热点。遗传算法虽然应用广泛，但在解决复杂问题时，由于其自身的随机搜索特点也带来了收敛速度慢和算法局部收敛（早熟）等问题[4]。遗传算法的交叉率[Pc]和变异率[Pm]反映了算法交叉和变异操作的概率，直接影响算法的收敛性能。标准（基本）遗传算法（SGA）的交叉率和变异率这两个参数是固定的，导致收敛能力和稳定性较差。文献[5?8]对遗传算法做了一些改进。文献[5]提出一种根据适应度调整交叉率和变异率的自适应遗传算法（AGA），但在该算法中，个体适应度越高，平均适应度和最大适应度越接近，交叉率和变异率不断变小并接近于0，导致在进化初期，种群中的优良个体几乎不会改变，使算法搜索性能下降。文献[6]中的改进遗传算法（线性自适应遗传算法LAGA）解决了算法初期交叉率和变异率为零的不足，但在算法后期，当种群平均适应度和最大适应度接近时，交叉率和变异率自适应调整曲线变化比较陡峭，产生较大差异，使进化停滞不前，产生局部收敛的可能。文献[7]把交叉和变异率按个体适应度以Sigmoid函数曲线非线性自适应调整，但进化初期变异率过大，虽能增加种群多样性，但可能使算法收敛速度变慢。文献[8]提出一种新的交叉和变异算子，但算法交叉率和变异率是固定的，增加了产生早熟的概率。针对遗传算法存在的不足，本文提出一种改进的快速遗传算法（IFGA），该算法从全局出发，分别对初始化分配、选择、交叉和变异等几个方面进行改进，其中着重从交叉和变异改进的方向出发，自适应地以非线性曲线模式优化交叉概率和变异概率，满足算法对不同阶段的侧重，以增加种群多样性，提高算法搜索能力和收敛速度。复杂函数的仿真实验结果表明，改进的遗传算法能较好地解决传统遗传算法存在的不足，改善收敛性质。

1 改进的遗传算法基本原理

1.1 初始群体生成

初始群体的分布对算法的收敛有较大影响。初始群体分布不合理会导致算法收敛速度变慢，特别当遗传算子选择不当时，甚至早熟不收敛。基本（标准）遗传算法和大部分遗传算法的初始群体在搜索空间都是随机产生的，这种方法可能使解空间个体都集中在某一局部区域内，这对搜索全局最优点极为不利。本文针对常规初始群体存在的问题，借鉴文献[9]提出的小区间初始群体生产法，将规模为[n]的群体[E]以待求参数的取值范围分成群体总数个小区间，并在各小区间中分别随机产生一个初始个体，从而保证初始个体能均匀地分布在整个解空间范围内，增强初始群体的活力。

1.2 选择操作的改进

选择操作反映了“优胜劣汰，适者生存”的自然界规律，它以个体的适应度作为衡量标准，适应度高的个体作为父代被选择繁衍进入下一代进化；反之，则被淘汰。选择策略比较多，经典遗传算法常采用轮盘赌选择方式。轮盘赌选择方式根据个体适应度值在群体适应度总和中所占的比例来表示其被选中的概率，适应度越高的个体，被选中的几率越大。但这种选择方式的选择误差较大，对收敛速度有较大影响。为了丰富种群模式，优化算法收敛性质，本文中选择算子采用轮盘赌方式和遗传代数相结合自适应调整选择概率。改进后的选择算子为：

式中：[fE（1，i）i=1nfE（1，i）]为轮盘赌方式的初代选择算子；[T]为最大进化代数；[k]为实数，一般为8～10。

从式（2）可知，算法在进化初期根据轮盘赌方式进行遗传操作，使子代群体模式丰富，降低了早熟的可能性。在进化后期，随着进化代数的增加，加大了选择算子的概率，可极大地促进种群中适应度较高的个体进行进化操作，能够较好地提高算法的收敛速度。

1.3 自适应交叉率和变异率的改进

遗传算法中，交叉和变异算子是算法进化的核心，对算法收敛性和稳定性有重要作用。交叉算子通过基因重组获取优良个体，决定了遗传算法的全局搜索能力[10]。变异算子通过改变群体个体基因，保证算法能搜索到解空间中的任何角落，能够较好地维持群体的多样性，克服早熟，使算法具有全局收敛性。遗传算法的交叉率和变异率是算法收敛、稳定的关键参数。交叉率越大，算法搜索空间越大，种群越丰富，产生新个体的速度越快，但是优良个体破坏的可能性越大；交叉率过小，不易产生新个体，使得搜索过程缓慢。变异概率是全局最优解的关键，变异率越小，不容易产生新的个体结构，种群多样性变差；变异率过大，又会使遗传算法变成纯粹的随机搜索算法[6]。

本文基于Sigmoid函数和高斯分布函数对交叉率和变异率进行改进，设计自适应非线性调整交叉率和变异率的调节公式。改进算法解决以下几个问题：

1） 在进化初期，要提高搜索速度和个体多样性，而且保证种群中最优个体的交叉率和变异率不应为零；

2） 当平均适应度和最大适应度相差较大时，不会出现线性调整，避免进化停滞不前；

3） 算法后期，在满足精度的情况下，使接近最大适应度处曲线更光滑，缓慢减小交叉率和变异率，使交叉率和变异率的差异减小，较好地保留优良个体。

由图3和改进的式（5），式（6）可知，[Pc]按照个体适应度在[favg]和[fmax]之间随S曲线进行非线性调整，[Pm]按照个体适应度以[favg]为中心随高斯分布曲线进行非线性调节。在种群进化初期，保证了当前种群优良个体[Pc]和[Pm]不为零，而且防止变异率过大破坏种群优良个体，使算法收敛速度变慢和进入局部最优的可能。同时，当大多数个体适应度与[favg]接近时，使个体[Pc]和[Pm]接近最大，避免了算法停滞不前。在个体适应度接近[fmax]时，尽可能缓慢地减小个体[Pc]和[Pm]，减少它们之间的差异，使[Pc]和[Pm]最小，最大限度地保留[fmax]处的优良个体，克服算法早熟和局部收敛，满足算法在进化过程中对不同阶段的要求。

2 改进遗传算法的实现

改进遗传算法实现步骤如下：

1） 对求解参数进行二进制编码，采用小区间生产法初始化种群，进化代数为[T]，种群规模为[n]；

2） 解码，计算种群个体适应度，确定适应度函数[F]，评价是否满足收敛条件。目标函数求最大值，则[F=f（x）]，否则，[F=1f（x）]。同时，对个体适应度按从小到大进行排序，选出最大个体适应度。

3） 如果满足要求（精度10-5或进化代数[T]），输出结果；否则继续步骤4）；

4） 按轮盘赌和遗传代数确定选择复制，生产匹配池；

5） 根据[favg]和个体适应度，结合自适应调节公式进行交叉和变异操作；

6） 返回步骤2），如达到指定要求，算法结束，否则继续执行操作。

3 改进遗传算法的实验及结果分析

3.1 测试函数的选择及优化目标的确定

为研究改进的快速遗传算法（IFGA）的性能及解决多模态复杂问题的能力，选用3个不同的空间函数，通过对比IFGA、基本遗传算法（SGA）、文献[6]的LAGA线性自适应遗传算法的的仿真结果，测试IFGA的收敛速度（平均收敛代数）和稳定性（收敛次数）。在3个函数中，[f1]函数侧重于测试克服早熟，[f2]函数侧重于测试收敛速度。

3.2 算法参数的选择及仿真结果分析

各遗传算法参数见表1。

选择[f1，f3]的最大进化代数为200代，[f2]的最大进化代数为100代。3种遗传算法均采用二进制编码，交叉操作采用单点交叉，变异操作采用基本位变异，SGA和LAGA采用经典轮盘赌选择策略。

由于遗传算法中存在大量随机操作，因此对每种算法各运行20次，统计最优解的收敛次数和平均收敛代数。各算法测试结果见表2和表3，以及图4～图6。

从表2和表3看出，對[f1]函数，SGA的平均收敛代数是本文算法的10.18倍，LAGA平均收敛代数是本文算法的8.2倍，同时，SGA未收敛5次，LAGA未收敛4次，IFGA无未收敛情况。对[f2]函数，SGA和LAGA的平均收敛代数比本文算法多1.02次和5.22次。而对[f3]函数，SGA和LAGA的平均收敛代数比本文算法多19.3次和20.4次。可见，IFGA无论在收敛性还是稳定性上均极大地改善了遗传算法的性能。

图4～图6为在3个测试函数下IFGA，SGA和LAGA搜索最大适应度值的对比曲线。从图4～图6可看出，SGA和LAGA在进化初期容易出现停滞现象。当种群大部分个体接近平均适应度时，由于SGA采用固定的[Pc]和[Pm]，很难跳出局部收敛，虽然LAGA采用了线性自适应调节[Pc]和[Pm]，可以跳出局部收敛的不利状态，但是拖慢了其收敛速度。相比之下，本文提出的改进遗传算法能较好地适应外部环境，当SGA和LAGA在进化初期处于停滞阶段时，IFGA将接近平均适应度的相近个体进行大交叉和变异操作，呈阶梯上升趋势，以最快速度摆脱局部收敛，具有较好的收敛速度和稳定性。

4 结 语

本文针对传统和改进遗传算法在收敛性和稳定性上的不足，提出一种改进的遗传算法。算法从全局出发，对初始化分配、选择、交叉和变异等几个方面进行改进。其中，结合S型曲线和高斯分布曲线，着重对交叉率和变异率的自适应调节进行设计。在求解函数优化问题时，改进的遗传算法无论在收敛速度还是稳定性上，都比SGA和LAGA等遗传算法有较明显的优势，克服了遗传算法易陷入早熟和收敛速度慢等问题。因此，本文提出的改进遗传算法是有效的，为实际工程应用提供了理论支持。

参考文献

[1] 余有明，刘玉树，阎光伟.遗传算法的编码理论与应用[J].计算机工程与应用，2006，42（3）：86?89.

YU Youming， LIU Yushu， YAN Guangwei. Encoding theory and application of genetic algorithm [J]. Computer engineering and applications， 2006， 42（3）： 86?89.

[2] 程敏，宋宇博，孙刚，等.改进的自适应遗传算法及其性能研究[J].计算机与数字工程，2014，42（3）：355?358.

CHENG Min， SONG Yubo， SUN Gang， et al. An improved self?adaption genetic algorithm and its performances [J]. Computer and digital engineering， 2014， 42（3）： 355?358.

[3] LINDA M M， NAIR N E. A new?fangled adaptive mutation breeder genetic optimization of global multi?machine power system stabilize [J]. International journal of electrical power and energy systems， 2013， 44（1）： 249?258.

[4] XU Haiyan. Research for new modified adaptive genetic algorithm [C]// 2012 IEEE World Automation Congress. Puerto Vallarta： IEEE， 2012： 146?147.

[5] SRINVAS M， PATNAIK L M. Adaptive probabilities of crossover and， mutation in genetic algorithms [J]. IEEE transactions on system man and cybernetics， 2002， 24（4）： 656?667.

[6] 任子武，伞冶.自适应遗传算法的改进及在系统辨识中应用研究[J].系统仿真学报，2006，18（1）：41?43.

REN Ziwu， SAN Ye. Improved adaptive genetic algorithm and its application research in parameter identification [J]. Journal of system simulation， 2006， 18（1）： 41?43.

[7] 金立兵，胡颖，祁继鹏.改进的自适应遗传算法在结构优化设计中的应用[J].信阳师范学院学报（自然科学版），2016，29（4）：621?624.

JIN Libing， HU Ying， QI Jipeng. Application of improved adaptive genetic algorithm in structural optimization design [J]. Journal of Xinyang Teachers College （natural science edition）， 2016， 29（4）： 621?624.

[8] 谢燕丽，许青林，姜文超.一种基于交叉和变异算子改进的遗传算法研究[J].计算机技术与发展，2014，24（4）：80?83.

XIE Yanli， XU Qinglin， JIANG Wenchao. An improved genetic algorithm based on crossover and mutation operators [J]. Computer technology and development， 2014， 24（4）： 80?83.

[9] 高玮.改进的快速遗传算法及其性能研究[J].系统工程与电子技术，2003，25（11）：1427?1430.

GAO Wei. An improved fast?convergent genetic algorithm and its performance study [J]. Systems engineering and electronics， 2003， 25（11）： 1427?1430.

[10] 杨从锐，钱谦，王锋，等.改进的自适应遗传算法在函数优化中的应用[J].计算机应用研究，2018，35（4）：1042?1045.

YANG Congrui， QIAN Qian， WANG Feng， et al. Application of improved adaptive genetic algorithm in function optimization [J]. Application research of computers， 2018， 35（4）： 1042?1045.

[11] 梅俊伟，彭仕宓，李雄炎，等.利用Sigmoid函数表征超低渗透储层的非达西渗流特征[J].西安石油大学学报（自然科学版），2011，26（2）：64?67.

MEI Junwei， PENG Shimi， LI Xiongyan， et al. Characterization of the non?darcy seepage flow in ultra?low permeability reservoir based on Sigmoid function [J]. Journal of Xian Shiyou University （natural science edition）， 2011， 26（2）： 64?67.