Genetic and hybrid algorithms for graph coloring

R. Battiti and G. Tecchiolli, Parallel biased search for combinatorial optimization: Genetic algorithms and tabu, Microproc. Microsyst. 16(1992)351–367.

R. Battiti and G. Tecchiolli, The reactive tabu search, ORSA J. Comp. 6(1994)126–140.

T. Starkweather, S. McDaniel, K. Mathias, D. Whitley and C. Whitley, A comparison of genetic sequencing operators,Proc. 4th Int. Conf. on Genetic Algorithms, ed. R.K. Belew and L.B. Booker (Morgan Kaufmann, San Mateo, CA, 1991) pp. 69–76.

D. Brelaz, New methods to color vertices of a graph, Commun. ACM 22(1979)251–256.

B. Carter and K. Park, How good are genetic algorithms at finding large cliques: An experimental study, Technical Report BU-CS-93-015, Boston University (1994).

M. Chams, A. Hertz and D. de Werra, Some experiments with simulated annealing for coloring graphs, Euro. J. Oper. Res. 32(1987)260–266.

L. Davis,Handbook of Genetic Algorithms (Van Nostrand Reinhold, New York, 1991).

F. Dammeyer and S. Voss, Dynamic tabu list management using the reverse elimination method, Ann. Oper. Res. 41(1993)31–46.

DIMACS, Discrete Mathematics and Theoretical Computer Science anonymous ftp site at dimacs.rutgers.edu.

L.J. Eshelman, The CHC adaptive search algorithm: How to have safe search when engaging in nontraditional genetic recombination, in:Foundations of Genetic Algorithms, ed. G.J.E. Rawlings (Morgan Kaufmann, San Mateo, CA, 1992) pp. 265–283.

C. Fleurent and J.A. Ferland, Genetic hybrids for the quadratic assignment problem, DIMACS Series, Discr. Math. Theor. Comp. Sci. 16(1994)173–187

B.R. Fox and M.B. McMahon, Genetic operators for sequencing problems, in:Foundations of Genetic Algorithms, ed. G.J.E. Rawlings (Morgan Kaufmann, San Mateo, CA, 1992) pp. 284–300.

C, Friden, A. Hertz and D. de Werra, STABULUS: A technique for finding stable sets in large graphs with tabu search, Computing 42(1989)35–44.

M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).

F. Glover, Heuristics for integer programming using surrogate constraints, Dec. Sci. 8(1977)156–166.

F. Glover, Genetic algorithms and scatter search: Unsuspected potentials, Technical Report, University of Colorado at Boulder (1993).

F. Glover, Future paths for integer programming and links to artificial intelligence, Comp. Oper. Res. 13(1986)533–549.

F. Glover, Tabu search for nonlinear and parametric optimization (with links to genetic algorithms), to appear in Discr. Appl. Math.

F. Glover and M. Laguna, Tabu search, in:Modern Heuristic Techniques for Combinatorial Problems, ed. C.R. Reeves (Blackwell Scientific, Oxford, 1993) pp. 70–141.

D.E. Goldberg,Genetic Algorithms in Search, Optimization, and Machine Learning (Addison-Wesley, 1989).

J.J. Grefenstette, Incorporating problem specific knowledge into genetic algorithms, in:Genetic Algorithms and Simulated Annealing (Morgan Kaufmann, 1987) pp. 42–60.

A. Hertz and D. de Werra, Using tabu search techniques for graph coloring, Computing 39(1987)345–351.

J.H. Holland,Adaptation in Natural and Artificial Systems (University of Michigan Press, Ann Arbor, 1975).

D.S. Johnson, C.R. Aragon, L.A. McGeoch and C. Schevon, Optimization by simulated annealing: An experimental evaluation, Part II; Graph coloring and number partitioning, Oper. Res. 39(1991)378–406.

A. Johri and D.W. Matula, Probabilistic bounds and heuristic algorithms for coloring large random graphs, Technical Report, Southern Methodist University, Dallas, TX (1982).

P. L'Écuyer, Efficient and portable combined random number generators, Commun. ACM 31(1988)742–774.

F. Leighton, A graph coloring algorithm for large scheduling problems, J. Res. Nat. Bureau of Standards 84(1979)489–505.

S. Lin, Computer solutions of the traveling salesman problem, Bell. Syst. Tech. J. 44(1965)2245–2269.

S. Lin and B.W. Kernighan, An effective heuristic for the traveling salesman problem, Oper. Res. 21(1973)498–516.

C. Morgenstern, Distributed coloration neighborhood search, presented at the15th Int. Symp. on Mathematical Programming, Ann Arbor (1994).

H. Muhlenbein, M. Gorges-Schleuter and O. Kramer, Evolution algorithms in combinatorial optimization, Parallel Comp. 7(1988)65–88.

H. Muhlenbein, Evolution in time and space — the parallel genetic algorithm, in:Foundations of Genetic Algorithms, ed. G.J.E. Rawlings (Morgan Kaufmann, San Mateo, CA, 1992) pp. 316–335.

J.D. Schaffer, L.J. Eshelman and D. Offutt, Spurious correlations and premature convergence in genetic algorithms, in:Foundations of Genetic Algorithms, ed. G.J.E. Rawlings (Morgan Kaufmann, San Mateo, CA, 1992) pp. 102–112.

G. Syswerda, Uniform crossover in genetic algorithms,Proc. 3rd Int. Conf. on Genetic Algorithms (Morgan Kaufmann, 1989) pp. 2–9.

G. Syswerda, A study of reproduction in generational and steady-state genetic algorithms, in:Foundations of Genetic Algorithms, ed. G.J.E. Rawlings (Morgan Kaufmann, San Mateo, CA, 1992) pp. 94–101.

E. Taillard, Robust tabu search for the quadratic assignment problem, Parallel Comp. 17(1991)443–455.

E. Taillard, Recherches itératives dirigées parallèles, Ph.D. Thesis, École Polytechnique Fédérale de Lausanne (1993).

E. Taillard, Comparison of iteratives searches for the quadratic assignment problem, Technical Report ORWP94/04, DMA, École Polytechnique Fédérale de Lausanne (1994).

D.E. Tate and A.E. Smith, A genetic approach to the quadratic assignment problem, Comp. Oper. Res. 22(1995)73–83.

D. Welsh,Codes and Cryptography (Oxford University Press, New York, 1988).

D. Whitley, T. Starkweather and D. Shaner, The traveling salesman and sequence scheduling: Quality solutions using genetic edge recombination, in:Handbook of Genetic Algorithms (Van Nostrand Reinhold, New York, 1991) pp. 350–372.