遗传算法的改进与参数特性研究

刘帅+彭业飞+冯智鑫+张维继

摘要：先叙述了遗传算法的基本原理和操作流程，并结合实际问题具体分析其特点，针对遗传算法易早熟、局部搜索能力弱以及易受参数影响等缺陷，从适应值函数、变异概率和自适应调节三个方面对算法进行了改进研究，并通过实例进行仿真验证，结果表明改进的算法有较好的寻优性能。参数间的不同组合将影响算法的寻优性能，尤其是收敛性，研究交叉概率和变异概率之间的交互作用，得出交叉概率和变异概率的建议取值区间。

关键词： 遗传算法；早熟；局部搜索；交叉概率；变异概率

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2016）04-0182-04

Genetic Algorithm Optimizations Improve And Parameter Features Research

LIU Shuai ，PENG Ye-fei， FENG Zhi-xin，ZHANG Wei-ji

（Naval University of Engineering， Wuhan 430033， China）

Abstract：First describes the basic idea of genetic algorithm， mathematics principle and operation process， and analysis their characteristic combine with the actual problem. In view of the weak of local searching ability of the genetic algorithm is easy to premature and wait for blemish. From the fitness function 、mutation probability and adaptive control algorithm is improved in the aspect of research，and through the example to simulation， the results show that the improved algorithm has better optimization performance. parameters between different combination would have a great influence on the performance of genetic algorithm， particularly affect the convergence of the algorithm， by studying the interaction between the crossover probability and mutation probability， and concluded that the advice of the crossover probability and mutation probability values range.

Key words：Genetic Algorithm； precocious； local searching；crossover probability；mutation probability

1 概述

遗传算法（Genetic Algorithm，GA）是群智能算法的一个重要的组成部分，是基于对达尔文学说的论证的有关于生命进化机制的一种新学科，也是仿生算法的鼻祖 [1]。遗传算法根据生命遗传过程中发生的繁殖、交叉和基因突变现象，利用遗传算子（选择、交叉和变异）按照某一特定的标准进行迭代从而逐渐逼近而找出最优值。遗传算法经过几十年的发展对于解决优化问题有了质的飞跃。本文针对遗传算法易早熟、局部搜索能力弱和易受参数影响的缺陷，从三个不同的方面对算法进行改进研究，并分析交叉概率和变异概率之间的交互作用。

2 遗传算法原理

2.1 基本原理

在GA算法中，生命进化的原理转变为参数所形成的编码串，把染色体视为个体，而染色体又是由很多基因组成。通过基因型与表现型之间的关系，按遗传操作对种群和个体进行筛选[2]。从初始群体开始，重复进行选择、交叉和变异等操作，保留适值函数值高的个体，形成新群体，新群体在保留前代信息的同时，加入了新的更优个体，使得整个群体越来越接近最优结果。通过迭代，群体适应值不断提高，直至达到要求的极限条件。适应值最高的个体即为问题所求最优解。

2.2基本操作和流程

GA算法具有以下三个基本操作。

1）选择：这个方法是根据生物界自然选择的现象中优胜劣汰的原则，从现有的种群中选择出优良的个体，为个体的交叉操作和变异操作准备。一般来说，适应值越高的个体选择的几率就越大，则基因被遗传到下一代的几率也就越大。下面介绍几种比较常用的选择操作算子[3]。

① 适应度比例选择法

这个选择方法又被称为轮盘赌选择方法。选择的概率通过个体适应值所占的比例决定，适应值越大，则选择的概率越大，相反若个体适应值越小，则越容易被淘汰。

② 锦标赛选择法

这个选择法的方法是：选取若干个遗传个体，在这个群体中，选取适应值高的个体遗传到下一代，进而重复上面的过程，最终形成一个群体。

③ 最优保存策略

也称精英保留策略[4]，通过保留最优个体进行最优选择，是学者们比较喜欢采用的一种方法。通过比较当代最优个体和前代最优个体的适应值，保留最优的个体。这种选择方法可避免种群的最优个体不会被遗传操作破坏。

2）交叉：模拟生物进化的繁殖现象，通过两个个体基因的交换与组合，把前一代的个体特征随机搭配成对，来创造出新的优良个体。主要有单点交叉和多点交叉两种方式。

3）变异：这个操作就是在某个基因编码串中随机改变某一位的值，即把1变为0。这种操作为提供新个体提供条件，一般变异概率取值都比较小，大约为0.005-0.01之间，一定程度上，平衡了生命遗传的多样性和稳定性。

GA算法的操作步骤为：

