Summary
International Symposium on Nonlinear Theory and its Applications
2009
Session Number:B2L-B
Session:
Number:B2L-B1
Effects of Complex Chaotic Dynamics for Combinatorial Optimization
Mikio Hasegawa,
pp.-
Publication Date:2009/10/18
Online ISSN:2188-5079
Summary:
Chaotic dynamics has been shown effective for combinatorial optimization. In one of such approaches to optimization problems, the chaotic dynamics is utilized to efficiently drive a heuristic algorithm, which can be applied to large-scale problems. In this paper, the searching dynamics of such a chaotic search driving heuristic algorithm, which is a kind of hybrid dynamical systems, is analyzed. First, the performance of the chaotic search is compared with the stochastic search and the tabu search, and effectiveness of the chaotic dynamics is confirmed. Second, the searching dynamics of those algorithms are quantified by estimating expansion of a small difference added to their search, which corresponds to the largest Lyapunov exponent. By such an analysis, it has been clarified that the chaotic search expands a small difference slower but gradually makes it larger than the other compared heuristic approaches. It is also shown that the chaotic dynamics, which expands the difference the most slowly, corresponding to smaller Lyapunov exponent, has the best performance.