Abstract
The Artificial Bee Colony (ABC) is the name of an optimization algorithm that was inspired by the intelligent behavior of a honey bee swarm. It is widely recognized as a quick, reliable, and efficient methods for solving optimization problems. This paper proposes a hybrid ABC (HABC) algorithm for graph 3-coloring, which is a well-known discrete optimization problem. The results of HABC are compared with results of the well-known graph coloring algorithms of today, i.e., the Tabucol and Hybrid Evolutionary algorithm (HEA), and results of the traditional evolutionary algorithm with SAW method (EA-SAW). Extensive experimentations has shown that the HABC matched the competitive results of the best graph coloring algorithms, and did better than the traditional heuristics EA-SAW when solving equi-partite, flat, and random generated medium-sized graphs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aarts, E., Lenstra, J.K.: Local Search in Combinatorial Optimization. Princeton University Press, Princeton (1997)
Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, Berlin (2008)
Brelaz, D.: New methods to color vertices of a graph. Communications of the ACM 22(4), 251–256 (1979)
Cheeseman, P., Kanefsky, B., Taylor, W.M.: Where the really hard problems are. In: Proceedings of the International Joint Conference on Artificial Intelligence, vol. 1, pp. 331–337. Morgan Kaufmann (1991)
Culberson, J.: Graph Coloring Page, http://www.ncbi.nlm.nih.gov
Dorigo, M., Stützle, T.: Ant Colony Optimization. MIT Press, Cambridge (2004)
Eiben, A.E., Smith, J.E.: Introduction to Evolutionary Computing. Springer, Berlin (2003)
Eiben, A.E., Hauw, K., Hemert, J.I.: Graph coloring with adaptive evolutionary algorithms. Journal of Heuristics 4(1), 25–46 (1998)
Fister, I., Brest, J.: Using differential evolution for the graph coloring. In: Proceedings of IEEE SSCI 2011 symposium series on computational intelligence, Piscataway, pp. 150–156 (2011)
Fleurent, C., Ferland, J.: Genetic and Hybrid Algorithms for Graph Coloring. Annals of Operations Research 63, 437–464 (1996)
Galinier, P., Hao, J.: Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization 3(4), 379–397 (1999)
Galinier, P., Hertz, A.: A survey of local search methods for graph coloring. Computers & Operations Research 33, 2547–2562 (2006)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York (1979)
Glover, F.: Future paths for integer programming and links to artificial intelligence. Computers & Operations Research 13(5), 533–549 (1986)
Hertz, A., de Werra, D.: Using tabu search techniques for graph coloring. Computing 39(4), 345–351 (1987)
Iacca, G., Neri, F., Mininno, E., Ong, Y.-S., Lim, M.-H.: Ockham’s Razor in Memetic Computing: Three Stage Optimal Memetic Exploration (2011) (in press)
Karaboga, D., Basturk, A.: A survey: algorithms simulating bee swarm intelligence. Artifficial Intelligence Review 31(1-4), 61–85 (2009)
Kennedy, J., Eberhart, R.C.: Particle swarm optimization. In: Proceedings of the 1995 IEEE International Conference on Neural Networks, vol. 4, pp. 1942–1948. IEEE Service Center, Piscataway (1995)
Lü, Z., Hao, J.K.: A memetic algorithm for graph coloring. European Journal of Operational Research 203(1), 241–250 (2010)
Malaguti, E., Toth, P.: A survey on vertex coloring problems. International Transactions in Operational Research, 1–34 (2009)
Pan, Q.K., Tasgetiren, M.F., Suganthan, P.N., Chua, T.J.: A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem. Information Sciences 181(12), 2455–2468 (2011)
Petford, A.D., Welsh, D.J.A.: A randomized 3-coloring algorithms. Discrete Mathematic 74(1-2), 253–261 (1989)
Rao, S.S.: Engineering Optimization: Theory and Practice. John Willey & Sons, New Jersey (2009)
Robinson, J., Rahmat-Samii, Y.: Particle Swarm Optimization in Electro-Magnetics. IEEE on Antennas and Propagation 52(2), 397–407 (2004)
Tasgetiren, M.F., Pan, Q.K., Suganthan, P.N., Chen, A.H.-L.: A discrete artificial bee colony algorithm for the total flowtime minimization and permutation flow shops. Information Sciences 181(16), 3459–3475 (2011)
Turner, J.S.: Almost all k-colorable graphs are easy to color. Journal of Algorithms 9(1), 63–82 (1988)
Yang, X.-S.: Nature-Inspired Metaheuristic Algorithms. Luniver Press, Cambridge (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fister, I., Fister, I., Brest, J. (2012). A Hybrid Artificial Bee Colony Algorithm for Graph 3-Coloring. In: Rutkowski, L., Korytkowski, M., Scherer, R., Tadeusiewicz, R., Zadeh, L.A., Zurada, J.M. (eds) Swarm and Evolutionary Computation. EC SIDE 2012 2012. Lecture Notes in Computer Science, vol 7269. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29353-5_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-29353-5_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-29352-8
Online ISBN: 978-3-642-29353-5
eBook Packages: Computer ScienceComputer Science (R0)