Step 1 对参数进行编码。针对具体问题选择适当的编码方式，把参数集合X转换为相应编码空间S；

Step 2 初始化种群，计算机随机产生N个个体的初始群体，并以这N个群作为算法计算的开始点；

Step 3 进行个体评价。计算个体的适应值，适应值的设定从求解问题的实际出发考虑，按一定的概率选择相应的个体作为父代依照选择算子进行操作；

Step 4 进行交叉操作；

Step 5 进行变异操作；

Step 6 若满足终止条件，则执行执行Step7；否则执行Step 2；

Step 7 输出最优解。

2.3算法特点

1）通用性和鲁棒性较强。GA算法与常规传统寻优方法不同的是，它直接利用目标函数作为信息进行处理，不需要非常准确地描述整个问题的特征，也不需要所求问题的先验知识，因此对知识的依赖性低[2]。

2）具有全局搜索能力。遗传算法的群体搜索策略和遗传算子使遗传算法得以突破领域搜索的限制，可以实现动态调整整个解空间上的信息和采集、探索相应的信息，而变异算子更是有助于跳出局部最优值。此外，遗传算法处理多个个体，即是对多个个体进行评估，可以应用在多峰分布的搜索空间中，避免陷入局部最优值，实现可遗传算法的全局搜索能力。

3）具有良好的扩展性。遗传算法是一个基础的算法，易于和其他的算法相结合。

4）易早熟。因算法的局部搜索能力较弱，在求解优化问题时，GA算法容易过早收敛，即便增大迭代次数，也无法提高解的质量。

5）处理约束问题缺乏良好的手段。编码的不规范和编码的表示不准确，难以把约束问题表示出来。

3遗传算法的改进

3.1 适应值函数遗传算法

一般情况下，直接把目函数作为适应值的函数[5]，这样比较个体的优劣十分便捷。但目标函数值之间往往差别很小，使个体的选择概率也很相近，这样就会使得遗传算法的选择功能被弱化，此时需要对目标函数所得到的适应值进行相对衡量。结合动态线性衡量的方法，本文提出适应值函数改进型遗传算法（Modified Fitness GA，MFGA）。

求解最小值时的公式为：

[F=f-fkmax+ξk]

上式中为适应值函数，为目标函数，为第k代个体的最小目标函数值， 为选择压力调节值，它是一个较小的数，随着k的增大而减小，一般采用如下方法设置：

[ξ0=MξK=K?ξK-1，K∈0.9，0.999] [（2）]

其中M，K为常数。

算法步骤基本与遗传算法相同，但Step 2做如下改进： 对目标函数值作为变换，计算个体适应值，并判断是否满足优化准则，若满足，则输出最优解；否则继续下一步。

3.2 大概率变异遗传算法

为改善算法的稳定性，变异概率的取值一般很小，但当算法出现“早熟”时，就要变异很多代才能得出一个新个体。因此，针对这一情况，提出大概率变异遗传算法（Big probability Mutation GA，BPMGA ） [6]。每一次变异操作的概率都取得很大，使得群体能够随机、独立地产生更多新个体，避免“早熟”。

具体操作过程：当某一代的最大适应度[fmax]与平均适应度[favg]满足

[β?][fmax][<][favg] [（3）]

其中，[0.5<β<1]为密集因子，表征个体的集中程度。

密集因子和变异大概率是BPMGA算法的两个重要参数：

1）密集因子决定变异操作在整个算法搜索过程中所占的比重，数值越接近0.5，则被调用越频繁。

2）变异概率越大，稳定性就越好，但降低了收敛速度。

大变异遗传算法步骤基本与遗传算相同，Step 5稍作改变，内容为：如果当代最大适应度[fmax]与平均适应度[favg]满足[β?][fmax][<][favg]时，进行大概率变异，否则进行普通变异操作。

3.3动态调节遗传算法

在GA算法中，交叉概率越大，产生新个体的速度就越快，但如果过大，遗传模式将可能被破坏，而如果过小，则制约搜索过程。即对于过小变异概率不易产生新个体，而过大的变异概率将增加搜索的盲目性。因此针这个情况，提出动态调节遗传算法[7]（Adjust GA，AdjGA），交叉概率和变异概率能够随适应度自动改变，根据具体问题来改善优化。

动态调节遗传算法中交叉概率[Pc]和变异概率[Pm]为：

