控制与决策  2020, Vol. 35 Issue (9): 2277-2284  
0

引用本文 [复制中英文]

宋莹莹, 王福林, 兰佳伟. 基于跳跃基因算子的改进实数遗传算法[J]. 控制与决策, 2020, 35(9): 2277-2284.
[复制中文]
SONG Ying-ying, WANG Fu-lin, LAN Jia-wei. Improved real-coded genetic algorithm based on jumping gene operator[J]. Control and Decision, 2020, 35(9): 2277-2284. DOI: 10.13195/j.kzyjc.2019.0024.
[复制英文]

基金项目

公益性行业专项课题项目(201503116-04);国家重点研发计划课题项目(2018YFD0300105);黑龙江省哲学社会科学研究规划项目(18GLC205)

作者简介

宋莹莹(1993-), 女, 博士生, 从事遗传算法、数据挖掘、图像处理的研究, E-mail: songyingying@neau.edu.cn;
王福林(1982-), 男, 教授, 博士生导师, 从事遗传算法理论及应用、神经网络理论及应用等研究, E-mail: fulinwang1462@163.com;
兰佳伟(1993-), 男, 硕士生, 从事遗传算法、组合预测的研究, E-mail: 269005186@qq.com

通讯作者

王福林. E-mail: fulinwang1462@163.com

文章历史

收稿日期:2019-01-04
修回日期:2019-03-27
基于跳跃基因算子的改进实数遗传算法
宋莹莹 , 王福林 , 兰佳伟     
东北农业大学 工程学院,哈尔滨 150030
摘要:为了避免遗传算法在求解数值优化问题时出现搜索能力差、多样性缺失等弊端, 提出一种基于实数编码的改进遗传算法(IRCGA).算法集成两个特别设计的算子:模拟二进制跳跃基因算子(SBJG)和多方向交叉算子(MX). SBJG算子以染色体为操作对象, 本质上模拟了二进制跳跃基因操作中的插入运动, 即利用一种随机的方式将选定的染色体块插入到染色体位点, 实现种群内部染色体间的转位, 为种群提供额外的遗传多样性; MX算子通过增加交叉方向的方式扩大算子的搜索区域, 从而提升后代个体质量与算法的搜索能力.在11个实例的基础上进行对比实验, 结果表明, 采用改进算子能够明显提升算法在求解数值优化问题时的性能, 同时, 相比于其他先进有效的算法, IRCGA具有较强的搜索能力且能够维持一定的种群多样性, 从而验证了改进算法的有效性和可行性.
关键词实数遗传算法    数值优化    模拟二进制跳跃基因算子    种群多样性    多方向交叉算子    搜索能力    
Improved real-coded genetic algorithm based on jumping gene operator
SONG Ying-ying , WANG Fu-lin , LAN Jia-wei     
School of Engineering, Northeast Agricultural University, Harbin 150030, China
Abstract: In order to avoid the disadvantages of genetic algorithms in solving numerical optimization problems, such as poor search ability and lack of diversity, an improved real-coded genetic algorithm (IRCGA) is proposed. The algorithm integrates two specially designed operators: the simulated binary jumping gene (SBJG) operator and the multi-directional crossover (MX) operator. The SBJG operates on chromosomes. It essentially simulates the insertion motion in binary jumping gene operation, that is, inserts the selected chromosomal block into the chromosomal locus in a random way, and realizes the translocation between the chromosomes within the population, which provids additional genetic diversity for the population. The MX operator expands the search area of the operator by increasing the crossover direction to improve the quality of the offspring and the search ability of the algorithm. The comparative experiment is carried out on the basis 11 examples. The results show that the improved operator can significantly improve the performance of the algorithm in solving numerical optimization problems. At the same time, compared with other advanced and effective algorithms, the IRCGA has strong search ability and can maintain a certain population diversity, thus verifying the effectiveness and feasibility of the improved algorithm.
Keywords: real-coded genetic algorithm    numerical optimization    simulated binary jumping gene operator    population diversity    multi-directional crossover    search ability    
0 引言

遗传算法的有效性通过在适者生存的原则下进化搜索能力与种群多样性实现, 交叉作为影响搜索能力的核心算子, 其与精英保留操作的结合会在一定程度上降低种群多样性, 影响算法性能[1].

