Summary

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

2013

Session Number:C1L-C

Session:

Number:370

Synchronous Exponential Chaotic Tabu Search for Analog-Digital Hybrid Parallel Hardware Systems

Akihito Toyoda,  Yoshihiko Horio,  Kazuyuki Aihara,  

pp.370-373

Publication Date:

Online ISSN:2188-5079

DOI:10.15248/proc.2.370

PDF download (280.6KB)

Summary:
Exponential chaotic tabu search is an effective method for solving combinatorial optimization problems. Several modifications such as synchronous updating of the neuronal states has been introduced to try to take advantage of parallel processing in analog-digital hybrid hardware systems. Exponential chaotic tabu search often involves a 2-opt exchange. However, multiple neurons may fire during synchronous update, which prevents the unique determination of the target for 2-opt exchange. To overcome this problem, several neuron selection methods have been proposed, in which neurons are sorted according to the values of their internal states, but these are computationally intensive. These methods are also not suited to a quick and compact hardware implementation because of complicated parameter settings and physical restrictions in hardware devices.
In this paper, we propose a simplified synchronous exponential chaotic tabu search algorithm which is suitable for analog-digital hybrid parallel hardware implementation. First, we modify the chaotic neuron model. Second, we exclude global couplings between chaotic neurons, which impose a heavy hardware burden. Finally, we take into account all the possible restrictions and properties of hardware systems. Furthermore, we can optimize the performance simply by adjusting the external threshold value of the neurons. We confirm the efficiency of the proposed method for quadratic assignment problems through numerical simulations.

References:

[1] M. Hasegawa, T. Ikeguchi and K. Aihara, “A novel chaotic search for quadratic assignment problems,” European Journal of Operational Research, vol. 139, pp. 543-556, 2002.

[2] N. Yokota, Y. Horio, K. Aihara and M. Hasegawa, “A modified synchronous exponential chaotic tabu search for quadratic assignment problems,” Tech. Rep. IEICE, vol. NLP107, no. 561, pp. 49-54, 2008.

[3] A. Shirakuma, Y. Horio and K. Aihara, “An improved neuron selection technique in an exponential chaotic tabu search hardware system for large quadratic assignment problems,” in Proc. Int. Workshop on Nonlinear Circuit and Signal Processing, CD-ROM 2009.

[4] T. Kawamura, Y. Horio and M. Hasegawa, “Mutual information analyses of chaotic neurodynamics driven by neuron selection methods in synchronous exponential chaotic tabu search for quadratic assignment problems,” ICONIP 2010, Part I, LNCS 6443, pp. 49-57, 2010.

[5] Akihito Toyoda, Yoshihiko Horio and Kazuyuki Aihara, “An Improved Exponential Chaotic Tabu Search in Quadratic Assignment Problems for Parallel Hardware Implementation, ” Tech. Rep. IEICE, vol. 112, no. 6, NLP2012-3, pp. 13-18, 2012.

[6] R. E. Burkard, S. E. Karisch and F. Rendl, “QAPLIB -A quadratic assignment problem library,” http://www.opt.math.tu-graz.ac.at/qaplib/