遗传算法变异算子的改进

王春阳,赵玉庆,谢金兴,苏本堂

遗传算法变异算子的改进

王春阳,赵玉庆,谢金兴,苏本堂*

山东农业大学信息科学与工程学院, 山东泰安 271018

为了提高遗传算法的全局寻优能力，本文提出变异算子的一种新的构造机制。在种群进化的初始阶段，使变异点发生在二进制染色体的高位区，以保证种群的多样性；在进化的中期阶段，使变异点发生在染色体的中位区，以保持种群持续大范围寻优；在收敛阶段，使变异点发生在染色体的低位区，以提高最优个体的精度。数值试验表明，在不增加算法整体计算量的前提下，这样构造的变异算子，对避免遗传算法出现早熟具有明显的积极作用。

遗传算法; 变异算子; 二进制

其中表示决策变量个数，()为多峰函数。记(1,2,…,l)，=(1,2,…,u)，[,]为可行解空间。

多峰函数全局最优化问题的求解方法有两类，第一类是确定性算法，譬如填充函数法[1]、隧道法[2]、积分-水平集法[3]、割峰函数法[4]等；另一类是智能算法，典型的有遗传算法[5]、模拟退火算法[6]、粒子群算法[7]等。确定性算法计算效率高，但对目标函数的性态要求苛刻；智能算法虽然计算量较大，但可以并行计算，并且对目标函数的性态要求低。

作为一种应用广泛的智能算法，遗传算法的改进一直受到学术界的重视。这些改进工作主要围绕提高算法的计算效率、克服早熟现象展开。譬如，江中央等提出了一种自适应正交交叉算子的方法，并引入了基于种群分割和单形搜索的局部搜索策略[8]；曾三友[9]等把正交实验方法和统计优化方法相结合，提出了一种基于正交设计的多目标最优化算法；谢燕丽[10]等给出一种基于黄金分割法的变异算子构造。

本文给出一种控制变异算子变异点的策略，在种群进化的不同阶段，选择不同的位置进行变异。将该变异算子与文[8]的遗传算法相结合，对提高算法的计算效率和健壮性有较为明显的作用。

1 遗传算法及其变异算子

遗传算法的核心内容由参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定等五个要素组成，其中遗传操作分交叉、选择和变异三个环节。

变异是对基因链上的某个基因按较小概率改变，以此保持个体的多样性，克服早熟现象。变异算子是遗传算法产生新个体的重要操作，是影响算法收敛性能的关键。变异操作主要有四种形式：

（1）基本位变异。对个体编码串以一定的变异概率随机指定某一位或某几位基因进行变异操作。

（2）均匀变异。分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因上的原有基因值。

（3）二元变异。对于选取的两条染色体，通过二元变异操作生成两条新个体中的各个基因分别取原染色体对应基因值的同或/异或。

（4）高斯变异。用正态分布的一个随机数来替换原有基因值。其操作过程与均匀变异类似。

2 变异算子的改进

2.1 变异算子的改进思路

本文采用二进制编码，在种群进化的不同阶段，对变异基因的位置采取不同的控制策略。

高位变异：指在遗传进化的初始阶段（第1~1代，其中0<1<(/2)，代表种群进化的代数）时，控制变异发生在染色体的高位区，使变异产生的新个体能够均匀的分布在整个解空间中，从而使个体的分布具有多样性，提高了种群基因库的多样性，避免了早熟现象的发生。

中位变异：指在遗传进化的中期阶段（第(1+1)~2代，其中1<2<）时，通过控制变异发生在染色体的中位区，使种群的个体在可行解空间持续大范围寻优，加快算法收敛的速度。

低位变异：指在遗传进化的收敛阶段（第2+1~代）时，即在种群进化末期，整个种群基本上收敛在全局最优解的附近，通过控制变异发生在染色体的低位区，有利于提高最优个体的精度。

2.2 改进变异算子的伪代码

Step1 根据解空间和精度，将实数值个体转化为二进制表示的个体

Step2分割二进制段

对每一个存储在数组（下标从0开始）中的长度为BitLength二进制染色体进行以下划分，使其染色体的表示变为：[高位，中位，低位] BitLength1=[BitLength-BitLength/3]；BitLength2=[BitLength1-BitLength/3]。

将每一个二进制染色体均匀地分割为三部分，分别为：“高位”：[0, BitLength2]；“中位”：(BitLength2, BitLength1]；“低位”：(BitLength1, BitLength]

Step3进行变异

判断：如果为1~1代，则在染色体的“高位”，随机选取一个位点进行取反。

判断：如果为(1+1)~2代，则在染色体的“中位”，随机选取一个位点进行取反。

判断：如果为(2+1)~代，则在染色体的“低位”，随机选取一个位点进行取反。

3 遗传算法的实现

除了上述给出的变异算子，本文采纳了文[8]算法中的自适应正交交叉算子和聚类局部搜索技术，以增强算法的局部寻优能力，简述如下。

3.1 自适应正交交叉算子(简称SOC)

自适应正交交叉算子是选取两个父代个体，指定正交设计的水平Q，对超长方体的每一维按选定的水平数进行离散化。正交设计的因素F依据两个父代个体数值接近的分量个数动态确定，并通过正交设计产生子代个体。

3.2 聚类局部搜索

聚类局部搜索策略是先对群体进行聚类，将种群分割为互不相交的局部邻域，使每个子种群仅覆盖搜索空间一个较小的邻域。对每个子种群，利用单形交叉算子[11]进行局部搜索，以提高单形搜索的局部收敛速度；同时对不相交的局部邻域进行并行搜索,以实现快速的全局搜索。

