Editorial Office:
Management:
R. S. Oyarzabal
Technical Support:
D. H. Diaz
M. A. Gomez
W. Abrahão
G. Oliveira
Publisher by Knobook Pub
doi: 10.6062/jcis.2011.02.02.0033(Free PDF)
Stefan Boettcher
ABSTRACT Dynamic features of the recently introduced extremal optimization heuristic are analyzed. Numerical studies of this evolutionary search heuristic show that it performs optimally at a transition between a jammed and an diffusive state. Using a simple, annealed model, some of the key features of extremal optimization are explained. In particular, it is verified that the dynamics of local search possesses a generic critical point under the variation of its sole parameter, separating phases of too greedy (non-ergodic, jammed) and too random (ergodic, diffusive) exploration. Analytic comparison with other local search methods, such as a Metropolis algorithm, within this model suggests that the existence of the critical point is the essential distinction leading to the optimal performance of the extremal optimization heuristic.
self-organized criticality, extremal dynamics, evolutionary processes, combinatorial optimization, spin glasses.
[1] BOETTCHER S & PERCUS AG. 2000. Artificial Intelligence, 119: 275.
[2] BOETTCHER S & PERCUS AG. 2001. Phys. Rev. Lett., 86: 5211.
[3] BOETTCHER S & PERCUS AG. 2001. Phys. Rev., E 64: 026114.
[4] BOETTCHER S & PERCUS AG. 2004. Phys. Rev., E 69: 066703.
[5] BOETTCHER S. 2003. Phys. Rev., B 67: R060403.
[6] BOETTCHER S. 2005. Eur. Phys. J. B 46: 501.
[7] BOETTCHER S. 1999. J. Phys. A: Math. Gen., 32: 5201.
[8] DALL J & SIBANI P. 2001. Comp. Phys. Comm., 141: 260.
[9] WANG J-S & OKABE Y. 2003. J. Phys. Soc. Jpn., 72: 1380.
[10] BOETTCHER S & SIBANI P. 2005. Eur. Phys. J., B 44: 317.
[11] BOETTCHER S & FRANK M. 2006. Physica A 367: 220.
[12] MANG NG & ZENG C. 2008. J. Comp. Chem., 29: 1762.
[13] MESHOUL S & BATOUCHE M. 2002. Lecture Notes in Computer Science, 2449: 330.
[14] MESHOUL S & BATOUCHE M. 2002. In: 16th International Conference on Pattern Recognition (ICPR02), 3: 30823.
[15] MESHOUL S & BATOUCHE M. 2003. Int. J. Pattern Rec. and AI, 17: 1111.
[16] YOM-TOV E, GROSSMAN A & INBAR GF. 2001. Biological Cybernatics, 85: 395.
[17] SVENSON P. 2004. Proc. SPIE, 5429: 162.
[18] DE SOUSA FL, VLASSOV V & RAMOS FM. 2004. Heat Transf. Eng., 25: 34.
[19] ZHOU T, BAI W-J, CHENG L-J & WANG B-H. 2005. Phys. Rev. E, 72: 016702.
[20] MENAI ME & BATOUCHE M. 2002. In: Proceedings of the International Conference on Artificial Intelligence (IC-AI), pp. 954-958.
[21] MENAI ME & BATOUCHE M. 2003. Lecture Notes in Computer Science, 2718: 592.
[22] MENAI ME & BATOUCHE M. 2003. In: Proceedings of the International Conference on Artificial Intelligence (IC-AI), pp. 257-262.
[23] DUCH J & ARENAS A. 2005. Phys. Rev. E, 72: 027104.
[24] DANON L, DIAZ-GUILERA A, DUCH J & ARENAS A. 2005. J. Stat. Mech.-Theo. Exp., p. P09008.
[25] NEDA Z, FLORIAN R, RAVASZ M, LIBAL A & GYšORGYI G. 2006. Physica A., 362: 357.
[26] ONODY RN & DE CASTRO PA. 2003. Physica A, 322: 247.
[27] KAUFFMAN SA & JOHNSEN S. 1991. J. Theor. Biol., 149: 467.
[28] PERCUS A, ISTRATE G & MOORE C. 2006. Computational Complexity and Statistical Physics (Oxford University Press, New York).
[29] FISCHER KH & HERTZ JA. 1991. Spin Glasses (Cambridge University Press, Cambridge).
[30] BOETTCHER S & GRIGNI M. 2002. J. Phys. A: Math. Gen. 35: 1109.
[31] HEILMANN F, HOFFMANN KH & SALAMON P. 2004. Europhys. Lett., 66: 305.
[32] HOFFMANN KH, HEILMANN F & SALAMON P. 2004. Phys. Rev. E, 70: 046704.
[33] KIRKPATRICK S, GELATT CD & VECCHI MP. 1983. Science, 220: 671.
[34] SALAMON P, SIBANI P & FROST R. 2002. Facts, Conjectures, and Improvements for Simulated Annealing (Society for Industrial & Applied Mathematics).
[35] PALMER RG, STEIN DL, ABRAHAM E & ANDERSON PW. 1984. Phys. Rev. Lett., 53: 958.