Computación evolutiva de bosques de expansión mínimos con restricción de grado y de rol

Abstract

Encontrar el árbol de expansión mínimo con restricción de grado de un grafo
(DCMST por sus siglas en inglés) es un problema NP-complejo ampliamente estudiado.
Una de sus aplicaciones más importantes es el dise~no de redes. Aquí nosotros
tratamos una nueva variante del problema DCMST, que consiste en encontrar el
árbol de expansión mínimo no solo con restricciones de grado, sino también con restricciones
de rol (DRCMST), es decir, a~nadimos restricciones para restringir el rol
que los nodos tienen en el árbol. Estos roles pueden ser nodo raíz, nodo intermedio o
nodo hoja. Por otra parte, no limitamos el número de nodos raíz a uno, por lo que,
en general, construiremos bosques de DRCMSTs. El modelado en los problemas de
dise~no de redes puede beneficiarse de la posibilidad de generar más de un árbol y
determinar el rol de los nodos en la red.
Proponemos una nueva representación basada en permutaciones para codificar
los bosques de DRCMSTs. En esta nueva representación, una permutación codifica
simultáneamente todos los árboles que se construirán. Nosotros simulamos una amplia
variedad de problemas DRCMST que optimizamos utilizando ocho algoritmos
de computación evolutiva diferentes que codifican los individuos de la población utilizando
la representación propuesta. Los algoritmos que utilizamos son: algoritmo
de estimación de distribuciones (EDA), algoritmo genético generacional (gGA), algoritmo
genético de estado estacionario (ssGA), estrategia evolutiva basada en la
matriz de covarianzas (CMAES), evolución diferencial (DE), estrategia evolutiva elitista
(ElitistES), estrategia evolutiva no elitista (NonElitistES) y optimización por
enjambre de partículas (PSO). Los mejores resultados fueron para el algoritmo de
estimación de distribuciones utilizado y ambos tipos de algoritmos genéticos, aunque
los algoritmos genéticos fueron significativamente más rápidos.---ABSTRACT---Finding the degree-constrained minimum spanning tree (DCMST) of a graph is a
widely studied NP-hard problem. One of its most important applications is network
design. Here we deal with a new variant of the DCMST problem, which consists of
finding not only the degree- but also the role-constrained minimum spanning tree
(DRCMST), i.e., we add constraints to restrict the role of the nodes in the tree to
root, intermediate or leaf node. Furthermore, we do not limit the number of root
nodes to one, thereby, generally, building a forest of DRCMSTs. The modeling of
network design problems can benefit from the possibility of generating more than
one tree and determining the role of the nodes in the network.
We propose a novel permutation-based representation to encode the forest of
DRCMSTs. In this new representation, one permutation simultaneously encodes
all the trees to be built. We simulate a wide variety of DRCMST problems which
we optimize using eight diferent evolutionary computation algorithms encoding individuals
of the population using the proposed representation. The algorithms we
use are: estimation of distribution algorithm (EDA), generational genetic algorithm
(gGA), steady-state genetic algorithm (ssGA), covariance matrix adaptation evolution
strategy (CMAES), diferential evolution (DE), elitist evolution strategy (ElististES),
non-elitist evolution strategy (NonElististES) and particle swarm optimization
(PSO). The best results are for the estimation of distribution algorithm and
both types of genetic algorithms, although the genetic algorithms are significantly
faster.
iv