Automatically generated algorithms for the vertex coloring problem.

Area of Science:

• Combinatorial Optimization
• Computer Science
• Artificial Intelligence

Background:

• The vertex coloring problem, a fundamental challenge in combinatorial optimization, involves assigning colors to graph vertices to avoid adjacent conflicts while minimizing total colors.
• Its NP-hard nature presents significant computational difficulties, despite numerous practical applications.
• Existing high-performance solutions often arise from hybridizing various heuristics, yet automated exploration of these heuristic combinations remains underexplored.

Purpose of the Study:

• To investigate the efficacy of evolutionary algorithms in automatically generating effective heuristic combinations for the vertex coloring problem.
• To develop and evaluate novel algorithms derived from combining elementary heuristics through evolutionary approaches.
• To compare the performance of these newly generated algorithms against established heuristics on challenging benchmark instances.

Main Methods:

• Employing evolutionary algorithms to systematically explore the search space of heuristic combinations for vertex coloring.
• Automatically generating three distinct algorithms by combining predefined elementary heuristics.
• Conducting a computational experiment to numerically assess the performance of the new algorithms against selected literature heuristics.

Main Results:

• The newly developed algorithms achieved an average relative error of 29.97% on difficult DIMACS benchmark instances.
• In contrast, four established heuristics from the literature exhibited a significantly higher average relative error of 59.73%.
• The evolutionary approach successfully identified superior heuristic combinations, outperforming existing methods.

Conclusions:

• Evolutionary algorithms offer a powerful mechanism for automating the discovery of effective heuristic combinations in combinatorial optimization problems like vertex coloring.
• The generated algorithms demonstrate a substantial improvement in solution quality and computational efficiency over traditional heuristics.
• This research highlights the potential of automated heuristic discovery for advancing the state-of-the-art in solving NP-hard problems.