Summary

Proceedings of the 2012 International Symposium on Nonlinear Theory and its Applications

2012

Session Number:C1L-C

Session:

Number:582

Effectiveness of Chaotic Dynamics with Negative Autocorrelation and its Applications to Combinatorial Optimization Problems

Tomohiro Kato,  Mikio Hasegawa,  Kazuyuki Aihara,  

pp.582-585

Publication Date:

Online ISSN:2188-5079

DOI:10.15248/proc.1.582

PDF download (484.9KB)

We analyze effectiveness of a metaheuristic approach, which utilizes ideal spatio-temporal chaotic dynamics generated by Lebesgue Spectrum Filter (LSF). In the previous researches on the additive chaotic noise to the heuristic searches for combinatorial optimization problems, it has been shown that the chaotic sequences with negative autocorrelation improve the performance of asynchronously updated algorithms. The effectiveness of chaos can be understood by the conventional theory of the chaotic CDMA, which showed that the cross-correlation between the sequences with negative autocorrelation becomes lowest. The spatio-temporal chaotic searching dynamics with such lowest cross-correlation has been shown effective to improve asynchronously updated combinatorial optimization algorithms. In this paper, as asynchronously updated combinatorial optimization algorithms, we apply the LSF to the 2-exchange method, the 2-opt method, the Lin-Kernighan method, and the Oropt method, and analyze the spatio-temporal dynamics of them. Our numerical simulation results show that the cross-correlation of all above heuristic methods could be minimized and their performance can be improved by using negative autocorrelation.

[1] H. Nozawa, “A neural network model as a globally coupled map and applications baced on chaos,” Chaos, vol. 2, no. 3, pp.337-386, 1992.

[2] L. Chen, K. Aihara, “Chaotic Simulated Annealing by a Neural Network Model with Transient Chaos,” Neural Networks, vol. 8, no. 6, pp.915-930, 1995.

[3] Y. Hayakawa, A. Marumoto, and Y. Sawada, “Effects of the chaotic noise on the performance of a neural network model for optimize at ion problems,” Journals of the American Physical Society, Phys. Rev. E 51, pp. 2693-R2696 1995.

[4] M. Hasegawa, T. Ikeguchi, and K. Aihara, “Solving large scale traveling salesman problem by chaotic neurodynamics,” Neural Networks, vol. 15, pp.271-283, 2002.

[5] M. Hasegawa, T. Ikeguchi, T. Matozaki, K. Aihara, An Analysis on Additive Effects of Nonlinear Dynamics for Combinatorial Optimization,” IEICE Trans. Fundamentals, vol. E80-A, pp. 206-212, 1997.

[6] M. Hasegawa, K. Umeno, “Solvable Performances of Optimization Neural Networks with Chaotic Noise and Stochastic Noise with Negative autocorrelation,” Lecture Notes in Computer Science (International Conference on Neural Information Processing), vol. 4984, pp. 693-702, 2008.

[7] G. Mazzini et al., “Interference minimization by autocorrelation shaping in asynchronous DS-CDMA systems: chaosbased spreading is nearly optimal,” Electronics Letters, vol. 35, no. 13, pp.1054-1055, 1999.

[8] T. Kohda, H. Fujisaki, “Pursley’s aperiodic crosscorrelation functions revisited,” IEEE Transactions on Circuits and Systems I-Fundamental Theory and Applications, vol. 50, pp.800-805, 2003.

[9] K. Umeno, A.Yamaguchi, “Construction of Optimal Chaotic Spreading Sequence Using Lebesgue Spectrum Filter,” IEICE Trans. Fundamentals, vol. E85-A, no. 4, 849-852, 2002.

[10] M. Hasegawa, “Realizing Ideal Spatiotemporal Chaotic Searching Dynamics for Optimization Algorithms Using Neural Networks,” Lecture Notes in Computer Science (International Conference on Neural Information Processing), vol. 6443, pp. 66-73, 2010.

[11] M. Hasegawa, “Improving Performance of Heuristic Methods using Chaotic Dynamics with Negative autocorrelation,” IEICE, vol. 111, no. 106, NLP2011-35, pp. 59-64, 2011.

[12] E. Taillard, “Robust taboo search for the QAP,” Parallel Computing, vol. 17, pp. 443-455, 1991.

[13] QAPLIB: http://www.seas.upenn.edu/qaplib/

[14] S. Lin and B. Kernighan. “An effective heuristic algorithm for the traveling-salesman problem,” Operations Research, pp. 498-516, 1973.

[15] I. Or, “Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking,” Ph.D thesis. Department of Industrial Engineering and Management Science, Northwestern University, Evanston, Illinois, 1967.

[16] TSPLIB: http://elib.zib.de/pub/Packages/mp-testdata/tsp/tsplib/tsplib.html