No Detail Found!

An innovative method to escape local minima using quantum system degeneracy in simulated annealing

Author(s)
Bouchaib Aylaj Computer Sciences, CRMEF-Rabat, Morocco
Mostafa Belkasmi ENSIAS, MED5 University, Morocco
Said Nouh Faculty of Sciences BM, H2C University, Morocco
Fouad Ayoub Computer Sciences, CRMEF-Rabat, Morocco
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.
Publication Details
Page(s) 1472-1483
DOI DOI not available
Published Journal: ARPN Journal of Engineering and Applied Sciences, Volume: 19, Issue: 24, Year: 2024

Request the full text from PASTIC

Keywords
Simulated Annealing, combinatorial optimization, degenerate quantum, TSP
References
Papadimitriou C. H. .1978 .Euclidean traveling salesman problem is NP-complete, Theoretical Computer Science. , : .
Ansari .2016 .Traveling Salesman Problem for a Bidirectional Graph Using Dynamic Programming. 2016 International Conference on Micro-Electronics and Telecommunication Engineering (ICMETE), : 127-132.
Radharamanan R.,Choi L. I. .1986 .A branch and bound algorithm for the traveling salesman and the transportation routing problems Computers and Industrial Engineering. , : .
Yang J.,Wu C.,Lee H. P.,Liang Y. .2008 .Solving traveling salesman problem using generalized chromosome genetic algorithm. Progress in Natural Science, 18(86) : 887-892.
Chun-Wei Tsai,Shih-Pang Tseng,Ming-Chao Chiang,Chu-Sing Yang,Tzung-Pei Hong Yang .2014 .A HighPerformance Genetic Algorithm: Using Traveling Salesman Problem as a Case. The Scientific World Journal. 2014(Article ID 178621), : 14.
Baraglia R.,J. I. Hidalgo R.,Perego R. .2021 .A hybrid heuristics for the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 5(6) : 613-622.
Mustapha A.,Amphawan A. .2021 .An Enhanced Swap Sequence-Based Particle Swarm Optimization Algorithm to Solve TSP. in IEEE Access, 3133493 : 164820-164836.
Cui Y.,Zhong J.,Yang F.,Li S.,Li P. .2020 .MultiSubdomain Grouping-Based Particle Swarm Optimization for the Traveling Salesman Problem. in IEEE Access, 3045765 : 227497-227510.
generalized TSP . .Particle swarm optimization-based algorithms for TSP. , : .
Xing Z.,Tu S. .2020 .A Graph Neural Network Assisted Monte Carlo Tree Search Approach to Traveling Salesman Problem. in IEEE Access, 3000236 : 108418-108428.
Gee A. H.,Prager R. W. .1995 .Limitations of neural networks for solving traveling salesman problems. In IEEE Transactions on Neural Networks, 6(1) : 280-282.
K. J. Man ,Part A,Zhu H.,You X.,Liu S. .2019 .Multiple Ant Colony Optimization Based on Pearson Correlation Coefficient. in IEEE Access, 2915673 : 61628-61638.
Wang Z.,Geng X.,Shao Z. .2009 .An Effective Simulated Annealing Algorithm for Solving the Traveling Salesman Problem. Journal of Computational and Theoretical Nanoscience, 6(7) : 1680-1686.
M. .2018 .Simulated Annealing with Adaptive Neighborhood using Fuzzy Logic Controller. International Conference on Learning and Optimization Algorithms., : .
.2018 .List-Based Simulated Annealing Algorithm with Hybrid Greedy Repair and Optimization Operator for 0-1 Knapsack Problem. in IEEE Access, 2872533 : 54447-54458.
Wang L. .2019 .Enhanced List-Based Simulated Annealing Algorithm for Large-Scale Traveling Salesman Problem. IEEE Access, 7 : 144366-144380.
Shi- Z.,Juan Lin,Ze-jun Zhang,Zhong Zhang .2016 .. , : .
. .List-Based Simulated Annealing Algorithm for Traveling Salesman Problem. 2016(Article ID 1712630), : 12.
Metropolis N.,Rosenbluth A.,Rosenbluth M.,Teller A.,Teller E. .1953 .Equation of state calculations by fast computing machines. Journal of Chemical Physics, 21 : 1987-1091.
Kirkpatrick S.,Gelatt C. D.,Vecchi M. P. .1983 .. , : .
. .Optimization by simulated annealing. Science, 220 : 671-680.
Cerny V. .1985 .A thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of Optimization Theory and Applications, 45 : 41-51.
Kardar M. .2007 .. , : .
0

Citations

0

Downloads

87

Views