Studying the effect of Eliminating Repeated Individuals from the Population in a Genetic Algorithm: Solution Perspectives for the Travelling Salesman Problem

Abstract

The Travelling Salesman Problem (TSP) is one of the main routing problems in the Logistics and Supply Chain Management fields. Given its computational complexity, metaheuristics are frequently needed to solve it to near-optimality. In this aspect, Genetic Algorithms (GA) are promising methods, however, their search performance depends of populations of solutions which can increase computational processing. Thus, the management of this component is subject to adaptations to reduce its computational burden and improve overall performance. This work explores on the elimination of repeated individuals within the population which may represent a significant fraction of its size and do not add valuable information to the solution search mechanisms of the GA. This cleaning process is expected to contribute to solution diversity. Experiments performed with different TSP test instances support the finding that this cleaning process can improve the convergence of the GA to very suitable solutions (within the 10% error limit). These findings were statistically validated.