Título: Algoritmo Heurístico Baseado Em Colônia De Formigas Artificiais Colorant2 Com Busca Local Aplicado Ao Problema De Coloração De Grafo
Autores: Lintzmayer, Carla Négri; Mulati, Mauro Henrique; Silva, Anderson Faustino da
Resumo: O problema de coloração de grafo é N P-difícil e é utilizado em aplicações práticas, como escalonamento de tarefas e alocação de registradores. Para obter soluções para este problema em tempo aceitável, a investigação reportada no presente trabalho utiliza a meta-heurística Ant Colony Optimization, cujo funcionamento é baseado no comportamento de formigas durante a busca por alimento em um ambiente. Com base nesta meta-heurística é apresentado o algoritmo ColorAnt 2 , que utiliza Busca Tabu como busca local. Os experimentos realizados reportam que ColorAnt 2 é uma opção promissora para encontrar boas aproximações para grafos geométricos e/ou le450 em um tempo de execução aceitável, como também para minimizar a quantidade de conflitos, o principal problema da coloração de grafo com um número fixo de cores.
Palavras-chave: Meta-heurística; Problema de Coloração de Grafo; Otimização por Colônia de Formigas Artificiais; Ant Colony Optimization; ColorAnt2
Páginas: 8
Código DOI: 10.21528/CBIC2011-31.4
Artigo em pdf: st_31.4.pdf
Arquivo BibTex: st_31.4.bib