A New Improved Guided Genetic Algorithm for CSOP to Solve the Hamiltonian Circuit Problem in superimposed graphs

This paper presents a systematic approach for obtaining the best Hamiltonian circuit among specified nodes within a given superimposed graph (SG). To address this challenge, we introduce a formalism, Constraint Satisfaction Optimization Problem (CSOP), that finds the minimal Hamiltonian circuit in superimposed graphs. As a resolution method, we used updated versions of the genetic algorithm (GA), the improved GA, and the guided improved GA. After comparison, we find that our algorithm IG2A, combined with guided mutation strategies and improved with Dijkstra’s algorithm, optimizes the circuit-finding process more efficiently. Our contribution lies in developing a new Guided Genetic Algorithm (GGA). The well-known guided mutation strategies and efficient search heuristics enhance the latter. Our approach significantly outperforms the standard genetic algorithm in solving the HCP in superimposed graphs, providing better optimization results and faster convergence.