Uma Nova Abordagem Evolucionária para a Coloração das Vértices de um Grafo
Autores
|
1761 |
648,163
|
|
|
1762 |
648,163
|
Informações:
Publicações do PESC
Uma Nova Abordagem Evolucionária para a Coloração das Vértices de um Grafo
Carlos Augusto Garcia Assis
Maio/1999
| Orientador: | Valmir Carneiro Barbosa | |
| ||
Nesta tese foi proposta uma nova nova abordagem evolucionária para o problema de coloração dos vértices de um grafo não orientado. A abordagem é baseada em um teorema da teoria dos grafos que relata o número cromático de um grafo com suas orientações acíclicas. De acordo com esse teorema, o problema de calcular o número cromático de um grafo é equivalente a encontrar a orientação acíclica que possui o menor entre todos os maiores caminhos orientados de cada grafo acíclico. A solução consiste essencialmente em um algoritmo genético que opera com uma população de grafos acíclicos e orientados, junto com técnicas apropriadas para calcular a fitness e os operadores genéticos. Foi implementado uma versão sequencial e outra paralela neste algoritmo evolucionário, e foi testado experimentalmente em grafos complexos, especialmente projetados para testar algoritmos de coloração de vértices. Os resultados obtidos colocam o algoritmo implementado entre os melhores nos resultados obtidos por outras heurísticas e relatadas no desafio DIMACS.
A New Evolutionary Formulation to the Coloring the Nodes of an Graph
Carlos Augusto Garcia Assis
May/1999
| Advisor: | Valmir Carneiro Barbosa | |
| Department: Systems Engineering and Computer Science | ||
In this thesis we propose a new evolutionary formulation to the problem of coloring the nodes of an undirected graph. The formulation we propose is based on a theorem from graph theory that relates the chromatic number of a graph with its acyclic orientations. According to this theorem, the problem of computing a graph's chromatic number is equivalent to searching for the acyclic orientation whose longest directed path is shortest over all acyclic orientations. Our approach consists essentially of a genetic algorithm that operates on a population of acyclic orientations, together with appropriate techniques to compute an orientation's fitness and appropriate genetic operators. We have implemented sequential and parallel versions of this evolutionary algorithm, and have evaluated them experimentally on graphs especially designed to test coloring algorithms within a DIMACS implementation challenge. The results we have obtained place our approach among the best that were reported within that challenge.