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

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: Avrim Blum, New approximation algorithms for graph coloring, Journal of the ACM (JACM), v.41 n.3, p.470-516, May 1994 [doi>10.1145/176584.176586]
• 4: Daniel Brélaz, New methods to color the vertices of a graph, Communications of the ACM, v.22 n.4, p.251-256, April 1979 [doi>10.1145/359094.359101]
• 5: Massimiliano Caramia , Paolo Dell'Olmo, Bounding vertex coloring by truncated multistage branch and bound, Networks, v.44 n.4, p.231-242, December 2004 [doi>10.1002/net.v44:4]
• 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: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 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: Nicole Drechsler , Wolfgang Günther , Rolf Drechsler, Efficient Graph Coloring by Evolutionary Algorithms, Proceedings of the 6th International Conference on Computational Intelligence, Theory and Applications: Fuzzy Days, p.30-39, May 25-28, 1999
• 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. Van Der Hauw , J. I. Van Hemert, Graph Coloring with Adaptive Evolutionary Algorithms, Journal of Heuristics, v.4 n.1, p.25-46, June 1998 [doi>10.1023/A:1009638304510]
• 14: Leah Epstein , Asaf Levin , Gerhard J. Woeginger, Graph coloring with rejection, Proceedings of the 14th conference on Annual European Symposium, p.364-375, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_34]
• 15: E. Falkenauer. A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 2:5--30, 1996.
• 16: Uriel Feige , Joe Kilian, Zero knowledge and the chromatic number, Journal of Computer and System Sciences, v.57 n.2, p.187-199, Oct. 1998 [doi>10.1006/jcss.1998.1587]
• 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. Karger , R. Motwani , M. Sudan, Approximate graph coloring by semidefinite programming, Proceedings of the Proceedings 35th Annual Symposium on Foundations of Computer Science, p.2-13, November 20-22, 1994 [doi>10.1109/SFCS.1994.365710]
• 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: Rajeev Kumar , Peter Rockett, Improved sampling of the Pareto-front in multiobjective genetic optimizations by steady-state evolution: a Pareto converging genetic algorithm, Evolutionary Computation, v.10 n.3, p.283-314, Fall 2002 [doi>10.1162/106365602760234117]
• 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: David W. Matula , Leland L. Beck, Smallest-last ordering and clustering and graph coloring algorithms, Journal of the ACM (JACM), v.30 n.3, p.417-427, July 1983 [doi>10.1145/2402.322385]
• 25: A. Mehrotra and M. A. Trick. A column generation approach for graph coloring. INFORMS Journal on Computing, 8:344--354, 1996.
• 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.
• 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: Avi Wigderson, Improving the performance guarantee for approximate graph coloring, Journal of the ACM (JACM), v.30 n.4, p.729-735, Oct. 1983 [doi>10.1145/2157.2158]
• 29: Jiaqi Yu , Songnian Yu, A Novel Parallel Genetic Algorithm for the Graph Coloring Problem in VLSI Channel Routing, Proceedings of the Third International Conference on Natural Computation (ICNC 2007), p.101-105, August 24-27, 2007 [doi>10.1109/ICNC.2007.121]
• 30: Eckart Zitzler , Lothar Thiele, Multiobjective Optimization Using Evolutionary Algorithms - A Comparative Case Study, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.292-304, September 27-30, 1998
• 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies; Heuristic methods

General Terms:
Algorithms, Design, Experimentation

Keywords:
combinatorial optimization, evolutionary algorithm, genetic algorithm, heuristics, multi-objective optimization, optimization methods, pareto front, soft graph coloring