Abstract
The graph coloring problem is one of famous combinatorial optimization problems. Some researchers attempted to solve combinatorial optimization problem with evolutionary algorithm, which can find near optimal solution based on the evolution mechanism of the nature. However, it sometimes requires too much cost to evaluate fitness of a large number of individuals in the population when applying the GA to the real world problems. This paper attempts to solve graph coloring problem using a fuzzy clustering based evolutionary approach to reduce the cost of the evaluation. In order to show the feasibility of the method, some experiments with other alternative methods are conducted.
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
Omari, H.A., Sabri, K.E.: New graph coloring algorithms. J. Mathematics and Statistics 2(4), 439–441 (2006)
Brelaz, D.: New methods to color vertices of a graph. Communcations of ACM 22, 251–256 (1979)
Hertz, A., De Werra, D.: Using tabu search techniques for graph coloring. Computing 39, 345–351 (1987)
Freisleben, B., Merez, P.: New Genetic Local Search Operators for the Traveling Salesman Problem. In: Ebeling, W., Rechenberg, I., Voigt, H.-M., Schwefel, H.-P. (eds.) PPSN 1996. LNCS, vol. 1141, pp. 890–899. Springer, Heidelberg (1996)
Merez, P., Freisleben, B.: A genetic local search approach to the quadratic assignment problem. In: 7th International Conference on Genetic Algorithms, pp. 465–472 (1997)
Falkenauer, E.: A hybrid grouping genetic algorithm for bin-packing. J. Heuristics 2(1), 5–30 (1996)
Fleurent, C., Ferland, J.A.: Genetic and hybrid algorithms for graph coloring. Annals of Operations Research 63, 437–463 (1995)
Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization - Algorithms and Complexity. Prentice Hall (1982)
Johnson, D.S., Aragon, C.R., McGeoch, L.A., Schevon, C.: Optimization by simulated annealing: an experimental evaluation: part ii, graph coloring and number partitioning. Operations Research 39(3), 378–406 (1991)
Gose, E., Johnsonbaugh, R., Jost, S.: Pattern Recognition and Image Analysis. Prentice Hall (1996)
Anderberg, M.R.: Cluster Analysis for Applications. Academic Press (1973)
Fukunaka, K.: Introduction to Statistical Pattern Analysis. Academic Press (1990)
Haritigan, J.A.: Clustering Algorithms. John Wiley & Sons (1975)
Hoppner, F., Klawonn, F., Kruse, R., Runkler, T.: Fuzzy Cluster Analysis. John Wiley & Sons (1999)
Xie, X.L., Beni, G.: A validity measure for fuzzy clustering. IEEE Trans. of Pattern Analysis and Machine Intelligence, PAMI-13(8), 841-847 (1991)
Chams, M., Hertz, A., De Werra, D.: Some experiments with simulated annealing for coloring graphs. European Journal of Operational Research 32, 260–266 (1987)
Lotfi, V., Sarin, S.: A graph coloring algorithm for large scale scheduling problems. Computers & Operations Research 13(1), 27–32 (1986)
Klotz, W.: Graph coloring algorithms. IEICE Trans. Information and Systems 5, 1–9 (2002)
Porumbel, D.C., Hao, J.-K., Kuntz, P.: Diversity Control and Multi-Parent Recombination for Evolutionary Graph Coloring Algorithms. In: Cotta, C., Cowling, P. (eds.) EvoCOP 2009. LNCS, vol. 5482, pp. 121–132. Springer, Heidelberg (2009)
Eiben, A.E., Van Der Hauw, J.K., Van Hemer, J.I.: Graph coloring with adaptive evolutionary algorithms. J. of Heuristics 4(1), 25–46 (1998)
Costa, D., Hertz, A., Dubuis, O.: Embedding a sequential procedure within an evolutionary algorithms for coloring problems in graphs. J. of Heuristics 1(1), 105–128 (1995)
Jin, Y., Sendhoff, B.: Reducing Fitness Evaluations Using Clustering Techniques and Neural Network Ensembles. In: Deb, K., Tari, Z. (eds.) GECCO 2004. LNCS, vol. 3102, pp. 688–699. Springer, Heidelberg (2004)
Kim, H.-S., Cho, S.-B.: An efficient genetic algorithms with less fitness evaluation by clustering. In: Proceedings of IEEE Congress on Evolutionary Computation, pp. 887–894. IEEE (2001)
Yoo, S.-H., Cho, S.-B.: Partially Evaluated Genetic Algorithm Based on Fuzzy c-Means Algorithm. In: Yao, X., Burke, E.K., Lozano, J.A., Smith, J., Merelo-Guervós, J.J., Bullinaria, J.A., Rowe, J.E., Tiňo, P., Kabán, A., Schwefel, H.-P. (eds.) PPSN VIII. LNCS, vol. 3242, pp. 440–449. Springer, Heidelberg (2004)
Bezdek, J.C.: Pattern Recognition with Fuzzy Objective Function Algorithms. Plenum Press (1981)
Chen, X.S., Ong, Y.S., Lim, M.H., Tan, K.C.: A Multi-Facet Survey on Memetic Computation. IEEE Transactions on Evolutionary Computation 15(5), 591–607 (2011)
Ong, Y.S., Lim, M.H., Chen, X.S.: Research Frontier: Memetic Computation - Past, Present & Future. IEEE Computational Intelligence Magazine 5(2), 24–36 (2010)
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
Lee, YS., Cho, SB. (2012). Solving Graph Coloring Problem by Fuzzy Clustering-Based Genetic Algorithm. In: Bui, L.T., Ong, Y.S., Hoai, N.X., Ishibuchi, H., Suganthan, P.N. (eds) Simulated Evolution and Learning. SEAL 2012. Lecture Notes in Computer Science, vol 7673. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34859-4_35
Download citation
DOI: https://doi.org/10.1007/978-3-642-34859-4_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34858-7
Online ISBN: 978-3-642-34859-4
eBook Packages: Computer ScienceComputer Science (R0)