Evolutionary computation solutions to the circle packing problem

Abstract

In this thesis I present an evolutionary computation based solution to the Circle Packing Problem (ECPP). The Circle Packing Problem consists of placing a set of circles into a container without overlaps; a problem known to be NP-hard. Given the impossibility to solve this problem efficiently, traditional and heuristic methods have been proposed to solve it. A native representation for chromosomes in a population-based heuristic search leads to high probabilities of violation of the problem constraints, i.e. overlapping. To convert solutions that violate constraints into ones that do not (i.e. feasible solutions), in this thesis I propose two repair mechanisms. The first one considers every circle as an elastic ring; overlaps create repulsion forces that lead the circles to positions where the overlaps are resolved. The second one forms a Delaunay Triangulation with the circle centers and repairs the circles in each triangle at a time, making sure repaired triangles are not modified later on. Based on the proposed repair heuristics, I present the results of the solution to the CPP problem to a set of unit circle problems (whose exact optimal solutions are known). These benchmark problems are solved using Genetic Algorithms, Evolutionary Strategies, Particle Swarm Optimization, and Differential Evolution. The performance of the solutions are compared to those known solutions based on the packing density. I then perform a series of experiments to determine the performance of ECPP with non-unitary circles.

En esta tesis se presenta una solución basada en Computación Evolutiva al Problema del Empaquetamiento de Círculos (ECPP). El Problema del Empaquetamiento de Círculos consiste en colocar un conjunto de círculos en un contenedor sin que existan traslapes entre los círculos; un conocido problema que es NP-duro. Dada la imposibilidad de resolver este problema de manera eficiente, se han propuesto métodos tradicionales y heurísticos para resolverlo. Una representación nativa de cromosomas en una búsqueda heurística basada en la población conduce a altas probabilidades de violación de las restricciones del problema, es decir, provoca traslapes. Para convertir las soluciones que violan las restricciones en las que no (es decir, soluciones factibles), en esta tesis se proponen dos mecanismos de reparación. El primero considera cada circulo como un anillo elástico; los traslapes existentes crean fuerzas de repulsión que llevan los círculos a los espacios donde se resuelven estos traslapes. La segunda forma está basada en la Triangulación de Delaunay con los centros de los círculos y las reparaciones de los círculos en cada triangulo a la vez, asegurando triángulos reparados que no serán modificados en el futuro. Basados en las heurísticas de reparación propuestas, se presentan los resultados de la solución al Problema del Empaquetamiento de Círculos para un conjunto de problemas de círculos unitarios (cuyas soluciones ´optimas son conocidas). Estos problemas con ´optimas soluciones conocidas se resuelven usando Algoritmos Genéticos, Estrategias Evolutivas, Optimización por Enjambre de Partículas y Evolución Diferencial. Los rendimientos de las soluciones se comparan con las soluciones conocidas basadas en la densidad del empaquetamiento. Luego se realizó una serie de experimentos para determinar el rendimiento de ECPP con círculos no unitarios.