Graph Coloring with Adaptive Evolutionary Algorithms

• Angeline, P. (1995). “Adaptive and Self-Adaptive Evolutionary Computation.” In M. Palaniswami, Y. Attikiouzel, R.J. Marks, D. Fogel, and T. Fukuda (eds.), Computational Intelligence: A Dynamic System Perspective. IEEE Press, pp. 152-161.

• Arora, S., C. Lund, R. Motwani, M. Sudan, and M. Szegedy. (1992). “Proof Verification and Hardness of Approximation Problems,” Proceedings 33rd IEEE Symposium on the Foundations of Computer Science. IEEE Computer Sociecty, Los Angeles, CA, pp. 14-23.

  Google Scholar 

• Bäck, T., D. Fogel, and Z. Michalewicz. (eds.) (1997). Handbook of Evolutionary Computation. Bristol: Institute of Physics Publishing and New York: Oxford University Press.

  Google Scholar 

• Belew, R. and L. Booker. (eds.) (1991). Proceedings of the 4th International Conference on Genetic Algorithms. Morgan Kaufmann.

• Blum, A. (1989). “An O.n0.4/-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithms for k-Coloring),” Proceedings of the 21st ACM Symposium on Theory of Computing. New York, ACM, pp. 535-542.

  Google Scholar 

• Brélaz, D. (1979). “New Methods to Color Vertices of a Graph,” Communications of the ACM22, 251-256.

  Google Scholar 

• Cheeseman, P., B. Kenefsky, and W.M. Taylor. (1991). “Where the Really Hard Problems Are.” In J. Mylopoulos, and R. Reiter (eds.), Proceedings of the 12th IJCAI-91. Morgan Kaufmann, vol. 1, pp. 331-337.

• Clearwater, S. and T. Hogg. (1996). “Problem Structure Heuristics and Scaling Behavior for Genetic Algorithms,” Artificial Intelligence81, 327-347.

  Google Scholar 

• Coll, P., G. Durán, and P. Moscato. (1995). “A Discussion on Some Design Principles for Efficient Crossover Operators for Graph Coloring Problems,” Anales del XXVII Simposio Brasileiro de Pesquisa Operacional.

• Culberson, J. (1996). “On the Futility of Blind Search,” Technical Report TR 96-18, The University of Alberta.

• Culberson, J. and F. Luo. (1996). “Exploring the k-Colorable Landscape with Iterated Greedy.” In D. Johnson and M. Trick (eds.), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge. American Mathematical Society, pp. 245–284. Available by http://web.cs.ualberta.ca/~joe/.

• Davis, L. (1991). “Order-Based Genetic Algorihms and the Graph Coloring Problem.” Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold, pp. 72-90.

  Google Scholar 

• De Jong, K. and W. Spears. (1992). “A Formal Analysis of the Role of Multi-point Crossover in Genetic Algorithms,” Annals of Mathematics and Artificial Intelligence5, 1-26.

  Google Scholar 

• Eiben, A., P.-E. Raué, and Z. Ruttkay. (1994). “Genetic Algorithms with Multi-parent Recombination.” In Y. Davidor, H.-P. Schwefel, and R. Männer (eds.), Proceedings of the 3rd Conference on Parallel Problem Solving from Nature, number 866 in Lecture Notes in Computer Science. Springer-Verlag, pp. 78-87.

• Eiben, A., P.-E. Raué, and Z. Ruttkay. (1995a). “Constrained Problems.” In L. Chambers (ed.), Practical Handbook of Genetic Algorithms. CRC Press, pp. 307-365.

• Eiben, A., P.-E. Raué, and Z. Ruttkay. (1995b). “GA-Easy and GA-Hard Constraint Satisfaction Problems.” In M. Meyer (ed.), Proceedings of the ECAI-94 Workshop on Constraint Processing, number 923 in Lecture Notes in Computer Science. Springer-Verlag, pp. 267-284.

• Eiben, A. and Z. Ruttkay. (1996). “Self-adaptivity for Constraint Satisfaction: Learning Penalty Functions,” Proceedings of the 3rd IEEE Conference on Evolutionary Computation. IEEE Press, pp. 258–261.

• Eiben, A. and J. van der Hauw. (1996). “Graph Coloring with Adaptive Evolutionary Algorithms,” Technical Report TR-96-11, Leiden University. Also available as http:// www.wi.leidenuniv.nl/~gusz/graphcol.ps.gz.

• Eiben, A. and J. van der Hauw. (1997). “Solving 3-SAT by GAS Adapting Constraint Weights,” Proceedings of the 4th IEEE Conference on Evolutionary Computation. IEEE Press, pp. 81-86.

• Eiben, A. and Z. Ruttkay. (1997). “Constraint Satisfaction Problems.” In T. Bäck et al. (eds.), Handbook of Evolutionary Computation. Bristol: Institute of Physics Publishing, and New York: Oxford University Press.

  Google Scholar 

• Falkenauer, E. (1994). “A New Representation and Operators for Genetic Algorithms Applied to Grouping Problems,” Evolutionary Computation2(2), 123-144.

  Google Scholar 

