An Analysis on Additive Effects of Nonlinear Dynamics for Combinatorial Optimization

Mikio HASEGAWA  Tohru IKEGUCHI  Takeshi MATOZAKI  Kazuyuki AIHARA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E80-A   No.1   pp.206-213
Publication Date: 1997/01/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Neural Networks
Keyword: 
chaos,  neural networks,  combinatorial optimization problems,  traveling salesman problems,  surrogation,  

Full Text: PDF(635KB)>>
Buy this Article




Summary: 
We analyze additive effects of nonlinear dynamics for conbinatorial optimization. We apply chaotic time series as noise sequence to neural networks for 10-city and 20-city traveling salesman problems and compare the performance with stochastic processes, such as Gaussian random numbers, uniform random numbers, 1/fα noise and surrogate data sets which preserve several statistics of the original chaotic data. In result, it is shown that not only chaotic noise but also surrogates with similar autocorrelation as chaotic noise exhibit high solving abilities. It is also suggested that since temporal structure of chaotic noise characterized by autocorrelation affects abilities for combinatorial optimization problems, effects of chaotic sequence as additive noise for escaping from undesirable local minima in case of solving combinatorial optimization problems can be replaced by stochastic noise with similar autocorrelation.