3.3 遗传算法实现的主要步骤

Step1种群初始化：正交设计产生初始种群。

Step2生成临时种群ʹ：每代种群的每一个个体以一定的概率被选择进临时种群中。

若临时种群个体数为奇数，则再从进化种群中随机选择一个个体加入到临时种群中。

Step3交叉操作：对临时种群中的个体进行随机配对，对其中的每一个个体都以概率p进行SOC，将交叉后产生的新一代个体加入到群体集合C中。

Step4局部搜索：临时种群ʹ经过最近原则局部搜索后生成新种群L。

Step5变异：种群ʹ的任一个体p=(p,1,p,2,…,p,N)，Î{1,2,…}（其中，代表种群个体数），以概率p参与变异操作，选择出要变异的个体后，按照2.2中改进的变异算法进行变异，群体经变异后生成的新种群记G。

Step6选择：最优选择策略，从种群(P+C+L+G)中选择适应度值最好的初始种群个数的70%进入下一代种群，再从种群(P+C+L+G)剩余的个体中，随机选择至种群最初个数。

Step7终止判断：达到满意结果，结束并输出结果，否则转Step2。

4 数值试验

为了测试本文提出的改进的变异算子的性能，我们采用文[8]中的14个高维的Benchmark函数作为测试集，并将求解效果与文[8]的结果进行了比较。对于函数1~6及函数10~14，=30；对函数7~9，=100。函数1~8属于多峰函数，每一个函数具有多个局部极值点，其中函数7具有100!=9.33×10157个局部极值点。

对所有的测试函数，参数的选取与文[8]是一致的。种群的规模=200，同时取p=0.6，p=0.1。当程序运行达到=120代或找到最优解时，就终止运行，其中变异算子的1=20，2=70。对每一个函数，在相同的条件下独立运行30次，记录其平均函数评价次数(M-num-fun)，最优平均值(M-best)和标准差(St.dev)。

由表1可见，函数1~4、10~14得到全局最优解，而5~9得到近似最优解。与[8]的结果相比较，函数3，5，7，9在精确度与稳定性方面均有了明显的提高，函数1，8在稳定性方面有较大的提升，函数6在精确度与稳定性方面有所提高，其余函数在精确度与稳定性方面均与文[8]的结果相同。

表1 两种算法（本文算法，HSOGA[8]）对14个测试函数的实验结果比较

5 结语

随着计算机技术的不断进步和超级计算的广泛应用，遗传算法作为求解复杂优化问题全局最优解的有效算法之一，构造健壮性更好的算法是有意义的。本文在前人的基础上给出遗传算子设计的新思路，使算法的全局搜索能力有所提高，对克服早熟现象、提高收敛速度具有比较明显的作用。

[1] Ge R: A filled function method for finding a global minimizer of a function of severalvariables[J]. Math. Prog,1990,46:191-204

[2] Levy AV, Montalvo A.The tunneling algorithm for the global minimization of functions[J]. SIAM J. Sci. Stat. Comput,1985,6:15-29

[3] 田蔚文,邬冬华,张连生,等.一种修正的求约束总极值的积分-水平集方法[J].应用数学和力学,2004,25(2):181-188

[4] Wang Y, Fang W, Wu T. A cut-peak function method for global optimization [J].Comput. Appl. Math, 2009,230:135–142

[5] Holland JH. Adaptation in Natural and Artificial Systems[M].Cambridge: MIT Press, 1992

[6] 康立山.非数值并行算法-模拟退火算法[M].北京:科学出版社,1994

[7] Kennedy J, Eberhart R. Particle Swarm Optimization [M].New York: IEEE, 1995

[8] 江中央,蔡自兴,王勇.求解全局优化问题的混合自适应正交遗传算法[J].软件学报,2010,21(6):1296-1307

[9] 曾三友,魏巍,康立三,等.基于正交设计的多目标演化算法[J].计算机学报,2005,28(7):1153-1162

[10] 谢燕丽,许青林,姜文超.一种基于交叉和变异算子改进的遗传算法研究[J].计算机技术与发展,2014,24(4):80-83

[11] 蔡自兴,江中央,王勇,等.一种新的基于正交实验设计的约束优化进化算法[J].计算机学报,2010,33(5):855-864

An Improved Genetic Algorithm Variation Operator

WANG Chun-yang, ZHAO Yu-qing, XIE Jin-xing, SU Ben-tang*

271018,

In order to improve the global optimization ability of genetic algorithm, this paper proposes a new construction mechanism of the mutation operator. In the initial stage of population evolution, we select the mutation point in the high region of the binary chromosome to ensure the diversity of the population; in the middle stage of evolution, we make the mutation point occur in the middle region of the chromosome to maintain a large range of population optimization, while in the convergence phase, the mutation point occurred in the lower region of the chromosome to improve the accuracy of the optimal individual. Numerical experiments show that the mutation operator constructed in this way has obvious positive effects on avoiding the premature development of the genetic algorithm without increasing the overall calculation of the algorithm.

Genetic algorithm; mutation operator; binary system

TP301.6

A

1000-2324(2019)05-0898-04

10.3969/j.issn.1000-2324.2019.05.036

2018-06-12

2018-10-26

国家大学生科技训练计划项目(201710434312)

王春阳(1995-),男,本科生,研究方向:计算科学. E-mail:15726569335@163.com

Author for correspondence.E-mail:sbtmath@sdau.edu.cn