种群失去多样性, 会导致搜索过程停滞.为了避免这种情况, 常用的方法是对变异算子进行改进, 但程度往往不够, 因此, 需要引入其他机制进行抵消[2-3].为此, Mitchell等[4]对遗传物质重排进行了研究, 发现跳跃基因能够为种群提供额外的多样性.与跳跃基因算子一样, 设计高效的交叉算子能够促使算法有效地探索解空间, 因此, 对跳跃基因算子与交叉算子进行改进研究对于提升算法性能有着重要的意义.

在对跳跃基因算子的研究中, 文献[3, 5]最先提出了跳跃基因的概念, 即基因能够在染色体与染色体之间随意跳动, 从而影响基因组的遗传行为.随后, Kasat等[6]提出了一种二进制跳跃基因算子(JG), 并将其应用于遗传算法中.但二进制编码的随机性会降低算法的局部搜索能力, 为此, Sankararao等[7-8]通过向算法内部引入特定适应机制, 模拟JG的概念提出了SBJG-1算子, 并成功将其应用于整数变量. Ripon等[3]提出的SBJG-2算子根据随机选定的染色体数目调整算法所执行的操作. Ramteke等[8]提出的SBJG-3算子利用指数分布对基因进行动态调控, 在变量及其组合方面保留了大量原始信息.

在对交叉算子的研究中, 最常见的是SBX算子, 通过模拟单点交叉算子, 使子代与父代的跨度成正比, 但却限制了算子的搜索区域[8].王吉权[9]提出的DBHX算子利用目标函数值确定交叉方向, 仅适用于单峰函数, 并不适用于全局优化的普遍情形.文献[1, 8, 10]根据算法区间模式的概念提出了BLX-算子, 但当个体间差异性较大时, 算子的搜索方式类似于随机搜索, 收敛性不强.

综上所述, 传统的跳跃基因操作过度专注于模拟JG的过程, 忽视了算子的效果, 而交叉算子的方向过于单一, 搜索区域受限, 无法有效引导个体向最优区域进化, 启发性不强.因此, 为了更好地维持种群多样性, 提升算法搜索能力, 本文提出一种新的模拟二进制跳跃基因算子SBJG与多方向的交叉算子MX, 并在11个实例的基础上进行对比实验.结果表明, 采用改进算子能够明显提升算法在求解数值优化问题时的性能, 同时, 相比于其他先进有效的算法, IRCGA具有较强的搜索能力且能够维持一定的种群多样性, 从而验证了改进算法的有效性和可行性.

1 改进算法描述 1.1 选择算子

改进算法选用排序分组选择[9], 能够增大配对个体间的差异性, 有效避免近亲繁殖.

1.2 模拟二进制跳跃基因算子

传统的跳跃基因算子以基因为操作对象, 利用基因的剪切、插入与互换运动实现染色体内部基因间的转位[6-8].但对于实数编码的算法而言, 由于变量的取值范围不同, 剪切与互换会产生越界问题.此外, 剪切与互换是在原基因库上进行的操作, 只有插入会向基因库内引入新的遗传信息[3].因此, 本文提出的SBJG算子以染色体为操作对象, 通过模拟基因的插入运动为种群提供多样性, 具体操作步骤如下.

SBJG算子在规模为n的种群(X1, X2, …, Xn)内利用取值范围[1, n]的整数随机数Rx选定两个染色体位点jgx1、jgx2, 满足1≤jgx1≤jgx2n, 染色体位点jgx1与jgx2间的染色体块长度为ljgx=(jgx2-jgx1+1).利用Rx选定染色体的插入位点Ix, 满足插入位点的个数NIxljgx. SBJG算子利用新产生的染色体块替换原染色体块并以随机插入选定位点的方式实现种群内部染色体间的转位, 新染色体块中个体Xinew的产生公式为

(1)

其中: a=[a1, a2, …, aD]、b=[b1, b2, …, bD]为变量取值下限和上限, D为染色体维数, rand(1, D)为1行D列取值范围[0, 1]的随机向量, rand(1, D)(b-a)为(b-a)与rand(1, D)中相同位置元素的乘积.以种群规模n=6, 染色体块长度ljgx=3为例, SBJG算子操作示意图如图 1所示.

图 1 SBJG算子的操作示意

图 1中SBJG算子利用随机产生的新染色体块X2newX3newX4new替换原染色体块.由关系式NIxljgx可知, NIx的取值有3种情况, 依次如图 1(a) ~ 图 1(c)所示, 其中图 1(b)还可以表示在Ix1处插入两条染色体、Ix2处插入一条染色体的情况.

