算法分析
一句话概括：我研究多目标优化器在什么条件下适合某类问题，以及熟悉的设计选择会在何时悄悄变成负担。
这个问题在多目标组合优化中尤其重要。其搜索空间离散，结构可能与许多流行算法所针对的平滑连续基准问题截然不同；在连续问题上表现出色的算法，可能在这里受挫。
研究目标不是选出一个永远最好的算法，而是理解各种搜索范式在什么条件下有效，让算法选择从习惯变成有依据的判断。
多目标演化算法与局部搜索
多目标演化算法（MOEA）通常是人们首先采用的工具。在离散问题上，邻域容易定义，因此局部搜索是一种自然替代方案。在 GECCO 2024 中，我们在多个多目标组合优化问题上比较了知名 MOEA 与局部搜索启发式方法。
结果并非单一胜负：不同范式会在不同问题、实例设置和计算预算下胜出。最突出的现象是 SEMO 表现强劲——这个极简算法实际上位于演化算法与随机局部搜索之间。
这说明算法家族之间的边界不只是分类，也是一片有价值的设计空间。SEMO 的成功成为我后续许多工作的起点。
简单算法能扩展到多大规模？
早期比较使用的实例相对较小，因此一个自然问题是：当变量数扩大到数百乃至数千时，极简算法还能保持优势吗？
答案是否定的。在多类大规模组合问题上，SEMO 相对 NSGA-II、SMS-EMOA 和 MOEA/D 的收敛速度明显下降。预算足够时，它仍可覆盖广泛的帕累托前沿，却会随着维度增加而越来越慢。主要原因是缺少交叉。加入交叉后，大实例上的收敛会显著加快；即使两个相似解之间的交叉也有效，这并不是通常认为交叉所需要的场景。但它也有代价：交叉会降低种群多样性，使前沿上的解分布不那么均匀。
因此，简单并非普遍的好或坏，而是一种随问题规模变化的取舍。极简算法在小问题中刻意省略的组件，恰好可能是大问题所需；重新加入它，又会以多样性换取收敛速度。真正有用的知识是找出这种转折发生在哪里。
外部档案截断
外部档案保存搜索中发现的非支配解。若不管理，档案可能变得非常大，而决策者通常只需要少量有代表性的方案。因此问题是：
应在什么时候截断档案？
在 GECCO 2025 中，我们比较了即时截断、分批截断，以及始终保留无限档案并只在最后截断。直觉上，无限档案保留的信息最多，应该表现最好；实验却显示，在使用标准 MOEA 种群维护准则时，即时截断通常最好，无限档案反而经常最差。
结论是：“全部保留，最后再决定”并不自动更好。大档案需要专门为子集选择设计的方法，而不是直接借用种群维护规则。
局部搜索行为
局部搜索常被描述为系统过程：选一个解，检查其邻域，发现改进后移动。关于随机与系统多目标局部搜索的工作表明，这种描述可能具有误导性。只随机抽取一个邻居有时更快，即使它可能重复访问；原因是系统扫描的成本取决于有效邻居在搜索过程中如何分布。
所以我把算法比较视为一个行为问题。计算评价次数很重要，但理解有用评价出现在哪里往往更能揭示原因。
面向学习型求解器
这种行为视角也需要用于更新的一类方法。神经组合优化通过训练模型直接构造解，已成为组合问题上演化搜索的重要替代方案。但学习型求解器仍是搜索过程，同样要问：它的景观是什么样？会在哪里停滞？在什么问题条件下真正胜过经典算法？把不同范式的比较扩展到神经求解器，并通过适应度景观分析其行为，是我当前的研究方向。
我关注的特征
这些研究试图识别真正能够预测性能的问题与算法特征：
- 问题是否崎岖、具有欺骗性、受约束或高度多峰；
- 小种群是否可能丢失有前景的区域；
- 外部档案是在承担记忆、搜索材料，还是最终输出；
- 计算预算更偏向广泛探索还是局部精炼；
- 方法的成功来自其主要设计原则，还是隐藏在内部的较小机制。
这类分析把算法选择从黑箱竞赛变成对搜索行为的诊断。
代表论文
完整记录请见论文发表页面。
- M. Li, X. Han, X. Chu, Z. Liang. Empirical Comparison Between MOEAs and Local Search on Multi-objective Combinatorial Optimisation Problems. GECCO, 2024. [PDF] [DOI]
- Z. Cui, Z. Liang, L. M. Pang, H. Ishibuchi, M. Li. When to Truncate the Archive? On the Effect of the Truncation Frequency in Multi-Objective Optimisation. GECCO Companion, 2025. [PDF] [DOI] [arXiv]
- Z. Liang, M. Li. Random is Faster than Systematic in Multi-Objective Local Search. AAAI, 2026. [PDF] [Code]