基于偏好的交互多目标进化优化方法

殷昭宁

连云港润众制药有限公司，江苏连云港 222069

0 引言

近几年，结合决策者的偏好解决多目标优化问题，成为进化计算领域的研究热点之一。这是因为，已有进化多目标优化方法的目的是找到收敛性好且分布均匀的Pareto最优解集，而在实际应用中，往往仅需要找到一个最满意解或最满意区域。因此，和单目标优化问题相比，在多目标优化中，有两个同等重要的任务：搜索Pareto优化解和选择最满意解[1]。2个任务之间的先后关系决定了3种不同的方法：第一种是先决策后优化方法，也称为先验方法[2]；第二种是先优化再决策方法，也称为后验方法[3]；第三种是边优化边决策方法，也称为交互方法[4]。

与先验法和后验法相比，交互方法有如下3个优点[1]：1）交互方法所需的偏好信息比先验方法简单得多；2）交互方法比后验方法需要更少的计算开销；3）当决策者控制搜索进程时，可以通过介入进程了解潜在的候选解，对最终的选择更加自信。因此，交互方法是一种解决实际多目标优化问题非常有前景的方法。下面介绍近两年有关交互方法的研究工作。

1 基于偏好的交互进化多目标优化算法

1.1 简单交互方法

张华军等提出一种最大化个人偏好的多目标优化进化算法，首先采用加权法将多目标优化问题转化为单目标优化问题，再利用遗传算法进行全局搜索，在满足个人偏好约束条件下，每一代进化结束后，通过求解一个约束优化问题，获得能够使种群综合适应度具有最大方差的权重组合，从而最大化个人偏好[4]。

Chen 等采用基于偏好导向的精英选择策略选择父代个体，从而提供给用户更多接近其偏好的解[5]。

Chaudhuri和Deb提出一种解决多目标优化问题的交互集成方法，该方法结合多种多目标进化算法和一些普遍且有效的多准则决策方法，用边优化边决策过程，开发了功能强大、使用灵活的交互多目标优化和决策进化算法软件[6]。

利用决策者关于目标相对重要性的偏好信息，Rachmawati和 Srinivasan 提出了目标相对重要性的数学模型和提取算法，并给出了将提取的偏好信息和NSGA-II结合的3种方法[7]。

1.2 构建偏好的代理模型

从近2年的相关工作可以看出，在优化过程中，定期与决策者交互，逐渐获取其偏好信息，并构建偏好函数的代理模型成为研究热点。方法可分为3类：基于机器学习的方法、基于拟合的方法和基于偏好凸锥或多面体锥的方法。

结合基于事例的有监督在线学习策略和进化算法，Krettek等提出一个新的多目标交互进化优化方法。决策者每隔n代参与决策，将当前Pareto最优解集聚类后，决策者对类中心两两比较，利用两两相似性学习决策者的偏好[8]。

Battiti 和 Passerini采用反应搜索方法，提出一种多目标交互进化算法，该算法将在线机器学习作为自适应优化策略的组成部分，实现边优化边学习[9]。

上述2种方法在优化过程中逐渐获取决策者的偏好信息，并用机器学习方法构建决策者偏好的代理模型，以学习决策者的偏好，指导种群的后续进化。

Deb等提出一种基于偏好的渐进多目标交互进化算法。在进化固定代数后，通过逐渐获取决策者的偏好信息，构建满足该信息的严格增加价值函数，利用基于偏好的占优关系和终止条件，引导算法向最满意解搜索。该方法可以得到决策者偏好的显式表示，但需事先给出函数的类型[10]。

在文献[10]的基础上，Sinha等提出一个拟合用户偏好价值函数的广义多项式函数，该函数的乘积项个数是任意可变的，这样可以有效减少价值函数不能拟合决策者偏好的情形[11]。

上述2种方法利用决策者定期提供的偏好信息，用一个优化过程拟合决策者的偏好，该方法可以得到决策者偏好的显式表示，但需事先给出函数的类型。

Fowler等针对多目标背包问题，提出一种拟凹偏好函数的多目标交互进化优化方法。该方法定期提交部分非被支配解给决策者，利用获得的偏好信息生成偏好锥，对决策者没有评价的非被支配解隐式排序，引导算法向决策者偏好的区域搜索，最终得到决策者的最满意解[12]。

Sinha等利用多面体锥修改占优关系，提出一个基于偏好的多目标进化优化方法。通过逐渐获取决策者的偏好信息不断修改多面体锥，用该多面体锥缩减搜索空间，在感兴趣区域中找到更好的优化解[13]。

