Tesis
Structure-Driven Randomized Particle Swarm Optimization
Fecha
2017-12-05Registro en:
Aguilar Canepa, José Carlos. (2016). Structure-Driven Randomized Particle Swarm Optimization. (Maestría en Ciencias de la Computación). Instituto Politécnico Nacional,
Centro de Investigación en Computación, México.
Autor
Aguilar Canepa, José Carlos
Institución
Resumen
El problema de coloreado de grafos es uno de los problemas más conocidos en las ciencias de la computación. Dado que fue uno de los primeros problemas en ser demostrado pertenecer a la clase de complejidad NP-Difícil, ha recibido una gran cantidad de atención e interés en el campo. El problema puede definirse de la siguiente manera: dado un grafo G = (V;E), definir una función f : V ! f1; 2; : : : ; kg con la condición que, si (u; v) 2 E, entonces f(u) 6= f(e).
Dicha función f se denomina un k-coloreado, y el valor k más pequeño para el cual un grafo G tiene un k-coloreado se denomina su número cromático, denotado (G). Así pues, el problema de coloreado de grafos consiste en hallar el número cromático (G) de un grafo dado G.
Diversas estrategias han sido desarrolladas para resolver el problema de coloreado de grafos.
Algoritmos exactos han sido propuestos para instancias pequeñas, pudiendo colorear satisfactoriamente grafos pequeños de poco más de un centenar de vértices. Por otro lado, se han propuesto algunos algoritmos aproximados, capaces de garantizar que la cantidad de colores utilizada en la solución encontrada permanece dentro de determinado radio del número cromático. La gran mayoría de algoritmos propuestos para el coloreado de grafos, sin embargo, son técnicas heurísticas, que pueden abarcar desde simples algoritmos voraces, pasando por técnicas de búsqueda local, hasta complejos sistemas metaheurísticos basados en poblaciones como algoritmos genéticos, colonias de hormigas o enjambres de partículas.
En este trabajo, se propone modificar un conocido algoritmo aproximado utilizando una técnica llamada Búsqueda guiada por Estructura (Structure-driven Search, SdS) que consiste en identificar una propiedad o característica inherente a un problema (su estructura) la cual es explotada por un algoritmo aproximado, y perturbarla en cierto modo que permita mejorar el desempeño del algoritmo. Para esto, se presenta un análisis del algoritmo seleccionado y se explica la manera en como la Búsqueda guiada por Estructura fue aplicada al mismo. El desempeño del algoritmo propuesto es posteriormente incrementado aún más al combinar la Búsqueda guiada por Estructura con una técnica de optimización conocida como Optimización por Enjambre de Partículas (Particle Swarm Optimization, PSO). Ambas versiones del algoritmo, la propuesta original y la optimizada son ejecutados sobre un conjunto de instancias estandarizadas para comparar su desempeño con el de otros algoritmos del estado del arte, mostrando que el algoritmo propuesto ofrece resultados competitivos. Abstract
The graph coloring problem is one of the most well-known problems in computer science. Since
it was one of the first problems demonstred to belong to the NP-Hard complexity class, it has
received a great amount of research and interest on the field. The graph coloring problem can
be defined as follows: given a graph G = (V, E), define a function f : V → {1, 2, . . . , k} with
the constraint that, if (u, v) ∈ E, then f(u) 6= f(v). Such a function f is called a k-coloring,
and the smallest k for which a graph G has a k-coloring is known as its chromatic number,
denoted χ(G). Therefore, the graph coloring problem consists in, given any graph G, to find
its chromatic number χ(G).
Diverse strategies had been developed to solve the graph coloring problem. Exact algorithms
has been proposed for small instances, being able to successfully color graphs of up to
a hundred vertices. On the other hand, approximated algorithms had been proposed, which
guarantee that the amount of colors used on the solution found are within a certain ratio of
the chromatic number. The vast majority of algorithms proposed for graph coloring, however,
are heuristic techniques, from simple greedy algorithms to local search methods, to complex
metaheuristic systems that are population-based, such as genetic algorithms, ant colonies and
particle swarms.
In this work, we propose a modification for a well-known approximation algorithm, using a
technique called Structure-driven Search (SdS), which consists in identify a particular property
or characteristic inherent to a problem, exploited by an approximation algorithm, and modify
it in some way that allows to improve the performance of the algorithm. In order to do this, the
selected algorithm is analyzed, and the modifications made to apply Structure-driven Search
to the algorithm is explained. The proposed algorithm’s performance is then further improved
by combining Structure-driven Search with an optimization method known as Particle Swarm
Optimization. Both algorithms, the original propose and the optimized one are the executed
over a set of benchmark instances to compare their performance against those of state-of-theart
algorithms, showing that the proposed algorithm offers competitive results.