基于局部搜索变异的重启动差分进化算法的研究及其性能优化

埃及信息学杂志（2014年）15，175开罗大学埃及信息学杂志www.elsevier.com/locate/eijwww.sciencedirect.com原创文章RDEL：一种基于局部搜索变异的重启动差分进化算法Ali Wagdy Mohamed*阿卜杜勒阿齐兹国王大学科学系统计系，邮政编码：Box 80203，Jeddah 21589，Saudi Arabia Operations ResearchDepartment，Institute of Statistical Studies and Research，Cairo University，Giza，Egypt接收日期：2013年10月8日;修订日期：2014年6月24日;接受日期：2014年2014年8月24日在线发布摘要提出了一种基于局部搜索变异和重新启动机制的差分进化算法，用于求解连续空间上的全局数值优化问题。该算法被命名为重启差分进化算法与局部搜索变异（RDEL）。在RDEL中，受粒子群优化算法（PSO）的启发，引入了一种新的局部变异规则，该规则基于特定世代整个种群中最好和最差个体的位置。新的局部变异方案通过线性递减函数与基本变异规则相结合。提出的局部变异策略增强了基本差分进化算法的局部搜索能力，加快了收敛速度。此外，重新启动机制的基础上的随机变异计划和改进的育种遗传算法（BGA）的变异计划相结合，以避免停滞和/或过早收敛。此外，指数增加的交叉概率规则和DE的统一比例因子的引入，以提高人口的多样性和改善搜索过程中，分别。RDEL的性能进行了研究，并与基本的差分进化，和国家的最先进的参数自适应差分进化的变种。结果发现，所提出的修改显着提高DE的性能方面的解决方案，效率和鲁棒性的质量。©2014制作和主办由Elsevier B.V.代表计算机与信息学院开罗大学。* 地 址 ： P.O. 阿 卜 杜勒 阿 齐 兹国 王 大 学科 学 系 统计 系 。 Box80203，Jeddah 21589，Saudi Arabia联系电话：+966 556269723。电子邮件地址：aliwagdy@gmail.com开罗大学计算机和信息系负责同行审查。1. 介绍差分进化算法（Differential Evolution，DE）是由Storn和Price提出的一种基于种群的随机搜索算法。它在解决来自多个领域和许多现实世界应用问题的具有不同特征的广泛优化问题方面表现出出色的能力[3]。与所有其他进化算法（EA）类似，1110-8665© 2014由Elsevier B. V.代表开罗大学计算机与信息学院制作和主办。http://dx.doi.org/10.1016/j.eij.2014.07.001制作和主办：Elsevier关键词进化计算;差分进化;局部搜索变异;重启机制;全局数值优化176A.W. 穆罕默德我8 ¼我IJ我R2！R3IJDE在每一代使用变异、交叉和选择算子来达到全局最优。差分进化算法的性能主要取决于变异策略和交叉算子。此外，算法的内部控制参数（种群规模NP、比例因子F、交叉率Cr）在平衡种群多样性和算法收敛速度方面起着至关重要的作用。优点是实现简单，可靠，速度和鲁棒性[3]。然而，DE与其他进化搜索技术一样，也有许多弱点。一般而言，差分进化算法具有很好的全局搜索能力，可以到达全局最优解，但速度较慢解决方案[4]。此外，DE的参数是问题相关的，并且很难针对不同的问题调整它们。此外，DE性能随着搜索空间维度的增加而降低[5]。最后，当出现过早收敛和/或停滞问题时，DE的性能显著恶化[5，6]。因此，研究人员提出了许多技术来提高基本DE。从文献[7]中可以看出，这些对DE的修改、改进和发展集中在以自适应或自适应的方式调整控制参数，而在开发新的突变规则方面也有一些尝试。为了克服DE的这些缺点，本 文 提 出 了 一 种新 的 局 部 搜 索 变 异 的 重 启 DE ， 简 称RDEL，用于全局数值优化。因此，本文借鉴DE中的粒子群优化算法（PSO），提出了一种新的局部变异策略，以增强局部利用倾向，提高算法的收敛速度。事实上，在全局PSO中，每个粒子都从个人最佳位置其中f是目标函数，~x是由变量组成的决策向量，a j和b j分别是每个决策变量的上界和下界。在简单DE中，通常称为DE/rand/1/bin[1，9]，一个初始随机人口组成的NP向量X！i;i1;2;.. . ;N P，是在边界内生成的。这些个体通过DE算子（变异和交叉）进化以生成试验向量。然后进行亲本和其试验载体之间的比较，以选择应该存活到下一代的载体[9]。DE步骤讨论如下：2.1. 初始化为了建立优化过程的起点，必须创建初始种群。通常，初始种群的每个向量中的每个决策参数都被分配一个从边界约束中随机选择的值：x0¼ajrandj·bj-aj 2其中randj表示[0，1]之间的均匀分布的数，从而为每个决策参数生成新值2.2. 突变在G代，对于每个靶载体xG，突变载体根据以下公式vG 1：vG1½xGFωxG-xG;r1i r1也是迄今为止全体居民所取得的最好成绩r2r3类似地，所提出的新变异的主要思想是基于每个向量从最佳位置学习最坏的人在整个人口的一个利用随机选择的索引r1，r2，r3 e {1，2，.. . ，NP}。F是实数来控制差分向量的放大。根据Storn和Price[2]，特别的一代。此外，指数增加的交叉概率规则和DE的统一比例因子的引入，以提高人口的多样性和改善搜索过程中，分别。此外，该算法还结合了基于随机变异策略的重启机制和改进的育种遗传算法（BGA）变异策略，以避免停滞和过早收敛。本文对14个著名的高维基准函数进行了大 量 的 数 值 实 验 和 比 较 ， 结 果 表 明 ， 所 提 出 的 算 法（RDEL）优于传统的算法。在[0，2]中如果突变向量的一个分量违反了搜索空间，则该分量的值被生成新的使用（2）或新的其他修复方法。2.3. 交叉有两种主要的交叉类型，二项式和指数。在二项式交叉中，使用以下方案将目标向量与突变向量混合，以产生试验向量uG 1。（vG101;兰特106CR 或jrandni;IJ微分方程和几种最先进的参数自适应特别是在高维com的情况丛优化问题论文的其余部分是有组织的uG1.5IJð4Þ如下 在第2节中，介绍了标准DE算法。介绍了它的运营商和参数的审查。接下来，在第3节中，介绍了所提出的算法第4其中j=1，2，.. . ，D，rand（j）e [0，1]是a的第j次求值均匀随机生成器编号。CRe [0，1]是交叉rate，randn（i）e {1，2，.. . ，D}是随机选择的索引，其确保uG 1从vG 1获得至少一个元素;否则测试基准函数的计算结果和ii与其他技术的比较报告，并讨论了建议的修改的有效性。最后，在第5节中得出结论和未来的工作2. 差分进化首先，有界约束全局优化问题可以定义如下[8]：最小值f~x;~x¼½x1;x2;.. . ;xD]; S：t：xj2½aj;bj];8j1;2;.. . ;Dð1Þ不会产生新的亲本载体，不会改变。在指数交叉中，在范围{1，D}内随机选择整数值l。这个整数值充当~xj;G 中的 起始点，从这里交叉或交换的组件！Vi;G1开始。另一个整数值L（表示分量的数量）也选自区间{1，D-1}。 试验向量（~ui;G1）是通过从Vi; G 1继承位置l到l+L中的变量值并且从x^j;G 继承 剩余的变 量值而创 建的。基于局部搜索变异的重启差分进化算法177我我我表1标准DE算法的描述。01. 开始02.G=0创建一个随机的初始种群~xG，我03.04.05.06.07.08.09.10.11.12.13.14.15.16.17.18.19.20.21.f ~x= 8i;i/1;。. . ;NPG我对于G=1到GEN Do对于i=1到NP Do随机选择r1nr 2nr 3ni e [1，NP]，jrand=randint（1，D）对于j=1到D Do如果（randj [0，1] CR orj=jrand）则=（1-G/GEN））则（使用新的局部突变运算符）确定锦标赛x G，以及基于f的xG最好最糟糕u¼ x 第一届世界杯足球赛ð~x G我G-1GG GG G;i ¼ 1; 2; 3.. . NP我R1x-x F2·最好R1x-x，R1最糟糕Else（使用基本变异操作符）u1/4x10F3·10G-1GG Gi;j r1;jx-x轴r2;j r 3;jEnd If其他u¼ xGi; j i; jþ1GEnd If端如果，~u6fG-1G我~x我 然后~x¼~uG 1我G1 i其他~x¼~xG 1我G我End If如果|f（i）current-f（i）previous|6d = 10 - 6，K = 25代，6i，i =1，. . ，NP如果（rand（0，1）P0.5）则（使用重启机制）28.~x¼G 1..arandωJij j jIJxijb-a否则n.兰特;j1;.. . ;D（随机突变）29.30.其他~x¼G 1x randωIJij j jIJxijb- a<$ωa否则n.兰特... ;D（Modified BGA31.32.33.34.35.36.End If如果结束则结G=G+ 1首尾互掉ak·2-k;ak2f0;1g13180A.W. 穆罕默德Ko是移位向量。o1是复合函数中第一个基本函数的移位向量-j-j因此，Cr应该取一个小的值，以避免可能导致过早收敛和收敛速度慢的多样性超过水平。然后，通过世代，随着种群中的向量变得相似，种群的方差将减小。因此，为了提高多样性并增加收敛速度，Cr应该是大的值。基于上述分析和讨论，为了在多样性和收敛速度之间或在全局探索能力和局部开发倾向之间取得平衡，提出了一种动态非线性增加交叉概率方案：函数F5然而，当D > 3时，广义Rosenbrock这14个测试函数是维度明智的规模。基准问题的定义见附录A。表3给出了这14个基准函数的初始化范围、搜索空间范围和全局最小值的位置。4.2.比较算法为了评估拟议修改的好处，铬/铬Max公司简介min -Crmax·将RDEL算法与六种现有的自适应差分进化算法进行了比较。这些方法其中，G是当前代数，GEN是最大代数。mum代数，Crmin 和Crmax 分别表示Cr的最小值和最大值 ， k 为 正 数 。 这 些 参 数 的 最 佳 设 置 为 Crmin=0.1 、Crmax=0.8和k=4。该算法从G=0开始，Crmin=0.1，但随着G向GEN增加，Cr增加到Crmax=0.8。从Eq可以看出。（15）中，Crmin=0.1被认为是良好的初始速率，以避免早期阶段的高水平多样性，如先前以及Storn和Price[2]所讨论的。此外，Crmax=0.8是可以在探索和利用之间平衡的交叉的最大值k被设置为其所观察到的平均值，如果它近似小于或等于1或2，则对于某些函数，群体的多样性恶化，并且它可能导致停滞。另一方面，如果它几乎大于6或7，则随着多样性急剧增加，它可能导致过早收敛。因此，所有尺寸的平均值4被选为所有基准问题的默认值RDEL的详细描述见表2。4. 实验与讨论4.1. 基准函数为了评估所提出的算法（RDEL）的性能，使用了[5，35]中提到的14个著名的基准测试函数。所有这些函数都是极小化问题。在这些函数中，f1[2019 -05 - 15][2019 - 05][2019 -01] 19 - 05 01EPSDE[17]. 上述基准函数f1至f14分别在10维（10-D）、30维（30-D）和50维（50-D）中进行测试。对于10维问题，函数评估的最大数量设置为100，00，对于30维问题，设置为300，000，对于50维问题，设置为500，000。对于具有所有功能的所有维，总体大小设置为对于每个问题，进行30次独立运行，并提供统计结果，包括平均值和标准偏差值。通过统计t检验，不同算法的性能在统计学上与RDEL一致，显著性水平为0.05.数值1、0、1（h值）分别表示RDEL劣于、等于和优于与之比较的算法实验在Intel（R）Corei 7处理器1.6GHz和4GB-RAM上进行。RDEL算法在MATLAB中实现4.3. 实验结果和讨论比较结果（平均值、最佳运行误差的标准差和t检验结果）见表4（10维问题）、表5（30维问题）和表6（50维问题）。请注意，最佳运行误差对应于最佳运行值f*与特定目标函数的实际最优f* 之间的绝对差，即f~x最佳fω。这些方法提供的结果直接被（注：17）。在表4 从结果表3 测试函数的全局最优值、搜索范围和初始化范围功能尺寸全局最优值x*f（x*）搜索范围搜索范围f110、30和50OD D0 [-100，100][-100，100]F2OD D0 [-100，100][-100，100]F3（1，1，.. . （1）D D0 [-100，100][-100，100]f4OD D0 [-100，100][-100，100]F5OD D0 [-32，32][-32，32]F6OD D0 [-32，32][-32，32]F7O0 R [0，600]DF8O0 R [0，600]D女性9OD D0 [-5，5][-5，5]F10OD D0 [-5，5][-5，5]F11（420.96，.. . ，420.96）D D0 [-500，500][-500，500]F12（420.96，.. . ，420.96）D D0 [-500，500][-500，500]F13o1D D0 [-5，5][-5，5]F14o1D D0 [-5，5][-5，5]表4 RDEL和各种最先进的方法在10维问题上的比较。0007.50E-0316.60E-037.38E-015.93E-010000000000001.37E-20–02.66E-0101.01E+007.59E-012.21 E+0001111.77E+005.30E-0111.40E+007.13E-1013.90E-09 1.06E-12–001.02E+001.83E-0901.00E-08000000011008.13E-180–000000002.30E-203.27e-122.09E-1700 0 0 0 0 0FCN萨德JDEAdeSDE玉EPSDERDEL是说STD是说STD是说STD是说STD是说STD是说STD是说STDf100000000000000000000–F60000000000002.04E+0118.48E-010000–0F70000000004.20E-0317.90E-039.68E-1201.77E-110000–0F81.37E-0201.18E-022.26E-0201.77E-027.93E-0214.24E-023.81E-0213.06E-022.19E-0208.70E-38.91E-0214.27E-028.21E-03–6.73E-03女性90000000001.33E-0211.26E-020000000–0F102.82E+001.28E+00 4.41E+001.14E+00 5.46E+001.37 E+003.98E+002.06E+00 4.22E+001.30E+00 7.33E+001.39 E+005.50E+002.06E+00F110-100000000001.40E+00011.19 E+00000001000––0F120001.18 E+0113.61E+01 0007.90E+0013.01E+01 0000000–0F130006.67E+0012.54E+01 1.20E-0313.00E-031.67E+0113.79E+01 2.33E+0114.30 E+010000–0F142.54E-01-15.21E-011.27 E+0013.20 E+005.87E+0014.85E+008.26 E+0011.28E+01 3.33E+0011.83E+01 0006.52E-01–9.94E-01基于局部搜索变异的重启差分进化算法181F20F30f40F50表5 RDEL与各种最先进的方法在30维问题上的比较。FCNf1萨德是说000-1STD000JDE平均标准品0 00 10 0-111.01E+011012.24E+0010Ade是说009.29 E+0213.18E+0117.51E+03STD002.55E+02翡翠平均标准平均标准1.62E+00 0 0EPSDE平均标准品0 0RDEL平均标准品0 0–3.14E-01F215.31E+0213.33E+0213.77E-017.09E-011.59 E+0300-12.78E-12-12.69E-22-11.32E-051.26E-119.9E-225.41E-050–8.83E-06f31.33E-017.28E-013.01E+015.98E-011.44E+001.57E+014.02E+00 1.60E+011–5.98E-09f41.01E+011.54E+033.22E+023.60E-03104.03E-151.21E-051.81E-087.54E-020F6-1F70-10-114.10E-038.80E-034.70E-034.32E-014.97E+00-1000000001.23E-151.08E-15011.67E-013.37E-015.16E-014.58E+005.32E-156.70E-031.81E-155.21E-0100-1–6.83E-02F501003.91E-152.11E-011.65E-010-13.55E-15–01.36E-07女性91.33E-013.32E-021.82E-013.23E+006.27E-0704.10 E+0011.54E+0011.08E+0011.00E+0112.32E+0101.46E+0113.76E+0216.76E+0011.16 E+0111001.87E+001.49E-023.49E+001.34E-0206.98E+004.47E+000000007.81E+0110000004.94E+001-1001.33E+01–0–0–0––0–0–3.55E-15001F82.20E-030011004.22 E+01100001002.57E+010007.90E+0011.33E+0118.84E+01100F1012.38E+00-112.36E+0106.05E+00F112.00E-014.07E-0103.33E-021.83E-016.34E+0104.23E+00000F12100003.51E+01113.55E+0111.00E+0119.22E+00101.89E+023.00E+0100F1304.03E+011.67E-039.13E-034.18E+003.65E+015.07E+010F149.38E-012.56E+0112.56E+0111.86E+012.55E+017.19E-01–1.61 E+00–5.25E-314.53E-307.79E-01182A.W. 穆罕默德表6 RDEL和各种最先进的方法在50维问题上的比较。FCN萨德JDEAdeSDE玉EPSDERDEL是说STD是说STD是说STD是说STD是说STD是说STD是说STDf10002.57E-2906.61E-290002.17 E+0113.85E+01 0000007.79E-29–1.12E-28f2f3f41.47E-091.42E+003.05E+ 03-115.93E-092.44E+001.98E+ 032.11E-047.25E+001.26 E+03112.72E-041.77E+011.39E+ 031.70 E+044.55E+014.15E+ 04112.72E+031.08E+004.98E+033.26 E+025.54E+069.46E+ 03113.57E+021.36E+073.38E+035.20E-231.20 E+001.42E+ 03-111.13E-221.93E+001.55E+034.47E-0905.47E+ 02-1-11.75E-0809.47E+024.58E-017.93E-062.66E+02––5.12E-012.82E-052.34E+02111111–F56.45E-0117.09E-014.62E-1501.63E-157.11E-1118.45E-121.17 E+0017.35E-017.11E-1501.52E-168.05E-1502.46E-153.90E-15–1.08E-15F61.05E+ 0016.58E-014.38E-1501.50E-156.87E-1508.86E-169.90E-0117.95E-011.08E+ 0017.78E-017.11E-1502.46E-153.67E-15–6.48E-16F76.40E-0311.15E-022.00E-0411.30E-030001.40 E+0111.20 E+015.70E-0311.09E-010000–0F85.00E-0311.26E-027.00E-0412.90E-036.49E-1202.56E-111.14 E+0111.40 E+013.20E-0315.30E-030000–0女性9 2.09E+ 0011.34E+ 00 1.99E-0113.99E-010002.39E+ 0115.54E+000000000–0F107.33E+ 0111.65E+ 01 4.09E+ 0115.98E+ 00 1.27 E+0219.79E+015.94E+ 0111.23E+017.75E+ 0111.96E+012.00E+ 0212.90 E+014.40 E+01–9.03E+00F111.57 E+ 0011.28E+ 00 3.33E-0114.71E-012.00E-0114.00E-013.46E+ 0115.71E+000000000–0F12F133.95E+ 001.67E+ 01112.16 E+014.61 E+011.10 E+022.33E+ 01111.36E+ 024.96E+ 011.28E-111.19E-08-113.45E-126.52E-081.07E+ 032.24+ 01113.29 E+025.44E+015.92E+ 011.00E+ 01111.15 E+023.16 E+0100-10001.82E-111.72E-30––03.55E-30F145.01E+ 0111.75E+ 02 2.41 E+0114.02E+ 01 1.26 E+0112.16 E+002.14 E+0112.55E+011.52E+ 0113.11E+013.15E+ 0114.13 E+011.15E+0003.71E-01基于局部搜索变异的重启差分进化算法183184A.W. 穆罕默德表7 RDEL和不同版本的RDEL与Basic DE在50维问题上的比较可以清楚地得出结论，在大多数情况下，RDEL可以比其他比较算法更好地执行。从表4中可以明显地看出，RDEL 、 SaDE 和 EPSDE 对 于 所 有 基 准 问 题 都 比 jDE 、ADE、JADE和JADE表现出更好的高质量结果。从t检验结果可以观察到，在总共84例病例中，RDEL分别有2例、53例和19例劣于、等于和优于比较算法。因此，RDEL总是更好或相等。表5表明，RDEL算法在平均值和标准偏差值方面优于所有函数中的RDEL算法。然而，RDEL在函数f10上被RDEL算法超越。RDEL算法的性能在大多数情况下分别优于SaDE、jDE、ADE和JADE算法。最后，可以观察到RDEL和EPSDE算法的性能几乎相同，并且它们在大多数函数中近似地实现了相同的结果。总的来说，从t检验结果中可以观察到，在总共84个案例中，RDEL分别有3个、44个和41个案例劣于、等于和优于比较算法。因此，RDEL几乎要么更好，要么相等。根据表6，随着问题的维数从10D 增加到50D ，我们可以得出结论，除RDEL和EPSDE外，所有其他计算算法的性能都显著恶化。因此，RDEL优于所有的算法，具有较低的平均值和标准偏差值的高质量的最终解，与EPSDE竞争。结果表明，在最困难的函数f4，f10和f14上，RDEL算法的性能明显优于EPSDE算法.从t检验结果可以看出，在84例病例中，RDEL分别有6例、22例和56例劣于、等于和优于比较算法。因此，RDEL几乎要么更好，要么相等。总之，我们提出