Lagrangian object relaxation neural network for combinatorial optimization problems

详细信息    查看全文

• 作者：Hiroki Tamura ; Zongmei Zhang ; Xinshun Xu ; Masahiro Ishii and Zheng Tang
• 刊名：Neurocomputing
• 出版年：2005
• 出版时间：2005
• 年：2005
• 卷：68
• 期：Complete
• 页码：297-305
• 全文大小：203 K

文摘

We propose a Lagrangian object relaxation technique that can obtain a more near-optimal solution for the traveling salesman problem (TSP). It consists of two stages. First, a feasible solution is calculated and second, a more near-optimal solution is calculated by a Hopfield neural network (HNN). The Lagrangian object relaxation technique can help the HNN escape from the local minimum by correcting Lagrangian multipliers. The Lagrangian object relaxation neural network is analyzed theoretically and evaluated experimentally through simulating the TSP. The simulation results based on some TSPLIB benchmark problems show that the proposed method can find 100 % valid solutions which are near-optimal solutions.