高维复杂函数优化在实际工程问题当中具有十分广泛的应用, 如大规模作业车间调度问题[1]、大规模电力系统无功优化[2]等.高维函数一般是指维数超过100维的函数, 具有非线性、高复杂度等特点, 且存在着大量的局部最优解.随着维数的不断增加, 问题的复杂度会呈指数级的速度增长[3], 因此求解起来十分困难.
目前, 针对高维函数的优化主要从两个方面来解决:一是通过降低问题的规模, 采用多种群并行算法进行寻优.徐东方等[4]提出了一种多种群子空间学习粒子群算法, 采用多种群进化模式加快了算法的收敛速度.拓守恒等[5]提出了一种并行差分进化算法, 利用种群中各维变量间的相关性进行维度划分, 从而实现降维.针对大规模非线性函数优化问题, 刘剑英[6]将协同进化的思想引入差分进化算法, 提出了一种基于GPU的协同差分进化算法.另外, 为了有效地对问题进行分解, Omidvar等[7]提出了一种自动分解的策略对大规模优化问题进行求解.虽然以上改进算法取得了一定的效果, 但是多种群并行算法会随着函数维度的增加, 对高维问题的求解精度有所下降.
在改进算法的研究方面, 通过改善算法的全局收敛性以提高算法对高维函数的寻优能力.针对粒子群算法求解高维函数容易早熟收敛的问题, 胡成玉等[8]提出了一种基于动态维度交叉的改进粒子群算法.另外, 田瑾[9]在分析量子行为粒子群优化算法QPSO机理的基础上, 对QPSO算法进行改进, 大大提高了粒子群算法的收敛速度和收敛精度.针对混合算法的研究, 王忠贵等[10]将模拟退火算法与几种经典算法相结合, 提出了一种针对高维复杂函数的混合模拟退火全局优化策略.于万霞等[11]将遗传算法和粒子群算法相结合, 提出了一种主从结构算法, 很好地发挥了算法的全局搜索和局部搜索的能力.以上改进算法在全局收敛性和求解精度方面还有待提高, 同时算法中参数的选择对其寻优性能有一定的影响.
灰狼优化算法(grey wolf optimizer, GWO)是Mirjalili等[12]提出的一种群体智能优化算法, 具有控制参数少、收敛速度快等优点.灰狼算法自提出以来, 不同学者对其进行了相关改进研究.例如, 利用佳点集策略[13]、混沌序列策略[14]生成初始种群, 控制参数的非线性调整[15]等. GWO算法虽然得到了许多改进, 但对于高维复杂函数问题的研究仍不多见.因此, 为解决高维复杂函数优化问题, 本文将选择、交叉、变异3种遗传算子与GWO算法相结合, 提出一种遗传-灰狼混合算法(hybrid genetic grey wolf algorithm, HGGWA).算法的主要改进策略如下:
1) 采用反向学习策略初始化种群, 利用基本灰狼算法平衡全局搜索和局部搜索;
2) 通过精英保留策略与赌轮盘相结合的方式对种群进行选择操作;
3) 基于降维和种群划分的方法, 将整个种群划分为多个子种群进行交叉操作, 以增加种群的多样性;
4) 对种群中的精英个体进行变异操作, 防止算法陷入局部最优.
经过测试, 改进算法具有较高的收敛精度, 能有效地解决高维函数优化问题.
1 遗传-灰狼混合算法 1.1 基本灰狼算法原理在GWO算法中, α狼的位置为最优解, β、δ狼的位置为次优解和第3优解, ω狼的位置是剩余的候选解.在狼群搜寻猎物的整个过程中, ω狼是追随α、β、δ狼的最佳位置情况, 逐步更新自己的位置, 以此来逐渐接近猎物, 即搜寻最优解的过程.灰狼的位置更新公式如下:
(1) |
(2) |
其中: t是迭代次数; A、C是系数向量, A是收敛因子, 用来平衡全局搜索和局部搜索, C是用来模拟自然界的影响作用; Xp是猎物位置向量, X是狼群位置向量.系数向量A和C按如下公式计算:
(3) |
(4) |
其中: r1、r2∈[0, 1]; a随着整个迭代过程的进行, 从2到0逐渐线性减少.如此, 根据式(1)和(2), 灰狼随机地在靠近猎物的空间内做出移动, 以逐渐接近最优解.
1.2 混合算法的改进策略 1.2.1 基于反向学习的初始化种群策略对于种群迭代的群智能优化算法而言, 初始化种群的多样性奠定了算法搜索效率的基础, 多样性较好的种群会减少算法的计算时间, 同时提高算法的全局收敛性[16].反向学习是由Tizhoosh[17]提出来的一种提高算法搜索效率的策略, 利用已知个体位置的对立点生成新的个体位置, 从而增加搜索种群的多样性.目前, 反向学习策略初始化种群已经成功地应用到多种群体智能优化算法中[18-19].反向点的定义如下:假设在种群P中存在个体X(x1, x2, ..., xD), 则每一维度上的元素xi(i=1, 2, ..., D)反向点的计算公式为
其中li和ui分别是第i维度的下界和上界.
根据上述定义, HGGWA算法采用反向学习策略初始化种群的步骤如下:
1)~随机初始化种群P, 计算每个个体位置xi的反向点x'i, 所有反向点构成反向种群P';
2)~计算初始种群P和反向种群P'中每个个体的适应度, 并按照降序进行排列;
3)~选取适应度最高的前N个灰狼个体作为最终的初始种群.
1.2.2 基于最佳保留的选择操作对于种群进化的智能优化算法而言, 每一代种群进化的优劣直接影响到算法的寻优效果.为了将父代种群中优良的个体遗传到下一代, 并且不遭到破坏, 需要将优良个体直接保存下来.最佳保留选择策略是遗传算法中保存优良个体的一种有效方式, 本文将其融入到GWO算法中, 以提高算法的求解效率.假设当前种群为P(X1, X2, ..., XD), 个体Xi的适应度为Fi, 具体的操作如下:
1)~计算个体的适应度值Fi(i=1, 2, ..., D), 并按照降序进行排列.
2)~选取适应度最高的个体直接复制到下一代种群中.
3)~计算剩余个体的适应度总和S, 以及每个个体被选取的概率pi, 即
(5) |
(6) |
4)~计算每个个体的累积适应度值si, 并按照赌轮盘的方式进行选择操作, 直到子代种群中的个体数目与父代种群保持一致.\vspace{-1pt}
(7) |
协同进化[20]是求解高维函数优化问题的一种策略, 此方法采用了“分而治之”的思想, 通过将高维优化问题划分为多个相互独立的低维子问题, 然后利用多个种群分别对子问题进行求解.在HGGWA算法中, 通过借鉴多种群协同进化的思想, 对应于高维优化问题的降维策略, 将整个种群P划分为υ×η个子种群Pi, j(i=1, 2, ..., υ, j=1, 2, ..., η), 分别对每个子种群的个体进行交叉操作.这种基于多种群降维的交叉操作很好地保持了种群的多样性, 使得HGGWA算法能有效地在解空间内搜索最优解.经过测试, 每个子种群Pi, j的最佳规模为5×5.具体的划分方法如下所示.
初始种群P为
(8) |
子种群Pi, j为
(9) |
在遗传算法中, 交叉操作具有十分重要的作用, 是产生新个体的主要方式.在本文的改进算法中, 采用线性交叉的方式对子种群中的每个个体进行交叉操作.即将子种群中的每个个体xi生成对应的随机数ri∈(0, 1), 当ri < 交叉概率Pc时, 将对应的个体xi两两配对进行交叉操作.示例如下.
Crossover (p1, p2):
1) 随机选择λ∈(0, 1).
2) 两个子代c1=(c11, ..., cD1), c2=(c12, ..., cD2)由父代p1=(p11, ..., pD1), p2=(p12, ..., pD2)生成, 公式为
(10) |
(11) |
由于HGGWA算法加入了最优保存策略的选择操作, 在算法的迭代后期, 整个种群中的灰狼个体都聚集在一个较小的最优区域内, 从而导致种群多样性的丧失.特别是在求解高维多峰函数时, 若当前最优个体为局部最优解, 则算法很容易陷入局部最优.为此, 本文在HGGWA算法中引入了变异算子对种群中的精英个体进行变异操作.具体操作如下.
假设最优个体为xi=(x1, x2, ..., xd), 以概率Pm对当前得到的最优个体进行变异操作, 即从最优个体中以概率Pm选择一个基因xk, 然后随机生成[l, u]范围之间的一个实数替代此基因, 从而生成一个新个体x'i=(x'1, x'2, ..., x'd).多样性变异算子为
(12) |
其中: λ是[0, 1]之间的随机数, l和u分别是个体xi的下界和上界.
综上所述, 本文所提出的HGGWA算法的基本流程如下.
step 1:初始化参数, 包括种群规模N, 最大迭代次数Maxiter, 交叉概率Pc, 变异概率Pm;
step 2:反向学习策略生成初始种群, 计算个体的适应度, 将前3个最优个体的位置依次保存为Xα、Xβ和Xδ;
step 3:根据式(1)和(2)更新灰狼位置信息, 更新参数a、A、C的值;
step 4:对灰狼种群进行选择、交叉、变异3种遗传操作, 从而得到下一代种群, 计算新种群中个体的适应度, 更新Xα、Xβ和Xδ;
step 5:重复step 3和step 4, 直到求得最优解或达到最大迭代次数, 算法终止.
2 HGGWA算法的全局收敛性分析在高维复杂优化问题中, 变量之间的支配关系为进化算法的求解过程提供了理论基础, 从进化算法收敛性的角度来说, 如果种群中变量之间的支配关系没有改变, 则算法会保持收敛的鲁棒性[21].对于某一求最大值的函数优化问题f(x), 假设sk*和sk+1*分别是第k代和第k+1代种群Sk和Sk+1中的最优个体, f(sk*)和f(sk+1*)为其相应的适应度.即存在∀ sk∈ Sk, 都有f(sk)≤ f(sk*), 这说明最优个体在整个种群中对其他个体存在支配关系.在HGGWA算法中, 基于最佳保留的选择操作维持了最优个体的支配地位, 即在下一代种群Sk+1中仍然存在f(sk+1)≤ f(sk+1*)的支配关系.随着遗传代数k的不断增加, 每代最优个体的适应度所组成的数列{f(s1*), f(s2*), ...}为单调不减数列.通过以下定理来证明HGGWA算法的全局收敛性.
定理1 假设问题f(x)的全局最优解为X*, 包含全局最优解X*的种群或状态的集合为E, HGGWA算法具有全局收敛性的充分条件为:在搜索过程中, HGGWA算法能发现全局最优解X*, 或经历包含全局最优值的状态E.
证明 根据最佳保留策略, 若HGGWA算法在第n代种群中发现最优解X*, 则个体之间的支配关系将一直保持下去, 该最优解将一直保留而不会丢失.即, 当进化代数k>n时, 会一直满足f(sk*)=f(X*)的关系, 则存在
为了测试本文所提出的HGGWA算法的性能, 首先选取文献[12]中的13个标准测试函数(30维)对比测试GWO和HGGWA两种算法的寻优性能, 以验证改进策略的有效性.另外, 为了进一步验证HGGWA算法求解高维复杂函数的能力, 选取10个高维测试函数进行寻优测试, 并将测试结果与PSO、GSA、GWO三种算法进行比较. 10个标准测试函数的具体特征见表 1所示.
为了更清晰地表达算法的寻优效果, 本文选取两个指标评价算法的性能[22].一是求解精度(accuracy, AC), 该指标反映了算法寻优的结果与理论最优值之间的差距.在一次实验中, 如果算法最终的收敛结果小于求解精度AC, 则认为此次寻优成功.假设某次寻优的最优值为Xopt, 理论最优值为Xmin, 则AC的计算方式如下:
(13) |
二是寻优成功率(successful ratio, SR), 该指标反映了算法在求解精度一定的条件下, 寻优成功的次数占总寻优次数的比重.假设在算法的T次迭代中, 寻优成功的次数为t次, 则SR的计算方式如下:
(14) |
为了保证比较结果的公平性, 几种算法均采用相同的参数设置, 其中种群规模N=50, 最大迭代次数Maxiter=1 000.另外, 在PSO中, c1=c2=2, ω=0.729 4;在GSA中, G0=100, β=20;在GWO中, 参数a的初始值为2; HGGWA中交叉概率Pc=0.8, 变异概率Pm=0.01.每种算法独立运行30次, 记录每种算法寻优的最优值、最差值、平均值以及标准差, 并计算寻优成功率.所有测试均在Intel Core I5-6300HQ、8 G内存、2.30 GHz的计算机上进行, 编写程序在Matlab 2017b上实现.
表 2给出了GWO、HGGWA两种算法对13个测试函数的寻优结果对比.通过分析得知, HGGWA算法在所有13个测试函数上均取得了比GWO算法更好的寻优结果.其中对于函数f1、f2、f3、f4、f10、f11的收敛精度大大提高, 特别是对于函数f9和f11, 算法的收敛结果达到了理论最优值0.仿真结果表明了HGGWA算法改进策略的有效性.
表 3给出了PSO、GSA、GWO以及HGGWA四种算法对表 1中10个高维测试函数, 分别在100维、500维、1 000维的情况下, 30次运行结果的平均值、标准差和寻优成功率SR的对比分析.
通过分析表 3可以得知, 对于大部分测试函数, HGGWA算法的收敛精度和寻优成功率明显高于其他3种算法.其中在100维的情况下, 除了函数f3, HGGWA算法对于其他9个测试函数的寻优成功率均达到了100 %.特别地, 对于函数f7和f9的寻优结果达到了理论最优值0.在500维的情况下, HGGWA算法对于函数f1、f2、f6~ f10的寻优成功率达到了100 %, 对于函数f7的寻优结果达到了理论最优值0.在1 000维的情况下, HGGWA算法对函数f1、f2、f7 ~ f10的寻优成功率达到100%.随着函数维度的增加, 几种算法的收敛精度均有所下降, 但HGGWA算法的寻优结果明显优于PSO、GSA、GWO三种算法, 且在标准差方面具有优势.总体而言, 在100维、500维和1 000维的测试函数上, HGGWA算法表现出比PSO、GSA、GWO三种算法更好的寻优效果, 验证了HGGWA算法求解高维复杂函数的有效性.
为了更清晰地比较4种算法的收敛性能, 将Sphere、Schwefel's 2.22、Rastrigin、Rosenbrock、Ackley、Griewank六种函数的适应度进化曲线图进行对比.从图 1可以很明显看出, 不管是求解单峰函数还是多峰函数, HGGWA算法都具有更快的收敛速度和更高的收敛精度.
为了进一步验证HGGWA算法中3种改进策略的有效性, 本小节对3种只加入某一种策略的改进算法与GWO和HGGWA算法进行寻优效果对比分析.其中, 分别只加入选择、交叉、变异操作的算法分别记作HGGWA-1、HGGWA-2、HGGWA-3. 10个测试函数以及算法的参数设置与上文相同, 每种算法独立运行30次.具体的测试结果见表 4.
由表 4可以得知, 除了函数f3, HGGWA算法比HGGWA-1、HGGWA-2、HGGWA-3三种算法获得了更好的全局最优解和标准差.特别地, 对于函数f7、f9, 3种改进策略对算法性能的改善作用十分明显.具体而言, 策略1和策略2对于函数f1、f2、f3、f7、f8、f9的改进效果显著, 大幅度提高了算法的收敛精度; 策略3对于函数f1、f2、f7、f8、f9的改进效果显著, 但是对于函数f3和f5却使得收敛结果变差, 这说明精英个体的变异操作对于求解函数f3和f5起了相反的效果.
3.4 与其他改进算法的比较分析为了进一步验证HGGWA算法的有效性, 将其与文献[23]中的9种改进算法进行寻优结果对比分析.这9种改进算法依次为: CLPSO、OLPSO、HPSO、SaDE、JADE、jDE、GABC、CABC、OCABC.在表 1中选取单峰函数f1、f2、f6和多峰函数f7、f8、f9, 在30维的情况下测试算法的性能, 9种改进算法的寻优结果直接来源于文献[23].具体的比较结果见表 5.
从表 5可以看出, 除了函数f8, HGGWA算法对其他5个测试函数均取得了最好的寻优结果.特别是对函数f7、f9, HGGWA算法的全局收敛结果达到了理论最优值0, 这体现了HGGWA强大的全局搜索能力, 验证了HGGWA算法求解高维复杂函数的优势.
4 结论针对灰狼优化算法求解高维复杂函数易陷入局部最优的缺点, 本文对基本灰狼优化算法进行了改进, 将3种遗传算子融入到算法中, 提出了一种遗传-灰狼混合算法(HGGWA).改进算法采用反向学习策略初始化种群, 为提高算法的搜索效率奠定了基础, 通过种群划分的方式降低了问题的规模, 针对精英个体的变异操作有效地防止了算法陷入局部最优值.通过对10个高维测试函数的仿真模拟, 与PSO、GSA和GWO三种基本算法的结果相比较, 可以看出HGGWA算法在收敛精度方面得到了极大改进, 验证了HGGWA算法求解高维函数的有效性.最后, 通过与9种改进算法的寻优结果相比较, 表明了HGGWA算法不管是求解单峰函数还是多峰函数, 都表现出比其他9种算法更好的全局收敛性.
[1] |
翟颖妮, 孙树栋, 杨宏安, 等. 大规模作业车间多瓶颈调度算法[J]. 计算机集成制造系统, 2011, 17(7): 1486-1494. (Zhai Y N, Sun S D, Yang H A, et al. Multi-bottleneck scheduling algorithm for large-scale job shop[J]. Computer Integrated Manufacturing Systems, 2011, 17(7): 1486-1494.) |
[2] |
尚文洁, 吉兴全, 郑耀东, 等. 大规模电力系统无功优化的一种分解协调算法[J]. 华北电力大学学报:自然科学版, 2011, 38(6): 17-22. (Shang W J, Ji X Q, Zheng Y D, et al. A decomposition and coordination algorithm for reactive power optimization in large-scale power systems[J]. Journal of North China Electric Power University: Natural Science Edition, 2011, 38(6): 17-22.) |
[3] |
Rahnamayan S, Wang G G. Solving large scale optimization problems by opposition-based differential evolution (ODE)[J]. WSEAS Transactions on Computers, 2008, 7(10): 1792-1804. |
[4] |
徐东方, 郭战伟. 求解高维复合体函数的智能优化算法[J]. 数学的实践与认识, 2016, 46(19): 205-211. (Xu D F, Guo Z W. Intelligent optimization algorithm for high-dimensional and complex functions[J]. Mathematics in Practice and Theory, 2016, 46(19): 205-211.) |
[5] |
拓守恒, 周涛. 基于维度分组交叉的自适应差分进化算法[J]. 计算机工程与设计, 2011, 32(9): 3174-3177. (Tuo S H, Zhou T. Self-adaptive differential evolution algorithm based on dimensionality group cross[J]. Computer Engineering and Design, 2011, 32(9): 3174-3177.) |
[6] |
刘剑英. 基于GPU的并行协同差分进化算法研究[J]. 计算机工程与应用, 2012, 48(7): 48-50. (Liu J Y. Research of parallel cooperation differential evolution algorithm based on GPU[J]. Computer Engineering and Applications, 2012, 48(7): 48-50. DOI:10.3778/j.issn.1002-8331.2012.07.012) |
[7] |
Omidvar M N, Li X D, Mei Y, et al. Cooperative co-evolution with differential grouping for large scale optimization[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(3): 378-393. DOI:10.1109/TEVC.2013.2281543 |
[8] |
胡成玉, 王博. 基于动态维度交叉的粒子群高维函数优化[J]. 计算技术与自动化, 2009, 28(1): 92-95. (Hu C Y, Wang B. Particle swarm optimization with dynamic dimension crossover for high dimensional problems[J]. Computing Technology and Automation, 2009, 28(1): 92-95. DOI:10.3969/j.issn.1003-6199.2009.01.024) |
[9] |
田瑾. 高维多峰函数的量子行为粒子群优化算法改进研究[J]. 控制与决策, 2016, 31(11): 1967-1972. (Tian J. Improvement of quantum-behaved particle swarm optimization algorithm for high-dimensional and multi-modal functions[J]. Control and Decision, 2016, 31(11): 1967-1972.) |
[10] |
王忠贵, 罗亚中. 高维复杂函数的混合模拟退火全局优化策略[J]. 计算机工程与应用, 2004, 40(23): 36-39. (Wang Z G, Luo Y Z. SA-based hybrid global optimization approach for complex functions with high-dimension[J]. Computer Engineering and Applications, 2004, 40(23): 36-39. DOI:10.3321/j.issn:1002-8331.2004.23.012) |
[11] |
于万霞, 张维存, 郑宏兴. 基于遗传粒子群算法的高维复杂函数优化方法[J]. 计算机工程与应用, 2007, 43(36): 31-33. (Yu W X, Zhang W C, Zheng H X. Genetic and particle swarm algorithm-based optimization solution for high-dimension complex functions[J]. Computer Engineering and Applications, 2007, 43(36): 31-33. DOI:10.3321/j.issn:1002-8331.2007.36.011) |
[12] |
Mirjalili S, Mirjalili S M, Lewis A. Grey wolf optimizer[J]. Advances in Engineering Software, 2014, 69(3): 46-61. |
[13] |
龙文, 伍铁斌. 协调探索和开发能力的改进灰狼优化算法[J]. 控制与决策, 2017, 32(10): 1749-1757. (Long W, Wu T B. Improved grey wolf optimization algorithm coordinating the ability of exploration and exploitation[J]. Control and Decision, 2017, 32(10): 1749-1757.) |
[14] |
龙文, 蔡绍洪, 焦建军, 等. 求解高维优化问题的混合灰狼优化算法[J]. 控制与决策, 2016, 31(11): 1991-1997. (Long W, Cai S H, Jiao J J, et al. Hybrid grey wolf optimization algorithm for high-dimensional optimization[J]. Control and Decision, 2016, 31(11): 1991-1997.) |
[15] |
Rodríguez L, Castillo O, Soria J. Grey wolf optimizer with dynamic adaptation of parameters using fuzzy logic[C]. Evolutionary Computation. IEEE, 2016: 3116-3123.
|
[16] |
Anderson-Cook R B C M. Practical genetic algorithms[J]. Journal of the American Statistical Association, 2005, 100(471): 1099. |
[17] |
Tizhoosh H R. Opposition-based learning: A new scheme for machine intelligence[C]. International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce (CIMCA-IAWTIC'06). Vienna: IEEE, 2005: 695-701.
|
[18] |
夏学文, 刘经南, 高柯夫, 等. 具备反向学习和局部学习能力的粒子群算法[J]. 计算机学报, 2015(7): 1397-1407. (Xia X W, Liu J N, Gao K F, et al. Particle swarm iptimization algorithm with reverse-learning and local-learning behavior[J]. Chinese Journal of Computers, 2015(7): 1397-1407.) |
[19] |
汪慎文, 丁立新, 谢承旺, 等. 应用精英反向学习策略的混合差分演化算法[J]. 武汉大学学报:理学版, 2013, 59(2): 111-116. (Wang S W, Ding L X, Xie C W, et al. A hybrid differential evolution with elite opposition-based learning[J]. Journal of Wuhan University: Natural Science Edition, 2013, 59(2): 111-116.) |
[20] |
Potter M A, Jong K A D. A cooperative coevolutionary approach to function optimization[C]. International Conference on Parallel Problem Solving from Nature. Berlin: Springer, 1994: 249-257.
|
[21] |
Hao G S, Lim M H, Ong Y S, et al. Domination landscape in evolutionary algorithms and its applications[J]. Soft Computing, 2018(4): 1-8. |
[22] |
Engelbrecht A P. Fundamentals of computational swarm intelligence[M]. New York: John Wiley & Sons, 2006: 35-36.
|
[23] |
Gao W F, Liu S Y, Huang L L. A novel artificial bee colony algorithm based on modified search equation and orthogonal learning[J]. IEEE Transactions on Cybernetics, 2013, 43(3): 1011-1024. DOI:10.1109/TSMCB.2012.2222373 |