A Comparison of different crossover operators in genetic algorithms for clusters shortest-path tree problem
Cosmin Sabo, Petrică Claudiu Pop, Adrian Petrovan

Abstract. The clustered shortest-path tree (CluSPT) problem is an extension of the classical shortest path problem, given a graph with the nodes partitioned into several mutually exclusive and collectively exhaustive clusters looks for a shortest-path spanning tree from a predefined source node to all the other nodes of the graph, with the property that every cluster should generate a connected subgraph. Due to the problem’s complexity, different metaheuristic algorithms have been proposed to find good-quality solutions within reasonable computational effort. Between these methods, evolutionary algorithms proved to be the most efficient method for solving the CluSPT problem. The present paper aims to investigate the
effect of different crossover operators on the quality of the achieved solutions by the hybrid genetic algorithm proposed by Petrovan et al. [10], the current state-of-the-art algorithm for the CluSPT problem. Computational experiments were conducted on 46 benchmark instances from the literature. In our computational experiments, we used four variants of crossover operators, which allowed us to perform a comprehensive analysis and comparison of the achieved results, enabling us to thoroughly examine the impact of the crossover operators on the obtained results.

Keywords: genetic algorithms, the clustered shortest path tree problem.

Cosmin Sabo, Petrică Claudiu Pop, Adrian Petrovan, "A Comparison of different crossover operators in genetic algorithms for clusters shortest-path tree problem", , 2023.

Other publications