Evolutionary algorithm hybridized with local search and intelligent seeding for solving multi-objective Euclidian TSP. (1st November 2021)

• Record Type: Journal Article
• Authors: Agrawal, Anubha; Ghune, Nitish; Prakash, Shiv; Ramteke, Manojkumar
• Is Part Of: Expert systems with applications. Volume 181(2021)
• Publication Date: 2021-11-01
• Subjects: Genetic algorithm -- Meta-heuristic algorithms -- Travelling salesman problem -- Nearest neighbor -- 2-opt -- Seed solutions; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2021.115192
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: A hybrid algorithm combining local heuristics with genetic algorithm is developed. Seeding of corner solutions is used to improve the performance. Twenty-five multi-objective TSP problems solved. Problems having objectives up to four and number of cities up to 10, 000 are solved. Abstract: Multi-objective Euclidian TSP (ETSP) has several practical applications such as mobile computing and maritime surveillance. This problem has complexity not only in terms of combinatorial constraints but also in terms of multiple objectives. The local heuristic-based algorithms are extremely efficient in solving the single-objective ETSPs. However, their efficacy is limited in solving the multi-objective ETSPs due to the presence of multiple objectives. To bridge this gap, a two-stage evolutionary algorithm (TSEA) is developed to solve multi-objective ETSPs. In this algorithm, the first stage involves the use of a hybrid local search evolutionary algorithm (HLS-EA) which incorporates the local heuristic of nearest neighbor and 2-opt in the framework of real-coded NSGA-II to solve the individual objectives of multi-objective ETSP. These individual single-objective solutions which represent the corner solutions of the Pareto optimal front are used in the second stage as seed solutions in seeded HLS-EA (SHLS-EA) for solving the corresponding multi-objective ETSP. The developed algorithm is tested on 17 two-objective, 6 three-objective, and 2 four-objective ETSPs to show the superior performance over multi-objective variants of the Lin-Kernighan algorithm. Also, the developed algorithm is compared with several variants of DE and GA to illustrate the superior performance over the variants of evolutionary algorithms. Further, the algorithm is extended to the multi-objective ETSPs up to 10, 000 cities.