Summary

International Symposium on Nonlinear Theory and its Applications

2010

Session Number:B3L-A

Session:

Number:B3L-A2

Slide-and-Insert Assignment Method with Chaotic Dynamics for Quadratic Assignment Problems

Yusuke Sakamoto,  Yoshihiko Horio,  

pp.382-385

Publication Date:2010/9/5

Online ISSN:2188-5079

DOI:10.34385/proc.44.B3L-A2

PDF download (73.7KB)

Summary:
A quadratic assignment problem (QAP) is an NP-hard combinatorial optimization problem. Some heuristic algorithms for the QAPs is proposed in order to find the sub-optimum solutions efficiently. In this paper, we propose a novel heuristic algorithm for the QAPs based on the Or-opt algorithm used for traveling salesman problems. The proposed method introduces a slide-and-insert operation for the assignments of the elements in the QAP. Furthermore, we improve the proposed algorithm by combining it with the 2-opt algorithm. We also use chaotic dynamics instead of the random numbers. Numerical simulation results, which compare the solving performance of the proposed algorithms with the random numbers and the chaotic dynamics, are shown.