Chen, Jiayin (The University of New South Wales), Nurdin, Hendra I. (The University of New South Wales)

Generalized Simulated Annealing with Sequentially Modified Cost Function for Combinatorial Optimization Problems

Scheduled for presentation during the Regular Session "Learning, Fuzzy and Neural Systems" (FC1), Friday, November 29, 2019, 15:45−17:45, WZ Building Room WZ416

2019 Australian & New Zealand Control Conference (ANZCC), November 27-29, 2019, Auckland, New Zealand

This information is tentative and subject to change. Compiled on April 24, 2024

Abstract

Recent efforts to develop hybrid quantum-classical algorithms for solving combinatorial problems have rekindled interest in revisiting heuristic classical optimization algorithms and exploring possibilities for improving them. A popular approach for finding good solutions to combinatorial problems is local search. In spite of its efficiency, if the search space is rugged, local search often gets trapped in unsatisfactory local optima. On the other hand, global search meta-heuristic algorithms, such as classical simulated annealing, guarantee asymptotic convergence in probability distribution to global optima. Despite its theoretical appeal, practical performance of classical simulated annealing is often sensitive to implementation details. In this paper, we revisit classical simulated annealing and propose a generalization in which the annealing is guided by a sequentially modified cost function. We prove asymptotic convergence to global optima and give an example choice of the modified cost function. We test the proposed algorithm with this example modified cost function on the traveling salesman problem. Numerical results suggest that the performance of this method is more robust to the initial temperature choice. Furthermore, the method demonstrates a significant efficiency gain without compromising its performance.