8.19 多目标优化中的机器学习
多 目 标 优 化 问 题 (MOP, multiobjecitveoptimization problem) 是指含有 2 个或 2 个以上目标函数的优化问题。当目标数多于 3 个时,MOP也常被称作超多目标优化问题。由于多个目标之间通常不协调甚至存在矛盾,MOP 最优解不是单个解而是一个解集。法国经济学家 V. Pareto 最早在经济福利理论研究中提出了多目标优化问题,并引入了 Pareto 最优的概念,因此这个最优解集也被称作 Pareto 最优解集[15] 。对于现实问题,求出Pareto 最优解集的解析表达式是一件极其困难的事情,因此决策者更偏向于获取 Pareto 最优解集的一个逼近,即要求所得解尽可能分布均匀和尽可能靠近 Pareto 最优解集[16] 。
求解多目标优化问题的传统方法包括分解法和分层序列法等方法。与传统方法需要多次运行才能得到 Pareto 解集的逼近不同,EA 等启发式方法能够执行一次而得到整个 Pareto 解集的逼近,因此EA 已成为求解 MOP 的主要方法。目前多目标演化算法 (MOEA,multiobjective EA) 主要包括:基于Pareto 支配关系的算法,利用 Pareto 支配关系来选择后代个体;基于评价指标的算法,利用评价指标来选择后代个体;基于分解的算法,将 MOP 分解为一系列简单的 MOP 或单目标优化问题,同时求解这些简单问题以得到原问题Pareto解集的逼近 [17] 。
MOP Pareto 最优解集在搜索空间呈现出特殊的拓扑特性:可以证明在某些连续性假设前提下,一个包含 m 个目标的连续 MOP Pareto 最优解集在搜索空间形成一个分段连续的 m-1 维流形。如图 3显示,对于含有 2 个目标和 2 维搜索空间的问题,其 Pareto 最优解集形成一个 1 维流形。对于该特性,可以利用流形学习 (manifold learning) 方法来估计 Pareto 最优解集并指导新解产生。文献 [18]利用局部主成分分析 (Local PCA, local principalcomponent analysis)将当前群体划分成多个区域,在每个区域使用PCA来得到其主分量,即低维流形;产生新解时,在低维流形上通过实验设计采样新点,通过逆映射及添加高斯噪音得到搜索空间中的新解。图 4 显示了该方法的基本原理。事实上,除了Local PCA, 其他一些流形学习方法,如生成拓扑映射 (generative topographic mapping) [19] 、 自 组 织映射 (self-organizing map) [20] 等方法均可以用于学习群体隐空间模型。若放松对隐空间流形的假设,则可认为 Pareto 最优解具有某种空间结构或关联关系。机器学习中其他的一些方法,如混合高斯模型[21] 都可以用于学习群体的结构并指引算法搜索。
除学习上述连续 MOP 问题的特性,机器学习在单目标领域的应用也能自然地被拓展到多目标问题。上节所述 EDA、参数选择与调优、代理模型构造技术都在 MOEA 的研究中有所体现,这些机器学习模型包括高斯过程[22-23] 、分类 [24] 、聚类 [25-26] 、负相关学习[26] 、密度估计 [27] 、玻尔兹曼机 [28]等,这些方法在 MOEA 停机条件分析[29] 、新解产生[24-28] 、代理模型构造 [22-23] 、群体选择 [24] 、最优决策[30]等方面辅助 MOEA 提高搜索效率。