Ant Local Search and its efficient adaptation to graph colouring

M Plumettaz, D Schindl and N Zufferey ()
Additional contact information
M Plumettaz: Columbia University
D Schindl: Geneva School of Business Administration (HEG)
N Zufferey: University of Geneva

Journal of the Operational Research Society, 2010, vol. 61, issue 5, 819-826

Abstract: Abstract In this paper, we propose a new kind of ant algorithm called Ant Local Search. In most ant algorithms, the role of each ant is to build a solution in a constructive way. In contrast, we propose to consider each ant as a local search, where at each step and in concordance with all ant algorithms, each ant modifies the current solution by the use of the greedy force and the trail systems. We also propose ways to reduce the computational effort associated with each ant decision. Such a new and general ant methodology is then applied to the well-known k-colouring problem, which is NP-hard. Computational experiments give evidence that our algorithm is competitive with the best colouring methods.

Keywords: heuristics; networks and graphs; artificial life; optimization (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1057/jors.2009.27 Abstract (text/html)
Access to full text is restricted to subscribers.

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:pal:jorsoc:v:61:y:2010:i:5:d:10.1057_jors.2009.27

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/jors.2009.27

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().