动态多目标优化研究综述

A Survey on Dynamic Multi-Objective Optimization

现实生活中,存在许多动态多目标优化问题(Dynamic Multi-objective Optimization Problems,DMOPs),这类问题的目标函数之间相互矛盾,并且目标函数、约束或者参数都可能随着时间的变化而发生变化.这种随时间不断变化的特性,给解决DMOPs带来了挑战,算法不仅要能够追踪到最优解,同时还要求算法能够快速地对发生的变化做出响应.本文对动态多目标优化(Dynamic Multi-objective Optimization,DMO)的研究进行了比较全面的综述,具体内容如下:(1)描述了DMO的相关理论背景;(2)阐述了DMOPs的分类并对现有的基准问题做了分类归纳;(3)详细讨论了DMO研究的发展概况;(4)对DMO算法的性能评价指标进行了归类介绍;(5)通过实验对比了主流DMO算法的性能;(6)总结了DMO算法在一些领域的应用;(7)分析了解决DMOPs存在的挑战以及诸多难题.

In real life,there are many dynamic multi-objective optimization problems(DMOPs),in which the objective functions restrict each other and the objective functions,constraints or parameters may change over time.This changing property with time brings challenges to solving DMOPs.The algorithm not only needs to track the optimal solution,but also needs to respond to changes in the environment quickly.This paper gives a comprehensive review of the research on dynamic multi-objective optimization(DMO),including the following contents.(1)This paper first introduces the relevant theoretical background of DMO,including the definition of DMOP,the definition of Pareto-optimal set(PS)and Pareto-optimal front(PF).(2)This paper shows the classification of DMOPs and summarizes the existing benchmark functions according to the different characteristics of problems,for instance the change types,the shape of PS or the shape of PF,the relationship between the variables,change in the number of objective functions,change in the dimension of the decision vectors,whether there are constraints and so on.(3)Based on the simple analysis of general framework of solving DMOPs,this paper discusses the research status of the dynamic multi-objective optimization algorithms(DMOAs)in detail.When solving a DMOP,if the environment changes,the algorithm must be able to detect the changes of environment sensitively and respond to the changes occurred in the environments effectively;if the environment does not change,the algorithm should track the Pareto optimal solutions of the current environment as quickly and accurately as possible.Therefore,an environmental change detection operator,an environmental change response strategy and an excellent static multi-objective optimization algorithm are three indispensable parts of a DMOA.Thus,the discussion of the status of DMOAs also based on the above three parts.Specially,the review of response strategies mainly includes the diversity introduction strategy,diversity maintenance strategy,prediction strategy,memory-based strategy,self-adaptive response strategy and some new response strategies based on special models such as transfer learning and support vector machine.It is worth noting that we have analyzed the advantages and disadvantages of each method.(4)The main purpose of performance evaluation is to evaluate the convergence and diversity of DMOAs.In this paper,the performance metrics are classified and introduced according to whether the metric is for evaluation convergence,evaluation diversity or comprehensive evaluation convergence and diversity.(5)This paper compares the performance of some mainstream DMOAs through empirical studies,finding each algorithm has more or less shortcomings and cannot solve every DMOP perfectly.(6)This paper summarizes some practical application cases of DMOAs,such as control problem,scheduling problem,mechanical design problem,image segmentation problem,resource management problem,path optimization problem.(7)Finally,this paper proposes the challenges and the existing problems in solving the DMOPs.On one hand,it is difficult to design efficient and effective environmental change detection operators and environmental change response strategies to solve some complex DMOPs.On the other hand,the research of DMO and practical application are disconnect,most of the existing DMOAs can only handle theoretical DMOPs.