上述2种方法的共同特点是：不需要知道决策者偏好的显式形式，利用决策者从候选解对应的目标函数值中选出的最差值或最好值和其他候选解对应的目标函数值，在目标空间中构建反映决策者偏好的凸锥或多面体锥，基于该隐式偏好函数改进非被支配解的排序策略，将搜索集中在感兴趣的区域。

2 结论

在构建偏好代理模型的方法中，前2种需要对所有候选解两两比较其优劣，相比较而言，基于凸锥或多面体锥的方法，仅需要从候选解对应的目标函数值中选出最好值和最差值，该方法可以大大减轻决策者的比较负担，同时也可以避免因选择合适显式偏好函数而带来的难题。因此，构建反应决策者偏好的多面体是值得进一步研究的方向。

此外，虽然上面述及的方法可以有效解决实际多目标优化问题，得到决策者的最满意解，数值实验也证实了上述方法对很多目标优化问题优越的求解能力，但只适用于确定参数多目标优化问题。对于区间参数多目标优化问题，至今还没有结合决策者偏好的求解方法，更不必说边优化边决策的方法。进化计算的权威期刊《IEEE Transactions on Evolutionary Computation》 2010年10月特刊表明，以后的多目标优化算法将广泛地在优化过程中融入决策者的偏好信息[14]。因此，结合决策者偏好信息解决区间参数多目标优化问题，是富有挑战性和有意义的工作。

[1]Branke J., Deb K., Miettinen K., Slowinski R.. Multi-objective Optimization Interactive and Evolutionary Approaches (LNCS 5252)[M].Heidelberg:Springer, 2008.

[2]Zio E., Baraldi P., Pedroni N..Optimal power system generation scheduling by multi-objective genetic algorithms with preferences[J].Reliability Engineering and System Safety, 2009, 94(2): 432-444.

[3]Lee D.H., Kim K.J., Koksalan M..A posterior preference articulation approach to multiresponse surface optimization[J].European Journal of Operational Research, 2011, 210(2): 301-309.

[4]张华军，赵金，王瑞.最大化个人偏好的多目标优化进化算法[J].信息与控制，2010, 39(2): 212-217.

[5]Chen Z.H., Zhuang Z. Q., Huang F.H., Lee J.S..User-preference-oriented multi-objective optimization algorithm[C].In Proceedings of 2010 International Computer Symposium, 2010: 1045-1049.

[6]Chaudhuri S., Deb K..An interactive evolutionary multi-objective optimization and decision making procedure[J].Applied Soft Computing, 2010,10(2): 496-511.

[7]Rachmawati L., Srinivasan D..Incorporating the notion of relative importance of objectives in evolutionary multi-objective optimization[J].IEEE transactions on evolutionary computation, 2010, 14(4):530-546.

[8]Krettek J., Braun J., Hoffmann F., Bertram T., Ewald T., Schubert H.G., Lausch H..Interactive evolutionary multi-objective optimization for hHydraulic valve controller parameters[C].In Proceedings of the IEEE/ASME International Conference on Advanced Intelligent Mechatronics, 2009, 816-821.

[9]Battiti R., Passerini A..Brain computer evolutionary multiobjective optimization: A genetic algorithm adapting to the decision maker[J].IEEE transactions on evolutionary computation, 2010, 14(5):671-687.

[10]Deb K., Sinha A., Korhonen P., Wallenius J..An interactive evolutionary multi-objective optimization method based on progressively approximated value functions[R].Kanpur Genetic Algorithms Laboratory,Department of Mechanical engineering, Indian Institue of Technology, Kanpur, India, KanGAL Report Number 2009005, 2009.

[11]Sinha A., Deb K., Korhonen P., Wallenius J..Progressively interactive evolutionary multiobjective optimization method using generalized polynomial value functions[C].In Proceedings of the IEEE Congress on Evolutionary Computation, 2010: 1-8.

[12]Fowler J.W., Gel E.S., Koksalan M.M.,Korhonen P., Marquis J.L., Wallenius J..Interactive evolutionary multi-objective optimization for quasiconcave preference functions[J]. European Journal of Operational Research, 2010, 206(2): 417-425.

[13]Sinha A., Deb K., Korhonen P., Wallenius J..An interactive evolutionary multi-objective optimization method based on polyhedral cones[C].In Proceedings of Learning and Intelligent Optimization Conference,2010, 6073: 318-332.

[14]Deb K., Koksalan M..Guest Editorial: Special issue on preference-based multi-objective evolutionary algorithms[J].IEEE transactions on evolutionary computation, 2010, 14(5): 669-670.