Cespe UnB

Editorial Assistants:
W. Abrahão
G. Oliveira
L. Salgueiro

Editorial Technical Support:
D. H. Diaz
M. A. Gomez
J. Barbosa

Editorial management and production:
SOLGRAF Editora
solgraf@gmail.com






95/105= 0.91


1,1

Evolutionary dynamics of extremal optimization

doi: 10.6062/jcis.2011.02.02.0033(Free PDF)

Authors

Stefan Boettcher

Abstract

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.

Keywords

self-organized criticality, extremal dynamics, evolutionary processes, combinatorial optimization, spin glasses.

References

[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 (ICPR’02), 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.

Search










Combining wavelets and linear spectral mixture model for MODIS satellite sensor time-series analysis
doi: 10.6062/jcis.2008.01.01.0005
Freitas and Shimabukuro(Free PDF)

Riddled basins in complex physical and biological systems
doi: 10.6062/jcis.2009.01.02.0009
Viana et al.(Free PDF)

Use of ordinary Kriging algorithm and wavelet analysis to understanding the turbidity behavior in an Amazon floodplain
doi: 10.6062/jcis.2008.01.01.0006
Alcantara.(Free PDF)

A new multi-particle collision algorithm for optimization in a high performance environment
doi: 10.6062/jcis.2008.01.01.0001
Luz et al.((Free PDF)

Reviewer Guidelines
(Under Construction)
Advertisers/Sponsors
Advertises Media Information