The quadratic assignment problem (QAP) is one of the combinatorial optimization problems which belong to a class of NP-hard. To solve QAP, various algorithms for rinding near optimal solutions have already been proposed. Among them, the Hopfield-Tank neural network approach is very attractive from a viewpoint of an application of neural dynamics to combinatorial optimization, this approach is not so effective because of local minimum problem. To overcome this problem, a method which uses chaotic dynamics has already been proposed. On the other hand, to avoid undesirable local minima, dynamical noise is often used. In this paper, we combine these two approaches-chaotic dynamics and dynamical noise-to realize an effective approach for solving combinatorial optimization problems: we add dynamical noise to chaotic neural network for solving QAP. The results show that when the small amount of dynamical noise is added, the solving performance is much improved. We also analyze the influence of dynamical noise to the chaotic dynamics, and show that dynamical noise diversifies the searching states to explore much better solutions.
展开▼
