CAGraph cultural algorithm for coloring graph - Cruda, Antonio Jr. P.; Orias, Chrisantie J. (2008)
Graph Coloring Problem is a popular problem in Graph Theory due to its various applications in real-world problems. Though backtracking and other deterministic algorithms were able to solve small instances of the problem, the difficulty to solve GCP grows exponentially as the problem grows. Several non-deterministic algorithms were utilized in finding a solution for GCP and were successful. However, solving the problem is a lot easier than optimizing the problem. Therefore the battle for supremacy over GCP is not over. Majority of the successful algorithms were population-based and now in the spotlight for optimization. Presently, a relatively new population-based algorithm is gaining recognition for real-world problem optimization-- the Cultural Algorithm. This algorithm is based upon the idea of extracting individual experiences from the social interaction of the population and applying these experiences for future movement of the population. This paper aims to explore the potential of Cultural Algorithm in its application to Graph Coloring Problem.