Evolution of hyperheuristics for the biobjective graph coloring problem using multiobjective genetic programming

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 aim to evolve hyperheuristics for this class of problem using multiobjective genetic programming (MOGP). The major advantage being that these hyperheuristics can then be applied to any instance of this problem. We test the hyperheuristics on benchmark graph coloring problems, and in the absence of an actual Pareto-front, we compare the solutions obtained with existing heuristics. We then further improve the quality of hyperheuristics evolved, and try to make them closer to human-designed heuristics.

REFERENCES

• 1: 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]
• 2: 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.
• 3: 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]
• 4: Rajeev Kumar , Paresh Tolay , Siddharth Tiwary, Enhancing solution quality of the biobjective graph coloring problem using hybridization of EA: biobjective graph coloring problem, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389203]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Stochastic programming

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program synthesis

General Terms:
Algorithms, Design, Experimentation

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