Toward Better Performance of ColorAnt ACO Algorithm

Author

Lintzmayer, C.N. ; Mulati, Mauro Henrique ; da Silva, Allan F.

Author_Institution

State Univ. of Maringa, Maringa, Brazil

fYear

2011

fDate

9-11 Nov. 2011

Firstpage

256

Lastpage

264

Abstract

This paper presents the Color Ant-RT algorithm version 3, an algorithm for graph coloring problems which is based on the Ant Colony Optimization metaheuristic and uses Tabu Search as local search. The experiments demonstrated that ColorAnt3-RT is a promising option in finding good approximations to the best known results for geometric random, geometric standard and le450 graphs of DIMACS benchmark in an acceptable runtime, also, it is good in minimizing the amount of conflicts, the main problem of graph coloring with a fixed number of colors.

Keywords

graph colouring; optimisation; search problems; ColorAnt ACO algorithm; ColorAnt-RT algorithm version 3; DIMACS benchmark; ant colony optimization metaheuristic; geometric random graphs; geometric standard graphs; graph coloring problems; le450 graphs; local search; tabu search; Ant colony optimization; Color; Equations; Heuristic algorithms; Mathematical model; Search methods; Standards; Ant Colony Optimization; ColorAnt3-RT; Graph Coloring; Local Search;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Science Society (SCCC), 2011 30th International Conference of the Chilean

Conference_Location

Curico

ISSN

1522-4902

Print_ISBN

978-1-4673-1364-3

Type

conf

DOI

10.1109/SCCC.2011.33

Filename

6363405