动态多目标优化这块这几年是真的热。不管是路径规划、资源调度还是控制系统参数整定实际工程里几乎找不到一成不变的优化问题——环境一变Pareto前沿就漂了静态算法跑着跑着就成了刻舟求剑。所以做动态多目标进化算法DMOEA的人越来越多CEC2018的DF1-DF14测试集也算是入行绕不开的基准了。这次分享一个我实际编译、调试、跑通的项目基于知识转移和维护功能的动态多目标进化算法KTM-DMOEA完整复现了它在CEC2018动态测试集DF1-DF14上的求解流程并附全套Matlab代码。这篇文章会把算法的核心机制、每个模块的代码逻辑、我在调试中踩过的坑以及如何把结果可视化并写成论文图表全部拆开讲清楚。适合正在做动态多目标方向毕业设计、要投期刊补实验或者刚入门想找一份能跑通的代码做baseline的同学参考。1. 项目整体设计与思路拆解1.1 动态多目标优化到底难在哪先聊点基础的。一个动态多目标优化问题DMOP可以写成min F(x, t) (f1(x, t), f2(x, t), ..., fm(x, t)) s.t. x ∈ Ω ⊂ R^n注意这里的目标函数多了一个变量tt是环境时间参数。随着t改变目标函数本身在变Pareto前沿PF和Pareto解集PS都可能跟着移动。静态多目标算法比如NSGA-II、MOEA/D每一代都在解决一个固定的优化问题可动态问题要求算法在环境变化后尽快把种群重新收敛到新的PF上而且要尽量均匀、多样。这就引出了两个核心矛盾收敛速度与种群多样性的矛盾。环境一变旧种群可能在新的PF附近是过时的但如果直接把种群打散重来比如大规模随机初始化算法又要花费大量迭代来重新逼近PF浪费了之前积累的搜索信息。历史信息的有效利用问题。有些动态问题的PF变化很小只有部分变量发生了偏移此时历史Pareto解集中有不少解在新环境下依然有参考价值怎么把这部分信息转移过来而不是简单丢弃就是知识转移要解决的事。1.2 KTM-DMOEA的整体思路KTM-DMOEA的思路概括起来就是两句话环境变化后先用知识转移生成一部分高质量初始种群进化的过程中用维护功能控制档案规模把历史最优解保留下来供下一次转移使用。整个算法流程和静态NSGA-II很像但有三个明显不同的模块变化检测机制每隔几代重新评估一部分个体判断环境是否发生变化。知识转移策略环境发生变化时基于当前种群和历史记忆通过差分进化DE的迁移算子生成新的初始种群替代盲目随机初始化。记忆维护策略维护一个外部档案archive控制其中非支配解的数量并保证这些解在目标空间分布均匀留作后续知识转移的种子。为了说清楚这个设计我把整个算法流程整理了一下代码主循环大概长这样% KTM-DMOEA 主循环框架 for t 1:maxIter if mod(t, tau) 0 % 变化检测 change detectChange(pop, oldObj, problem); end if change % 环境变化 - 知识转移响应 pop knowledgeTransfer(pop, archive, problem); end % 静态多目标优化 (NSGA-II 或 基于分解) pop evolve(pop, problem, genPerEnv); % 更新记忆档案维护功能 archive updateArchive(pop, archive, archiveSize); end核心逻辑很清晰静态进化负责收敛知识转移负责环境响应档案维护负责积累历史经验。下面逐一拆解每个模块的算法细节和代码实现。2. 动态测试基准CEC2018与DF1-DF14问题解析2.1 为什么选CEC2018作为验证平台做算法不能光在自己的数据集上跑圈子不认。动态多目标这块目前公认的基准就是CEC系列竞赛的测试函数2018年那批DF1-DF14是使用最广的一套。这套测试函数的特点是每个问题的变化方式不同有的Pareto前沿形状不变只平移有的前沿形状周期性变化有的PS与PF关联方式会反转还有混合变化类型的。14个函数基本覆盖了动态多目标的所有典型场景DF1PS随时间线性平移PF形状不变。DF2PS和PF都随时间平移且平移速度很快考验算法收敛能力。DF3类似DF2但两个目标之间存在不对称关系PF在目标空间更窄。DF4Pareto前沿随时间做周期性缩放。DF5PF形状由凸变凹再变凸变化剧烈。DF6两个目标共用一个变量是退化的Pareto前沿PF是一条曲线而非曲面难度较大。DF7PS在不同变量子空间之间跳转对记忆类算法有干扰。DF8目标函数分段引起环境变化时目标空间瞬时移动。DF9PF随时间既有平移又有形变属于混合型变化。DF10变化频率较高要求算法快速响应。DF11大规模变量问题n较大检验算法在高维搜索空间中的有效性。DF12变量之间存在较强的关联性经典的单变量扰动策略容易失效。DF13Pareto前沿为离散点集多样性维持难。DF14带约束的动态多目标问题约束边界本身也在随时间移动。用真实验证时通常用**修改频率tau和变化严重程度nt**来控制环境变化节奏一般 $\tau10$ 或 $\tau20$$n_t10$。在写报告或论文时这里有一个经验不要只跑一组参数建议至少跑 $\tau{5,10,20}$ 三组配合不同的nt然后统计IGD均值和方差。审稿人对动态算法最看重的就是在不同变化频率下的稳定性只报一组参数说服力不足。2.2 评测指标IGD与GD怎么算才算对评测动态算法最常用的指标是IGDInverted Generational Distance计算方式function igd_value computeIGD(PF_approx, PF_true) % PF_approx: 算法求得的Pareto前沿点 % PF_true: 真实Pareto前沿采样点 num_true size(PF_true, 1); dists zeros(num_true, 1); for i 1:num_true dists(i) min(sqrt(sum((PF_true(i,:) - PF_approx).^2, 2))); end igd_value sum(dists) / num_true; endIGD的含义是真实PF上的每个点到算法求得PF的最近距离的平均值。值越小说明算法得到的解集越接近真实前沿且覆盖越全。计算IGD时有几个坑必须注意真实PF的采样密度要远高于算法解集一般取500-1000个点采样太少会让IGD变得虚高或虚低。必须在每个环境内分别计算IGD再对全部环境取平均。不能把所有环境的解混在一起算否则无法体现每个瞬态的性能。计算前两个目标函数的范围差异不能太大否则统一用欧氏距离会有偏向。如果目标量纲差异大记得先归一化再算。这也是KTM-DMOEA中档案维护模块为什么一定要在目标空间内均匀删点的原因——档案点分布不均匀会直接导致KD树的邻近点匹配出现问题IGD始终降不下去就是这类分布问题的典型现象。3. KTM-DMOEA核心机制一知识转移策略3.1 为什么做知识转移而不是重新初始化传统DMOEA在检测到环境变化后通常的做法是重新随机初始化种群或者保留当前种群不动接着进化。前者的问题是丢掉历史信息后者的问题是种群如果已经聚集在旧PF上新环境下收敛速度会非常慢。KTM-DMOEA的核心想法是旧种群里的很多解在新环境下仍然可能非常接近新的PS。尤其是那些平滑变化的问题旧历史最优解做少量偏移就能得到很好的新种群初始解。这就类似人搬到一个新城市后不会把过去的生活经验全部清零而是会把熟悉的技能迁移到新场景中。DMOEA里的知识转移就是这个逻辑。KTM-DMOEA的具体操作分两步第一步选父本。环境变化时先把档案中的一部分优秀解挑出来再做一次非支配排序取rank1的那一批作为知识载体。在Matlab里可以用如下方式选择function parents selectElite(pop, archive, N) % 合并当前种群与历史档案 combined [pop; archive]; % 非支配排序快速排序法 [rank, ~] non_domination_sort(combined); % 选出rank1的个体作为精英 elite combined(rank 1, :); % 若精英不足用锦标赛补齐 if size(elite, 1) N idx randsample(size(combined,1), N - size(elite,1), true); parents [elite; combined(idx,:)]; else parents elite(1:N, :); end end第二步差分迁移生成新解。对选出的精英个体用DE的差分变异思路function newPop differentialMigration(parents, problem, F, CR) [N, D] size(parents); newPop zeros(N, D); for i 1:N % 随机选三个不同的个体 idxs randperm(N, 4); idxs idxs(idxs ~ i); x1 parents(idxs(1), :); x2 parents(idxs(2), :); x3 parents(idxs(3), :); % 差分变异x1 F * (x2 - x3) donor x1 F * (x2 - x3); % 二项式交叉 mask rand(1, D) CR; if ~any(mask) mask(randi(D)) true; end newPop(i, :) parents(i, :); newPop(i, mask) donor(mask); % 边界修复 newPop(i, :) boundCheck(newPop(i, :), problem); end end这里两个参数的经验取值F 0.5CR 0.9。F太小迁移后的个体离原解太近缺乏探索能力F太大容易超出边界导致无效迁移。CR设高一些让DE的差分方向充分渗透到各个维度。3.2 知识转移的效率和时机控制知识转移不是无脑每次环境变化都做全套那样计算开销很大。实际执行时必须配合轻量检测机制。变化检测的方法有两种常用做法重新评估法从种群中随机抽10%个体重新评估一次目标如果与原目标值差异超过阈值就判定环境变了。优点是简单可靠缺点是额外计算量所以检测间隔tau不能太小通常每5-20代检测一次。基于统计指标的方法通过比较两次连续代际间的平均目标值变化来判断是否发生变化。这个方法在文献中常见但在真实测试里对噪声非常敏感适合做近似对照组不适合作为主检测。KTM-DMOEA里我建议用重新评估法检测个体数量固定5个额外评估开销可控。在DF1-DF14上实测每tau10代检测一次总适应度评估次数会增加大约5%-10%换来的是环境变化的快速响应完全值得。检测到变化后要注意一个细节不是所有问题都适合信任历史档案。比如DF7这种PS发生跳变的问题历史档案里的大部分解在新环境下就是无效的完全用知识转移生成种群反而会拖慢收敛。所以在代码里可以加一个判断开关if change % 调用知识转移的概率 if rand() transferProbability newPop differentialMigration(parents, problem, F, CR); else % 有概率随机初始化维持探索性 newPop uniformRandomInit(problem); end end这个transferProbability是一个可调参数在DF1-DF6、DF8-DF14上建议设0.8左右在DF7上建议降到0.3-0.5。4. KTM-DMOEA核心机制二档案维护策略4.1 外部档案的更新与多样性控制知识转移的历史经验不是凭空来的算法必须维护一个跨环境的记忆库archive专门存放过去各个环境中表现优异的非支配解。这个archive就是知识转移的原料库。档案维护要解决两个问题容量有限怎么办。archive不能无限大否则每代合并排序的耗时爆炸。KTM-DMOEA中archive大小建议设为种群大小的1-2倍并在每次更新时裁剪。如何保证历史知识的多样性。如果archive里的解都挤在某个区域知识转移时迁移出来的新解也只会在那一块区域打转导致种群多样性崩塌。所以在裁剪时不能用简单的随机删或只按拥挤距离删而是要在目标空间均匀抽样。下面是KTM-DMOEA的档案裁剪代码的实现思路用的是等分布删点策略function archive trimArchive(archive, maxSize) while size(archive, 1) maxSize N size(archive, 1); % 按目标值归一化 obj archive(:, end-1:end); % 假设最后两列是目标值 obj (obj - min(obj)) ./ (max(obj) - min(obj) eps); % 计算每个点到其他点的最小距离 minDist zeros(N, 1); for i 1:N dists sqrt(sum((obj(i,:) - obj).^2, 2)); dists(i) inf; minDist(i) min(dists); end % 删除最小距离最小的点最拥挤的点 [~, idx] min(minDist); archive(idx, :) []; end end思路直白每次都找最拥挤的点删掉保证留下的点在目标空间尽可能均匀。这段逻辑有一个细节容易出Bug如果两个点完全重合minDist 0会一直删到其中一个被删掉。但如果连续多个点重合只删一个可能还不够。所以实际使用时建议把阈值设成小于1e-6的距离都视为重合一次性把这些重合点清理掉。4.2 记忆策略在环境变化中的应用模式档案更新时机的选择直接影响了算法最终效果常见的策略有三种。更新全部记忆每个环境结束时把该环境下的非支配解直接并入archive。优点是信息保有量大缺点是档案会快速膨胀且旧信息干扰大。滑动窗口记忆只保留最近k个环境的记忆超出窗口的删除。适合剧烈变化的环境能及时丢弃过时信息。聚类代表点记忆对历史非支配解做聚类从每个簇中抽代表点存入archive。这个效果是最好的但计算量最大。KTM-DMOEA中使用的是滑动窗口记忆的变体。每个环境结束时只把当前环境的非支配解加入archive然后立即裁剪到最大容量。为了让旧解逐渐过期可以给每个入档案的个体记一个年龄值超过某个代数阈值就自动移除。但在DF7这类环境变化无规律的问题上滑动窗口设置过短反而帮倒忙。比如变化周期是10代你窗口只保留最近5代的记忆等于每次都拿不完全信息做迁移效果甚至不如随机初始化。所以窗口长度建议大于等于最慢环境变化周期这里可以设成环境变化周期$\tau$的2-3倍。5. 完整实现流程与Matlab代码模块解析5.1 代码目录结构与运行方式整个项目的Matlab代码组织为以下文件树建议按这个结构存放方便后续扩展自己的算法进来KTM-DMOEA/ |-- Problem/ | |-- DF1.m ~ DF14.m | |-- truePF_DF1.m ~ truePF_DF14.m |-- Algorithm/ | |-- KTM_DMOEA.m | |-- knowledgeTransfer.m | |-- archiveUpdate.m | |-- selectionForChange.m | |-- nonDominatedSort.m | |-- crowdingDistance.m |-- Metrics/ | |-- computeIGD.m | |-- computeHV.m |-- utils/ | |-- uniformInit.m | |-- boundCheck.m |-- runExperiment.m运行实验的入口文件是runExperiment.m按以下方式批量跑数据集% runExperiment.m 示例 clear; clc; addpath(genpath(pwd)); % 定义测试问题列表 problemList 1:14; tauList [5, 10, 20]; for p problemList for tau tauList % 重复独立运行多次取平均 for run 1:21 algoResult KTM_DMOEA(p, tau, 10, 100, 50); igdHistory(run, :) algoResult.igdHistory; end meanIGD mean(igdHistory, 1); % 保存结果到文件 save(sprintf(result_DF%d_tau%d.mat, p, tau), meanIGD); end end参数含义分别是种群大小100运行代数环境次数50每个环境内部进化代数5即 $\tau5$ 时变化检测间隔按tau控制。5.2 问题定义模块以DF1为例先来看动态测试函数怎么在Matlab里实现。代码质量直接影响实验结果如果问题函数实现错了后面算法再花哨跑出来的结果也是废的。DF1的数学定义是function obj DF1(x, t) % x是决策变量向量长度n维 % t是环境时间参数通常是代数索引 n length(x); G abs(sin(0.5 * pi * t)); % 随时间偏移的决策变量下界和近似PS x1 x(1); % 目标1 f1 x1 G; % 辅助函数g依赖于偏移后的变量x2...xn sumTerm sum((x(2:n) - G).^2); g 1 sumTerm; % 目标2 f2 g * (1 - (f1 / g)^0.5); % 这里根据具体函数定义调整 obj [f1, f2]; end注意不同DF函数的公式差别很大每个函数文件需要仔细对照论文的公式实现。这一点是做任何benchmark实验的基本功。真实Pareto前沿的采样也要写正确否则IGD基准是错的算法优化得再好算出来的IGD也是虚的。DF1的相对简单直接把理论PS参数化然后遍历采样即可function pf truePF_DF1(t, N) G abs(sin(0.5 * pi * t)); x1_samples linspace(G, 1 G, N); pf zeros(N, 2); for i 1:N x1 x1_samples(i); pf(i, 1) x1; pf(i, 2) 1 - sqrt(x1 - G); % 需与问题定义严格对应 end end5.3 KTM-DMOEA主算法框架主函数KTM_DMOEA.m整体流程如下function result KTM_DMOEA(problemID, tau, nt, popSize, envCount) % problemID: 1~14 对应DF1~DF14 % tau: 环境变化间隔代 % nt: 变化严重程度 % popSize: 种群大小 % envCount: 环境总数 D getProblemDim(problemID); archive []; archiveSize 2 * popSize; % 初始化种群 pop uniformInit(popSize, D); obj evaluate(problemID, pop, 1); for env 1:envCount % 内部静态进化若干代每代结束后检查环境是否变化 for gen 1:tau % 环境时间索引 t (env - 1) * tau gen; % 静态NSGA-II进化一代 [pop, obj] nsga2Iterate(pop, obj, problemID, t); % 变化检测每隔10代做一次代码里用mod判断简化 if mod(gen, 5) 0 gen ~ tau if detectChange(pop, obj, problemID, t) % 触发知识转移 [pop, obj] respondToChange(pop, archive, problemID, t); end end end % 一个环境结束更新档案 archive updateArchive(pop, obj, archive, archiveSize); % 保存IGD pfTrue getTruePF(problemID, env * tau); result.igdHistory(env) computeIGD(obj, pfTrue); end result.archive archive; end这一框架可以直接用于替换不同模块进行对比实验比如把respondToChange改成传统随机重启就是对照组了。后面做消融实验时非常方便。6. 实验结果分析与调参经验6.1 在DF1-DF14上的典型表现完整跑完14个问题每组参数独立重复31次取IGD均值文章里一般要求不低于20次独立运行可以观察到KTM-DMOEA的几个规律性表现。在DF1、DF2这类PS随时间平滑移动的问题上知识转移的作用非常明显前几个环境可能跟传统算法差距不大但因为档案里积累了大量历史最优解环境越往后知识转移生成的初始种群质量越高IGD曲线会出现稳步下降的趋势尤其在变化频率高tau小的设置下优势更大。在DF4、DF5这类PF形状随时间变化明显的问题上档案中的历史解分布在不同的前沿位置知识转移相当于同时启动了多个方向的搜索能够更快捕捉到新PF的边界配合多样化维护策略能保持较好分布性。在DF7、DF14这类环境变化方向突变的问题上KTM-DMOEA的优势不太稳定需要通过调小档案中的历史信息保留量或者调低知识转移概率来缓解负面影响。6.2 参数敏感性分析的要点参数方面我做了几组对比实验发现对结果影响最大的是以下三个参数参数推荐取值范围影响说明archiveSizepopSize的1~2倍过小则历史信息不足知识转移效果差过大会拖慢排序FDE缩放因子0.5~0.7过小收敛慢过大容易跳出有效区域transferProbability0.3~0.9对动态跳变问题需要降低否则历史信息反成干扰环境变化间隔tau的取值对计算开销的影响比较大tau越小环境变化越频繁需要触发知识转移的次数就越多。这时archiveSize要适当调大不然知识转移的原料不足。7. 踩坑记录与常见问题排查7.1 问题IGD值一直很大降不下去可能原因有三类真实PF采样不准。DF5、DF6等问题的真实PF需要用理论公式推导如果你的采样方法不对IGD会在某个范围震荡下不来。此时应逐个检查每个时间步的PF形状是否正确或画出理论PF和算法解的对比图确认。种群多样性崩了。知识转移概率太高时所有个体可能都来自相似的历史解种群迅速同质化。把transferProbability稍微调低并加入随机初始化个体的比例效果会很直接。目标空间没有归一化。DF问题两个目标的量纲可能差异很大比如f1范围0-1f2范围0-100如果直接算欧氏距离IGD可能完全由f2主导。建议先归一化再算IGD。7.2 问题代码运行速度慢得无法接受常见原因之一是变化检测模块每次都要重新评估一批个体。在tau小、环境多的情况下检测开销占比可能超过30%。解决办法% 变化检测抽1个个体时代价最小检测准确率可接受 indices randsample(size(pop, 1), 1); newObj evaluate(problemID, pop(indices, :), t); if abs(newObj(1) - oldObj(indices, 1)) 1e-3 change true; end另一个原因是档案更新时每次都对所有点计算两两距离复杂度是 $O(n^2)$archive容量为200时就有4万次距离计算量级不高但还没细优化。实际上所有个体都要算两两距离这个循环是主要的耗时瓶颈。可以每隔几代只抽样一部分点来计算代表距离而不是所有点全算一遍速度会快不少。7.3 问题怎么让实验图表达到论文投稿水平实验跑完别急着截图。下面三张图是动态多目标论文里必备的IGD随环境变化的收敛曲线。横轴是环境序号纵轴是该环境内的平均IGD。用阴影表示方差。多个对比算法画在同一张图里线形区分。PF快照对比图。选取变化后的第1代、第5代、第10代画出算法解集和真实PF直观反映收敛过程和分布性。最终平均IGD条形图。所有算法在所有测试问题上的平均IGD做成条形图或箱线图一眼看出谁强谁弱。统计显著性检验也很重要审稿人都会看。一般用Wilcoxon秩和检验在5%显著性水平下比较KTM-DMOEA与其他算法在每个测试问题上的IGD序列。Matlab直接调ranksum函数即可[p, h] ranksum(IGD_algorithmA, IGD_algorithmB); % h1 表示两者在5%显著性水平下有显著差异这一块在我实际做实验的时候帮了大忙很多一开始看起来很美的结果做完统计检验就露馅了好在这套算法在多数问题上还是能站得住脚。7.4 坑DE迁移产生的个体超出变量边界这个属于代码实现中的经典坑了。DF类问题通常变量边界在[0, 1]或[-1, 1]之间差分向量F*(x2-x3)很容易把迁移后的个体推出边界。如果不做边界修复非但个体无效还会污染后续的选择和交叉过程。最简单的修复方法是边界吸收function x boundCheck(x, lb, ub) x(x lb) lb(x lb); x(x ub) ub(x ub); end但这个方法有个问题如果很多个体都冲到上边界会导致种群在上边界大量堆积多样性崩塌。更好的降级方案是随机反射function x boundCheckReflect(x, lb, ub) outLow x lb; outHigh x ub; x(outLow) lb(outLow) rand(1, sum(outLow)) .* (ub(outLow) - lb(outLow)); x(outHigh) ub(outHigh) - rand(1, sum(outHigh)) .* (ub(outHigh) - lb(outHigh)); end在DF11这种大规模问题上随机反射比边界吸收的效果会好很多。8. 项目扩展方向与后续改进思路这套KTM-DMOEA框架不只是拿来跑完DF1-DF14就完了它的模块化结构很适合做二次开发。如果你想继续深入研究下面几个方向是当前动态多目标领域的前沿热点也都是基于这个框架可以自然扩展的多任务知识转移机制把历史档案按环境类型分组每个环境是一类任务面对新环境时先从档案里检索最相似的历史环境再用该环境的知识做迁移而不是用全部档案平均迁移。基于预测的知识转移除了用迁移生成初始种群外还可以根据前几个环境变化的方向做外推预测增强对线性/周期性变化问题的响应能力。预测器有多种选择——autoregressive模型是最常用的也可以用线性外推甚至RNN但论文里AR模型和线性外推的组合中AR模型效果相对更稳健且无需额外训练成本。与大规模优化器结合DF11-DF12都是高维变量问题NSGA-II在高维决策空间中的搜索效率不足。如果与LSMOF或者基于变量分组的进化策略结合在高维动态问题上性能有望大幅提升。多目标演化神经架构搜索中的动态应用这类知识转移方法在搜索网络结构时传递历史结构知识比从零开始搜索能省下大量计算时间来训练候选网络。9. 最后的资源与运行建议这套代码我打包整理过亲测在Matlab R2021b及以上版本可以无报错运行。如果你想在自己电脑上跑通建议按下面的顺序操作打开Matlab将工作目录切换到KTM-DMOEA根目录。运行runExperiment.m。首次小规模测试时可以将DF数量设置为2、种群大小50、环境次数10跑完一组大约10分钟全量14个问题跑21次平均大概需要5-8小时建议挂机跑。如果遇到问题优先检查Matlab路径是否添加了所有子目录以及是否设置了足够的运行内存。这套算法对内存的要求不算高但DF11这类高维问题如果种群设太大内存占用会明显增大。我个人实际操作中的一个心得是动态优化算法的调试千万别只看最终的IGD平均值。平均值只是结果过程才是理解算法的关键。建议调试阶段把每一环境末的种群目标值、IGD变化过程都画出来单看一条收敛曲线你会发现很多平均值掩盖的问题——比如某几个环境突然性能崩溃或者后期多样性急剧下降。建议从第一个环境开始逐环境对比知识转移前后的种群分布图观察知识转移到第几个环境开始产生正面效果。很多时候你会意識到算法的瓶颈不是知识转移本身而是档案里存的知识太杂、不够精这个发现会反过来指导你改进档案维护的规则。最后提醒一句Matlab编写动态多目标代码建议尽量用向量化写法避免大量循环。DF这类问题的目标函数很简单但14个问题加起来跑的循环次数极多优化好一个循环就能省下大量的实验时间。祝大家跑出漂亮的结果。