Analysis of multiobjective evolutionary algorithms on the biobjective traveling salesman problem (1,2)
- PDF / 1,117,468 Bytes
- 22 Pages / 439.642 x 666.49 pts Page_size
- 88 Downloads / 202 Views
Analysis of multiobjective evolutionary algorithms on the biobjective traveling salesman problem (1,2) Xinsheng Lai1
· Yuren Zhou2
Received: 9 August 2019 / Revised: 6 June 2020 / Accepted: 21 July 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Multiobjective evolutionary algorithms have been successfully used to deal with multiobjective combinatorial optimization problems for more than two decades. However, we know little about the performance of multiobjective evolutionary algorithms on multiobjective combinatorial optimization problems in theory so far, especially on NP-hard ones from real-world, since Pareto curves are often of exponential size, meanwhile, evolutionary algorithms rely heavily on the use of randomness and are hard to understand from a theoretical point of view. In this paper, we theoretically investigate the performance of two simple multiobjective evolutionary algorithms with different population diversity mechanisms on the biobjective traveling salesman problem (1,2). It is found that one of them can efficiently find a 32 -approximation Pareto curve for the problem, the best result so far. At the same time, these two multiobjective evolutionary algorithms are proved to be superior to a multiobjective local search algorithm, and the multiobjective local search algorithm is also proven to outperform these two multiobjective evolutionary algorithms as well. Finally, the population diversity is proved to be helpful in reducing the expected runtime of multiobjective evolutionary algorithm. Keywords Multiobjective evolutionary algorithm · Multiobjective traveling salesman problem · Approximation algorithm · Population diversity · Combinatorial optimization problem
1 Introduction The biobjective traveling salesman problem (TSP)(1,2) is a biobjective version of the TSP(1,2) problem, in which each edge has a couple of distances and each is one or two. Though it is a special case of the multiobjective TSP problem, the biobjective TSP(1,2) Xinsheng Lai
xsl2001 [email protected] 1
School of Computer Science and Engineering, Shaoxing University, Shaoxing, 312000, Zhejiang, China
2
School of Data and Computer Science, Sun Yat-sen University, Guangzhou, 510006, China
Multimedia Tools and Applications
problem is NP-hard as the single objective TSP(1,2) problem is NP-hard [18]. Therefore, we tend to believe that we cannot find all non-dominated solutions in a polynomial runtime for the biobjective TSP(1,2) problem. Practically, we are interested in approximation algorithms that are able to find in a polynomial runtime a set of solutions that (1 + )-dominate all other solutions, where > 0. For two solutions X and Y of the biobjective TSP(1,2) problem, if fi (X) ≤ (1 + )fi (Y ), where fi (i = 1, 2) is the ith objective function, then we say that X (1 + )-dominates Y . Angel et al. [1] proposed an approximation algorithm called the biobjective local search (BLS) for the biobjective TSP(1,2) problem, which is capable of finding a set of solutions that (1+ 12 )domina
Data Loading...
