A Effective Ant Colony Algorithm applied to the Graph Coloring Problem


The KIPS Transactions:PartB , Vol. 11, No. 2, pp. 221-226, Apr. 2004
10.3745/KIPSTB.2004.11.2.221,   PDF Download:

Abstract

Ant Colony System(ACS) Algorithm is new meta-heuristic for hard combinational optimization problem. It is a population-based approach that uses exploitation of positive feedback as well as greedy search.Recently, various methods and solutions are proposed to solve optimal solution of graph coloring problem that assign to color for adjacency node(vi, vj) that they has not same color. In this paper introducing ANTCOL Algorithm that is method to solve solution by Ant Colony System algorithm that is not method that it is known well as solution of existent graph coloring problem. After introducing ACS algorithm and Assignment Type Problem, show the way how to apply ACS to solve ATP. And compare graph coloring result and execution time when use existent generating functions(ANT_Random, ANT_LF, ANT_SL, ANT_DSATUR, ANT_RLF method) with ANT_XRLF method that use XRLF that apply Randomize to RLF to solve ANTCOL. Also compare graph coloring result and execution time when use method to add re-search to ANT_XRLF(ANT_XRLF_R) with existent generating functions.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
A. S. Hyeog, L. S. Gwan, J. T. Chung, "A Effective Ant Colony Algorithm applied to the Graph Coloring Problem," The KIPS Transactions:PartB , vol. 11, no. 2, pp. 221-226, 2004. DOI: 10.3745/KIPSTB.2004.11.2.221.

[ACM Style]
An Sang Hyeog, Lee Seung Gwan, and Jeong Tae Chung. 2004. A Effective Ant Colony Algorithm applied to the Graph Coloring Problem. The KIPS Transactions:PartB , 11, 2, (2004), 221-226. DOI: 10.3745/KIPSTB.2004.11.2.221.