为了验证SBJG算子是否模拟了JG算子的本质, 对JG和SBJG算子进行定性分析.设二进制编码字符串长度lstr=20, 变量维数D=3, 变量取值上下限为ai=0, bi=1(i=1, 2, 3).用随机生成的5 000个实例Xold作为初始变量分别进行JG与SBJG操作, 得到新变量Xnew, 其中JG操作得到的Xnew需解码回实际值[8].利用XoldXnew的实际值计算操作对变量扰动的分布函数α, 有

(2)

其中α在区间[-1, 1]内波动, 当α趋近于0时表示变量受到较低的扰动; 当α接近-1和1时表示变量受到较大的扰动. JG算子(图 2(a)图 2(b))与SBJG算子(图 2(c)图 2(d))对变量扰动的分布如图 2所示.

图 2 JG算子与SBJG算子的变量扰动分布

图 2(a)图 2(c)中分别有约80 %和70 %的点位于0附近, 意味着SBJG与JG算子一样对大量实例产生了局部扰动.将α按升序排序, 如图 2(b)图 2(d)所示, 两幅图中均有明显的递增和递减曲线, 表明SBJG与JG算子均对部分变量产生了较大扰动, 因此证实了SBJG算子模拟了JG算子对变量扰动的性质.

SBJG算子虽与变异作用相似, 但是两者机制不同, SBJG在交叉操作前进行, 不需要概率的设定, 可以为种群提供额外的多样性.此外, SBJG以染色体为操作对象, 通过模拟基因的插入运动实现种群内部染色体间的转位, 因此不需要计算复杂的种群结构, 程序简单.

1.3 多方向的交叉算子

为了增大算子的搜索区域, MX算子在传统交叉方向的基础上新增了两个交叉方向.传统方向以较大的概率指向目标函数值较优的一侧, 为了使算子能够产生优质个体, 新增方向与传统方向指向同侧, 因此新方向通过将传统方向分别向两边旋转90°和45°获得的, 这样既能保证新增方向与传统方向指向同侧, 又能保证新增方向以不同的程度扩大搜索区域.以配对个体X1X2为例, X1的目标函数值优于X2, 传统交叉方向为X2X1, X2X3X2X4分别为X2X1向两边旋转90°和45°形成的新方向.算法具体步骤如下.

step 1:确定点X3, 根据向量垂直、模长相等的关系, 对随机生成的点X'=[x'1, x'2, …, x'D]中x'D进行归一化处理, 使其位于X2X3所在的直线上, 进而确定点X3, 有

(3)

step 2:作RtΔ X1X2X3斜边X1X3中点关于直角边的对称点, 即点X4, 有

(4)

由式(3)和(4)可以确定交叉方向X2X1X2X3X2X4, 算子在交叉方向XiXj上按下式产生个体:

(5)

step 3:从产生的个体中选择两个目标函数值最优的个体作为配对个体产生的后代.以变量维数D=2为例, MX算子产生的交叉方向的空间分布如图 3所示, 其中Xbest为全局最优解.

图 3 交叉算子的空间分布

图 3可见, 不同于单方向的交叉算子[9], MX算子中新增的交叉方向在不同程度上扩大了算子的搜索区域, 使算法能够更加全面地探索解空间, 从而提升算法的搜索能力.

1.4 变异算子

本文改进算法使用组合变异算子(CM).当迭代次数为奇数代时, 执行均匀变异[11], 此时算子具有较强的全局搜索能力; 否则, 执行高斯变异[9], 此时算子具有较强的局部搜索能力.

1.5 进化策略

改进算法选用罚函数法处理约束条件[4], 同时, 以算法是否达到给定最大迭代次数为终止条件.改进算法的伪代码如下所示, 算法中的参数设置为: n=100, Pc=1, Pm=0.5, M=1010, maxgen= 1 000, s=40.

输入:种群大小n, 交叉概率Pc, 变异概率Pm, 罚函数M, 最大迭代次数maxgen, 精英个体数s;

输出:实际最优值X*, 种群多样性div.

1.初始种群X={Xi, i=1, 2, …, n}

2. {F(Xi), i=1, 2, …, n}←计算目标函数值(Xi)

3. s←精英保留(Xi)

4. gen=1 //迭代次数

5. while(满足最大迭代次数) do

6.    {X1, X2}←RS算子(X)

7.    {X1, X2}←SBJG算子{X1, X2}

8.    Xc← MX算子{X1, X2}

9.    s←精英保留(Xc, s)

10.   xM←CM算子(Xc)

11.   s←精英保留(XM, s)

