More Web Proxy on the site http://driver.im/

article

Variations on memetic algorithms for graph coloring problems

Authors:

Laurent Moalic,

Alexandre GondranAuthors Info & Claims

Journal of Heuristics, Volume 24, Issue 1

Pages 1 - 24

https://doi.org/10.1007/s10732-017-9354-9

Published: 01 February 2018 Publication History

Abstract

Graph vertex coloring with a given number of colors is a well-known and much-studied NP-complete problem. The most effective methods to solve this problem are proved to be hybrid algorithms such as memetic algorithms or quantum annealing. Those hybrid algorithms use a powerful local search inside a population-based algorithm. This paper presents a new memetic algorithm based on one of the most effective algorithms: the hybrid evolutionary algorithm (HEA) from Galinier and Hao (J Comb Optim 3(4): 379---397, 1999). The proposed algorithm, denoted HEAD--for HEA in Duet--works with a population of only two individuals. Moreover, a new way of managing diversity is brought by HEAD. These two main differences greatly improve the results, both in terms of solution quality and computational time. HEAD has produced several good results for the popular DIMACS benchmark graphs, such as 222-colorings for $${<}{} \texttt {dsjc1000.9}{>}$$, 81-colorings for $${<}{} \texttt {flat1000\_76\_0}{>}$$ and even 47-colorings for $${<}{} \texttt {dsjc500.5}{>}$$ and 82-colorings for $${<}{} \texttt {dsjc1000.5}{>}$$ .

References

[1]

Aardal, K., Hoesel, S., Koster, A., Mannino, C., Sassano, A.: Models and solution techniques for frequency assignment problems. Q. J. Belg. Fr. Ital. Oper. Res. Soc. 1 (4), 261-317 (2003).

[2]

Allignol, C., Barnier, N., Gondran, A.: Optimized flight level allocation at the continental scale. In: International Conference on Research in Air Transportation (ICRAT 2012), Berkeley, California, USA, 22-25 May 2012 (2012).

[3]

Barnier, N., Brisset, P.: Graph coloring for air traffic flow management. Ann. Oper. Res. 130 (1-4), 163-178 (2004).

[4]

Dib, M., Caminada, A., Mabed, H.: Frequency management in radio military networks. In: INFORMS Telecom 2010, 10th INFORMS Telecommunications Conference Montreal, Canada (2010).

[5]

Dubois, N., de Werra, D.: Epcot: an efficient procedure for coloring optimally with Tabu search. Comput. Math. Appl. 25 (10-11), 35-45 (1993).

[6]

Fleurent, C., Ferland, J.: Genetic and hybrid algorithms for graph coloring. Ann. Oper. Res. 63 , 437-464 (1996).

[7]

Galinier, P., Hao, J.-K.: Hybrid evolutionary algorithms for graph coloring. J. Comb. Optim. 3 (4), 379-397 (1999).

[8]

Galinier, P., Hertz, A.: A survey of local search methods for graph coloring. Comput. Oper. Res. 33 , 2547-2562 (2006).

Digital Library

[9]

Galinier, P., Hertz, A., Zufferey, N.: An adaptive memory algorithm for the k -coloring problem. Discret. Appl. Math. 156 (2), 267-279 (2008).

Digital Library

[10]

Galinier, P., Hamiez, J.-P., Hao, J.-K., Porumbel, D.C.: Recent advances in graph vertex coloring. In: Zelinka, I., Snásel, V., Abraham, A. (eds) Handbook of Optimization, Vol. 38 of Intelligent Systems Reference Library, pp. 505-528. Springer, Berlin (2013).

[11]

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

[12]

Gusfield, D.: Partition-distance: a problem and class of perfect graphs arising in clustering. Inf. Process. Lett. 82 (3), 159-164 (2002).

[13]

Hao, J.-K.: Memetic algorithms in discrete optimization. In: Neri, F., Cotta, C., Moscato, P. (eds.) Handbook of Memetic Algorithms, Vol. 379 of Studies in Computational Intelligence, pp. 73-94. Springer, Berlin (2012).

[14]

Hao, J.-K., Wu, Q.: Improving the extraction and expansion method for large graph coloring. Discret. Appl. Math. 160 (16-17), 2397-2407 (2012).

