Abstract
We present in this article an evolutionary procedure for solving general optimization problems. The procedure combines efficiently the mechanism of a simple descent method and of genetic algorithms. In order to explore the solution space properly, periods of optimization are interspersed with phases of interaction and diversification. An adaptation of this search principle to coloring problems in graphs is discussed. More precisely, given a graphG, we are interested in finding the largest induced subgraph ofG that can be colored with a fixed numberq of colors. Whenq is larger or equal to the chromatic number ofG, then the problem amounts to finding an ordinary coloring of the vertices ofG.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Berge, C. (1989). Minimax relations for the partialq-colorings of a graph.Discrete Mathematics, 74, 3–14.
Bollobas, B. (1985).Random Graphs. New York: Academic Press.
Brélaz, D. (1979). New methods to color vertices of a graph.Communications of the ACM, 22, 251–256.
Carter, B., and Park, K. (1993). How good are genetic algorithms at finding large cliques? An experimental study. Technical Report BU-CS-93-015, Boston University.
Chams, M., Hertz, A., and de Werra, D. (1987). Some experiments with simulated annealing for coloring graphs.European Journal of Operational Research, 32, 260–266.
Colorni, A., Dorigo, M., and Maniezzo, V. (1992a). Distributed optimization by ant colonies. In F. Varela and P. Bourgine (Eds.),Proceedings of the First European Conference on Artificial Life (pp. 134–142). Paris: Elsevier.
Colorni, A., Dorigo, M., and Maniezzo, V. (1991b). An autocatalytic process. Technical Report 91-016, Politecnico di Milano, Dipartimento di Elettronica, Milano.
Colorni, A., Dorigo, M., and Maniezzo, V. (1992). An investigation of some properties of an ant algorithm. In R. Männer and B. Manderick (Eds.),Proceedings of the Second Conference on Parallel Problem Solving from Nature (pp. 509–520). Brussels: Elsevier.
Cosla, D. (1995). An evolutionary tabu search algorithm and the NHL scheduling problem.INFOR 33(3), 161–178.
Culberson, J.C. (1992). Iterated greedy graph coloring and the difficulty landscape. Technical Report TR 92-07, University of Alberta, Department of Computing Science, Edmonton.
Davis, L. (1991).Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold.
Dubois, N., and de Werra, D. (1994). EPCOT—an efficient procedure for coloring optimally with tabu search.Computers and Mathematics with Applications 25, 35–45.
Eglese, R.W. (1990). Simulated nnealing: A tool for operational research.European Journal of Operational Research, 46, 271–281.
Fleurent, C., and Ferland, J.A. (1994). Genetic hybrids for the quadratic assignment problem. In P.M. Pardalos and Wolkowicz (Eds.),DIMACS Series in Discrete Mathematics and Theoretical Computer Science (Vol. 16) (pp. 173–188).
Fleurent, C., and Ferland, J.A. (1995). Genetic and hybrid algorithms for graph coloring.Annals of Operations Research.
Fogarty, T.C. (1989). Varying the probability of mutation in the genetic algorithm. In J.D. Schaffer (Ed.),Proceedings of the Third International Conference on Genetic algorithms. George Mason University: Morean Kaufmann.
Friden, C., Hertz, A., and de Werra, D. (1989). STABULUS: A technique for finding stable sets in large graphs with tabu search.Computing, 42, 35–44.
Friden, C., Hertz, A., and de Werra, D. (1990). TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph.Computers and Operations Research, 17(5), 437–445.
Garey, M.R., and Johnson, D.S. (1979).Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: Freedman.
Gendreau, M. (1994). An appraisal of greedy heuristics for the maximum clique problem. Technical Report, Université de Montréal, Centre de Recherche sur les Transports.
Goldberg, D.E. (1989).Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, MA: Addison-Wesley.
Glover, F. (1993). Scatter search and star-paths: Beyond the genetic metaphor. Technical Report, University of Colorado, School of Business, Boulder.
Glover, F. (1994). Genetic algorithms and scatter search: Unsuspected potentials.Statistics and Computing, 131–140.
Glover, F., Taillard, E., and de Werra, D. (1993). A user's guide to tabu search.Annals of Operations Research, 41, 3–38.
Grefenstette, J.J. (1987). Incorporating problem scpecific knowledge into genetic algorithms. In L. Davis (Ed.),Genetic Algorithms and Simulated Annealing (pp. 42–60). Cambridge: Morgan Kaufmann.
Hertz, A. (1995). Polynomially solvable cases for the maximum stable set problem.Discrete Applied Mathematics 60, 195–210.
Hertz, A., and de Werra, D. (1987). Using tabu search for graph coloring.Computing, 39, 345–351.
Hertz, A., Taillard, E., and de Werra, D. (1995). Tabu search. In J.K. Lenstra (Ed.),Local Search in Combinatorial Optimization. Wiley.
Johrson, D.S., Aragon, C.R., McGeoch, L.A., and Schevon, C. (1991). Optimization by simulated annealing: An experimental evaluation. Part II, graph coloring and number partitioning.Operations Research, 39, 378–406.
Johri, A., and Matula, D.W. (1982). Probabilistic bounds and heuristic algorithms for coloring large random graphs. Technical Report 82-CSE-06, Southern Methodist University, Department of Computing Science, Dallas.
Kirkpatrick, S., Gelatt, C.D., and Vecchi, M.P. (1983). Optimization by simulated annealing.Science, 220, 671–680.
L'Ecuyer, P. (1988). Efficient and Portable Combined Random Number Generators.Communications of the ACM, 31, 742–774.
Liepins, G.E., and Hilliard, M.R. (1989). Genetic algorithms: Foundations and applications.Annals of Operations Research, 21, 31–58.
Mannino, C., and Sassano, A. (1992). An exact algorithm for the maximum stable set problem. Working Paper No. 334, IASI-CNR, Roma.
Morgenstern, C. (1990). Algorithms for General Graph Coloring. Doctoral dissertation, University of New Mexico, Department of Computer Science, New Mexico.
Moscato, P. (1993). An introduction to population approaches for optimization and hierarchical objective functions: A discussion on the role of tabu search.Annals of Operations Research, 41, 85–121.
Mühlenbein, H., Gorges-Schleuter, M., and Krämer, O. (1988). Evolution algorithms in combinatorial optimization.Parallel Computing, 7, 65–85.
Reeves, C.R. (Ed.). (1993).Modern Heuristic Techniques for Conbinatorial Optimization. Oxford: Blackwell Scientific.
Syswerda, G. (1989). Uniform crossover in genetic algorithms. In J.D. Schaffer (Ed.),Proceedings of the Third International Conference on Genetic Algorithms (pp. 2–9). San Mateo, CA: Morgan Kaufmann.
Thangiah, S.R., Osman, I.H., and Sun, T. (1994). Hybrid genetic algorithm, simulated annealing and tabu search methods for vehicle routing problems with time windows. Research Report, Artificial Intelligence and Robotics Laboratory, Computer Science Department, Slippery Rock University, Slippery Rock, USA.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Costa, D., Hertz, A. & Dubuis, C. Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs. J Heuristics 1, 105–128 (1995). https://doi.org/10.1007/BF02430368
Issue Date:
DOI: https://doi.org/10.1007/BF02430368