Evolutionary Algorithm Using Random Immigrants for the Multiobjective Travelling Salesman Problem

This paper addresses the Multiobjective Travelling Salesman Problem (MoTSP) with the aim to study the effects of including random immigrants in the population of solutions processed by the evolutionary algorithm. Random immigrants are typically used in evolutionary optimization in order to increase the diversity of the population and to allow the algorithm to explore a larger area of the search space. Introducing random immigrants incurs a certain overhead which is especially significant in combinatorial optimization, because local search procedures are usually employed, which, while effective in improving the solutions, are computationally expensive. In this paper several strategies of introducing new specimens are tested with the aim of improving the effectiveness of the optimization process given a limited computation time. In the experiments the proposed approach was tested on kroABnnn instances of the MoTSP. It was found to improve the results of multiobjective optimization in terms of both the hypervolume and the IGD indicators. The most effective immigration strategy turned out to be to decrease the number of immigrants with time. (C) 2021 The Authors. Published by Elsevier B.V.