research-article

Enhancing solution quality of the biobjective graph coloring problem using hybridization of EA: biobjective graph coloring problem

Authors:

Siddharth TiwaryAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 547 - 554

https://doi.org/10.1145/1389095.1389203

Published: 12 July 2008 Publication History

Abstract

We consider a formulation of the biobjective soft graph coloring problem so as to simultaneously minimize the number of colors used as well as the number of edges that connect vertices of the same color. We solve this problem using well-known multiobjective evolutionary algorithms (MOEA), and observe that they show good diversity and (local) convergence. Then, we consider and adapt the single objective heuristics to yield a Pareto-front and observe that the quality of solutions obtained by MOEAs is much inferior. We incorporate the problem specific knowledge into representation and reproduction operators, in an incremental way, and get good quality solutions using MOEAs too. The spin-off point we stress with this work is that, for real world applications of unknown nature, it is indeed difficult to realize how good/bad the quality of the solutions obtained is.

References

[1]

H. Al-Omari and K. E. Sabri. New graph coloring algorithms. Journal of Mathematics and Statistics, pages 739--741, 2006.]]

[2]

S. Bhowmick and P. Hovland. A backtracking correction heuristic for improving performance of graph coloring algorithms. 2nd Int. Workshop on Combinatorial Scientific Computing, 2005.]]

[3]

A. Blum. New approximation algorithms for graph coloring. J. ACM, 41(3):470--516, 1994.]]

Digital Library

[4]

D. Brélaz. New methods to color the vertices of a graph. Commun. ACM, 22(4):251--256, 1979.]]

Digital Library

[5]

M. Caramia and P. Dell’Olmo. Bounding vertex coloring by truncated multistage branch and bound. Netw., 44(4):231--242, 2004.]]

Digital Library

[6]

C. Croitoru, H. Luchian, O. Gheorghies, and A. Apetrei. A new genetic graph coloring heuristic. Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, 63--74, 2002.]]

[7]

J. Culberson. Iterated greedy graph coloring and the difficulty landscape. Technical Report TR 92--07, 1992.]]

[8]

K. Deb. Multiobjective Optimization Using Evolutionary Algorithms. Chichester, UK: Wiley, 2001.]]

Digital Library

[9]

K. Deb and R. B. Agrawal. Simulated binary crossover for continuous search space. Complex Systems, 9:115--148, 1995.]]

[10]

K. Deb and S. Jain. Running performance metrics for evolutionary multiobjective optimization. In SEAL, Singapore, pages 13--20, November 2002.]]

[11]

N. Drechsler, W. Günther, and R. Drechsler. Efficient graph coloring by evolutionary algorithms. In Proceedings of the 6th International Conference on Computational Intelligence, Theory and Applications, pages 30--39, London, UK, 1999. Springer-Verlag.]]

Digital Library

[12]

A. Eiben and J. van der Hauw. Graph coloring with adaptive genetic algorithms. Technical Report TR 96--11, Leiden University, August 1996.]]

[13]

A. E. Eiben, J. K. V. D. Hauw, and J. I. V. Hemert. Graph coloring with adaptive evolutionary algorithms. Journal of Heuristics, 4(1):25--46, 1998.]]

Digital Library

[14]

L. Epstein, A. Levin, and G. J. Woeginger. Graph coloring with rejection. In ESA'06: Proceedings of the 14th conference on Annual European Symposium, pages 364--375, London, UK, 2006. Springer-Verlag.]]

Digital Library

[15]

E. Falkenauer. A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 2:5--30, 1996.]]

[16]

U. Feige and J. Kilian. Zero knowledge and the chromatic number. J. Comput. Syst. Sci., 57(2):187--199, 1998.]]

Digital Library

[17]

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

[18]

F. Huang and G. Chen. A symmetry-breaking approach of the graph coloring problem with gas. Computer Supported Cooperative Work in Design, 2004. Proceedings. The 8th International Conference on, 2:717--719 Vol.2, 26--28 May 2004.]]

[19]

D. R. Karger, R. Motwani, and M. Sudan. Approximate graph coloring by semidefinite programming. In IEEE Symposium on Foundations of Computer Science, pages 2--13, 1994.]]

Digital Library

[20]

R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85--103. Plenum Press, 1972.]]

[21]

R. Kumar and P. Rockett. Improved Sampling of the Pareto-Front in Multiobjective Genetic Optimizations by Steady-State Evolution: A Pareto Converging Genetic Algorithm. Evolutionary Computation, 10(3):283--314, Fall 2002.]]

Digital Library

[22]

R. Kumar, P. K. Singh, A. P. Singhal, and A. Bhartia. Evolutionary and heuristic algorithms for 0-1 knapsack problem. In 10th Online World Conf. Soft Computing & Indutrial Applications, Applications of Soft Computing: Recent Trends, 2005.]]

[23]

A. Marino, A. Prugel-Bennett, and C. Glass. Improving graph colouring with linear programming and genetic algorithms. In K. Miettinen, M. M. Makela, and J. Toivanen (Eds.), Proceedings of EUROGEN99, Jyvaskyla, Finland, 113--118, 1999.]]

[24]

D. W. Matula and L. L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. J. ACM, 30(3):417--427, 1983.]]

Digital Library

[25]

A. Mehrotra and M. A. Trick. A column generation approach for graph coloring. INFORMS Journal on Computing, 8:344--354, 1996.]]

Digital Library

[26]

