Solving combinatorial optimization problems using augmented lagrange chaotic simulated annealing

• Main Authors: Wang, Lipo., Tian, Fuyu, Soong, Boon Hee, Wan, Chunru
• Other Authors: School of Electrical and Electronic Engineering
• Format: Article
• Language: English
• Published: 2012
• Subjects: DRNTU::Engineering::Electrical and electronic engineering
• Online Access: https://hdl.handle.net/10356/99861; http://hdl.handle.net/10220/8193
• Institution: Nanyang Technological University

Chaotic simulated annealing (CSA) proposed by Chen and Aihara has been successfully used to solve a variety of combinatorial optimization problems. CSA uses a penalty term to enforce solution validity as in the original Hopfield–Tank approach. There exists a conflict between solution quality and solution validity in the penalty approach. It is often difficult to adjust the relative magnitude of the penalty term, so as to achieve a high quality solution which is at the same time valid. To overcome this, we incorporate augmented Lagrange multipliers into CSA, obtaining a method that we call augmented Lagrange chaotic simulated annealing (AL-CSA). Simulation results on two constrained optimization benchmarks derived from the Hopfield–Tank formulation of the traveling salesman problem show that AL-CSA can maintain CSA’s good solution quality while avoiding the potential difficulties associated with penalty terms. Furthermore, AL-CSA’s convergence time is shorter and choice of system parameters is easier compared to CSA.