Optimization with extremal dynamics for the traveling salesman problem

Yu-Wang Chen, Yong-Zai Lu and Peng Chen

Physica A: Statistical Mechanics and its Applications, 2007, vol. 385, issue 1, 115-123

Abstract: By mapping the optimization problems to physical systems, the paper presents a general-purpose stochastic optimization method with extremal dynamics. It is built up with the traveling salesman problem (TSP) being a typical NP-complete problem. As self-organized critical processes of extremal dynamics, the optimization dynamics successively updates the states of those cities with high energy. Consequently, a near-optimal solution can be quickly obtained through the optimization processes combining the two phases of greedy searching and fluctuated explorations (ergodic walk near the phase transition). The computational results demonstrate that the proposed optimization method may provide much better performance than other optimization techniques developed from statistical physics, such as simulated annealing (SA). Since the proposed fundamental solution is based on the principles and micromechanisms of computational systems, it can provide systematic viewpoints and effective computational methods on a wide spectrum of combinatorial and physical optimization problems.

Keywords: Optimization; Extremal dynamics; Simulated annealing; Phase transition; Traveling salesman problem (search for similar items in EconPapers)
Date: 2007
References: View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037843710700684X
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:385:y:2007:i:1:p:115-123

DOI: 10.1016/j.physa.2007.06.014

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().