| Presentation | 2013-03-14 A Chaotic Local Search Algorithm with Adaptive Exchange of Elements for Quadratic Assignment Problems Akio WATANABE, Kaori KURODA, Kantaro FUJIWARA, 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 NP-hard combinatorial optimization problems. Then, it is required to develop approximate algorithms for finding near optimal solutions in realistic time. 0n the other hand, to solve traveling salesman problems which is a special case of QAP, the Lin-Kernighan algorithm has been proposed. In this report, we propose an algorithm for solving QAPs by introducing characteristic property of searching process in the Lin-Kernighan algorithm. We also in- troduced chaotic dynamics into the proposed algorithm to escape undesirable local minima. To evaluate solving performance of the proposed method, we compared the performance of the proposed method with that of the conventional methods. As a result, the solving performance of the proposed method with chaotic dynamics exhibits smaller gaps from optimal solutions than the conventional algorithms. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | combinatorial optimization / quadratic assignment problems / local search |
| Paper # | NLP2012-145 |
| Date of Issue |
| Conference Information | |
| Committee | NLP |
|---|---|
| Conference Date | 2013/3/7(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 | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Chaotic Local Search Algorithm with Adaptive Exchange of Elements for Quadratic Assignment Problems |
| Sub Title (in English) | |
| Keyword(1) | combinatorial optimization |
| Keyword(2) | quadratic assignment problems |
| Keyword(3) | local search |
| 1st Author's Name | Akio WATANABE |
| 1st Author's Affiliation | Faculty of Engineering, Saitama University() |
| 2nd Author's Name | Kaori KURODA |
| 2nd Author's Affiliation | Graduate School of Science and Engineering, Saitama University |
| 3rd Author's Name | Kantaro FUJIWARA |
| 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:Brain Science Institute, Saitama University |
| Date | 2013-03-14 |
| Paper # | NLP2012-145 |
| Volume (vol) | vol.112 |
| Number (no) | 487 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |