基于遗传算法的精英反向群优化算法解决大规模优化问题

认知机器人2（2022）112基于遗传算法的精英反向群算法求解大规模优化问题李章，于坦桂林电子科技大学图像与图形智能处理广西重点实验室，广西桂林541004aRT i cL e i nf o保留字：大规模优化传播学习精英反向学习粒子群算法a b sTR a cT针对传统粒子群优化算法（PSO）在复杂问题空间搜索效率低下的问题，提出了一种新的基于扩散的精英反向群优化算法（SEOSO）。灵感来自自然界中的种子，种子可以随风随机传播，为下一代生长得更好。为了实现这一点，在SEOSO中引入了扩散学习和精英对立学习。在扩散学习中，粒子被划分为若干个子群，这些子群之间可以相互交换粒子以获得更多有用的信息，从而提高了种群的多样性。在精英反向学习中，粒子的相反位置用于排除更差的方向。在35个基准函数上进行了实验，与几种最先进的算法进行比较，以评估SEOSO的性能。比较结果表明了SEOSO算法在求解大规模优化问题中的有效性1. 介绍在大多数现实世界中，需要处理大量的决策变量，称为大规模优化（LSO）问题。由于其广泛的应用，激光振荡器在许多研究领域得到了广泛的应用。维数灾难是大多数优化算法中的一个主要问题。因此，开发新的方法来简化给定的大规模优化问题是非常重要的[1]。有许多方法已经从两个角度发展：合作的共同进化算法（CCEAs）[2]，和经典PSO的新的更新策略1.1. 相关作品1.1.1. 协同进化算法合作协同进化（CC）是Potter和De Jong提出的。这是一种LSO的分解方法[4]。使用这种技术提高性能的关键是将整个优化问题细分为更容易处理的较小问题[1]。Vanden Bergh和Engelbrecht首先尝试将CC模型应用于粒子群优化[5]。提出了一种基于有效变量分组技术的协同进化粒子群优化算法（CCPSO 2）。2014年，Li et al.[6]采用离散分组协同进化（CCDG）来自动分解决策变量。之后，提出了差异分组（DG2）来寻找可靠的阈值[7]。1.1.2. 经典粒子群优化算法为了解决大规模优化问题，许多研究者致力于发展各种经典进化算法的更新策略。1995年，Kennedy和Eberhart提出了用于解决优化问题的PSO[8]。2006年，梁提出了一个*通讯作者。电子邮件地址：tanyu1997@126.com（Y. Tan）。https://doi.org/10.1016/j.cogr.2022.03.005收稿日期：2021年11月8日;接受日期：2022年3月26日2022年4月2日在线发布2667-2413/© 2022作者。Elsevier B. V.代表KeAi Communications Co. Ltd.提供的出版服务。这是CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）可在ScienceDirect上获得目录列表认知机器人期刊首页：http://www.keaipublishing.com/en/journals/cognitive-robotics/L. Zhang和Y.谭认知机器人2（2022）112113综合学习粒子群全局优化算法（CLPSO）。在[10]中，提出了一种将种群划分为子种群的方法，称为动态多种群粒子群优化（DMS-PSO）。Ran Cheng已经表明，具有社会学习机制的PSO（SLPSO）具有解决LSO问题的潜力[11]。2015年，提出了一种粒子从获胜者学习的成对竞争机制[12]。为了解决大规模优化问题，杨et al.[13]在2017年提出了一种基于层次的学习群优化器（LLSO），LLSO根据拟合值将群划分为多个层次，粒子的处理根据其层次而变化。虽然这些算法都表现出很高的优化性，但大多数算法存在早熟收敛和局部最优等问题1.2. 我们的贡献这项工作的目的是提出一种新的优化器，以提高性能的粒子群算法解决大规模问题。在所提出的SEOSO中，扩散学习和精英反向学习是两个重要的部分。SEOSO的主要贡献如下：• 我们提出了一种新的策略命名为传播学习。这些粒子是连续分布的不同的子群。它提供了通过不断变化的子群进行探索的能力，从而使SEOSO比现有方法具有更好的群多样性。由于它充分利用了搜索信息，粒子更有可能达到全局最优状态。• 我们使用精英对立学习来构造一个有希望的学习样本，而不是���������������粒子的位置和它的相对位置是粒子最佳位置值的两种选择。通过这种方式，我们可以构建样本来引导粒子更平滑地运动而不是振荡。• 在由测试函数组成的基准上，通过理论分析和客观的实验评价，研究了SEOSO的性能严格的实验数据比较表明，所提出的SEOSO显着优于国家的最先进的方法。本文的结构安排如下。第二节简要介绍了粒子群算法的基本框架、基于反对的学习方法以及近年来改进粒子群算法的研究进展。在第3节中，我们详细介绍了拟议的SEOSO。实验结果在第4中给出。关于SEOSO的结论最后在第5中介绍。2. 预赛2.1. 问题描述不失一般性，我们将本文的最小化问题定义如下：min（），= [1，2，������������其中 （k）表示拟合值，并且���是搜索空间的对应维度。随着的增加 ，优化[6]非常困难，因为多模态问题非常容易陷入局部最优，搜索空间呈指数增长。2.2. 粒子群算法中的多样性保持方法粒子群优化算法（PSO）已经证明在复杂和困难的优化问题上取得了很大的进展[14]。是这是一个基于社会动物群体行为研究的框架，肯尼迪和埃伯哈特于1995年首次提出。粒子群算法有两个非常有利的特点：效率和简单，许多工作都报道了保持其最佳性能的问题。有非常大量的粒子群算法变体，但它们可以简单地分为以下四类。第一类是混合PSO算法，它将其他特定的搜索算子和策略纳入PSO[15]。第二类是多群PSO。它在不同的群体之间交换信息，以提高群体多样性[16]。第三类是在粒子群算法中加入控制参数的策略。PSO中新的拓扑结构，可以分为第四类，例如，环拓扑、树拓扑和星型拓扑[11]。2.3. 反向学习基于对立的学习（OBL）是由Tizhoosh[17]提出的一种有效的优化方法。通过比较一个人和其相应的同龄人的适合性，然后保留更适合的一个，在总体中，OBL获得给定问题的最优解[18]。一个自然的事实是，从一个随机的初始值开始将远离现有的解决方案，但 相 反 的 方 向 可 能 是 有 益 的 。 因 此 ， 在 初 始 化 阶 段 ， 在 给 出 解 的 随 机 猜 测 的 同 时 ， 也 要 认 真 考 虑 解 的 反 例 。���[���1][2][3][4���][5][6][7][8][9] 相反的数字“”定义为：������ =���+��� − (2)L. Zhang和Y.谭认知机器人2（2022）112114，，，，，，图1.一、 传播学习的概述。在每一代中，不同子群中的粒子随机传播到其他太阳群。3. 该方法本节详细介绍了一种新的算法--精英反向传播群优化算法。设计了扩散学习和精英反向学习两种算子来分配种群资源和更新粒子。3.1. SEOSO的动机在经典粒子群算法中，为了更新粒子的速度和位置，所有粒子都从各自的最佳位置和全局解中学习。一方面，粒子在不断更新，需要从善和对中学习。如果这两个例子是在两个方面的，他们可能会振荡。另一方面，当和同时处于局部最优状态时，粒子会陷入局部最优������������������������������，导致粒子过早收敛。同时，增加维数的大小将使处理优化问题更加困难。应该提出一个好的优化器来克服这些缺点。在本文中，我们使用传播学习和精英相反的学习在整个群体。为了避免过早收敛，一个群中的粒子被分成两个子群。每个子群分别更新粒子。将同一子群中的粒子随机分为两组。采用竞争机制在当前子群中进行群体进化。优胜者组将通过精英反向学习进行更新，从而提高了搜索效率。然后通过扩散学习实现子群之间的信息交换。由于多样性的提高，它在解决高维问题上表现良好。3.2. SEOSO的推导3.2.1. 传播学习灵感来自于成熟的蒲公英种子，它可以被风随机传播到其他地方。当风停止时，种子会落下并在新的环境中生长。我们提出了一种新的学习称为扩散学习，和SEOSO是由经典的PSO的动机。在第一阶段，我们随机初始化群位置，其中，n是生成索引。������图1中的扩散学习展示了扩散学习的主要思想。首先，群被分解为具有相同数量粒子的子群。在本文中，将λ设定为5。每个子群都独立进化。此外，为了提高整个群体的多样性，我们使信息在子群体之间传播。每隔20代，子群中的一些粒子随机扩散到其他子群中，除了表现不好的子群，它具有更差的拟合性。具有较好拟合性的有希望的子群将随机选择粒子到表现较差的子群。当一个子群接收到传播粒子时，该粒子被替换为子群中的一个粒子。该过程将提高算法的多样性。3.2.2. 精英反向学习在本小节中，我们深入了解子群的粒子是如何更新的。首先，我们将子群分成两个大小相等的组，并根据拟合值将不同组中包含的粒子相互比较。具有更好拟合值的粒子，即获胜者，将被放置在获胜者组中。在竞争中失败的粒子称为失败者，将被CSO等胜利者更新失败者的粒子数的更新方程定义如下[19]：������,���(���+1)=���1(���)��� ������,���(���)+���2(���)(���������,���(���) − ���,��� ( )���)+������3(���)( ������ ()−������,���( ))(3), ( + 1) =, ( ) +, ( + 1)(4)，，，式中，������，（）表示失败粒子在第n个子群和第 n代中的第 n维速度（∈{1，2，.}），（∈������{1，2，������������������,���(���)and������,���(���) are the behavior vector but the superscript��� and你，你，你L. Zhang和Y.谭认知机器人2（2022）11211512分别代表赢家和输家。（ ）是第一维中粒子的平均行为向量 。 是从范围[0，1]生成的控制参数。 1（ ）、 2（ ）和 3（ ）是在生成中独立生成的向量的随机值 。获胜者的粒子将通过精英对立方法进行更新������（ 设���=（���1，2���，������ ...，）为维空间中获胜群的粒子. ������（���′，���′，���...，′）是精英反对派的立场 。我们比较适合性value���（���）with���（������），如果���（������）优于���（���），���则替换为。提高了整个搜索的效率空间基于维数的方法用于更新不同维数中每个粒子的位置采用了相反的方法���������,���=min+ max−������,���（五）你，你，你其中���，���是，在子群中的相对位置 ������，min表示第n维的最小适合度值 ，max是第n维的max���i，���������m，���ension的最大适合度值。我们随机地将粒子分成几个子群。每个子群通过使用精英相反学习来更新其粒子。它通过引导粒子更好地向相反方向运动，提高了SEOSO的开采能力。然后，传播学习为下一代更新子群，这增强了多样性。来自不同子群的粒子具有不同的探测和发展能力。因此，SEOSO提出的这些改进可以在简化LSO问题方面发挥关键作用SEOSO的主要思想在算法1中描述。算法1SEOSO的伪代码。终止条件是最大适合性评估数���������max，群大小���1随机初始化粒子和粒子，并计算粒子 的适合度值; 2粒子=0，粒子适合度=0;3.当不满足最大群密度时，4 ~将群划分为4个子群;���������<���������5 ~，适用于1：1：15 ~~每个子群随机分为两组; 6 ~~每个子群识别赢家和输家;7 ~~通过等式更新失败粒子。(3)和等式(4); 8 ~获胜者由等式更新。（5）;9 ~~~~~~~计算拟合度值; 5 ~~~~~~结束10 ~~交换各子群的信息，11~~使计算出的拟合值等于n（n+1），13 ~~n+ = 1;14 ~~+=15结束时，3.3. 方法分析SEOSO的主要特点是基于传播学习和精英相对学习的方式一方面，在SL-PSO和LLSO中，群中的粒子首先按适合度值的升序排列。在SEOSO中，不需要对颗粒进行分类。相反，种群被分成几个亚群。子群通过随机的粒子交换降低了种群多样性丧失的风险因此，SEOSO比这两个优化器具有更高的多样性和更低的概率获得局部最优状态另一方面，在SEOSO的每个子群中，粒子以两种不同的方式更新：一种是失败者被胜利者更新;另一种是胜利者也需要通过计算自己的相反值来更新，粒子通过向相反方向学习来增加利用率。大多数PSO依赖于粒子群算法或粒子群算法进行学习，但SEOSO中的粒子可以使用当前群体中的精英粒子来完成学习。此外，与CSO只采用优胜者对粒子学习过程进行简单的引导而忽略优胜者的更新不同，SEOSO采用两种不同的方式直接更新失败者和优胜者来引导粒子的学习过程，导致SEOSO存在探索与发展的折中.4. 实验4.1. 实验环境在实验过程中，我们在两个广泛使用的集合上执行了一组35个基准函数，即CEC��� ��� CECL. Zhang和Y.谭认知机器人2（2022）112116表1SEOSO，LLSO[13]，SL-PSO[11]，CSO[12]，DECC-DG[20]，DMS-L-PSO[10]，MLCC[21]在CEC'10上的优化错误基本功能（1000-D）。为了验证SEOSO算法的有效性和先进性，我们在高维（1000维）上进行了测试，测试函数具有相应的维数并且���是其维数的大小。除特别说明外，所有实验数据的统计结果均为每30个独立实验数据的平均值。将每次独立运行的最大拟合度值评价设定为3000×λ = 3.0 × 106。为了评估两种算法之间的差异，我们在= 0的显著性水平下采用Wilco X秩和检验���。05. ������在表的底部的搜索引擎优化闪烁显示了在搜索引擎优化功能上的胜利，在搜索引擎优化功能 上的平局，以及在搜索引擎优化功能上的损失。4.2. 高维函数为了进一步验证SEOSO的有效性，我们对SEOSO和以下六种最先进的方法进行了客观的实验评估：基于层次的学习群优化（LLSO），社会学习粒子群优化（SL-PSO）[11]，竞争群优化（CSO）[12]，多级合作与协同进化（MLCC）[21]，协同进化与差异化分组（DECC）[6]，使用局部搜索的动态多群粒子群优化（DMS-L-PSO）[10]。表1和表2详细示出了CEC'10和CEC'13的实验结果。对于每个函数，第一、第二和第三行分别表示平均值、标准差和最大值，其中粗体表示最佳结果。L. Zhang和Y.谭认知机器人2（2022）112117表2SEOSO，LLSO[13]，SL-PSO[11]，CSO[12]，DECC-DG[20]，DMS-L-PSO[10]，MLCC[21]对CEC'13基本函数（1000-D）的优化错误表1显示SEOSO在大多数功能中表现最好它取得了良好的性能，在20个功能中有12个功能表现最好，这表明了SEOSO的优势具体地说，SEOSO算法与LLSO算法、SL-PSO算法、CSO算法和DMA-L-PSO算法相比，分别在1988年、 1991年、 1995年和1998年表现出了很大的优势并且它只会使其他算法的 101、 104、 106和 107函数为���8、应强调探索的多模态功能。SEOSO显然比LLSO、CSO、MLCC和DECC-DG收敛得更快。相反，MLCC表现出较慢的收敛速度。12是单峰不可分函数，CSO和SL-PSO的拟合度较差，说明它们的开发能力较差。相比之下，DECC-DG方法优于其他方法，���十六岁其出色的性能来自于16号的迪赛进化变体 。另外， 16是移位功能。但它在���2012年表现不佳。为了验证SEOSO算法的有效性和可扩展性，我们分别在具有更高难度和更复杂函数的CEC10和CEC13标准集上进行了实验.SEOSO在15项功能中的11项上取得了优势与CEC'10相比这证明了SEOSO更适合处理复杂问题。如表2所示，SEOSO在LLSO、CSO、DMS-L-PSO和MLCC中具有最好的能力，特别是在可分离功能���1414和���1411以及不可分离功能���1414和���1515中。尽管它比LLSO和SL-PSO慢，但它仍然比许多其他PSO快���2002年，在SEOSO，开采略有偏差，没有严重的勘探损失，导致良好的性能。此外，在���2012年和���2013年与其他比较方法的实验评估表明，SEOSO有两个明显的优势，即更好的拟合值和更快的收敛速度。客观的实验结果表明，所提出的SEOSO优于传统的PSO和大多数现有的变种的改进PSO或CC框架测试基准函数，根据收敛速度，解决方案的准确性，和算法的稳定性。SEOSO不仅提供了粒子搜索空间的能力，而且还提供了更好的性能。SEOSO的优势L. Zhang和Y.谭认知机器人2（2022）112118可以归因于传播学习和精英对立学习，它们可以从搜索经验中发现、保存和利用有用的信息。5. 结论为了解决大规模优化问题，本文提出了一种新的优化算法SEOSO。在SEOSO算法中，设计了一个扩散学习和精英反向学习机制来探索和利用子群和粒子群中的有用信息。扩散学习有助于子群进行更有希望的多样性，以防止局部最优。精英反向学习有效地引导粒子，调整粒子的运动速度和方向，缓解“振荡”现象。对CEC'10和CEC'13进行了包括各种功能在内的综合实验测试从客观和严格的实验结果，我们提出的SEOSO方法取得了更好的性能比比较算法。竞争利益提交人声明，他没有已知的竞争性经济利益或个人关系，可能会出现在本文报告的工作中。引用[1] L. Zhang， Y. Zhu，S.忠河，巴西-地兰，X. Luo，用于大规模优化的多级竞争群优化器，在：智能计算和大数据服务安全国际会议上，Springer，2018年，pp.185-197.[2] X. Li，X.姚，协同进化粒子群大规模优化，IEEE Trans.评价Comput. 16（2）（2012）210-224。[3] Y.-- F. Ge，W.-余杰，Y.林，Y.- J. Gong，Z.- H. Zhan，W.- N. Chen，J. Zhang，基于自适应合并和分裂的分布式进化算法在大规模优化中的应用，IEEE Trans. 赛博恩48（7）（2017）2166[4] Y.朱湖，加-地张河，巴西-地兰，X. Luo，使用合作协同进化和竞争策略的大规模部分可分离函数优化，在：2019年第十一届高级计算智能国际会议（ICACI），IEEE，2019年，pp. 144比148[5] F. Van den Bergh，A.P.杨文，粒子群优化算法的一种新方法。评价Comput. 8（3）（2004）225-239。[6] M.N.奥米德瓦尔角Li，Y.梅，X。Yao，大规模优化中的协同进化与差异化分组，IEEE Trans.Evol. Comput. 18（3）（2014）378-393。[7] M.N.奥米德瓦尔湾Yang，Y.梅，X。Li，X. Yao，DG 2：a faster and more accurate difficulty grouping for large-scale black-boX optimization，IEEE Trans. Evol.Comput. 21（6）（2017）929[8] R. Eberhart，J.Kennedy，A new optimizer using particle swarm theory，in：Proc.第六届国际微机械与人体科学研讨会MHS'95.，IEEE，1995，pp. 39比43[9] J.J. Liang，A.K. Qin，P.N. Suganthan，S.李晓生，基于粒子群算法的多峰函数全局优化，北京大学学报，2001。Comput. 10（3）（2006）281-295。[10] J. - J. Liang，P.N. Suganthan，带局部搜索的动态多群粒子群优化器，在：Proc.IEEE Congress on Evolutionary Computation，vol.1，IEEE，2005，pp. 522-528[11]R. 郑，Y.Jin，一种用于可扩展优化的社会学习粒子群优化算法，Inf.Sci. 291（2015）43-60。[12] R. 郑，Y.Jin，A Competitive Swarm Optimization for Large Scale Optimization，IEEE Trans.赛博恩 45（2）（2015）191-204。[13] Q.杨文N.作者：Chen，J. Li，T.顾军，张军，一种基于层次学习的群优化算法及其在大规模优化中的应用，IEEE Trans. Evol. Comput. 22（4）（2017）578-594。[14] B. Jiang，N.Wang，X.李，带老化算子的粒子群优化算法用于多峰函数优化，国际。J. Comput. 内特尔系统 6（5）（2013）862-880。[15] S.- T. Hsieh，T. Y.孙角，澳-地C.刘氏J.Tsai，Solving large scale global optimization using improved particle swarm optimization，in：Proc. IEEE Congress onEvolutionary Computation，2008，pp. 1777-1784年。[16] S. Das，P.N.Suganthan，Di Escherichia演化：对最先进技术的调查，IEEE Trans.评价Comput. 15（1）（2011）4-31。[17] H.R. Tizhoosh，基于对立的学习：机器智能的新方案，在：建模、控制和自动化计算智能国际会议和智能代理、网络技术和互联网商务国际会议（CIMCA-IAWTIC'06），第1卷，IEEE，2005年，pp. 695-701[18] M.A. Ahandani，H.Alavi-Rad，基于反对的学习在shuanged离散进化算法中，Soft Comput。 16（8）（2012）1303-1337。[19] R. 兰湖，澳-地Zhang，Z.唐，Z.Liu，X.Luo，A hierarchical sorting swarm optimizer for large-scale optimization，IEEE Access 7（2019）40625-40635。[20] S.- T. Hsieh，T. Y.孙角，澳-地C.刘氏蔡志华，粒子群优化算法的有效种群利用策略，IEEE Trans.Syst.，伙计，赛博，B部分（Cyber-netics）39（2）（2009）444-456.[21] Z. Yang，K.唐，X.Yao，Multicooperative coevolution for large scale optimization，Proc.IEEE Congress on Evolutionary Computation，2008，pp. 1663-1670年。[22] K.唐，X. Li，P.N. Suganthan，Z. Yang，T. Weise，CEC 2010特别会议和大规模全局优化竞赛的基准函数：自然启发计算与应用实验室，中国科学技术大学，应用实验室，大学科学院中国，合肥，中国，技术Rep（2009）.[23] X. Li，K.Tang，M.N.奥米德瓦尔湾Yang，K.Qin，H.中国，CEC 2013年特别会议和大规模全局优化竞赛的基准函数，Gene 7（33）（2013）8。