Hirotaka NIITSUMA and Shin ISHII
λ-Opt Neural Approaches to Quadratic Assignment Problem
Abstract:In this paper, we propose new analog neural methods to combinatorial optimization problems, in particular, quadratic assignment problem. Our proposed methods are based on an analog version of the λ-opt heuristics, which simultaneously changes assignments for λ elements in a permutation. Since we can take a relatively large λ value, our new methods can achieve a middle-range search over the possible solutions, and this helps the system neglect shallow local minima and escape from local minima. In experiments, we have applied our methods to relatively large-scale (N=80～150) QAPs. Results have shown that our new methods are comparable to the present champion algorithms, and for two benchmark problems, they are able to obtain better solutions than the previous champion algorithms.