Modified Colonial Competitive Algorithm : An Approach for Graph Coloring Problem

Hojjat Emami, Parvaneh Hasanzadeh

Abstract


This paper describes a modified version of colonial competitive algorithm and how it is used to solve graph coloring problem (GCP). Colonial competitive algorithm (CCA) is a meta-heuristic optimization and stochastic search technique that is inspired from socio-political phenomenon of imperialistic competition. CCA has high convergence rate and in optimization problems can reach to global optimum. Graph coloring problem is the process of finding an optimal coloring for any given graph so that adjacent vertices have different colors. Graph coloring problem is an optimization problem.The original CCA algorithm is designed for continuous problems whereas graph coloring problem is a discrete problem. So in this paper we applied some changes in the assimilation and revolution operators of the original CCA algorithm and presented a modified CCA which is called MCCA. The performance of the MCCA algorithm is evaluated on five well-known graph coloring benchmarks. Simulation results demonstrate that MCCA is a feasible and capable algorithm.

Full Text:

PDF

References


Jensen T.R., and Toft B., "Graph Coloring Problems", Wiley interscience Series in Discrete Mathematics and Optimization, 1995.

Arathi R., Markov, I. L., and Sakallah, K. A., "Breaking Instance-Independent Symmetries in Exact Graph Coloring", Journal of Artificial Intelligence Research 26, 2006, pp. 289-322.

Fleurent C., and Ferland, J.A., “Genetic and hybrid algorithms for graph coloring,†Annals of Operations Research,vol. 63, 1996, pp. 437–461.

Anh T.H., Giang T.T.T., and Vinh T.L., “A novel particle swarm optimization – Based algorithm for the graph coloring problemâ€, Proceedings of International Conference on Information Engineering and Computer Science, ICIECS 2009.

Qin, J., Yin Y., and Ban, X., “Hybrid Discrete Particle Swarm Algorithm for Graph Coloring Problemâ€, Journal of Computers, VOL. 6, NO. 6, June 2011, pp. 1175-1182.

SangHyuck, A., SeungGwan L., and TaeChoong Ch., “Modified ant colony system for coloring graphsâ€, Proceedings of the Joint Conference of the Fourth International Conference on Information, Communications and Signal Processing, and Fourth Pacific Rim Conference on Multimedia, 2003, pp. 1849 – 1853.

Dowsland, K. A. and Thompson, J. M., “An improved ant colony optimization heuristic for graph coloringâ€, Discrete Applied Mathematics, Vol. 156, Issue 3, 2008, pp. 313-324.

Fister, I., and Brest, J., “Using differential evolution for the graph coloringâ€, IEEE Symposium on Differential Evolution (SDE), 2011, pp. 1-7.

Hamiez, J-P., and HAO, J.K, “Scatter Search For graph coloringâ€, Lecture Notes in Computer Science 2310: 168-179, Springer, 2002.

Hertz, A., Plumettaz, M., Zufferey, N., “Variable space search for graph coloringâ€, Discrete Applied Mathematics Vol. 156, 2008, pp. 2551–2560.

Torkestani, J.A., and Meybodi, M.R., “Graph Coloring Problem Based on Learning Automataâ€, International Conference on Information Management and Engineering, ICIME '09, 2009, pp. 718-722.

Choudhary, S., and Purohit, G.N., “Distributed algorithm for optimized vertex coloringâ€, International Conference on Methods and Models in Computer Science (ICM2CS), 2010, pp. 65–69.

Galinier. P., “Hybrid Evolutionary Algorithms for graph coloringâ€. J.Combin. Optim. Vol. 3, No.4, 1999, pp. 379-397.

Yang, Z., Liu, H., Xiao, X., and Wu, W., “Improved hybrid genetic algorithm and its application in auto-coloring problemâ€, International Conference on Computer Design and Applications (ICCDA), 2010, pp. 461-464.

Atashpaz-Gargari, E., Hashemzadeh, F., Rajabioun, R., Lucas, C., “Colonial competitive algorithm: A novel approach for PID controller design in MIMO distillation column processâ€, International Journal of Intelligent Computing and Cybernetics, Vol. 1, issue: 3, 2008, pp. 337 – 355.

Kubale M., "Introduction to Computational Complexity and Algorithmic Graph Coloring", Gdanskie Towarzystwo Naukowe, 1998.

Melanie, M., “An Introduction to genetic Algorithmsâ€, Massachusetts: MIT Press, 1999.

[Online:] http://mat.gsia.cmu.edu/COLOR/instances [Accessed on 10 March 2013].


Refbacks

  • There are currently no refbacks.


ISSN: 1694-2507 (Print)

ISSN: 1694-2108 (Online)