Performance Comparison of Repair Heuristics for the Circle Packing Problem

摘要

In this work we compare the performance of Repair Heuristics using Genetic Algorithms (GA) results of the solution to the Circle Packing Problem to a set of unit circle problems. The Circle Packing Problem consists of placing a set of circles into a larger containing circle without overlaps, this problem is known to be NP-hard. Given the impossibility to solve this problem efficiently, traditional and metaheuristic methods have been proposed to solve it. A naive representation for chromosomes in a population-based heuristic search leads to high probabilities of violation of the problem constraints. To convert solutions that violate constraints into ones that do not, in this paper we propose and compare three repair heuristics (Repulsion, Delaunay Triangulation-"DT" and Hybrid) that lead the circles to positions where the overlaps are resolved. The experiments show that the Delaunay Triangulation-based repair can produce better solutions than the other two repair heuristics. Further, the Delaunay Triangulation has the lowest computational complexity of the three heuristics proposed.