Two genetic algorithms for the bandwidth multicoloring problem

Jasmina Fijuljanin

doi:10.2298/YJOR100927020F

Authors

Jasmina Fijuljanin Faculty of Matematics, Belgrade

DOI:

https://doi.org/10.2298/YJOR100927020F

Keywords:

evolutionary computation, graph coloring problem, combinatorial optimization

Abstract

In this paper the Bandwidth Multicoloring Problem (BMCP) and the Bandwidth Coloring Problem (BCP) are considered. The problems are solved by two genetic algorithms (GAs) which use the integer encoding and standard genetic operators adapted to the problems. In both proposed implementations, all individuals are feasible by default, so search is directed into the promising regions. The first proposed method named GA1 is a constructive metaheuristic that construct solution, while the second named GA2 is an improving metaheuristic used to improve an existing solution. Genetic algorithms are tested on the publicly-available GEOM instances from the literature. Proposed GA1 has achieved a much better solution than the calculated upper bound for a given problem, and GA2 has significantly improved the solutions obtained by GA1. The obtained results are also compared with the results of the existing methods for solving BCP and BMCP.

References

Anderson, L.G., “A simulation study of some dynamic channel assignment algorithms in a high capacity mobile telecommunications system”, IEEE Transactions on Communications, 21 (1973) 1294–1301.

Avanthay, C., Hertz, A., and Zufferey, N., “A variable neighborhood search for graph coloring”, European Journal of Operational Research, 151 (2) (2003) 379–388.

Blöchliger, I., and Zufferey, N., "A graph coloring heuristic using partial solutions and a reactive tabu scheme", Computers and Operations Research, 35 (3) (2008) 960–975.

Bouchard, M., Čangalović, M., and Hertz, A., "On a reduction of the interval coloring problem to a series of bandwidth coloring problems", Journal of Scheduling, 13 (6) (2010) 583-595.

Brelaz, D., „New methods to color the vertices of a graph“, Communications Of The ACM, 22 (4) (1979) 251–256.

Chams, M., Hertz, A., and De Werra, D., “Some experiments with simulated annealing for coloring graphs”, European Journal of Operational Research, 32 (2) (1987) 260–266.

Chiarandini, M., and Stützle, T., An application of iterated local search to graph coloring, in: D. S. Johnson (ed.), Computational Symposium on Graph Coloring and its Generalizations, 2002, 112–125.

Chiarandini, M., and Stützle, T., "Stochastic local search algorithms for graph set T-colouring and frequency assignment", Springer Science + Business Media, 12 (2007) 371–403.

Chiarandini, M., Dumitrescu, I., and Stützle, T., “Stochastic local search algorithms for the graph colouring problem”, in T.F. Gonzalez (ed.), Handbook of Approximation Algorithms and Metaheuristics, Chapman & Hall/CRC, Boca Raton, FL, USA, 2007, 1-17.

Christofides, N., “An algorithm for the chromatic number of a graph”, The Computer Journal, 14 (1) (1971) 38–39.

Dorne, R., and Hao, J.K., "A new genetic local search algorithm for graph coloring", PPSN 98, Lecture Notes In Computer Science, Berlin: Springer, 1498 (1998) 745-760.

Dorne, R., and Hao, J.K., “Tabu search for graph coloring, t-colorings and set t-colorings” in: S. Voss (ed.), Meta-Heuristics Advances and Trends in Local Search Paradigms for Optimization, Kluwer, 1998, 77-92.

Eraghi, A.E., Torkestani, J.A., and Meybodi, M.R., „Solving the bandwidth multicoloring problem: a cellular learning automata approach“, Proceedings Of the 2009 International Conference On Machine Learning And Computing, Perth, Australia, 2009.

Fijuljanin, J., "Genetic algorithm for the bandwidth coloring problem and its application in teaching", Master thesis (in Serbian), Faculty of Mathematics, University of Belgrade, 2010.

Fleurent, C., and Ferland, J.A., “Object-oriented implementation of heuristic search methods for graph coloring, maximum clique, and satisfiability”, Cliques, Coloring, and Satisfiability: 2nd DIMACS Implementation Challenge, 1993, DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, (26) (1996) 619–652.