[Pc=k1（fmax-f）fmax-favg，f≥favgk2，f

[fmax]为种群体最大适应值；[favg]为种群平均适应值；[f]为进行交叉的两个个体中较大的适应值；[f']为要变异个体的适应度值；[k1，k2，k3，k4]为常数。

动态调节遗传算法步骤在基本遗传算法Step 4和Step 5上运用式来计算相应的变异和交叉概率。

4 算法测试

本文选取典型的多峰值测试函数：

测试函数[maxf（x）=2x2cos（3x）+xsin（5x）+8，?x∈2，10]，理论上的最大值点为[（8.3885，141.1756）]，该函数形状如图1所示。采用一般的寻优方法求解该函数时容易陷入局部极值。采用基本遗传算法和上述三种改进遗传算法对测试函数进行测试，参数设置如下：种群大小50，迭代次数100，交叉概率0.8.变异概率0.005，编码长度24。

结果如图2和表1 所示：

从图表中可以得出，虽然基本遗传算法所耗时少但是改进的遗传函数迭代了500代后的平均适应度值均比基本遗传算法的精确。BPMGA采用大变异率增强了整个函数的全局搜索能力，因此方差相对来说比较大，但是寻优值是较好的。MFGA虽然耗时较长，但是均值比较高，最小值也接近最优值，说明MFGA函数寻值优化较强，每次运行结果偏差小，高提稳定性。AdjGA方差较小，说明函数内部结构一直随着外界因素变化自行自我调节，适合复杂问题的优化计算。

5 交叉概率Pc和变异概率Pm

遗传算法应用于函数优化问题时，一个非常重要、值得研究的问题是遗传算法中的控制参数如何设定.各个控制参数不同选择，参数间的不同组合会对遗传算法的性能产生较大的影响，尤其影响算法的收敛性。文献[8]中对Pc和Pm交互作用进行了研究，其图像如图3 所示：

由图3可知，每条线的形状大体相同，由此本文得出如下结论Pc和Pm的交互作用很小。再者，根据文献[8]的实验结果，每组实验中都有一个Pc和Pm的最优组合，共有 20 组实验数据，数据积累如表2所示：

根据相关性分析知识，利用 SPSS 计算出交叉概率Pc和变异概率Pm相关系数为0.112，由此亦能说明Pc和Pm相关性不大，因此，在接下来的实验中本文采用固定Pc，研究Pm的最优取值范围，固定Pm，研究Pc的最优取值范围。

实验结果分析：

遗传算法中，根据大量资料给出的Pc和Pm取值范围，Pc的建议取值范围是0.4 ～ 0.99，Pm的建议取值范围是0.0001～ 0.1，本文经过大量实验，并根据实验结果分析研究，给出[f（x）=x″]一类幂函数求得全局最优解时所用最少遗传代数的均值，Pm取值范围是[0.009，0.03]，Pc的取值范围是[0.6，0.99]。

6 结束语

遗传算法是一种模拟自然生命进化的算法，为复杂系统的优化提供了一种新的方法，自提出以来，关注热点高，经过发展，如此理论、应用都很成熟，对其他仿生算法的提出和改进都具有借鉴性。本文介绍了遗传算法的基本原理和操作流程，对三个重要的操作因子：选择、交叉和变异分别做了阐述。引进三种常见的改进遗传算法，并修改了适应值函数遗传算法的计算方式。对算法的交叉概率和变异概率进行了研究，得出相应结论。

参考文献：

[1] 玄光男，程润伟. 遗传算法与工程优化[M].北京：清华大学出版社，2011 ：82-89.

[2] 李敏强，寇纪淞，林丹，等.遗传算法的基本理论与应[M].北京： 科学出版社，2012.

[3] 葛继科，邱玉辉，吴春明，等.遗传算法研究综述[J].计算机应用研究，2008，25（ 10） ：2911-2916.

[4] 喻寿益，邝溯琼.保留精英遗传算法收敛性和收敛速度的鞅方法分析[J].控制理论与应用，2010，27（ 7） ：843-848.

[5] 马永杰，马义德，蒋兆远，等.一种快速遗传算法及其收敛性[J].系统工程与电子技术，2009，31（3） ：714-718.

[6] ZHANG Jin-hua，ZHUANG Jian，DU Hai-feng，et al. Self-organizing genetic algorithm based tuning of PID controllers[J].Information Sciences，2009，179（ 7） ： 1007-1018.

[7] 申晓宁，郭毓，陈庆伟，等.一种保持群体多样性的多目标遗传算法[J].控制与决策，2008，23（ 12） ：1435-1440.

[8] Eusuff M M，Lansey K E.Optimization of water distribution network design usingthe shuffled frog leaping algorithm[J].Water Resources Planning and Management，2013，129（3）：210-25.