An innovative method to escape local minima using quantum system degeneracy in Simulated Annealing
|
Full Text |
Pdf
|
|
Author |
Bouchaib Aylaj, Mostafa Belkasmi, Said Nouh and Fouad Ayoub
|
|
e-ISSN |
1819-6608 |
|
On Pages
|
1472-1483
|
|
Volume No. |
19
|
|
Issue No. |
24
|
|
Issue Date |
January 25, 2025
|
|
DOI |
https://doi.org/10.59018/122481
|
|
Keywords |
simulated annealing, TSP, degenerate quantum, combinatorial optimization.
|
Abstract
Simulated Annealing (SA) is often used to provide satisfactory solutions to solving combinatorial problems. However, the SA is limited by its tendency to get stuck in local minima, which often prevents the global optimal solution from being reached for large or very complex problems. To overcome this obstacle, we present a new method inspired by the properties of degenerate quantum systems, named Degenerate Quantum Simulated Annealing (SA-DQS). This innovative approach exploits the coexistence of several quantum states of the same energy; this multiplicity of states is advantageous because it allows to finding of several solutions with identical energies, thus increasing the chances of discovering and building a promising solution among them, and of getting out of the traps of local minima more efficiently. The traveling salesman problem (TSP) is used as an application benchmark to validate the effectiveness of SA-DQS. Compared to standard simulated annealing (SA-S), SA-DQS showed superior performance on multiple instances of TSP. On average, the solutions provided by SA-DQS are equal to or closer to the optimum known in TSPLIB, in addition, it also offers a shorter computation time compared to that of other heuristic methods.
Back