Galinier, P., and Hao, J.K., “Hybrid evolutionary algorithms for graph coloring”, Journal of Combinatorial Optimization, 3 (4) (1999) 379–397.

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

Hertz, A., Plumettaz, A., and Zufferey, N., “Variable space search for graph coloring”, Discrete Applied Mathematics, 156 (13) (2008) 2551–2560.

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

Johnson, D.S., Aragon, C.R., McGeoch, L.A., and Schevon, C., “Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning”, Operations Research, 39 (3) (1991) 378–406.

Kratica, J., Čangalović, M., and Kovačević-Vujčić, V., "Computing minimal doubly resolving sets of graphs", Computers & Operations Research, 36 (7) (2009) 2149-2159.

Kratica, J., Kovačević-Vujčić, V., and Čangalović, M., "Computing strong metric dimension of some special classes of graphs by genetic algorithms", Yugoslav Journal of Operations Research, 18 (2) (2008) 143-151.

Kratica, J., Kovačević-Vujčić, V., and Čangalović, M., "Computing the metric dimension of graphs by genetic algorithms", Computational Optimization and Applications, 44 (2) (2009) 343-361.

Kratica, J., Milanović, M., Stanimirović, Z., and Tošić, D., "An evolutionary based approach for solving a capacitated hub location problem", Applied Soft Computing, DOI: 10.1016/j.asoc.2010.05.035.

Lim, A., Lou, Q., Rodrigues, B., and Zhu, Y., “Heuristic methods for graph coloring problems”, in: Proceedings of the 2005 ACM Symposium on Applied Computing, Santa Fe, NM, 2005, 933–939.

Lim, A., Zhang, X., and Zhu, Y., “A hybrid methods for the graph coloring and its related problems”, in: Proceedings of MIC2003: The Fifth Metaheuristic International Conference, Kyoto, Japan, 2003.

Lü, Z., and Hao, J.K., "A memetic algorithm for graph coloring", European Journal of Operational Research, 203 (1) (2010) 241–250.

Malaguti, E., “The vertex coloring problem and its generalizations“, Dottorato di Ricerca in Automatica e Ricerca Operativa, Universita degli studi di Bologna, Bologna, 2009.

Malaguti, E., and Toth, P., "An evolutionary approach for bandwidth multicoloring problems", European Journal of Operational Research, 189 (2008) 638–651.

Malaguti, E., Monaci, M., and Toth, P., "A metaheuristic approach for the vertex coloring problem", INFORMS Journal on Computing, 20 (2) (2008) 302-320.

Marti, R., Gortazar, F., and Duarte, A., “Heuristics for the bandwidth coloring problem”, 2009.

Matić, D., "A genetic algorithm for composing music", Yugoslav Journal of Operations Research, 20 (1) (2010) 157-177.

Phan, V., and Skiena, S., “Coloring graphs with a general heuristic search engine”, in: [38], 2002, 92–99.

Porumbel, C.D., Hao, J.K., and Kuntz, P., “A search space “cartography” for guiding graph coloring heuristics”, Computers and Operations Research, 37 (4) (2010) 769–778.

Prestwich, S., “Constrained bandwidth multicoloration neighborhoods”, in: [38], 2002, 126-133.

Prestwich, S., “Generalized graph colouring by a hybrid of local search and constraint programming”, Technical Report, Cork Constraint Computation Center, Ireland, 2005.

Resende, M.G.C., and Ribeiro, C.C., “Greedy randomized adaptive search procedures”, Handbook of Metaheuristic, Kluwer Academic Publishers, 2003, 219–249.

Trick, M.A., Computational Symposium: Graph Coloring and its Generalization, Cornell University, Ithaca, NY, 2002. <http://mat.gsia.cmu.edu/COLOR02/>.

Welsh, D.J.A., and Powell, M.B., “An upper bound for the chromatic number of a graph and its application to timetabling problems”, The Computer Journal, 10 (1) (1967) 85–86.

Two genetic algorithms for the bandwidth multicoloring problem

Authors

DOI:

Keywords:

Abstract

References

Downloads

Published

Issue

Section

License