多因子进化算法(multifactorial evolutionary algorithm，MFEA)是为解决多因子优化(multifactorial optimization，MFO)问题最早提出也是最为成熟的方法，已证明在同时解决多个优化任务时可发挥卓越的性能[1]．目前关于MFEA的研究主要集中在如何加强种群个体之间的知识传递从而提高算法性能上[2-3]；同时，一些替换了内核算法的MFEA变种算法同样在处理经典的优化问题方面展现出很好的效果[4]．除此之外，一些研究者还基于MFEA的核心思想提出了类似的多任务优化框架[5].目前MFEA存在的主要问题是由遗传算法造成的局部搜索能力的不足[6-7]，将种群个体进行自主学习的过程嵌入到MFEA框架中是解决这个问题的一种很好的方法．对于现有的自主学习策略，可以分为自定义的自学习方法[8-9]和传统的优化方法[10]两类．相对而言，传统的优化方法更为成熟，不须要对其性能另加验证．考虑到算法的普适性，拟牛顿方法是一个非常好的选择．这是因为拟牛顿方法在解决非线性问题方面有良好的效果，且不须要求解二阶导数，这使得嵌入拟牛顿方法就能够解决大部分优化问题；同时，由于不须要计算海森矩阵，因此使用拟牛顿方法可以节省很多计算成本．本研究通过单步迭代的拟牛顿方法实现个体的自学习过程，以此来弥补MFEA局部搜索能力不足的缺陷[11]．考虑到处于MFEA的框架中，个体自学习得到的知识可以通过知识传递效应在种群中传播，所以对所有个体采用拟牛顿方法显然不是最好的策略．为了得到最优的嵌入策略，本研究综合考虑种群个体类型及嵌入规模，设计了三种嵌入策略，并在多任务环境下进行了多角度的对比实验．1 算法基础在此先介绍多因子优化问题的一般性模型[12]，假设存在一个包含K个任务的优化问题，第j个任务Tj的特征域定义为Xj，其对应的目标函数即被定义为Fj:Xj⇒ℝ．为了实现不同任务个体之间的知识传递，MFEA定义了一些独特的指标支撑整个框架的实现．a. 因子成本(Ψij) 定义个体pi在任务Tj中的因子成本为Ψij=λδij+Fij,其中：λδij为惩罚项；Fij为对应的目标函数值．b. 因子排名(rij) 指标rij定义为个体pi基于任务Tj中因子成本在整个种群中的排名．c. 隶属因子(τi) 定义个体pi的隶属因子指标为τi=argminj{rij}，即表示个体pi在哪一个任务中的表现最好．d. 标准适应度(φi) 定义个体pi的标准适应度为φi=1/riT，其中T=τi．2 嵌入式MFEA2.1　嵌入拟牛顿方法在文献[9]中，已经尝试过将拟牛顿方法嵌入到MFEA框架中(adaptive memetic algorithm MFEA，AMA-MFEA)，且已证实效果远优于传统的MFEA．其具体做法是对每一次迭代后种群中不同任务的最优个体实行一次拟牛顿优化．实际上，这种嵌入的方式并不是很成熟．由于是处于MFEA的框架中，对最优个体的再优化会导致其更加优秀，该个体在筛选过程中会一直保留并有很大概率始终为最优个体，即使存在该个体和其他个体交配产生更优个体的可能，因此这种嵌入会使算法在处理局部陷阱过多的优化问题时退化成对单个个体的多次拟牛顿优化．考虑到知识传递效应的存在，在嵌入拟牛顿方法时须要考虑一些特殊的因素．只对单个任务的特征个体嵌入拟牛顿优化是一种思路，但是这种策略太过于依赖任务之间的相似程度．由于任务之间的相似度很大程度上限制了一个任务个体向另一个任务的个体传播知识的有效性，因此这种策略不是一个很好的选择，向多个任务的个体嵌入拟牛顿方法成为必然的选择．如何向多个任务的种群个体嵌入拟牛顿方法成为本研究的核心问题．2.2　嵌入策略设计考虑到个体的类型及嵌入后整个算法的计算时间成本，本研究提出了三种嵌入拟牛顿方法的可行策略，三种策略的详细说明及流程如下.a. 完全子代嵌入完全子代嵌入(subpopulation embedding，SE)是对每一次迭代后产生的子代进行一次拟牛顿单步优化，再结合父代进行种群排序，利用精英策略进行筛选，流程如图1所示．10.13245/j.hust.210602.F001图1完全子代嵌入策略 b. 完全种群嵌入完全种群嵌入(complete population embedding，CPE)策略与完全子代嵌入策略流程略为不同，这种嵌入方式是先将交叉变异产生的子代种群与父代种群合并，再对合并后种群进行拟牛顿优化，最后排序和筛选，具体流程如图2所示．10.13245/j.hust.210602.F002图2完全种群嵌入策略 c. 随机抽样嵌入随机抽样嵌入(random sampling embedding，RSE)是对每次迭代后整个种群个体进行随机抽样，对抽样个体进行拟牛顿优化，再进行排序和筛选，具体流程如图3所示．10.13245/j.hust.210602.F003图3随机抽样嵌入策略2.3　随机抽样嵌入的MFEA本文提出了三种嵌入拟牛顿方法的思路，其中随机种群抽样是一种折衷选择，其优点在于较低的计算成本和对MFEA中协同效应的充分利用，以及拥有可以维持充足的种群多样性的能力．本研究以随机种群抽样嵌入的MFEA(random sampling embedded MFEA，RSE-MFEA)为例，描述具体的算法流程．算法1 RSE-MFEA随机产生N个个体，构建初始种群P0初始化性能指标Ψij，rij，τit=0while(未达终止条件) do对种群Pt进行分类交配，产生子代Ct根据垂直文化传播更新Ct中个体的τi合并子代和父代，Rt=Pt⋃Ct对Rt进行随机抽样对抽样个体进行拟牛顿优化更新Rt中所有个体的性能指标Ψij，rij排序，筛选N个最优个体构成Pt+1t=t+1end while算法2 分类交配随机不重复选择两个个体p1和p2if (τ1==τ2) or (rand(1)rmp)基于父代进行交叉和变异产生子代c1和c2else通过p1变异产生子代c1通过p2变异产生子代c2end if算法3 垂直文化传播父代个体p1和p2产生子代个体c1和c2for c1和c2 doif rand1≤0.5ci继承p1的隶属因子τ1elseci继承p2的隶属因子τ2end ifend for3 对比实验3.1　测试集及参数设置为了测试新的嵌入策略在多种多任务环境下的性能，使用与文献[9]相同的多任务环境的测试数据集．数据集依据任务之间的相似度和最优解在统一空间中的重叠程度将多任务环境分为9种，具体测试集如表1所示．10.13245/j.hust.210602.T001表1测试数据集问题任务1任务2CI+HSGriewankRastraginCI+MSAckleyRastraginCI+LSAckleySchwefelPI+HSRastraginSpherePI+MSAckleyRosenbraockPI+LSAckleyWeierstrassNI+HSRosenbraockRastraginNI+MSGriewankWeierstrassNI+LSRastraginSchwefel本实验中MFEA框架的常规参数与多数研究者的实验保持一致：种群大小设置为100，知识传递概率设置为0.3，子代筛选策略为精英选择策略．嵌入式算法独有的参数设置如下：每次迭代进行自学习次数设置为1，通过在不同测试问题上的敏感性分析实验，随机抽样个体比例设置在10%~50%之间对实验结果无显著影响；因此，选择抽样比例20%作为统一参数，相同迭代次数实验中迭代次数设置为500次，相同优化时间实验中优化时间设置为150 s．3.2　实验结果分析3.2.1　相同迭代次数对比实验在迭代次数设置为500次的条件下，表1中优化函数20次重复实验的最终收敛值的均值和方差如表2所示，完全种群嵌入的结果与完全子代嵌入的结果基本相同，不在表中列出．通过实验结果可以发现：a. 在相同的迭代次数条件下，几乎所有测试问题中完全子代嵌入的结果都要优于AMA-MFEA中的嵌入策略；b. 尽管完全子代嵌入策略的效果非常显著，但是计算时间成本非常大，每一次迭代都须要消耗大量时间．本研究提出的随机抽样嵌入策略结合了完全子代嵌入的优点，缓解了计算时间上的压力，其结果同样优于AMA-MFEA的嵌入方式．10.13245/j.hust.210602.T002表2相同迭代次数实验结果问题AMA-MFEARSE-MFEASE-MFEA任务1任务2任务1任务2任务1任务2CI+HS0±00±00±00±00±00±0CI+MS11.54±1.551 011.15±318.318.93±2.85512.65±257.493.33×10-13±9.61×10-130±0CI+LS20.08±0.104 675.14±556.6220.00±0.003 819.81±700.1120.00±0.002 779.36±366.33PI+HS1 536.55±411.175.56×10-13±5.96×10-16901.49±85.053.48×10-13±6.48×10-14203.02±31.292.45×10-13±5.34×10-14PI+MS2.90±0.7390.38±132.561.51±0.8237.83±1.911.48×10-8±1.90×10-937.68±13.22PI+LS19.98±0.0620.20±3.1719.89±0.0319.94±2.9019.80±0.1321.45±3.32NI+HS103.06±208.57159.89±162.09114.13±204.6525.17±52.0133.92±3.810.30±0.94NI+MS4.16×10-11±2.07×10-1124.29±1.591.01×10-11±4.08×10-1224.77±2.486.89×10-12±1.50×10-1224.67±1.46NI+LS1 412.10±351.964 550.03±463.62839.23±153.333 526.75±365.53217.37±28.702 414.32±183.27在大多数环境下，随机抽样嵌入的效果不如完全子代嵌入的．这是因为拟牛顿方法存在的问题是容易陷入局部最优解，缓解这个问题的方法之一是选取不同的初始点进行优化．完全子代嵌入本质上就是使用了这个方法，在每次迭代时都会选取多个起始点(即交叉后新生成的个体)开始拟牛顿方法，这样做的结果是有更小的概率进入局部最优．综合以上分析发现，在相同迭代次数的情况下，几种嵌入策略的对比结果可以归纳为：在相同迭代次数的情况下，SE的优化结果约等于CPE且远优于RSE，而RSE的效果略优于AMA．其中，远优于意味着相差若干个数量级，略优于一般意味着差距在一个数量级以内．此外，算法所消耗的时间从短到长依次为AMA，RSE，SE和CPE．其中，SE和CPE所需要的时间要远远大于其他两种算法．3.2.2　相同优化时间对比实验在一些环境中，控制迭代次数相同是一种可取的对比策略，算法的时间成本同样须要考量．所以，为了更加公平地比较几种嵌入策略的优劣，本研究另外设计了在相同优化时间下各个嵌入策略的对比实验．在优化时间设置为150 s的条件下，表1中优化函数20次重复实验的最终收敛值的均值和方差如表3所示．10.13245/j.hust.210602.T003表3相同优化时间实验结果问题AMA-MFEARSE-MFEASE-MFEACPE-MFEA任务1任务2任务1任务2任务1任务2任务1任务2CI+HS2.61×10-124.77000000CI+MS12.531.27×1031.79×10-1401.15×10-1405.15×10-140CI+LS20.052.93×10320.002.38×10319.992.48×10320.002.50×103PI+HS1.68×1035.14×10-1398.121.85×10-13145.282.49×10-13165.361.91×10-13PI+MS2.991.241.56×10-87.651.57×10-80.121.55×10-818.08PI+LS19.9318.9419.8820.3819.8120.0419.8822.16NI+HS3.07107.5523.766.2618.4415.4213.490.19NI+MS4.45×10-1125.929.53×10-1227.731.02×10-1124.321.13×10-1131.35NI+LS1.55×1032.71×103107.272.47×103179.882.70×103190.902.58×103通过表3可以看出：在相同的优化时间内，完全子代嵌入和随机抽样嵌入的方式效果近似，这符合理论上的预期．在优化时间足够的情况下，随机抽样嵌入只是通过增加迭代次数来减少每次迭代所需要的时间．与完全子代嵌入相比，随机抽样嵌入方法维持了更丰富的种群多样性，当优化陷入局部陷阱时有更大的概率跳出局部陷阱．另外，值得注意的是AMA-MFEA的嵌入策略在一些特殊的测试环境下要略优于其他嵌入策略．这是因为在一些存在较少的局部陷阱或不容易陷入局部陷阱的问题上(例如Rosenbraock函数)，对单个个体多次进行拟牛顿优化是效率最高的，但是对那些复杂问题却不适用．此外，可以发现完全种群嵌入策略受到了很大的局限，因为其单次迭代时须要消耗大量的时间且存在很多无效的优化，所以在相同优化时间的条件下，效果并不理想．综上所述，在相同的优化时间条件下，几种嵌入策略的优化效果可以归纳为：RSE近似于SE且略优于CPE，而CPE的效果要略优于AMA．3.2.3　收敛曲线除了最终的优化能力，收敛速度同样是评判一个优化算法性能的重要指标．本研究选取两个较为典型的测试问题来比较几种策略的优化速度．图4和图5分别展示了4种嵌入策略在PI+MS问题和PI+LS问题上的表现，图中：Vo为最优值；n为迭代次数．为了展示更一般的对比效果，选取了在重复实验中多次出现的收敛曲线作为结果对比．10.13245/j.hust.210602.F004图4PI+MS收敛曲线10.13245/j.hust.210602.F005图5PI+LS收敛曲线总体而言，嵌入式MFEA的本质是一个概率突破局部最优解的问题．从AMA-MFEA的收敛曲线可以看到：算法陷入局部最优解后是无法跳出局部最优的，而图4(a)中非常直观地展示了随机抽样嵌入跳出局部最优的过程．除此之外，从图4和图5中也可以看出RSE的性能在迭代次数足够的情况下与SE非常接近．这可以从个体自学习的角度得到解释，从图1可以看出：完全子代嵌入会对所有子代个体进行自学习，并且这种经过自学习的个体有很大概率被保留．在下次迭代中，这些学习到的知识会直接通过MFEA的交叉操作在多个任务中传播，这种效率是非常高的．反观随机抽样嵌入，每次迭代自学习获得的知识相对较少，也可以通过协同效应在不同任务中传播，但是每次迭代需要的时间很短．所以，结合相同优化时间的实验结果，可以认为在迭代次数充足的情况下，随机抽样嵌入与完全子代嵌入的效果相当．4 结论为了解决现有的多因子优化算法中局部优化能力不足的情况，本研究提出将自学习策略这一抽象的概念嵌入到MFEA框架中，且具体通过嵌入拟牛顿方法加以实现；同时，结合MFEA框架本身的特殊性质以及嵌入后算法的计算性能，提出了三种嵌入策略，并与已知的嵌入策略AMA-MFEA进行了多角度的实验对比．为了综合评判几种嵌入策略的效果，本研究分别设计了在相同迭代次数和相同优化时间这两种不同环境下的实验，分析优化结果和收敛曲线，可以得出以下几点结论．a. 在迭代次数相同的情况下，完全子代嵌入可以取得最好的效果，主要是因为其在每次迭代中找到了更多的初始点进行拟牛顿优化，完全种群嵌入原理相同，但存在很多无效优化．b. 在优化时间相同且充足的情况下，随机抽样嵌入和完全子代嵌入效果近似且优于其他嵌入策略．这是因为随机抽样嵌入在时间充足的情况下可以有足够的迭代次数达到与完全子代嵌入近似的效果．c. AMA-MFEA中的嵌入策略在一些简单问题的优化中可以发挥出很好的效果，主要涉及一些存在较少局部陷阱的优化问题．拟牛顿方法只是自学习这一抽象概念的实现方式之一，还有许多其他的自学习方法可以被嵌入MFEA的框架中来获取更好的算法性能．如何寻求一个更适用于多任务环境下的自学习方法及设计相应的嵌入策略是下一步须要思考的问题．嵌入策略的不同可能会导致算法性能截然不同．多因子进化算法才刚刚兴起，如何优化整个算法框架是一个很重要的研究方向．除此之外，如何结合其他的方法来最大限度地挖掘算法在多任务环境下的性能也同样值得思考．