12.   X←替换操作(XM, s)

13. end while

14.输出X*, div

操作: s←精英保留(Xi)

1. s←从(Xi)中选择s个最优个体

2.输出s

操作: X←替换操作(XM, s)

1. X←从(XM, s)中选择最优的n个个体

2.输出X

2 实验结果与分析 2.1 算子的基本功能

为了系统地研究各算子在算法中的作用, 实验依次禁用算法中的某一算子, 其余算子正常使用.禁用MX算子时记为Test-1, 禁用SBJG算子时记为Test-2, 禁用CM算子时记为Test-3, 算法同时使用所有算子时记为Test-4[12].选择11个基准测试函数[1, 9-10, 13-15], 其中除f6f10除外, f1~ f11为高维或非线性优化问题, f6f10为工程设计中减速器与热换器优化问题, 测试函数如下:

为了获得公平的性能比较基础, 算法在同一台计算机上运行, 每个测试函数均运行1 000次, 实验评价指标取最优解的最小值(min), 均值(mean)以及平均种群多样性(div)[12], 结果如表 1 ~ 表 3所示.

表 1 评价指标min的实验结果
表 2 评价指标mean的实验结果
表 3 评价指标div的实验结果

由实验结果可知, 在11个测试函数上, 对于指标div而言, 实验Test-1最优, 表明同时使用SBJG和CM能够提升种群多样性, 且SBJG提升多样性的程度远大于CM(对比Test-2与Test-3可知).对于指标min和mean而言, 实验Test-4的结果最优, 表明MX具有较强的搜索能力.同时, 也证实了算法同时使用所有算子时性能最优(对比实验Test-1与Test-2、Test-3、Test-4可知).

2.2 算法的有效性验证

为了验证改进算法的有效性, 首先, 将其对比于在使用跳跃基因算子方面较为有效的算法RCGA-S-1[7]、RCGA-S-2[3]、RCGA-S-3[8]; 然后, 替换改进算法中的SBJG算子为以往跳跃基因算子SBJG-1、SBJG-2、SBJG-3, 替换后算法记为IRCGA-S-1、IRCGA-S-2、IRCGA-S-3;最后, 将算法对比于在求解测试函数上较为有效的算法RCGA-1[13]、RCGA-2[9]、RCGA-3[16]、RCGA-4[1]、RCGA-5[10].对于实验中涉及的算法而言, RCGA-3与RCGA-4的时间复杂度最大, 为O (n2log(maxgen)), 其余算法均为O (nlog(maxgen)), 而算法的空间复杂度均为O(n× D), 因此改进算法与对比算法在运行过程中无明显差异.实验结果如表 4~表 7所示, 其中指标time为算法的平均运行时间.

表 4 不同算法作用下测试函数f1f2f3的实验结果
表 5 不同算法作用下测试函数f4f5f6的实验结果
表 6 不同算法作用下测试函数f7f8f9的实验结果
表 7 不同算法作用下测试函数f10f11的实验结果

由实验结果可知, IRCGA求得的最小值min与均值mean最优, 表明IRCGA较对比算法而言具有较强的搜索能力.通过计算各算法在测试函数上的整体平均种群多样性[15]可以得出, IRCGA的平均种群多样性优于RCGA-S-2、IRCGA-S-3、RCGA-3、RCGA-4, 表明IRCGA能够将种群多样性维持在一个相对较高的水平.同理, 计算各算法的整体平均运行时间可知, 除RCGA-3外, IRCGA的平均运行时间最短, 而RCGA-3的搜索能力较差, 因此相较于对比算法, IRCGA能够在相同的迭代次数内以最短的时间搜索到最优解, 具有较快的收敛速度.综上, 实验强有力地表明了改进算法的有效性.

3 结论

为了在提升算法搜索能力的同时维持一定的种群多样性, 本文提出了一种模拟二进制跳跃基因算子SBJG与多方向的交叉算子MX.不同于传统跳跃基因算子, SBJG算子以染色体为操作对象, 通过模拟基因的插入运动实现种群内部染色体间的转位, 具有对大部分变量产生局部扰动的性质, 为种群提供了额外的多样性. MX算子在传统交叉方向的基础上新增了两个与其指向同侧的交叉方向, 在扩大算子搜索区域的同时保证算子以较大的概率产生优质的个体, 提升了算法的搜索能力.在11个测试函数上与一些先进的算法进行了对比实验, 由实验结果可以看出, 改进算法具有较强的搜索能力和较快的收敛速度, 且能够维持一定的种群多样性, 从而验证了算法的有效性和可行性.

