Summary

Proceedings of the 2013 International Symposium on Nonlinear Theory and its Applications

2013

Session Number:C1L-C

Session:

Number:362

A Chaotic Local Search Algorithm with Adaptive Exchange of Elements for Quadratic Assignment Problems

Akio Watanabe,  Kaori Kuroda,  Kantaro Fujiwara,  Tohru Ikeguchi,  

pp.362-365

Publication Date:

Online ISSN:2188-5079

DOI:10.15248/proc.2.362

PDF download (283.8KB)

Summary:
The quadratic assignment problem (QAP) is one of the NP-hard combinatorial optimization problems. Then, it is required to develop an effective approximation algorithm for finding near optimal solutions in realistic time. In this paper, we proposed a local search algorithm for solving QAP by introducing searching property of the Lin-Kernighan algorithm. We also applied chaotic dynamics to the proposed local search algorithm to escape from undesirable local minima. To evaluate solving performance of the proposed algorithm, we compared the performance of the proposed algorithm with those of the conventional algorithms. As a result, the solving performance of the proposed algorithm with chaotic dynamics exhibits smaller gaps from optimal solutions than the conventional algorithms.

References:

[1] “QAPLIB - A quadratic assignment problem library,” URL: http://www.opt.math.tu-graz.ac.at/qaplib/

[2] S. Lin and B. Kernighan: “An effective heuristic algorithm for the traveling salesman problem,” Operational Research, Vol.21 pp.498-516, 1973.

[3] M. Hasegawa, T. Ikeguchi and K. Aihara: “Combination of chaotic neurodynamics with the 2-opt algorithm to solve traveling salesman problems,” Physical Review Letters, Vol.79, No.12, pp.2344-2347, 1997.

[4] T. Kimura and T. Ikeguchi, “A new algorithm for packet routing problems using chaotic neurodynamics and its surrogate analysis,” Neural Computing and Applications, Vol16, No.6, pp.519-526, 2007.

[5] T. Matsuura and T. Ikeguchi, “Chaotic motif sampler: detecting motifs from biological sequences by using chaotic neurodynamics,” Nonlinear Theory and Its Applications, Vol 1, No.1, pp.207-220, 2010.

[6] S. Motohashi, T. Matsuura, T. Ikeguchi, and K. Aihara: “The Lin-Kernighan algorithm driven by chaotic neurodynamics for large scale traveling salesman problems,” Lecture Notes in Computer Science, Vol.5769, pp.563-572, 2009.

[7] K. Aihara, T. Takabe, and M. Toyoda, “Chaotic neural networks,” Physics Letters A, Vol.144, No.6, pp.333-340, 1990.