2021

Conférence

Procedia Computer Science Volume 192, 2021, Pages 4337-4347

In the last few years, there has been an increasing interest in Random Constraint Satisfaction Problems (CSP) from both experimental and theoretical points of view. To consider a variant instance of the problems, we used a random benchmark. In the present paper, some work has been done to find the shortest Hamiltonian circuit among specified nodes in each superimposed graph (SGs). The Hamiltonian circuit is a circuit that visits each node in the graph exactly once. The Hamiltonian path may be constructed and adjusted according to specific constraints such as time limits. A new constraint satisfaction optimization problem model for the circuit Hamiltonian circuit problem in a superimposed graph has been presented. To solve this issue, we propose amelioration for the genetic algorithm using Dijkstra’s algorithm, where we create the improved genetic algorithm (IGA). To evaluate this approach, we compare the CPU and fitness values of the IGA to the results provided by an adapted genetic algorithm to find the shortest Hamiltonian circuit in a superimposed graph.

@article{BOUAZZI20214337,
title = {Application of an improved genetic algorithm to Hamiltonian circuit problem},
journal = {Procedia Computer Science},
volume = {192},
pages = {4337-4347},
year = {2021},
note = {Knowledge-Based and Intelligent Information & Engineering Systems: Proceedings of the 25th International Conference KES2021},
issn = {1877-0509},
doi = {https://doi.org/10.1016/j.procs.2021.09.210},
url = {https://www.sciencedirect.com/science/article/pii/S1877050921019499},
author = {Khaoula Bouazzi and Moez Hammami and Sadok Bouamama},
keywords = {Optimization, Combinatorial problems, Metaheuristics, Hamiltonian circuit problem, Genetic algorithm, Dijkstra},
abstract = {In the last few years, there has been an increasing interest in Random Constraint Satisfaction Problems (CSP) from both experimental and theoretical points of view. To consider a variant instance of the problems, we used a random benchmark. In the present paper, some work has been done to find the shortest Hamiltonian circuit among specified nodes in each superimposed graph (SGs). The Hamiltonian circuit is a circuit that visits each node in the graph exactly once. The Hamiltonian path may be constructed and adjusted according to specific constraints such as time limits. A new constraint satisfaction optimization problem model for the circuit Hamiltonian circuit problem in a superimposed graph has been presented. To solve this issue, we propose amelioration for the genetic algorithm using Dijkstra’s algorithm, where we create the improved genetic algorithm (IGA). To evaluate this approach, we compare the CPU and fitness values of the IGA to the results provided by an adapted genetic algorithm to find the shortest Hamiltonian circuit in a superimposed graph.}
}