参考文献
[1]
Ismkhan H. Black box optimization using evolutionary algorithm with novel selection and replacement strategies based on similarity between solutions[J]. Applied Soft Computing, 2018, 64(3): 260-271.
[2]
何庆, 吴意乐, 徐同伟. 改进遗传模拟退火算法在TSP优化中的应用[J]. 控制与决策, 2018, 33(2): 219-225.
(He Q, Wu Y L, Xu T W. Application of improved genetic simulated annealing algorithm in TSP optimization[J]. Control and Decision, 2018, 33(2): 219-225.)
[3]
Ripon K S N, Kwong S, Man K F. A real-coding jumping gene genetic algorithm (RJGGA) for multi objective optimization[J]. Information Sciences, 2007, 177(2): 632-654. DOI:10.1016/j.ins.2006.07.019
[4]
Mitchell M, Forrest S. Genetic algorithms and artificial life[J]. Artificial Life, 1994, 1(3): 267-289. DOI:10.1162/artl.1994.1.3.267
[5]
Freeling M. The dynamic genome: Barbara McClintock's ideas in the century of genetics[J]. Trends in Genetics, 1992, 8(12): 463. DOI:10.1016/0168-9525(92)90333-Y
[6]
Kasat R B, Gupta S K. Multi-objective optimization of an industrial fluidized-bed catalytic cracking unit (FCCU) using genetic algorithm (GA) with the jumping genes operator[J]. Computers & Chemical Engineering, 2003, 27(12): 1785-1800.
[7]
Sankararao B, Gupta S K. Multi objective optimization of the dynamic operation of an industrial steam reformer using the jumping gene adaptations of simulated annealing[J]. Asia‐pacific Journal of Chemical Engineering, 2010, 1(1/2): 21-31. DOI:10.1002/apj.4
[8]
Ramteke M, Ghune N, Trivedi V. Simulated binary jumping gene: A step towards enhancing the performance of real-coded genetic algorithm[J]. Information Sciences, 2015, 325(20): 429-454. DOI:10.1016/j.ins.2015.07.033
[9]
王吉权, 程志文, 代伟婷, 等.求解有约束优化问题的实数遗传算法改进研究[DB/OL]. (2017-10-26)[2018-04-16]. http://kns.cnki.net/kcms/detail/21.1124.TP.20180416.0932.024.html.
((Wang J Q, Cheng Z W, Dai W T, et al. Research on improvement of real-coded genetic aligorithm for solving constrained optimization problems[DB/OL].(2017-10-26)[2018-04-16]. http://kns.cnki.net/kcms/detail/21.1124.TP.20180416.0932.024.html.)
[10]
Pathan M V, Patsias S, Tagarielli V L. A real-coded genetic algorithm for optimizing the damping response of composite laminates[J]. Computers & Structures, 2018, 198(3): 51-60.
[11]
Contaldi C, Vafaee F, Nelson P C. Bayesian network hybrid learning using an elite-guided genetic algorithm[J]. Artificial Intelligence Review, 2018, 52(293): 245-272.
[12]
Song Y, Wang F, Chen X. An improved genetic algorithm for numerical function optimization[J]. Applied Intelligence, 2019, 49(5): 1880-1902. DOI:10.1007/s10489-018-1370-4
[13]
杨新武, 杨丽军. 基于交叉模型的改进遗传算法[J]. 控制与决策, 2016, 31(10): 1837-1844.
(Yang X W, Yang L J. An improved genetic algorithm based on crossover model[J]. Control and Decision, 2016, 31(10): 1837-1844.)
[14]
Yao X, Liu Y, Lin G. Evolutionary programming made faster[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(2): 82-102. DOI:10.1109/4235.771163
[15]
Chuang Y C, Chen C T, Hwang C. A simple and efficient real-coded genetic algorithm for constrained optimization[J]. Applied Soft Computing, 2016, 38(1): 87-105.
[16]
任永泰, 张达, 许东阳, 等. 基于实数遗传算法与神经网络的农机总动力预测及分析[J]. 农机化研究, 2018, 40(7): 13-18.
(Ren Y T, Zhang D, Xu D Y, et al. Prediction and analysis of agricultural machinery total power based on real-valued genetic algorithm and neural network[J]. Agricultural Mechanization Research, 2018, 40(7): 13-18. DOI:10.3969/j.issn.1003-188X.2018.07.003)