Decision Fusion of Combinatorial Optimization Algorithms for Solving the Graph Coloring Problem

Abstract

The graph coloring problem is a practical method of representing many real world problems including time scheduling, frequency assignment, register allocation etc. Finding the minimum number of colors for an arbitrary graph is NP-hard. This paper applies Decision Fusion on combinatorial optimization algorithms (genetic algorithm (GA), simulated annealing algorithm (SA)) and sequential/greedy algorithms (highest order algorithm (HO) and the sequential algorithm (SQ)) to find an optimal solution for the graph coloring problem. Giving importance to the factors such as the time of execution and availability of processing resources, a new technique is introduced where selection of the algorithm yielding the optimal solution is made. Decision fusion rules facilitate the predictions on the future of the executing algorithms based on the so far performance at any given point when the problem is solved. The results support that prediction during solving the problem is an efficient way, than the algorithms implemented individually.

Document Type

Conference Proceeding

Keywords

Decision fusion, Genetic algorithm, Graph coloring, Greedy, Optimization, Simulated annealing

Publication Date

12-1-2007

Journal Title

Proceedings of the 2007 International Conference on Artificial Intelligence, ICAI 2007

Citation-only

Share

COinS