Summary
International Symposium on Nonlinear Theory and its Applications
2009
Session Number:B1L-B
Session:
Number:B1L-B5
Lyapunov Exponents of Chaotic Neural Network with Dynamical Noise for Solving Quadratic Assignment Problem
Takayuki Suzuki, Shun Motohashi, Takafumi Matsuura, Tohru Ikeguchi,
pp.-
Publication Date:2009/10/18
Online ISSN:2188-5079
Summary:
The quadratic assignment problem (QAP) is one of the most difficult NP-hard combinatorial optimization problems. To solve the QAP, various approximate algorithms for finding near optimal solutions have already been proposed. Among them, a method which uses the Hopfield neural network (HNN) can be applied to find solutions. However, this method cannot always offen gets good performance because it stuck at local minima. To avoid local minima, a method which uses chaotic neural network (CNN) has already been proposed. The method with CNN can solve the QAP effectively and shows good performance. On the other hand, to avoid undesirable local minima, it is possible to inject dynamical noise to a solver. Then, we have already proposed a method which uses both chaotic dynamics and dynamical noise for avoiding local minima. The result shows that when a small amount of dynamical noise is added, the performance becomes high. In this paper, we investigate the performance of the method using several types of dynamical?stochastic and deterministic noise. To analyze the proposed method, we investigate the relation between the performance and the Lyapunov exponents of the CNN with such dynamical noise.