《A surrogate-assisted multi-objective particle swarm optimization of expensive constrained combinatorial optimization problems》如果把多目标组合优化比作在迷宫里找路那么“昂贵评估”意味着你每走一步都要付出很高代价“约束”意味着很多路根本不能走而“离散变量”则意味着你不能沿着光滑曲面滑行只能一格一格跳着前进。Gu 等人在这篇论文里做的事就是请来一个并不完美、但足够便宜的向导——随机森林再配上一支更会判断方向的搜索队——改进的多目标粒子群最后给这支队伍补上约束边界修正与离散状态更新两套规矩。结果是路走得更少了方向却更准了。摘要这篇论文面向“评估代价高、变量离散、还带约束”的多目标组合优化问题提出了一个随机森林Random Forest, RF辅助的多目标粒子群优化Multi-Objective Particle Swarm Optimization, MOPSO算法 RFMOPSO它通过代理模型Surrogate Model降低精确评估次数通过自适应随机排序Adaptive Stochastic Ranking平衡“目标更优”与“解可行”并通过离散粒子状态更新策略改善搜索方向最终在多目标背包问题Multi-Objective Knapsack Problem, MOKP基准上取得了较好的收敛性与效率。一、论文基本信息论文标题A surrogate-assisted multi-objective particle swarm optimization of expensive constrained combinatorial optimization problems作者Qinghua GuQian WangXuexian LiXinhong Li主要来自西安建筑科技大学Xi’an University of Architecture and Technology相关院系与实验室。出处Knowledge-Based Systems2021223107049。DOI/链接10.1016/j.knosys.2021.107049原文链接https://doi.org/10.1016/j.knosys.2021.107049二、研究背景与动机这篇文章讨论的问题并不只是“组合优化”这么简单而是昂贵约束多目标组合优化。所谓“昂贵”Expensive意思是一次真实评估就可能对应一次物理实验、一次高成本仿真或者一次难以并行的大规模数值计算所谓“组合优化”Combinatorial Optimization意思是决策变量往往是离散的例如 0-1 选择、排序、分配、装配所谓“约束多目标”则意味着研究者不仅要同时优化多个彼此冲突的目标还要满足可行性约束。把这三件事叠加在一起问题立刻就从“难”变成了“非常难”。从工程视角看这类问题并不罕见。背包问题Knapsack Problem、车辆路径问题Vehicle Routing Problem、作业车间调度Job-shop Scheduling Problem这些经典对象往往都可以落入这一框架。真正麻烦之处在于许多现有多目标进化算法Multi-Objective Evolutionary Algorithms, MOEAs默认目标函数和约束函数要么显式可写、要么廉价可算而现实世界偏偏经常不是这样。作者抓住了两个关键痛点。第一约束处理并不容易。传统罚函数Penalty Function方法虽然朴素但罚参数高度依赖问题本身调不好就会把搜索引向歧途。第二搜索机制也并不容易。离散、多目标、昂贵评估三者叠加以后既要避免盲目精确计算又要防止代理模型把算法带偏这对优化器本身提出了更苛刻的要求。已有代理辅助进化算法Surrogate-Assisted Evolutionary Algorithm, SAEA大多集中在连续、无约束问题上即便有一些工作开始触及离散问题往往也还是直接拿连续代理模型去近似离散结构针对性不足。作者因此提出既然随机森林天然适合处理离散变量为什么不把它和多目标粒子群结合起来再为“约束判别”和“粒子更新”各补上一块更合适的机制这就是本文的动机所在。三、核心方法与创新点3.1 核心思想这篇论文的中心思想其实很清楚用随机森林替代大量昂贵的真实评估用粒子群优化维持较强的全局搜索能力再用专门为约束和离散变量设计的策略把“代理误差”与“离散搜索”这两个老大难问题压住。从结构上看RFMOPSO 由三层组成。第一层是随机森林代理模型分别近似每个目标和每个约束第二层是多目标粒子群优化器负责在代理空间里推进搜索第三层是两项关键修正其一是逻辑回归Logistic Regression 自适应随机排序做约束处理其二是自适应状态更新策略把连续 PSO 的速度-位置思想改造成适合 0-1 离散变量的更新规则。3.2 图 1粒子“飞行”机制的直观含义在进入作者的改进之前先看标准粒子群优化Particle Swarm Optimization, PSO的思想。PSO 的经典图景并不复杂粒子一方面受自身历史最好位置影响另一方面受群体最好位置吸引于是会在“个体认知”Individual Cognition与“社会交互”Social Interaction之间不断折中。图 1粒子的飞行模式The flight mode of the particles。图中展示了当前位置、速度影响、个体最优、群体最优与更新方向之间的关系。这张图的意义在于提醒我们PSO 的精髓从来不是“随机乱飞”而是“带记忆的受引导搜索”。本文后面的改进基本都围绕着如何在离散空间里保留这种“受引导性”。3.3 问题形式化作者讨论的是一般形式的约束多目标组合优化问题可以写成min⁡F(x)(f1(x),…,fm(x))T \min F(x) (f_1(x), \dots, f_m(x))^TminF(x)(f1​(x),…,fm​(x))Ts.t. G(x)(g1(x),…,gc(x))T≤0 \text{s.t. } G(x) (g_1(x), \dots, g_c(x))^T \le 0s.t.G(x)(g1​(x),…,gc​(x))T≤0其中(x) 是由离散、有限元素组成的决策向量。因为多个目标通常彼此冲突所以并不存在一个在所有目标上同时最优的单点解我们真正追求的是帕累托解集Pareto Set, PS及其对应的帕累托前沿Pareto Front, PF。3.4 创新点一用随机森林做代理模型作者选择随机森林Random Forest, RF而不是克里金Kriging、径向基函数网络Radial Basis Function Network, RBFN或神经网络Artificial Neural Network, ANN判断是有道理的。原因不在于随机森林“更高级”而在于它更贴合离散变量的结构特征。树模型对 0-1 变量、分段规则和非线性交互的表达往往更自然这比把离散空间硬塞进连续回归框架里要踏实得多。图 2随机森林的生成过程The generation process of the random forest。图中展示了作者的代理思路从训练样本中自助采样Bootstrap Sampling构造多棵分类与回归树Classification and Regression Tree, CART最终取多个树输出的平均作为预测结果。对于本文问题作者为每个目标和每个约束分别训练一个随机森林因此总共需要构造 (mc) 个代理模型。这一步的价值非常直接把昂贵真实评估替换成便宜得多的近似评估。但作者也很清楚代理模型不可能没有误差因此他们进一步利用均方根误差Root Mean Square Error, RMSE去修正由代理预测得到的目标值。若记第 (j) 个目标上的 RMSE 为 (e_j)则最小化问题中的预测值会被向“更保守”的方向修正以降低误判风险。3.5 创新点二逻辑回归修正约束边界代理模型最容易犯错的地方往往不是显然可行或显然不可行的区域而是可行边界附近。这正是本文处理约束的第一处亮点作者没有简单依赖代理给出的约束值 (g_i(x))而是再用逻辑回归Logistic Regression去估计一个候选解“成为可行解的概率”。其形式为Pexp⁡(β0β1x1⋯βhxh)1exp⁡(β0β1x1⋯βhxh) P \frac{\exp(\beta_0 \beta_1x_1 \cdots \beta_hx_h)} {1 \exp(\beta_0 \beta_1x_1 \cdots \beta_hx_h)}P1exp(β0​β1​x1​⋯βh​xh​)exp(β0​β1​x1​⋯βh​xh​)​当预测可行概率达到阈值文中取 0.95时作者会据此修正约束边界把原来 (g_i(x)\le 0) 的判别调整成 (g_i(x)\le \theta_i)。这一步看似只是“边界平移”本质上却是在说代理模型对于约束的判断不值得被完全相信尤其是靠近边界时必须做统计校正。这一点很重要。很多代理优化算法失败不是因为优化器太弱而是因为它们把代理输出当成了事实。本文至少在约束问题上保留了一种必要的怀疑精神。3.6 创新点三自适应随机排序标准随机排序Stochastic Ranking, SR的核心思想是在比较两个解时以某个概率选择“按目标优劣排”以另一个概率选择“按约束违背程度排”。它的优点在于避免了罚函数的繁琐调参但它的问题同样明显那个概率若是固定的就难以适应不同搜索阶段。作者的改进是把原先固定的可行性排序概率 (P_f) 改为随个体状态动态变化的值Pf(i)11exp⁡(−(FV(i)−FC)) P_f(i) \frac{1}{1\exp(-(FV(i)-FC))}Pf​(i)1exp(−(FV(i)−FC))1​这里(FV(i)) 表示个体的约束违反程度(FC) 表示经逻辑回归校正得到的可行性修正量。直觉上说违反约束越严重算法就越应该按“约束”来排而如果一个解只是轻微触碰边界过早把它扔掉反而可能损失潜在优解。这一步的思想并不花哨但很扎实不要把“目标优化”和“约束满足”当成静态二选一而要把它们视作搜索过程中的动态权衡。3.7 创新点四离散粒子的自适应状态更新标准 PSO 的位置更新是连续的但本文面对的是 0-1 组合变量不能直接照搬。因此作者引入了一个基于速度的概率映射把速度先通过 Sigmoid 函数转成取 1 的概率再据此更新粒子状态P[xid(t1)1]S[vid(t1)] P[x_{id}(t1)1] S[v_{id}(t1)]P[xid​(t1)1]S[vid​(t1)]S(vid(t))11exp⁡(−vid(t)) S(v_{id}(t)) \frac{1}{1\exp(-v_{id}(t))}S(vid​(t))1exp(−vid​(t))1​如果映射值靠近 1则对应位置更可能变成 1如果靠近 0则更可能变成 0如果恰在中间则再借助随机数打破平局。这样的更新机制本质上把“连续速度”变成了“离散选择倾向”既保留了 PSO 的记忆和引导又避免了将离散变量粗暴连续化。图 3随机森林辅助自适应多目标粒子群优化RFMOPSO流程图Flowchart of the RFMOPSO algorithm。这张图是全文最重要的结构图。它清楚展示了算法主循环初始化训练数据 → 构建目标/约束代理模型 → 代理评估粒子 → 逻辑回归做约束校正 → 自适应随机排序选父代 → 更新个体最优与全局最优 → 用自适应状态更新、交叉与变异产生新解 → 再用模型管理策略更新代理。换句话说RFMOPSO 不是一个单点改进而是一套彼此配合的系统工程。四、实验与结果分析4.1 数据集与实验设置作者使用了 10 个多目标背包问题MOKP实例决策变量规模从 10 到 100 不等目标数为 2 或 3。背包问题模型写成max⁡fj∑i1hvijxi,xi∈{0,1}, 1≤j≤m \max f_j \sum_{i1}^{h} v_i^j x_i,\quad x_i\in\{0,1\},\ 1\le j\le mmaxfj​i1∑h​vij​xi​,xi​∈{0,1},1≤j≤ms.t. ∑i1hwixi≤W \text{s.t. } \sum_{i1}^{h} w_i x_i \le Ws.t.i1∑h​wi​xi​≤W其中(w_i) 是物品重量(v_i^j) 是第 (i) 个物品在第 (j) 个目标上的价值(W) 是背包容量。作者假设每次精确评估都很昂贵因此把“总精确评估次数”视作主要计算预算。4.2 表 1参数设置实验参数并不复杂但很关键。作者设置种群规模为 100最大精确评估次数为 2000其中前 1000 次用于建模后 1000 次用于优化交叉概率为 1变异概率为 0.4随机森林每个模型使用 100 棵 CART。表 1RFMOPSO 的参数设置The parameter settings of RFMOPSO。ParametersDefinitionValue(N_p)Population size100(P_c)Cross probability1(P_m)Mutation probability0.4(P_\theta)Feasibility probability0.95(k)The number of CARTs100(t)Splitting tolerance of CARTs(1e^{-4}\ast \sigma^2)(EF_{max})Maximum exact evaluations2000从这里可以看出作者刻意把总体预算控制得比较紧这对于代理优化研究是合理的如果精确评估可以无限做那么代理模型也就没什么存在意义了。4.3 基线模型作者选取了两类基线。第一类是通用多目标进化算法MOEAs包括 MOPSO、NSGA-IINon-dominated Sorting Genetic Algorithm II和 MOEA/DMulti-Objective Evolutionary Algorithm based on Decomposition第二类是已有的随机森林辅助方法 RFCMOCO。这样的比较设置是合理的因为它既考察“代理辅助是否有必要”也考察“本文改进是否优于同类代理方法”。4.4 自适应随机排序是否真的有用这篇论文最先验证的不是整个算法而是其中一块关键部件自适应随机排序。我很赞成这种做法。把系统拆开来做消融Ablation比只报总成绩更有说服力。图 4在一个 3 目标、20 物品的 MOKP 实例上两种排序策略的平均选择准确率Average selection accuracy of the two different ranking strategies。从图中可以看到无论代理模型使用 1000 个还是 1500 个随机样本训练自适应随机排序的曲线都明显高于原始随机排序尤其在中后期提升更明显。作者据此指出选择准确率最高可提升到约 85%。这说明动态概率机制确实更善于处理“约束/目标如何平衡”的问题。值得注意的是训练样本从 1000 增加到 1500 后排序效果又有所提升。这一结果并不意外代理模型更准排序当然更稳。但它也提醒我们本文性能的一部分仍然是建立在足够好的代理建模之上的。4.5 自适应状态更新是否真的有用图 5两种状态更新策略在超体积Hypervolume, HV与最大误差Maximum Error, ME指标上的表现HV value and ME value of the two different strategies。作者把带有自适应位置更新的 AMOPSO 与随机位置更新的 RMOPSO 进行比较。结果是在早期两者差距不大但从大约第 20 代开始AMOPSO 在 HV 和 ME 两项指标上都逐渐拉开差距。换言之本文提出的离散状态更新机制并不是一个装饰性的改写而是真的提升了粒子的搜索引导质量。这个结果的解释也符合直觉离散空间里的粒子若没有合理的状态更新规则很容易退化为“带惯性的随机翻转”而一旦更新机制能够更精确地将速度映射到位置选择搜索过程就会更像真正的优化而不是受噪声驱动的游走。4.6 总体结果RFMOPSO 到底强在哪里表 2RFMOPSO、RFCMOCO、MOPSO、NSGA-II、MOEA/D 在各 MOKP 实例上的 HV 值。从作者的统计看RFMOPSO 在 10 个实例中有 7 个取得最优 HVRFCMOCO 在其余 3 个实例中领先。对一篇新算法论文而言这样的结果是相当像样的它并非“全盘碾压”但优势已经足够稳定且并不局限于单一规模。图 6所有算法在 2 目标或 3 目标 MOKP 上的 HV 值The HV values for all the algorithms。图 6 的信息很清楚代理辅助算法整体上优于不带代理的基础进化算法说明在昂贵评估条件下引入代理建模是值得的而在代理辅助方法之间RFMOPSO 又优于 RFCMOCO说明本文的优化器设计和约束处理策略并非可有可无。另外作者也指出在传统 MOEAs 中NSGA-II 通常优于 MOPSO而 MOEA/D 在这类离散受约束问题上表现最弱。这并不奇怪。MOEA/D 更依赖分解权重在目标空间中的均匀性但面对复杂可行域与离散结构时这种优势不一定能兑现。表 3RFMOPSO、RFCMOCO、MOPSO、NSGA-II、MOEA/D 在各 MOKP 实例上的 IGDInverted Generational Distance值。IGD 越小越好。从表 3 看RFMOPSO 在 10 个实例中的 7 个上取得最优RFCMOCO 在另外 3 个上领先。这个结果与 HV 的结论基本一致说明算法优势并不是某个单一指标下的偶然现象。图 7所有算法在 2 目标或 3 目标 MOKP 上的 IGD 值The IGD values for all the algorithms。从趋势图看随着决策变量数量增加所有算法的 IGD 都会上升但 RFMOPSO 上升得最慢这说明它在问题规模扩大时仍保留了更好的逼近能力。这一点尤其重要因为小规模问题上的漂亮结果往往在稍大规模下就会破功而本文的优势恰恰是在规模变大后更加明显。表 4RFMOPSO、RFCMOCO、MOPSO、NSGA-II、MOEA/D 在各 MOKP 实例上的 MEMaximum Error值。ME 指标反映与参考解集之间的最大偏差。从表 4 可以看出RFMOPSO 相比 RFCMOCO 通常略优而相较三种通用 MOEAs 的优势更明显。作者也坦率指出在 10–30 个决策变量的小规模实例上这种优势并不算特别大真正的差距是在问题规模扩大后逐步显现出来的。这个结论是可信的因为“代理快速收敛”的协同效应往往需要更复杂的问题才能充分显现。4.7 运行时间性能提升是否靠“更慢”换来的表 5RFMOPSO 与 RFCMOCO 的 HV 和运行时间对比The HV and Running Time values of RFMOPSO and RFCMOCO。这张表非常关键。很多代理优化论文的尴尬之处在于它们确实优化得更好但代价是算法本身更复杂、总时间反而更高。本文的结果则较为讨喜RFMOPSO 在多数基准上不但解更好而且耗时更少。图 8两种代理辅助进化算法SAEAs在 2 目标或 3 目标 MOKP 上的运行时间Runtime of the two SAEAs on MOKPs with 2 or 3 objectives。图中显示RFMOPSO 通常比 RFCMOCO 更快收敛。作者特别提到在一个 10 个物品、3 个目标的小实例上RFMOPSO 的总运行时间甚至会更长但这是因为它在 30 代左右就已经接近最优却仍然被统一跑满了 100 代。也就是说那里的“更慢”并不是算法本身低效而是实验协议下的表面现象。五、论文贡献如果要把这篇论文的贡献压缩成三句话那么我会这样概括。第一它把随机森林RF真正放到了一个离散、受约束、昂贵评估的多目标优化框架里而不是把连续代理模型生硬挪用到组合问题上。第二它没有停留在“代理 优化器”的简单拼接而是认真处理了代理辅助算法最容易失真的两个地方约束边界与离散状态更新。逻辑回归修正边界自适应随机排序处理可行性权衡这两步都不是噱头而是切中要害。第三它的实验呈现出一种相对可信的节制没有声称在所有场景下都压倒性领先也没有回避小规模问题上的优势有限恰恰相反作者展示的是一种更值得相信的叙事——在问题复杂度真正上来之后RFMOPSO 的结构性优势才逐渐显现。六、个人思考这篇文章给我最大的启发不在于“随机森林 粒子群”这个组合本身而在于它体现了一种正确的方法论当问题是离散的就不要假装它是连续的当代理模型是不可靠的就不要假装它是真实函数当约束边界最脆弱就应该把力气花在边界上。这三点恰恰是很多代理优化工作最容易偷懒的地方。当然这篇论文也并非没有可以继续推进之处。首先实验对象主要还是 MOKP 基准虽然足以说明方法有效但离真实工业问题还有一步距离。若能在更具结构性的实际场景——例如调度、路径规划、资源配置——上给出验证结论会更硬。其次随机森林虽然适合离散变量但其不确定性表达能力仍然比较粗糙若未来能结合更明确的代理不确定性度量Uncertainty Quantification模型管理策略可能会更稳健。再者当前的对比对象虽然合理但若能补充与更多现代离散代理优化方法的比较论文的说服力还会更强。但即便如此我仍然愿意给这篇文章一个相当正面的评价。它没有发明一个华而不实的宏大框架而是认真地把三个小而关键的问题——代理选择、约束处理、离散更新——一一补齐。对于优化研究而言这往往比空泛地喊“统一框架”更可贵。真正推动算法前进的常常不是壮丽的口号而是这些看上去不那么耀眼、却恰好卡在瓶颈处的改进。