Evolutionary Computation for Large-scale Multi-objective Optimization: A Decade of Progresses

  • Share:


Many real-world optimization problems involve multiple objectives, which are called multi-objective optimization problems (MOPs). The conflict between the multiple objectives makes it impossible to find a single solution that can optimize all objectives simultaneously. Searching for the best trade-off solutions, called Pareto-optimal solutions, for MOPs is thus critical to a decision maker. Evolutionary algorithms (EAs) are able to approximate the whole set of Pareto-optimal solutions in a single run due to their population-based nature and do not make particular assumptions about problems like continuity or differentiability. Thus, the use of EAs to deal with MOPs have been extensively studied and plenty of powerful multi-objective EAs (MOEA) have been proposed.

 

Scalability of MOEAs, which characterizes the changing trend of algorithm performance with the problem size, is not only a long-standing concern in the evolutionary computation community, but also is critical to whether MOEAs can be applied to broader real-world problems. In the context of MOPs, the number of decision variables and the number of objectives are two key factors for the problem size. Scalability with respect to the number of objectives, referred to as many-objective optimization, has drawn steady attention in past decades and a number of surveys are available.

  

On the other hand, although scalability with respect to the number of decision variables has attracted wide attention, there is no review paper in this regard. In recent years, there has been an increasing interest in the scalability of MOEAs with respect to decision variables, as large-scale MOPs (i.e., MOPs with a large number of decision variables) appear widely in various real-world applications. For example, the training of deep neural networks (DNN) needs to take into account both empirical risks (such as training errors) and structural risks (such as network sparseness), while typical industrial DNNs often contain millions of weights to be trained. Commercial promotion on social networks requires both influence maximization and cost minimization, while the number of nodes involved in real networks (such as Weibo, Facebook, twitter, etc.) can be in the order of millions or even hundreds of millions. Problems recently faced in logistics scheduling, software engineering, pattern mining, and many other fields have also shown the characteristics of large-scale multi-objective optimization problems, leading to an urgent need for efficient and effective approaches.

 

Nonetheless, most current practice of MOEAs has been restricted in MOPs with small-scale decision variables (normally, no more than 30). More recently, empirical studies have shown a severe decrease in efficiency of traditional MOEAs when increasing the number of decision variables. As a result, evolutionary computation for large-scale MOPs has attracted a lot of research effort in the past decade, which mainly focuses on two major problems:

 

1) What are the difficulties associated with large-scale multi-objective optimization? The scalability of MOEAs is determined jointly by their search mechanisms and the problem properties. An in-depth analysis of the specific difficulties associated with different large-scale MOPs when adopting different MOEAs can benefit the evaluation of algorithms, and thereby facilitate the development of new and improved large-scale MOEAs. To this end, there has been some work to systematically explore the scalability of traditional MOEAs and put forward some discoveries about the challenges faced by the algorithms. This paper briefly reviews recent efforts in this aspect.

 

2) How to enhance the scalability of an MOEA? As mentioned above, research on designing MOEAs with high scalability originates from practical needs. To this end, basic ideas include simplifying large-scale MOPs via divide-and-conquer methodology and dimensionality reduction and improving the search ability of MOEAs by rebalancing the exploration and exploitation. From these three aspects, this paper summarizes the advances in scalable algorithm designs. The main focus is on how characteristics of MOPs and scalability challenges are integrated into the design of highly scalable MOEAs.

 

To summarize, this paper focuses on the scalability of MOEAs with respect to the number of decision variables and presents an extensive review of recent progresses on evolutionary computation for large-scale multi-objective optimization in the last decade. We first introduce the study on the capabilities of traditional MOEAs to properly scale when increasing the number of decision variables as well as the difficulties encountered by these algorithms, and then categorize recent developments on scalable MOEAs into three classes based on the key idea used: the divide-and-conquer, dimensionality reduction and enhanced search-based approaches.

 

Download full text:

Evolutionary Computation for Large-scale Multi-objective Optimization: A Decade of Progresses

Wen-Jing Hong, Peng Yang, Ke Tang

https://link.springer.com/article/10.1007/s11633-020-1253-0 

http://www.ijac.net/article/doi/10.1007/s11633-020-1253-0 

 

◇◇◇◇◇◇

For more up-to-date information:

1) WeChat: IJAC

2) Twitter:IJAC_Journal

3) Facebook:International Journal of Automation and Computing

4) Linkedin: Int.J. of Automation and Computing

5) Sina Weibo:IJAC-国际自动化与计算杂志

 

  • Share: