Documents disponibles écrits par cet auteur

Ant Local Search and its efficient adaptation to graph colouring / M. Plumettaz in Journal of the operational research society (JORS), Vol. 61 N° 5 (Mai 2010) 

Public ISBD [article]  in Journal of the operational research society (JORS) > Vol. 61 N° 5 (Mai 2010) . - pp. 819–826 Titre : Ant Local Search and its efficient adaptation to graph colouring Type de document : texte imprimé Auteurs : M. Plumettaz, Auteur ; D. Schindl, Auteur ; N. Zufferey, Auteur Année de publication : 2010 Article en page(s) : pp. 819–826 Note générale : Recherche opérationnelle Langues : Anglais (eng) Mots-clés : Heuristics  Networks  and  graphs  Artificial  life  Optimization Index. décimale : 001.424 Résumé : 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. DEWEY : 001.424 ISSN : 0361-5682 En ligne : http://www.palgrave-journals.com/jors/journal/v61/n5/abs/jors200927a.html [article] Ant Local Search and its efficient adaptation to graph colouring [texte imprimé] / M. Plumettaz, Auteur ; D. Schindl, Auteur ; N. Zufferey, Auteur . - 2010 . - pp. 819–826. Recherche opérationnelle Langues : Anglais (eng) in Journal of the operational research society (JORS) > Vol. 61 N° 5 (Mai 2010) . - pp. 819–826 Mots-clés : Heuristics  Networks  and  graphs  Artificial  life  Optimization Index. décimale : 001.424 Résumé : 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. DEWEY : 001.424 ISSN : 0361-5682 En ligne : http://www.palgrave-journals.com/jors/journal/v61/n5/abs/jors200927a.html