Summary
International Symposium on Nonlinear Theory and its Applications
2010
Session Number:B2L-A
Session:
Number:B2L-A5
Double-Assignment Method Driven by Chaotic Neurodynamics for Quadratic Assignment Problems
Kazuaki Shibata, Yoshihiko Horio,
pp.301-304
Publication Date:2010/9/5
Online ISSN:2188-5079
Summary:
A quadratic assignment problem (QAP) is one of the NP-hard combinatorial optimization problems. Local search methods such as the 2-opt method are used to solve the QAPs. However, they are usually trapped in the local minima. In order to solve this problem, heuristic methods such as the tabu search have been proposed. In particular, the exponential chaotic tabu search shows exellent performance. On the other hand, we proposed a double-assignment method which searches sub-optimal solutions through a solution space including infeasible solutions. We have shown that the proposed method is superior to the 2-opt algorithm in solving the QAPs. In the double-assignment method, an infeasible solution is first constructed from the initial solution by assigning two elements to one index. Then, a feasible solution is composed from the infeasible solution. In this paper, we improve the double-assignment method for the QAPs by introducing chaotic neurodynamics. We show numerical simulation results comparing the performance of the improved method and the original double- assignment method.