• Falkenauer, E. (1996). “A Hybrid Grouping Genetic Algorithm for Bin Packing,” Journal of Heuristics2, 5-30.

  Google Scholar 

• Falkenauer, E. and A. Delchambre. (1992). “A Genetic Algorithm for Bin Packing and Line Balancing,” Proceedings of the IEEE 1992 Int. Conference on Robotics and Automation. IEEE Computer Society Press, pp. 1186- 1192.

• Fleurent, C. and J. Ferland. (1996a). “Genetic and Hybrid Algorithms for Graph Coloring.” In I.H.O. G. Laporte and P.L. Hammer (eds.), Annals of Operations Research, number 63 in Metaheuristics in Combinatorial Optimization. J.C. Baltzer AG, Science Publishers, pp. 437-461.

• Fleurent, C. and J. Ferland. (1996b). “Object-Oriented Implementation of Heuristic Search Methods for Graph Coloring, Maximum Clique, and Satisfiability.” In M.A. Trick and D.S. Johnson (eds.), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, volume 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, pp. 619-652.

• Fogel, D. (1995). Evolutionary Computation. IEEE Press.

• Fox, B. and M. McMahon. (1991). “Genetic Operators for Sequencing Problems.” In G. Rawlins (ed.), Foundations of Genetic Algorithms. Morgan Kaufmann, pp. 284–300.

• Frank, J. (1996a). “Learning Short-term Weights For GSAT,” Technical Report, University of California at Davis. Available by http://rainier.cs.ucdavis.edu/~frank/decay.ml96.ps.

• Frank, J. (1996b). “Weighting for Godot: Learning Heuristics For GSAT,” Proceedings of the 13th AAAI-96. AAAI / The MIT Press, pp. 338-343.

• Garey, M. and D. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freedman and Co.

• Glover, F. (1996). “Tabu Search and Adaptive Memory Programming-Advances, Applications, and Challenges,” Interfaces in Computer Science and Operations Research. Norwell, MA: Kluwer Academic Publishers, pp. 1- 75.

  Google Scholar 

• Grimmet, G. and C. McDiarmid. (1975). “On Colouring Random Graphs,” Mathematical Proceedings of the Cambridge Philosophical Society77, 313-324.

  Google Scholar 

• Hinterding, R., Z. Michalewicz, and A. Eiben. (1997). “Adaptation in Evolutionary Computation: A Survey,” Proceedings of the 4th IEEE Conference on Evolutionary Computation. IEEE Press, pp. 65-69.

• Johnson, D., C. Aragon, L. McGeoch, and C. Schevon. (1991). “Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning,” Operations Research39(3), 378- 406.

  Google Scholar 

• Kronsjo, L. (1987). Algorithms: Their Complexity and Efficiency. Wiley and Sons, second edition.

• Kučera, L. (1991). “The Greedy Coloring is a Bad Probabilistic Algorithm,” Journal of Algorithms12, 674-684.

  Google Scholar 

• Laszewski, G.V. (1991). “Intelligent Structural Operators For the k-Way Graph Partitioning Problem.” In R. Belew and L. Booker (eds.), Proceeding of the 4th International Conference on Genetic Algorithms. Morgan Kaufmann, pp. 45-52.

• Løkketangen, A. and F. Glover. (1996). “Surrogate Constraint Methods with Simple Learning for Satisfiability Problems.” In D. Du, J. Gu, and P. Pardalos (eds.), Proceedings of the DIMACS workshop on Satisfiability Problems: Theory and Applications. American Mathematical Society.

• Morris, P. (1993). “The Breakout Method for Escaping From Local Minima,” Proceedings of the 11th National Conference on Artificial Intelligence, AAAI-93. AAAI Press/The MIT Press, pp. 40-45.

• Nudel, B. (1983). “Consistent-Labeling Problems and Their Algorithms: Expected Complexities and Theory Based Heuristics,” Artificial Intelligence21, 135-178.

  Google Scholar 

• Schwefel, H.-P. (1995). Evolution and Optimum Seeking. Sixth-Generation Computer Technology Series. New York: Wiley.

  Google Scholar 

• Selman, B. and H. Kautz. (1993). “Domain-Independent Extensions to GSAT: Solving Large Structured Satisfiability Problems.” In R. Bajcsy (ed.), Proceedings of IJCAI'93. Morgan Kaufmann, pp. 290-295.

• Starkweather, T., S. McDaniel, K. Mathias, D. Whitley, and C. Whitley. (1991). “A Comparison of Genetic Sequenceing Operators.” In R. Belew and L. Booker (eds.), Proceedings of the 4th International Conference on Genetic Algorithms. Morgan Kaufmann, pp. 69-76.

• Turner, J. (1988). “Almost All k-Colorable Graphs are Easy to Color,” Journal of Algorithms9, 63-82.

  Google Scholar 

• Wolpert, D. and W. Macready. (1997). “No Free Lunch Theorems for Optimization,” IEEE Transactions on Evolutionary Computation1(1), 67-82.

  Google Scholar 

Download references