Multistage extremal optimization for hard travelling salesman problem

Guo-Qiang Zeng, Yong-Zai Lu and Wei-Jie Mao

Physica A: Statistical Mechanics and its Applications, 2010, vol. 389, issue 21, 5037-5044

Abstract: The adjustable parameters of probability distributions adopted by extremal optimization (EO) and its modified versions play a critical role in controlling their performances. Unlike the traditional static probability distribution based strategy, this paper presents a novel method called multistage EO to explore the configuration space of hard travelling salesman problem (TSP) by using different values of the parameters in different stages. This method is to optimize with multi-start techniques starting from random states in the first stage. In all later stages, it always selects the best configuration obtained from the last stage as the initial one for optimization in the current stage. The superior performance of the proposed method is proved by the experimental tests with the well-known hard TSP instances.

Keywords: Multistage; Extremal optimization; Control parameters; Probability distributions; Travelling salesman problem (search for similar items in EconPapers)
Date: 2010
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037843711000645X
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:389:y:2010:i:21:p:5037-5044

DOI: 10.1016/j.physa.2010.07.018

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 ().