Augmented Lagrange chaotic simulated annealing for combinatorial optimization problems

Chaotic simulated annealing (CSA) has recently been proposed and successfully used in solving combinatorial optimization problems by Chen and Aihara. In comparison with the Hopfield-Tank approach. CSA significantly improves the network´s ability to find solutions of good quality and even global minima. However, CSA still uses a penalty term to enforce solution validity like the Hopfield-Tank approach. There exists a conflict between solution quality and solution validity in the penalty approach. In addition, the relative magnitude of the penalty term often needs to be determined by trial-and-error. In this paper we incorporate augmented Lagrange multipliers into CSA, obtaining a method that we call augmented Lagrange chaotic simulated annealing (AL-CSA), which eliminates the need of the penalty term and guarantees solution validity, and at the same time maintains CSA´s solution quality. We demonstrate this method with the 10-city Traveling Salesman Problem