Digital Library

[15]

Held, S., Cook, W., Sewell, E.C.: Safe lower bounds for graph coloring. In: Günlük, O., Woeginger, G.J. (eds.) Integer Programming and Combinatoral Optimization. IPCO 2011. Lecture Notes in Computer Science, Vol. 6655. Springer, Berlin, Heidelberg (2011).

[16]

Hertz, A., de Werra, D.: Using Tabu search techniques for graph coloring. Computing 39 (4), 345-351 (1987).

Digital Library

[17]

Hertz, A., Plumettaz, M., Zufferey, N.: Variable space search for graph coloring. Discret. Appl. Math. 156 (13), 2551-2560 (2008).

Digital Library

[18]

Johnson, D.S., Trick, M.: Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1993, Vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, Providence (1996).

[19]

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. Oper. Res. 39 (3), 378-406 (1991).

Digital Library

[20]

Karp, R.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85-103. Plenum Press, New York (1972).

[21]

Leighton, F.T.: A graph coloring algorithm for large scheduling problems. J. Res. Natl. Bur. Stand. 84 (6), 489-506 (1979).

[22]

Lewis, R.: Graph coloring and recombination. In: Kacprzyk, J., Pedrycz, W. (eds.) Handbook of Computational Intelligence, pp. 1239-1254. Springer, Berlin (2015). (Ch. Graph Coloring and Recombination).

[23]

Lü, Z., Hao, J.-K.: A memetic algorithm for graph coloring. Eur. J. Oper. Res. 203 (1), 241-250 (2010).

[24]

Malaguti, E., Toth, P.: A survey on vertex coloring problems. Int. Trans. Oper. Res. 17 (1), 1-34 (2010).

[25]

Malaguti, E., Monaci, M., Toth, P.: An exact approach for the vertex coloring problem. Discret. Optim. 8 (2), 174-190 (2011).

Digital Library

[26]

Porumbel, D.C., Hao, J.-K., Kuntz, P.: An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring. Comput. Oper. Res. 37 , 1822-1832 (2010).

Digital Library

[27]

Titiloye, O., Crispin, A.: Graph coloring with a distributed hybrid quantum annealing algorithm. In: O'Shea, J., Nguyen, N., Crockett, K., Howlett, R., Jain, L. (eds.) Agent and Multi-Agent Systems: Technologies and Applications. Lecture Notes in Computer Science, vol. 6682, pp. 553-562. Springer, Berlin (2011a).

[28]

Titiloye, O., Crispin, A.: Quantum annealing of the graph coloring problem. Discret. Optim. 8 (2), 376-384 (2011b).

Digital Library

[29]

Titiloye, O., Crispin, A.: Parameter tuning patterns for random graph coloring with quantum annealing. PLoS ONE 7 (11), e50060 (2012).

[30]

Wood, D.C.: A technique for coloring a graph applicable to large-scale timetabling problems. Comput. J. 12 , 317-322 (1969).

[31]

Wu, Q., Hao, J.-K.: Coloring large graphs based on independent set extraction. Comput. Oper. Res. 39 (2), 283-290 (2012).

Digital Library

[32]

Zufferey, N., Amstutz, P., Giaccari, P.: Graph colouring approaches for a satellite range scheduling problem. J. Sched. 11 (4), 263-277 (2008).

Digital Library

Cited By

Khassiba A(2024)An efficient backtracking heuristic for the resource allocation problem with compatibility and exclusivity constraintsJournal of Heuristics10.1007/s10732-024-09538-x31:1Online publication date: 26-Nov-2024
https://dl.acm.org/doi/10.1007/s10732-024-09538-x
Goudet OGrelier CLesaint DElkind E(2023)New bounds and constraint programming models for the weighted vertex coloring problemProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/214(1927-1934)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/214
Fekete SKeldenich PKrupke DSchirra S(2023)Minimum Partition into Plane Subgraphs: The CG:SHOP Challenge 2022ACM Journal of Experimental Algorithmics10.1145/360490728(1-13)Online publication date: 11-Aug-2023
https://dl.acm.org/doi/10.1145/3604907
Show More Cited By

Variations on memetic algorithms for graph coloring problems
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