C. Mumford. New order-based crossovers for the graph coloring problem. In Parallel Problem Solving from Nature -- PPSN IX, pages 880--889, Reykjavik, Iceland, September 2006. LNCS 4193, Springer.]]

Digital Library

[27]

E. Ryan, R. M. A. Azad, and C. Ryan. On the performance of genetic operators and the random key representation. In Genetic Programming, Lecture Notes in Computer Science, pages 162--173, Berlin/Heidelberg, 2004. Springer.]]

[28]

A. Wigderson. Improving the performance guarantee for approximate graph coloring. J. ACM, 30(4):729--735, 1983.]]

Digital Library

[29]

J. Yu and S. Yu. A novel parallel genetic algorithm for the graph coloring problem in vlsi channel routing. Natural Computation, 2007. ICNC 2007. Third International Conference on, 4, 101--105, 2007.]]

Digital Library

[30]

E. Zitzler and L. Thiele. Multiobjective optimization using evolutionary algorithms -- a comparative case study. In Parallel Problem Solving from Nature -- PPSN V, pages 292--301, Berlin/Heidelberg, 292--301, 1998. Springer.]]

Digital Library

[31]

J. Zoellner and C. Beall. A breakthrough in spectrum conserving frequency assignment technology. IEEE Trans Electromag Compat, EMC--19:313--319, 1977.]]

[32]

D. Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3(6):103--128, 2007.]]

Cited By

Marappan RSethumadhavan G(2020)Complexity Analysis and Stochastic Convergence of Some Well-known Evolutionary Operators for Solving Graph Coloring ProblemMathematics10.3390/math80303038:3(303)Online publication date: 25-Feb-2020
https://doi.org/10.3390/math8030303
Saha SKumar RBaboo G(2013)Characterization of graph properties for improved Pareto fronts using heuristics and EA for bi-objective graph coloring problemApplied Soft Computing10.1016/j.asoc.2012.06.02113:5(2812-2822)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1016/j.asoc.2012.06.021
Pal ARay BZakaria NNaono KSarma S(2012)Generating Chromatic Number of a Graph using Ant Colony Optimization and Comparing the Performance with Simulated AnnealingProcedia Engineering10.1016/j.proeng.2012.10.06950(629-639)Online publication date: Jan-2012
https://doi.org/10.1016/j.proeng.2012.10.069
Show More Cited By

Index Terms

Enhancing solution quality of the biobjective graph coloring problem using hybridization of EA: biobjective graph coloring problem
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

Recommendations

Evolution of hyperheuristics for the biobjective graph coloring problem using multiobjective genetic programming
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

We consider a formulation of the biobjective soft graph coloring problem so as to simultaneously minimize the number of colors used as well as the number of edges that connect vertices of the same color. We aim to evolve hyperheuristics for this class ...
Improvement of bounded-diameter MST instances with hybridization of multi-objective EA
ICCCS '11: Proceedings of the 2011 International Conference on Communication, Computing & Security

The Bounded Diameter (a.k.a Diameter Constraint) Minimum Spanning Tree (BDMST/DCMST) is a well-known combinatorial optimization problem. In this work, we recast a few well-known heuristics, which are evolved for BDMST problem, to a Bi-Objective Minimum ...
Evolution of hyperheuristics for the biobjective 0/1 knapsack problem by multiobjective genetic programming
GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

The 0/1 knapsack problem is one of the most exhaustively studied NP-hard combinatorial optimization problems. Many different approaches have been taken to obtain an approximate solution to the problem in polynomial time. Here we consider the biobjective ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
282
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Marappan RSethumadhavan G(2020)Complexity Analysis and Stochastic Convergence of Some Well-known Evolutionary Operators for Solving Graph Coloring ProblemMathematics10.3390/math80303038:3(303)Online publication date: 25-Feb-2020
https://doi.org/10.3390/math8030303
Saha SKumar RBaboo G(2013)Characterization of graph properties for improved Pareto fronts using heuristics and EA for bi-objective graph coloring problemApplied Soft Computing10.1016/j.asoc.2012.06.02113:5(2812-2822)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1016/j.asoc.2012.06.021
Pal ARay BZakaria NNaono KSarma S(2012)Generating Chromatic Number of a Graph using Ant Colony Optimization and Comparing the Performance with Simulated AnnealingProcedia Engineering10.1016/j.proeng.2012.10.06950(629-639)Online publication date: Jan-2012
https://doi.org/10.1016/j.proeng.2012.10.069
Pal ARay BZakaria NSarma S(2012)Comparative Performance of Modified Simulated Annealing with Simple Simulated Annealing for Graph Coloring ProblemProcedia Computer Science10.1016/j.procs.2012.04.0349(321-327)Online publication date: 2012
https://doi.org/10.1016/j.procs.2012.04.034
(2012)Volume Removed - Publisher's DisclaimerProcedia Engineering10.1016/S1877-7058(14)00002-250(1-966)Online publication date: 2012
https://doi.org/10.1016/S1877-7058(14)00002-2
Saha SBaboo GKumar R(2011)An Efficient EA with Multipoint Guided Crossover for Bi-objective Graph Coloring ProblemContemporary Computing10.1007/978-3-642-22606-9_17(135-145)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22606-9_17
Tolay PKumar RRothlauf F(2009)Evolution of hyperheuristics for the biobjective graph coloring problem using multiobjective genetic programmingProceedings of the 11th Annual conference on Genetic and evolutionary computation10.1145/1569901.1570247(1939-1940)Online publication date: 8-Jul-2009
https://dl.acm.org/doi/10.1145/1569901.1570247

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten