多模态多目标进化算法研究综述

张佳星，褚晓凯，屈俊峰

（1.湖北文理学院计算机工程学院，襄阳 441053；2.河北地质大学信息工程学院，石家庄 050031；3.河北地质大学人工智能与机器学习研究室，石家庄 050031）

0 引言

在现实工程和科学研究中，许多优化问题需要同时满足多个目标，这类问题被称为多目标优化 问 题（multi-objective optimization problems，MOPs）［1-2］。近年来，使用进化算法（evolutionary algorithms，EAs）求解MOPs是比较流行且有效的方法。这类方法可以很好地在目标空间搜索到完整且分布均匀的Pareto前沿面，从而为决策者提供更合适的选择。然而，随着研究的深入和问题的复杂化，不仅目标空间的维度越来越高，而且Pareto最优解集（pareto optimal set，PS）和Pareto前沿面之间的映射关系变得越来越复杂，PS在决策空间的分布呈多模态性，即两个或多个不同的Pareto最优解对应同一Pareto前沿位置，这样的问题被称为“多模态多目标优化问题（multi-modal multi-objective optimization problems，MMOPs）”［3］。虽然找到Pareto前沿面就可以满足优化要求，但是获得更多PS可以为决策者提供更多的备选方案，以便做出更好的选择。在实际应用和科学研究中存在着许多MMOPs，例如流水车间调度问题［4］中存在多种优化方案同时满足调度要求、游戏地图生成问题［5］中存在多个候选映射空间都符合设计师的需求、选址优化问题［6］中有多个区域同时满足选址要求、特征选择问题［7］中相同的特征个数同时对应多个特征组合，等。因此，研究如何结合EAs的思想求解MMOPs具有很重要的现实意义。

近年来，研究者们提出了不同的多模态多目标进化算法（multi-modal multi-objective evolution⁃ary algorithms，MMOEAs）来求解 MMOPs。根据其算法特征，大致可以将其分为基于Pareto支配、基于目标分解、基于新型进化范例三大类。……