| Presentation | 2009-05-15 Solving Quadratic Assignment Problems by Chaotic Neural Network with Dynamical Noise Takayuki SUZUKI, Shun MOTOHASHI, Takafumi MATSUURA, Tohru IKEGUCHI, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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, the Hopfield-Tank neural network approach is attractive from a viewpoint of an application of neural dynamics to combinatorial optimization. However, this approach is not so effective because of the local minimum problem. To solve this problem, a method which uses chaotic dynamics has already been proposed. As a result, this method shows good performance. On the other hand, to avoid undesirable local minima, dynamical noise is often used. Then, we proposed a method which uses two approaches for avoiding local minima-chaotic dynamics and dynamical noise. As a result, when a small amount of dynamical noise is added, the proposed method shows higher performance. In this paper, we investigate the reason why chaotic neural network (CNN) with additive dynamical noise searches good solutions. Then, to quantify chaotic dynamics, we calculate Lyapunov spectra of CNN with dynamical noise, and investigate the relation between the solving performance and Lyapunov exponents. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Quadratic Assignment Problem / Chaotic Neural Network / Dynamical noise |
| Paper # | NLP2009-11 |
| Date of Issue |
| Conference Information | |
| Committee | NLP |
|---|---|
| Conference Date | 2009/5/8(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Nonlinear Problems (NLP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Solving Quadratic Assignment Problems by Chaotic Neural Network with Dynamical Noise |
| Sub Title (in English) | |
| Keyword(1) | Quadratic Assignment Problem |
| Keyword(2) | Chaotic Neural Network |
| Keyword(3) | Dynamical noise |
| 1st Author's Name | Takayuki SUZUKI |
| 1st Author's Affiliation | Graduate School of Science and Engineering, Saitama University() |
| 2nd Author's Name | Shun MOTOHASHI |
| 2nd Author's Affiliation | Graduate School of Science and Engineering, Saitama University |
| 3rd Author's Name | Takafumi MATSUURA |
| 3rd Author's Affiliation | Graduate School of Science and Engineering, Saitama University |
| 4th Author's Name | Tohru IKEGUCHI |
| 4th Author's Affiliation | Graduate School of Science and Engineering, Saitama University |
| Date | 2009-05-15 |
| Paper # | NLP2009-11 |
| Volume (vol) | vol.109 |
| Number (no) | 30 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |