Summary

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

2013

Session Number:C1L-C

Session:

Number:354

Efficiency of Chaotic Search and Realization of Ideal Search for Combinatorial Optimization

Mikio Hasegawa,  

pp.354-357

Publication Date:

Online ISSN:2188-5079

DOI:10.15248/proc.2.354

PDF download (310KB)

Summary:
This paper shows the causes of effectiveness of the chaotic noise for combinatorial optimization problems, and realizes ideal searches based on the theory in its background. Our previous works showed that effective chaotic noise for combinatorial optimization has negative autocorrelation. It has been also shown in a previous research that such negative autocorrelation in asynchronous sequences minimizes the cross-correlation among them. By applying such dynamics to asynchronously updated combinatorial optimization algorithms, cross-correlation among the heuristic operations becomes lowest and ideally complex search can be realized. In this paper, such ideal searches are applied to the Hopfield-Tank neural networks and the 2-opt methods. The results clearly show that the negative autocorrelation dynamics minimizes the cross-correlation among the heuristic operations and such ideal complex searches have highest performance. The proposed scheme does not require careful parameter settings to maximize its performance even for the large-scale problems.

References:

[1] N. Metropolis et al., J. Chem. Physics, 21, 1087, 1953.

[2] F. Glober et al., Annals. of Oper. Res., 41, 3-28, 1993.

[3] H. Nozawa, Chaos, 2, 377-386, 1992.

[4] M. Hasegawa et al., Physical Review Letters, 79, 2344-2347, 1997..

[5] M. Hasegawa et al., Neural Networks, 15, 111-123, 2002.

[6] M. Hasegawa et al., Euro. J. Oper. Res., 139, 543-556, 2002.

[7] M. Hasegawa et al., IEICE Trans. E80-A, 206-213, 1997.

[8] G. Mazzini et al., Electronics Letters, 35, 1054, 1999.

[9] T. Kohda et al., Proc. IEEE ISCAS, V, 225-228, 2000.

[10] J. J. Hopfield and D. W. Tank, Biological Cybernetics, 52, 141-152, 1985.

[11] M. Hasegawa et al., IEICE Trans. Commun., E91-B, 110-118, 2008.

[12] R. Burkard et al., J. Global Optimization, 10, 391-403, 1997.

[13] K. Umeno and A. Yamaguchi, IEICE Trans., E85-A, 849-852, 2002.

[14] G. Reinelt, ORSA J. on Computing, 3, 376-384, 1991.