Objetos Evolutivos Paralelos

Durante la última década los métodos de optimización han cobrado más importancia debido, sobre todo, a que con ellos se pueden resolver ciertos problemas de ingeniería que sólo pueden abordarse mediante aproximación en los computadores actuales.

A pesar de que la mayoría de los investigadores afirman que los distintos paradigmas de computación evolutiva sólo difieren en cuanto a la representación y a los operadores de individuo y de población, no existe una visión unificada para todos ellos, y mucho menos una herramienta que los unifique.

La aplicación de los algoritmos evolutivos a problemas con un gran espacio de búsqueda, con costosas funciones de evaluación y utilizando grandes tamaños de población, hace necesaria la realización de implementaciones los más rápidas posibles, por lo que el camino natural es la paralelización del algoritmo evolutivo.

Podemos encontrar dos enfoques principales para llevar a cabo la paralelización de algoritmos evolutivos (Adamidis [#!Adamidis!#] y Cantú-Paz [#!CantuPaz!#]):

• Paralelización estándar o global (Farming): Tal y como proponen Fogarty y Huang [#!FogartyHuang!#], Abramson y Abela [#!AbramsonAbela!#], o Hauser y Männer [#!HauserManner!#], la evaluación de los cromosomas y/o la aplicación de los operadores genéticos se realiza en paralelo. Un sólo procesador maestro supervisa toda la población y realiza la selección, los procesadores esclavos reciben los individuos para evaluarlos y, a veces, aplicarles los operadores genéticos.

• Paralelizacion por separación: La principal característica de este enfoque es que toda la población se encuentra distribuida bien como subpoblaciones o bien como individuos:
  • Paralelización de grano grueso (Migración): La población se divide en pequeñas subpoblaciones de igual tamaño, que se asignan a distintos procesadores. Periódicamente cada procesador selecciona sus mejores individuos y los envía a sus procesadores más cercanos, recibiendo copias de los mejores individuos de sus vecinos que reemplazarán a los peores individuos de la población, esto se conoce como migración de individuos. A este tipo de algoritmos también se les conoce como algoritmos evolutivos distribuidos (Tanese [#!Tanese!#], Pettey et al. [#!Pettey!#], Cantú-Paz y Goldberg [#!CantuPazGoldberg!#]). Según el esquema de comunicación entre las distintas subpoblaciones, se pueden distinguir los algoritmos distribuidos en estrella, en red, en anillo, etc.
  • Paralelización de grano fino (Difusión): En este modelo sólo evoluciona una población de forma que se asigna cada individuo de la población en una celda de una rejilla plana, tal que, cada procesador tiene asignadas partes de la población. La selección y el cruce se realizan sólo entre individuos más próximos en la rejilla de acuerdo a una estrategia predefinida. Este modelo es una aproximación de grano fino y hace una mayor exploración del espacio de búsqueda debido a su mecanismo de selección local, evitando una sobre-selección. Esta mayor exploración va acompañada de una carga computacional extra, por lo que sólo es recomendable para aquellos problemas que necesiten una fuerte exploración del espacio de búsqueda (Robertson [#!Robertson!#], Shapiro y Navetta [#!ShapiroNavetta!#]).

Por otra parte, podemos clasificar los algoritmos evolutivos paralelos según la forma de realizar sus comunicaciones:

• Comunicaciones síncronas: En este caso el algoritmo evolutivo para y espera para recibir información de otro procesador antes de proceder con la siguiente población (Collins y Jefferson. [#!CollinsJefferson!#]) .
• Comunicaciones asíncronas: En este esquema el algoritmo evolutivo no se detiene para esperar a otros procesadores más lentos (Atienza et al. [#!Atienza!#], Maruyama et al. [#!Maruyama!#]).

En este trabajo se presentará la biblioteca de Objetos Evolutivos Paralelos (en lo sucesivo OEP), que engloba todos los paradigmas de la computación evolutiva, abstrayendo las características comunes a todos los paradigmas, y que permite la realización de computación evolutiva paralela.

OEP son objetos evolutivos que siguen un esquema de paralelización de grano grueso, es decir, usan un esquema migratorio. Las comunicaciones entre poblaciones residentes en distintos procesadores son síncronas y se hace usando paso de mensajes, concretamente se utiliza la biblioteca MPI. Al usar dicha biblioteca, se necesita un conjunto de ordenadores homogéneos, además al utilizar un esquema síncrono para el intercambio de individuos en las migraciones se debería utilizar máquinas con una misma capacidad computacional.

En este capítulo se describe la biblioteca OEP, así como el diseño y el desarrollo de aplicaciones con ella (sección ), y se ofrecen una serie de conclusiones y líneas de trabajo en el desarrollo de la biblioteca (sección ).