Evolutionary Multimodal Multiobjective Optimization for Traveling Salesman Problems

Yiping Liu

doi:10.1109/TEVC.2023.3239546

Evolutionary Multimodal Multiobjective Optimization for Traveling Salesman Problems

2024-04-01

14

PRE

AI

DOI：10.1109/TEVC.2023.3239546

Original

Original request for help

Save

Abstract

En 中文

Multimodal multiobjective optimization problems (MMOPs) are commonly seen in real-world applications. Many evolutionary algorithms have been proposed to solve continuous MMOPs. However, little effort has been made to solve combinatorial (or discrete) MMOPs. Searching for equivalent Pareto-optimal solutions in the discrete decision space is challenging. Moreover, the true Pareto-optimal solutions of a combinatorial MMOP are usually difficult to know, which has limited the development of its optimizer. In this article, we first propose a test problem generator for multimodal multiobjective traveling salesman problems (MMTSPs). It can readily generate MMTSPs with known Pareto-optimal solutions. Then, we propose a novel evolutionary algorithm to solve MMTSPs. In our proposed algorithm, we develop two new edge assembly crossover operators, which are specialized in searching for superior solutions to MMTSPs. Moreover, the proposed algorithm uses a new environmental selection operator to maintain a good balance between the objective space diversity and decision space diversity. We compare our algorithm with five state-of-the-art designs. Experimental results convincingly show that our algorithm is powerful in solving MMTSPs.

Keywords:

Pareto optimization

Optimization

Evolutionary computation

Generators

Traveling salesman problems

Search problems

Approximation algorithms

Combinatorial optimization

evolutionary multimodal multiobjective optimization

test problems

traveling salesman problem (TSP)

Evolutionary Multimodal Multiobjective Optimization for Traveling Salesman Problems

Abstract

Journal

Organization