优化问题在现实生活中无处不在[1-3]，当一个优化问题嵌套另一个优化问题作为约束条件时，该优化问题称为双层优化问题．双层单目标优化问题，即双层优化中的上层优化和下层优化都只有一个优化目标．双层优化一直受到广泛关注．早些时候，一些学者提出用经典的方法求解双层单目标优化问题[4-6]．经典方法计算效率虽高，但求解过程往往依赖于问题本身的数学特性．由于经典方法的局限性，因此进化算法被广泛应用于处理双层单目标优化问题，如遗传算法[7]、粒子群算法[8]、差分进化[9]和蚁群算法[10]等．进化算法在经典方法处理不了的双层优化问题上颇有优势，但随着上层变量的增多，须要求解的下层优化任务的数量也剧增，计算开销巨大．针对上述问题，一些学者提出了不同的方法来处理双层单目标优化问题．文献[11]设计了一种基于自适应协方差矩阵的双层进化策略，文献[12]通过发掘和利用上层和下层决策变量之间的关系，将下层优化分成三类分而治之．此外，还有一些学者提出了基于代理模型的方法[13-14]，可以在一定程度上减少下层计算开销，但近似模型高度依赖于问题，并且近似模型的构建成本往往很高，模型的精度也会影响到问题的求解．由于双层优化问题上下层之间的嵌套关系，所有的上层决策都须要求解对应的下层优化问题，导致下层优化计算开销巨大，因此双层优化问题的求解难度和求解代价都远大于通常的约束优化问题．如何更高效、低代价地求解双层优化问题，一直都是该研究方向的热点问题．在机器学习领域，迁移学习广泛应用于分类、回归和聚类[15]．在智能计算领域，迁移学习也用于多目标多任务优化[16]．迁移学习广受欢迎的重要原因就在于其思想本质是将现有知识迁移应用于新的类似问题中．而在双层优化过程中，对每一个上层决策都要优化一个与之对应的下层，如果把每一个上层决策对应的下层优化看成多任务优化的子任务，那么原本孤立的下层优化就可以看成一个多任务优化．迁移学习可以应用到多任务优化，那自然就可以考虑将迁移学习应用到双层优化．本研究提出一种基于迁移学习的双层优化算法(BLOA-TF)来求解双层单目标优化问题．该算法融合了机器学习领域的迁移学习的思想，首先通过聚类算法挑选出有代表性的个体进行下层优化，获得的下层优化信息用归档集记录，再将归档集记录的下层优化信息迁移给其他相近的未经过下层优化的个体，以此加速整个优化过程，有效减少计算开销．将本研究提出的算法与通常基于嵌套的双层优化算法在12个标准测试问题上进行比较，实验结果表明本算法用于处理双层单目标优化问题是有效的．1 问题定义通常的双层单目标优化问题的数学模型可以表示为minxF(x)；s.t.  xL∈argminxL{f(x):gj(x)≤0(j=1,2,…,J)}; (1)Gk(x)≤0    (k=1,2,…,K)；x=(xU,xL)∈Rm+n，式中：xU=(xU1，xU2，…，xUm)为m维上层决策变量；xL=(xL1，xL2，…，xLn)为n维下层决策变量；F为上层优化目标；K为上层优化包含的约束条件数量；Gk为第k个上层约束条件；f为下层优化目标；J为下层优化包含的约束条件数量；gj为第j个下层约束条件．双层单目标优化问题(1)在本质上是一个约束优化问题，但其求解远难于通常的约束优化问题．在双层优化的决策过程中，对于任意一个上层决策xU，须要先求解对应的下层优化问题，得到最优下层决策xL*，再将xL*反馈回上层优化，只有当x=(xU，xL*)同时满足所有的上层约束条件时，x=(xU，xL*)才能作为双层单目标优化问题(1)的一个可行解[17]．从所有上述可行解中找出最优个体，最后得到双层优化的最优解．对于给定的双层优化问题，不同的上层决策对应的下层优化问题的数学结构高度相似．尤其当两个上层决策非常相似时，其各自对应的下层优化问题也趋于一致．图1表示了三个不同上层决策xU1，xU2和xU3对应的下层最优决策，其中xU1和xU2比较接近，其各自对应的下层最优决策也比较接近；而xU3与xU1和xU2相差甚远，其对应的下层最优决策与它们的也相差甚远[13]．对于相近的上层决策，其对应的下层最优信息高度相似，本研究以此为切入点，将迁移学习的思想应用到双层优化中，从而更高效、低代价地求解双层优化问题．10.13245/j.hust.220524.F001图1不同上层决策的对应的下层最优决策2 算法设计2.1　算法框架步骤1 进化代数t=0，在上层决策空间初始化上层种群P0={xU1，xU2，…，xUN}，其中N为种群规模；初始化归档集A=∅，A用于存储那些可供迁移的个体的信息，最大规模为10N．步骤2 在上层决策空间使用K-means聚类算法[18]将第t代种群Pt中的个体划分为k类，并得到k个聚类中心．对每个聚类中心进行下层优化，最终的优化信息被归档集A记录；对当前第t代，归档集A中的上层最优个体记为xbestt；对任意xUi∈Pt，找出归档集A中离xUi最近的个体(xU*，xL*)，并将其下层决策xL*迁移给xUi，得到个体xi=(xUi，xL*)，Pt中的xUi对应用xi替换；在Pt中的所有个体都完成迁移操作后，所有个体根据上层优化问题进行评估．步骤3 随机采用两种差分算子，即DE/best/1和DE/current-to-rand/1[19]，以及多项式变异[20]产生后代种群Ot={yU1，yU2，…，yUN}；交配个体随机从类内或类间选择．步骤4 对Ot执行步骤2中与Pt同样的操作，归档集A更新后同步更新xbestt．步骤5 根据上层优化，采用文献[21]中提出的方法，从Pt⋃Ot选择N个个体作为下一代种群，记为Pt+1，Pt+1中的最优个体为xpbest；若xpbest优于xbestt，则对xpbest启动重新评估机制并更新xbestt．步骤6 若局部搜索条件成立，则在xbestt附近进行局部搜索并更新xbestt．步骤7 当归档集A中的个体数目大于10N时，只选择保留A中较好的10N个个体；当前归档集A中的上层最优个体为xbestt+1．步骤8 若终止条件不成立，则重复执行步骤2～7；若终止条件成立，则输出xbestt+1．2.2　下层优化采用文献[21]中提出的方法处理下层优化，对于给定的上层决策，其对应的下层种群规模为M．下层优化的最大进化代数TLmax与上层优化的代数t有关，其对应关系为TLmax(t)=min(T0+5t/α,100)，(2)式中：T0为初始下层最大进化代数；α为控制TLmax变化周期的参数；⋅为向下取整．TLmax整体随上层进化代数t的增大呈上升趋势，但最大不超过100代．本研究取T0=10，α=5．下层优化在早期不须要很精确，早期设定较小的最大下层进化代数目的在于加速整个优化过程，通过下层优化引导种群快速接近最优解附近，同时也减少下层目标的评估次数．后期为了获取更精确的结果，就必须加强下层优化的程度．通过式(2)就能够实现自适应的控制下层优化的优化程度．在下层优化过程中，初始种群的产生也会用到归档集A中存储的下层优化信息．若给定的上层决策存在于归档集A中，则直接加载A中的存档作为初始种群；若上层决策不存在于归档集A中但与A中的个体很相似(上层决策空间欧式距离小于0.5)，则迁移这个相似个体的存档作为初始种群；否则直接随机初始化下层种群．2.3　后代选择与重新评估机制后代选择采用文献[21]中提出的方法．对于两个个体而言，可行解优于不可行解．当都是可行解时，目标函数值越小的越好；当都是不可行解时，违反约束程度越轻的越好．xbestt为归档集A中的上层最优个体，而xpbest记录了当前种群中的上层最优个体．由于xpbest可能是通过迁移学习得到的个体或只进行了较少代数的下层优化，其对应的下层优化信息未必很准确，因此当xpbest优于xbestt时不能直接用xpbest更新xbestt．这时引入重新评估机制，充分迁移利用归档集A中保存的历史优化信息对xpbest进行进一步下层优化，之后再用归档集A中的最优个体更新xbestt．2.4　局部搜索早期由于下层评估比较粗糙，很容易导致下层陷入局部最优．导致局部最优的原因有两个：一是上层优化问题本身是多峰问题；二是由于下层优化不精确，出现了比真实最优还好的伪优势个体．鉴于上述情况，本研究每隔τ代计算前τ代归档集A中上层最优个体的上层目标的方差，当方差小于某个较小的阈值ε时，意味着前τ代求得的最优个体变化幅度很小，上层优化陷入了局部最优，这时须要在xbestt附近进行局部搜索，即var(F(xbestt-τ+1),F(xbestt-τ+2),…,F(xbestt))ε，(3)式中：var为求方差；ε取值为1×10-6．当进行局部搜索时，从A中加载xbestt对应的历史优化信息，读取历史下层种群作为重新评估xbestt的初始种群，对xbestt进行进一步下层优化．下层优化结束后更新原先xbestt在A中对应的存档信息，从A中获取最新的最优个体x˜best．若x˜best优于xbestt，则xbestt直接用x˜best替换，否则通过多项式变异在xbestt附近产生新个体，对新个体执行下层优化，并用归档集A记录优化信息，最后用A中的最优个体更新xbestt．2.5　终止条件上层终止条件：a．根据式(3)，令τ=ΓU，上层全局最优解连续ΓU代变化幅度很小；b．上层(下层)函数评估次数达到设定的最大评估次数．下层终止条件：a．根据式(3)，令τ=ΓL，下层全局最优解连续ΓL代变化幅度很小，式中xbestt替换为第t代求得的下层最优；b．进化代数达到设定的最大下层进化代数．3 仿真实验3.1　标准测试问题与对比算法本研究选择的标准测试问题为文献[22]提出的测试问题集，该测试问题集包含了12个双层单目标优化问题．问题1～9的上下层优化问题真实最优值都为0；问题10～12的上层优化真实最优值分别为4，-1和3，下层优化真实最优值分别为3，1和4．该测试集包含的测试问题种类丰富，能较好测试算法的性能．为验证本研究提出的基于迁移学习的双层单目标优化算法的效果，对比算法为传统基于嵌套的双层优化算法，其上下层优化都利用文献[21]中的方法．3.2　参数设计与评价指标在测试问题中，上层决策空间的维数m=2，下层决策空间的维数n=3；上层种群规模N=20，下层种群规模M=30．其他参数取值如下：k=2，τ=2，ΓU=20，ΓL=5，对比算法的最大下层进化代数固定为100．上层目标函数最大评估次数为1×104，下层目标函数最大评估次数为1×106．本研究采用的评价指标有两个：一个为求解误差，即求得的近似最优解与真实最优解的差的绝对值；另一个为相对平均评估次数，其计算方式为下层函数评估次数与上层函数评估次数的比值．求解误差和相对平均评估次数都是越小越好，求解误差越小意味着求解精度越高，相对平均评估次数越小则表明计算开销越小．3.3　结果分析实验结果由Matlab软件经10次独立运行，最后取平均值得到．表1和表2分别记录了本研究提出的BLOA-TF算法与对比算法求解测试问题1～12的求解误差，表3和表4分别记录了BLOA-TF算法与对比算法求解测试问题1～12的上下层函数评估次数．10.13245/j.hust.220524.T001表1BLOA-TF算法求解测试问题1～12的求解误差问题求得的最优值求解误差上层下层上层下层11.31×10-69.55×10-71.31×10-69.55×10-72-2.52×10-55.28×10-52.52×10-55.28×10-531.31×10-64.34×10-61.31×10-64.34×10-64-1.31×10-63.59×10-51.32×10-63.59×10-55-9.26×10-41.15×10-39.26×10-41.15×10-3614.67×10-22.63×10-214.67×10-22.63×10-279.79×10-3244.36×10-19.85×10-3244.36×10-18-3.01×10-43.28×10-43.11×10-43.28×10-49-1.43×10-51.74×10-51.43×10-51.74×10-510397.54×10-2305.35×10-23.65×10-25.57×10-211-98.32×10-2103.28×10-24.00×10-23.28×10-212301.52×10-2407.31×10-28.38×10-28.61×10-210.13245/j.hust.220524.T002表2对比算法求解测试问题1～12的求解误差问题求得的最优值求解误差上层下层上层下层13.61×10-49.51×10-53.61×10-49.51×10-526.31×10-41.44×10-46.39×10-41.44×10-436.87×10-41.69×10-46.87×10-41.69×10-442.19×10-41.39×10-42.19×10-41.39×10-452.51×10-41.99×10-42.97×10-41.99×10-46416.63×10-12.51×10-6417.00×10-12.51×10-6777.96×10-2-125.0077.96×10-2125.0083.11×10-43.79×10-44.96×10-43.79×10-493.18×10-51.05×10-47.94×10-51.05×10-410701.90×10-2213.54×10-2301.90×10-286.45×10-211-100.21×10-2100.32×10-22.18×10-33.20×10-312714.07×10-2367.50×10-2415.79×10-261.71×10-210.13245/j.hust.220524.T003表3BLOA-TF算法求解测试问题1～12的上下层函数评估次数问题评估次数/103相对平均评估次数上层函数下层函数11.02152.6865221.07358.5485531.06759.0555541.11661.5725551.11462.7575662.881150.0995271.06958.8845581.29075.0005891.23671.78758103.588266.15474113.256204.53463124.760358.4977510.13245/j.hust.220524.T004表4对比算法求解测试问题1～12的上下层函数评估次数问题评估次数/103相对平均评估次数上层函数下层函数10.650206.31931720.620206.76033330.648227.05835040.532180.85534050.714255.30935861.806511.54528370.698223.75232180.746275.13336990.594196.398331101.666731.340439110.918313.395341121.488657.735442针对第一个指标，由表1和表2可知，对于所有的测试问题，本研究提出的BLOA-TF算法的求解误差总体优于对比算法．BLOA-TF算法动态调整下层优化的最大进化代数，前期采用较小代数使上层种群快速收敛，后期随着下层进化代数的增加，求解精度也进一步提高．BLOA-TF算法利用了迁移学习的思想，一定程度上减少了上层优化对下层优化的依赖，重新评估机制和局部搜索进一步增强了算法的探索性．而对比算法上层优化过分依赖下层，反而阻碍了整个优化进程．针对第二个指标，由表3和表4可知，同样对于所有的测试问题，BLOA-TF算法的相对平均函数评估次数也都少于传统的嵌套算法．传统的嵌套算法对每一个上层决策都要进行下层优化，其下层计算开销毫无疑问相当巨大．而BLOA-TF算法加入了迁移学习的思想，充分利用历史存档记录的信息，从多方面减少下层函数的评估，节省了大量计算开销．本研究提出一种基于迁移学习的双层优化算法求解双层单目标优化问题．该算法融合了机器学习领域迁移学习的思想，首先通过聚类算法挑选出有代表性的个体进行下层优化，将获得的下层优化信息用归档集记录，再将归档集记录的下层优化信息迁移给其他相近的未经过下层优化的个体，以此加速整个优化过程，并有效减少计算开销．实验结果进一步表明本研究提出的算法用于处理双层单目标优化问题是有效的．