Population-based and Learning-based Metaheuristic Algorithms for the Graph Coloring Problem

摘要

In this paper, two new metaheuristic algorithms for the graph coloring problem are introduced. The first one is a population-based multiagent evolutionary algorithm (MEA), using a multiagent system, where an agent represents a tabu search procedure. Rather than using a single long-term local search procedure, it uses more agents representing short-term local search procedures. Instead of a specific crossover, MBA uses relatively general mechanisms from artificial life, such as lifespans and elite list [3, 4]. We are introducing and investigating a new parametrization system, along with a mechanism of reward and punishment for agents according to change in their fitness. The second algorithm is a pseudo-reactive tabu search (PRTS), introducing a new online learning strategy to balance its own parameter settings. Basically, it is inspired by the idea to learn tabu tenure parameters instead of using constants. Both algorithms empirically outperform basic tabu search algorithm TabuCol [8] on the well-established DIM ACS instances [10]. However, they achieve this by using different strategies. This indeed shows a difference in potential of population-based and learning-based graph coloring metaheuristics.