Recommendations

About S-packing coloring of subcubic graphs
Abstract
For a non-decreasing sequence of integers ( a 1 , a 2 , … , a k ), an ( a 1 , a 2 , … , a k )-packing coloring of a graph G is a partition of V ( G ) into k subsets V 1 , V 2 , … , V k such that the distance between any two distinct vertices x , ...
Acyclic 3-choosability of sparse graphs with girth at least 7

Every planar graph is known to be acyclically 7-choosable and is conjectured to be acyclically 5-choosable (Borodin et al. 2002 [4]). This conjecture if proved would imply both Borodin's acyclic 5-color theorem (1979) and Thomassen's 5-choosability ...
2-distance (Δ+2)-coloring of planar graphs with girth six and Δ≥18

It was proved in [Z. Dvorak, D. Kral, P. Nejedly@?, R. Skrekovski, Coloring squares of planar graphs with girth six, European J. Combin. 29 (4) (2008) 838-849] that every planar graph with girth g>=6 and maximum degree @D>=8821 is 2-distance (@D+2)-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Heuristics

Journal of Heuristics Volume 24, Issue 1

February 2018

107 pages

ISSN:1381-1231

Issue’s Table of Contents

Copyright © Copyright © 2018 Springer Science+Business Media, LLC, part of Springer Nature.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 February 2018

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Khassiba A(2024)An efficient backtracking heuristic for the resource allocation problem with compatibility and exclusivity constraintsJournal of Heuristics10.1007/s10732-024-09538-x31:1Online publication date: 26-Nov-2024
https://dl.acm.org/doi/10.1007/s10732-024-09538-x
Goudet OGrelier CLesaint DElkind E(2023)New bounds and constraint programming models for the weighted vertex coloring problemProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/214(1927-1934)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/214
Fekete SKeldenich PKrupke DSchirra S(2023)Minimum Partition into Plane Subgraphs: The CG:SHOP Challenge 2022ACM Journal of Experimental Algorithmics10.1145/360490728(1-13)Online publication date: 11-Aug-2023
https://dl.acm.org/doi/10.1145/3604907
Crombez LDa Fonseca GFontan FGerard YGonzalez-Lorenzo ALafourcade PLibralesso LMomège BSpalding-Jamieson JZhang BZheng D(2023)Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph ColoringACM Journal of Experimental Algorithmics10.1145/358886928(1-13)Online publication date: 27-Mar-2023
https://dl.acm.org/doi/10.1145/3588869
Guo PGuo B(2023)NERS_HEAD: a new hybrid evolutionary algorithm for solving graph coloring problemSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-08413-427:17(12117-12131)Online publication date: 16-May-2023
https://dl.acm.org/doi/10.1007/s00500-023-08413-4
Watkins GMontana GBranke J(2023)Generating a Graph Colouring Heuristic with Deep Q-Learning and Graph Neural NetworksLearning and Intelligent Optimization10.1007/978-3-031-44505-7_33(491-505)Online publication date: 4-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-44505-7_33
Pinsolle JGoudet OEnderli CHao J(2023)A Memetic Algorithm for Deinterleaving Pulse TrainsEvolutionary Computation in Combinatorial Optimization10.1007/978-3-031-30035-6_5(66-81)Online publication date: 12-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30035-6_5
Pan SMa YWang YZhou ZJi JYin MHu S(2022)An improved master-apprentice evolutionary algorithm for minimum independent dominating set problemFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-022-2023-717:4Online publication date: 12-Dec-2022
https://dl.acm.org/doi/10.1007/s11704-022-2023-7
Zhong LZhou YZhou GLuo Q(2022)Enhanced discrete dragonfly algorithm for solving four-color map problemsApplied Intelligence10.1007/s10489-022-03791-y53:6(6372-6400)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1007/s10489-022-03791-y
Pinard MMoalic LBrévilliers MLepagnot JIdoumghar L(2020)A Memetic Approach for the Unicost Set Covering ProblemLearning and Intelligent Optimization10.1007/978-3-030-53552-0_23(233-248)Online publication date: 24-May-2020
https://dl.acm.org/doi/10.1007/978-3-030-53552-0_23
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents