 |
En este documento describimos nuestra implementación de un algoritmo genético en paralelo de grado fino. El escrito empieza introduciendo el funcionamiento básico de los algoritmos genéticos y tratando también diversas formas de "paralelizar" algoritmos. Describimos la implementación del algoritmo genético de grano fino en Charm++, un lenguaje en paralelo por paso de mensajes basado en C++. Nuestra implementación es totalmente asíncrona y distribuida. Debería, por tanto, escalar bien, incluso para un número muy grande de procesadores. Presentamos resultados de rendimiento para hasta 64 procesadores en una Origin2000, para verificar nuestra hipotésis de escabilidad. En la mayoría de los casos probados, se obtuvieron mejoras en la velocidad lineales o superlineales.
Los algoritmos genéticos [2,4] son una robusta herramienta de optimización que pueden ser usados para resolver un amplio abanico de problemas de forma eficiente y precisa. Son tres operadores básicos los que dirigen la búsqueda en los algoritmos genéticos. La función de selección (Selection) predispone la búsqueda hacia soluciones prometedoras. La calidad de cada individuo viene dada por la función de aptitud (Fitness), que será específica al problema que tengamos. Las funciones de cruzamiento y mutación (Crossover y Mutation) introducen variación al combinar el conjunto actual de soluciones prometedoras.
Los estudios recientes han demostrado que la paralelización puede mejorar significativamente el rendimiento de los algoritmos genéticos [1, 2,3,7]. Muchos operadores de búsqueda pueden ser distribuidos fácilmente, y obtenerse así grandes incrementos de velocidad en problemas difíciles. Existen dos enfoques generales para "paralelizar" algoritmos genéticos: maestro-esclavo y de grano grueso o fino. La arquitectura maestro-esclavo suele emplearse cuando la función de aptitud (que determina la calidad de cada solución individual) es el operador más costoso. La función de evaluación se distribuye entre un número determinado de procesadores esclavos y todas las operadores restantes (mutación, cruzamiento y selección) se realizan en el procesador maestro. En los algoritmos genéticos en paralelo de grano fino o de grano grueso, la población se divide en subpoblaciones organizadas en una red. Todos los operadores en cada subpoblación se ejecutan por un elemento de procesamiento separado que contiene a la subpoblación. Las diferentes subpoblaciones pueden comunicarse por medio de diversas topologías de red y patrones de comunicación.
El propósito de este escrito es describir nuestra implementación de un algoritmo genético versátil en paralelo de grado fino, y demostrar su escabilidad. Nuestras metas primarias incluían el diseño y la implementación de un sistema fácilmente extensible para resolver diferentes problemas de optimización. La implementación tolera soluciones representadas por cadenas binarias y grafos de decisión con tipos booleanos, reales y enteros (N. del T. boolean, real, integer). Las funciones de evaluación incluyen un simple problema lineal para cadenas binarias y clasificación de conjuntos de datos que son cargados dinámicamente de un fichero de datos especificado. Cualquiera de los componentes puede ser fácilmente extendido derivando una nueva clase para la representación y la función de evaluación. Un archivo de configuración permite al usuario seleccionar el problema a resolver, la representación y otros parámetros. Este escrito no analiza la eficiencia o la aplicabilidad de los algoritmos genéticos como herramienta general de optimización, sino que propone una forma de "paralelizar" una de sus variantes para lograr una buena escabilidad.
Un algoritmo genético [2,4] desarrolla una población de soluciones potenciales con vistas a resolver un problema dado. La primera población de soluciones se genera aleatoriamente. Se usa una medida de la calidad de las soluciones, expresada de forma usual en forma de una o múltiples funciones, para seleccionar las mejores soluciones de la población actual. Las soluciones seleccionadas pasan por los operadores de mutación y cruzamiento para crear una población de nuevas soluciones (la población descendiente). El proceso se repite hasta que los criterios de terminación (por ejemplo, convergencia a singleton) especificados por el usuario se cumplen.
Los algoritmos prosiguen discriminando de forma repetida la búsqueda de regiones de una mayor calidad, y combinando trozos prometedores de soluciones para formar combinaciones nuevas. De esta forma, los problemas que son descomponibles en problemas de dificultad definida se resuelven muy eficientemente (en tiempo cuadrático o subcuadrático). Aunque existen muchos problemas que no son descomponibles fácilmente, muchos otros problemas interesantes pueden resolverse de esta forma. Esto se cumple incluso para muchos ejemplos de problemas NP, aunque el algoritmo podría llegar a requerir un tiempo exponencial en el peor caso.
Los algoritmos genéticos se han aplicado de forma exitosa en un buen número de áreas, incluyendo diseño e ingeniería, negocios, telecomunicaciones, planificación y aprendizaje artificial. Muchos problemas difíciles pueden afrontarse en tiempo subcuadrático con respecto al número de variables. Sin embargo, para problemas muy grandes, incluso un tiempo subcuadrático puede llevar a enormes requisitos computacionales. Para resolver estos problemas más rápido, se ha realizado un gran esfuerzo de investigación que ha llevado al estudio de la paralelización de algoritmos genéticos. La siguiente sección aborda algunos de estos enfoques.
Los algoritmos genéticos pueden clasificarse en dos grandes clases [1, 2,3,7]. La primera clase, los algoritmos genéticos en paralelo maestro-esclavo, distribuye las funciones de aptitud entre procesadores esclavos. La información la recolecta el procesador maestro, que procesa la población de soluciones candidato, aplicando operadores de selección, cruzamiento y mutación. Entonces envía las nuevas soluciones a sus esclavos para que sean evaluadas.
La segunda clase son los algoritmos genéticos en paralelo de grano fino y de grano, donde la población se distribuye entre un número dado de procesadores. Cada procesador procesa su subpoblación. Se permite que las subpoblaciones se comuniquen entre sí e intercambien soluciones a algunos intervalos. Pueden usarse varias topologías de conexión y patrones de comunicación. Los algoritmos genéticos de grano fino dividen la población en pequeñas subpoblaciones que contienen sólo una o dos soluciones que están conectadas en topología de rejilla (N. del T. grid) (suelen usarse rejillas bidimensionales ó 2D). Los individuos se comunican únicamente con su vecindario. El propósito original de los algoritmos genéticos de grano fino era usar un gran número de pequeños procesadores, donde cada procesador procesaría una única solución.
En los algoritmos genéticos de grano grueso, las subpoblaciones son más grandes y la comunicación se reduce al intercambio de soluciones sólo de vez en cuando o después de que los algoritmos hayan convergido. Varias topologías comunes para la comunicación incluyen anillos, rejillas, hipercubos, grafos fuertemente conexos y grafos aleatorios con un número fijo de enlaces para cada elemento de proceso.
Cada una de las paralelizaciones pueden representar una mejora significativa para algunos problemas. Si la función de aptitud se lleva la mayoría de recursos computacionales, los algoritmos genéticos en paralelo maestro-esclavo suelen dar buenos resultados. Sin embargo, cuando la función evaluación no requiere un tiempo significativamente mayor que los otros operadores, los algoritmos genéticos de grano fino o grueso pueden mejorar aún más el rendimiento.
Como se ha mencionado antes, los algoritmos genéticos de grano fino fueron diseñados originalmente para ejecutarse en máquinas con un gran número de pequeños procesadores conectados en topología de rejilla. Mientras la optimización se realiza, uno podría esperar que soluciones parciales de gran calidad se propaguen de un sitio a otro de la rejilla en un proceso parecido a la difusión. Este comportamiento es interesante en si mismo, y puede eliminar problemas de convergencia prematura, y puede también mejorar la ejecución del algoritmo en máquinas monoprocesador. Estas razones motivan nuestra decisión de implementar un algoritmo de grano fino.
En nuestra implementación del algoritmo genético de grano fino, la población de soluciones candidato se ha acotado a una rejilla bidimensional (ó 2D), donde cada posición de la rejilla puede contener una solución particular o estar vacía. En cada iteración del algoritmo, todas las soluciones pasan por el operador de cruzamiento, en el que el individuo se combina con un vecino escogido al azar de su vecindario. El individuo, pasa entonces por un operador de mutación que realiza una ligera modificación a la solución actual. Si el nuevo individuo es de una calidad mayor, entonces reemplaza al individuo original. Esto introduce la presión de selección que discrimina la búsqueda hacia soluciones de mayor calidad. A continuación, puede aplicarse un operador local de búsqueda para afinar la solución particular. De este modo, un algoritmo genético realiza una búsqueda global, mientras que el operador local de búsqueda trata de mejorar el individuo en algún pequeño vecindario. La siguiente sección explica los detalles de nuestra implementación en paralelo.
Para hacer la implementación portable a un número de ordenadores paralelos diferentes, desde superordenadores a clusters de PCs, pueden ajustarse dinámicamente muchos atributos de la implementación al especificar diferentes parámetros de entrada.
Hemos elegido el lenguaje de programación Charm++ [5], un lenguaje en paralelo orientado a objetos, por paso de mensajes y basado en C++. En los lenguajes paralelos basados en el paso de mensajes, la ejecución, la invocación de métodos y la sincronización se realizan por el envío de mensajes entre diferentes procesos. Existen varias ventajas en Charm++. Charm++ está basado en un lenguaje orientado a objetos, lo que nos permite escribir código en un entorno flexible y comprensible. Charm++ soporta también balance de carga automatizado, que puede resituar algunos objetos de forma automática dependiendo de la carga de trabajo actual. Además, la ejecución en Charm++ está guiada por los mensajes, y esto permite la creación de aplicaciones totalmente distribuidas y asíncronas, que debieran ser escalables a un gran número de procesadores.
Nuestra implementación usa una rejilla bidimensional, que es dividida en un número dado de rectángulos. La división se realiza automáticamente, pero el usuario puede especificar el número medio de rectángulos que será procesado por cada procesador. El valor por defecto es 4, es decir, cada procesador debería contener 4 rectángulos de media. Las sub-rejillas pueden rotar entre distintos procesadores dependiendo de la actual carga. Las sub-rejillas colindantes deben comunicarse, puesto que el procesado de cada sub-rejilla requiere el conocimiento de los individuos en el borde de esa sub-rejilla.
Sin embargo, los procesos en algoritmos genéticos son estadísticos por naturaleza y, por tanto, no siempre es necesario que la información de los procesadores colindantes sea consistente. Esto nos permite crear un sistema totalmente asíncrono que puede mejorar en gran medida el rendimiento general.
Además de haber distribuido la rejilla con individuos, hemos distribuido el cálculo de la función de aptitud. Hay muchas alternativas que el usuario puede especificar al vuelo. La alternativa más simple es cuando todos los individuos son evaluados de forma local por el objeto responsable de esa parte de la rejilla (el rectángulo) donde los individuos están localizados. Esta solución no requiere comunicación, a menos que la función de aptitud requiera o una gran cantidad de tiempo o una cantidad de tiempo que cambie dinámicamente, convirtiéndola pues, en una solución eficiente. La segunda alternativa es tener un objeto especial para cada procesador, y hacer que cada rectángulo envíe sus evaluaciones al objeto evaluador local en su nodo local. Eso puede ser útil para funciones de aptitud más complejas.
La última alternativa es usar un esquema jerárquico donde existirá un gestor de evaluación para un número dado de procesadores. Cada rectángulo envía su individuo a su gestor asociado. Existirá un evaluador por procesador. Dependiendo de la carga de cada evaluador, el gestor decide que evaluador debería recibir el trabajo y se lo envía. Esta "carga umbral" puede ser calculada basándose en los registros de computación, puesto que el gestor conoce todas las transacciones entre los rectángulos y sus evaluadores.
La búsqueda local se realiza por los hill climbers (N. del T. trepadores de colinas). Existe un hill climber para cada sub-rejilla. Al comienzo, cada hill climber solicita una solución de la sub-rejilla correspondiente. Entonces, intenta buscar en su vecindario y mejorar la solución localmente durante un número de iteraciones. Una vez que ya no puede mejorarla más, devuelve la solución al rectángulo, donde la solución resultante sustituye a un individuo escogido aleatoriamente. El rectángulo responde con otro individuo que será sujeto de una búsqueda local. Los hill climbers rotan con los rectángulos de forma que la comunicación entre diferentes procesadores sea mínima.
El estado actual de ejecución se obtiene extrayendo la mejor solución general, la aptitud media, y otras informaciones extraídas de la actual población de soluciones. Para prevenir un cuello de botella en la implementación, usamos un árbol de extensión (N. del T. spanning tree) cuyos nodos se corresponden con los rectángulos y rotan con ellos. La información se mueve hacia arriba y el objeto más arriba y a la izquierda genera la información de salida a la pantalla a ciertos intervalos. Usando este esquema, no se requiere sincronización, mejorando así el rendimiento. Se explican brevemente más detalles de la implementación.
Esta sección proporciona información detallada de nuestra implementación. La sección empieza dando una lista de clases y una breve descripción del papel de cada clase del sistema. Después, se tratan los mensajes y la comunicación. El diseño general de la implementación está ilustrado en la Figura 1.
|
Un individuo en un algoritmo genético representa una solución candidato (por ejemplo, un vector o un clasificador). Dependiendo del problema, la solución puede representarse con diferentes esquemas de codificación. Así, tenemos un clase abstracta 'Individual' que encapsula los elementos esenciales de un individuo, a saber, la aptitud y funciones virtuales puras como la Inicialización, el Cruzamiento y la Mutación. Además de esto, todas las subclases de 'Individual" necesitan definir su propio método para empaquetar la representación en un buffer de caracteres y el desempaquetamiento en un individuo único, dado un buffer. Estos métodos facilitan la comunicación conveniente de clases 'Individual' para la evaluación de aptitud, para propósitos de comunicación de vecinos cercanos, y también durante la rotación del objeto 'FineGrainedGA' al que pertenezcan. Cada instancia de cada individuo contiene punteros a instancias de la clase 'FitnessFunction' a la clase 'Random' presente en el objeto 'FineGrainedGA'. La clase 'Individual' también incluye una función virtual pura que, en las clases descendientes, realiza una búsqueda local de una iteración y devuelve un valor tanto si continúa como si no haciendo una búsqueda local.
Las clases descendientes que hemos implementado son la 'BinaryStringIndividual', que representa la cadena convencional de bits binarios que representan las soluciones, y la 'DecisionTree', que es para representar el árbol de decisión de soluciones para problemas de clasificación. El usuario especifica que representación usar en el fichero de parámetros de entrada.
Los objetos más importantes en el programa pertenecen a la clase 'FineGrainedGA'. Esta clase es la que ejecuta en realidad las operaciones GA. La clase 'FineGrainedGA' se organiza como una matriz bidimensional de caracteres, y cada instancia de la clase tiene una matriz bidimensional de clases 'Individual'. La clase 'Individual' es una clase abstracta y cualquiera de las clases derivadas puede ser instanciada basándose en el problema que esté siendo resuelto (especificado a través del fichero de parámetros). El objeto 'main' instancia los objetos 'FineGrainedGA' que inicializa los individuos en la rejilla a clases 'Individual' generadas aleatoriamente y realizan una evaluación inicial. Una vez que esto acaba, el método start() se invoca para todos los objetos 'FineGrainedGA' por el objeto 'main'. La función start() es un método de entrada en la clase 'FineGrainedGA', que pasa por las generaciones GA en un bucle, produciendo al final de cada generación los mensajes que el objeto podría haber recibido.
En cada generación GA, se repite el siguiente proceso. Por cada columna de individuos, se realiza una copia de los mismos. Entonces, se selecciona un compañero de cruzamiento de un vecindario de 8, y se realiza el cruzamiento en las copias que hemos hecho. A esto le sigue la mutación. Una vez que se han completado estas alteraciones, los nuevos individuos se envían otra vez a ser evaluados, columna por columna. La evaluación puede tener lugar en uno de estos tres sitios: local, en objetos 'FitnessManager', u objetos 'FitnessEvaluator'. Cuando las evaluaciones se realizan en objetos 'FitnessEvaluator', pueden devolverse reordenadas. Por tanto, el proceso es potencialmente asíncrono. Para sacar partido de ello, el método start() procesa todas las columnas que estén actualizadas, en lugar de procesar las columnas consecutivamente.
Tras procesar todas las columnas actuales, el método se reinvoca a si mismo (por medio de su proxy), proporcionando a otros métodos de entrada la oportunidad de continuar. Cuando el método finaliza de procesar todas las columnas en una generación, se invoca al objeto 'StateInformationCollector' y se actualizan las estadísticas de la generación. El objeto 'StateInformationCollector' también envía las cuatro columnas o filas fronterizas a sus correspondientes vecinos, e incrementa el contador de generación. Después, el método se reinvoca a si mismo.
Existe también otro método de entrada, que se llama al final del procesamiento, que es el finito(). El propósito de este método es comunicar a otros objetos que finalicen su procesamiento, debido a la obtención del mejor individuo en algún otro procesador. Esto evita que los procesadores malgasten tiempo calculando las mismas soluciones.
La clase 'FitnessFunction' es una clase abstracta, de nuevo, de la que pueden derivarse cualquier número de clases descendientes para resolver problemas diferentes. Una clase descendiente debe redefinir la función evaluate(), que recibe un puntero a un objeto de la clase 'Individual' y devuelve un valor double que representa la aptitud del individuo dado. Tenemos, por ahora, una función 'OneMaxFitness' para el problema one-max, que cuenta el número de unos en una cadena dada de bits y una clase 'ClassifierFitnessFunction' que representa el problema de clasificación.
La clase 'FitnessManager' es un vector de caracteres unidimensional (1-D), que intenta equilibrar la carga entre un conjunto de objetos esclavos de la clase 'FitnessEvaluator'. La implementación es bastante directa. Cuando se envía un mensaje a un evaluador, esta clase incrementa el contador correspondiente a ese objeto y cuando los resultados se han devuelto, el contador del remitente se decrementa (que está codificado en el mensaje). Así, cuando 'FitnessEvaluator' tiene que enviar algún trabajo, recorre el vector de cargas y selecciona el evaluador con menos carga en ese momento. Cuando el número de evaluadores por gestor es uno, las evaluaciones son realizadas por el gestor mismo, que es mejor que enviar el mensaje a un evaluador en el mismo procesador.
Los objetos 'FitnessEvaluator' son los esclavos de los gestores, que reciben mensajes contenedores de individuos, los evalúan, y devuelven los resultados al gestor. Puesto que no hay ventajas inherentes a tener más de un evaluador por gestor, y puesto que necesitamos al menos uno por procesador para utilizar todos los recursos computacionales, la clase 'FitnessEvaluator' se deriva de la clase char Group, que da como consecuencia exactamente un evaluador por cada procesador. De nuevo, las funciones miembro son triviales y como se ha explicado antes, hay una para la recepción de mensajes que también "grinds" y hay otra para la devolución de resultados.
El objeto 'HillClimber' es un objeto autónomo que está practicamente ligado a cada objeto 'FineGrainedGA'. Cuando decimos ligado, nos referimos a que estos objetos han sido asignados de la misma forma que los objetos 'FineGrainedGA', es decir en una matriz bidimensional de caracteres y del mismo tamaño que la de los objetos 'FineGrainedGA'. Esta propiedad se mantiene para los objetos 'StateInformationCollector', también. Cuando un objeto 'FineGrainedGA' rota a otro procesador, fuerza también la rotación de los objetos ligados.
El objeto 'HillClimber' pide a su objeto ligado 'FineGrainedGA' individuos. Una vez que recibe uno, 'HillClimber' intenta mejorar al individuo invocando a la función miembro climbTheHill() del individuo. Una vez que 'HillClimber' ha acabado de "trepar", devuelve al individuo mejorado (o el mismo, en el caso de que no se hayan producido progresos) y, a cambio, recibe otro individuo que procesar.
El objeto 'StateInformationCollector' forma un árbol de extensión (N. del T. spanning tree) con los objetos 'FineGrainedGA' ligados a sus nodos. Al final de cada generación, el objeto 'StateInformationCollector' recibe un mensaje de su correspondiente objeto 'FineGrainedGA' a través del método pass(). Este compara entonces todos los mensajes que ha recibido de sus hijos y 'FineGrainedGA' ligado y le pasa esta información a su padre. El objeto 'StateInformationCollector' en la raíz del arbol agrupa toda la información e imprime las estadísticas. Puesto que no hay sincronización, el objeto raíz del árbol de recorrido (N.T. Spanning tree) puede recibir información nueva bastante a menudo. Para evitar exceso de salidas, el usuario puede especificar una espera mínima para imprimir el estado global de la ejecución.
Existen varios mensajes, cada uno con un propósito único. En Charm++, los mensajes son los únicos medios de comunicación entre procesos. El mensaje más importante es el mensaje 'GAParamsMessage', que se crea tras haber analizado los parámetros de entrada y se envía a todos los objetos cuando son creados. Los objetos 'FineGrainedGA' retienen cada uno una copia, de forma que puedan ser creados individuos nuevos incluso tras la inicialización. El mensaje 'IndividualsMessage' se usa para enviar trabajo a los gestores y para la comunicación entre vecinos cercanos. El mensaje 'FitnessValuesMessage' se usa para devolver resultados a los objetos 'FineGrainedGA'. El mensaje 'StateInformationMessage' se usa en el árbol de recorrido para obtener la aptitud del mejor individuo, y la aptitud media. El mensaje 'FinalInfoMessage' se usa para informar del final de procesamiento de una sub-rejilla al objeto 'main'. Este mensaje también contiene información de cuanto tiempo le llevó a la sub-rejilla todo el procesamiento.
Hemos realizado experimentos con dos problemas. El primer problema es una simple función lineal definida en cadenas binarias de longitud fija. La función de aptitud de cada cadena binaria es la suma de sus bits. El segundo problema es un problema de clasificación donde la tarea es el desarrollo de un clasificador para la predicción de erupciones solares. El conjunto de datos contiene 323 puntos de datos, cada uno con dos caracteres y 10 atributos enteros (integer). Cada punto de datos se clasifica en una de las 7 clases. El objetivo es desarrollar un grafo de decisión que sea capaz de predecir la clase para un nuevo punto. El conjunto de datos se obtuvo del Machine Learning Repository [6], donado por Gary Bradshaw.
El propósito de los experimentos no era evaluar el algoritmo desde el punto de vista de la optimización, sino más bien averiguar si el algoritmo escala bien para los dos clases sustancialmente diferentes de problemas. Pueden esperarse incrementos similares de velocidad para otros problemas de la misma clase, puesto que el tiempo consumido por todos los operadores debería ser comparable. La única diferencia puede aparecer en la evaluación de aptitud que depende fuertemente del problema a tratar. Ejecutamos el algoritmo con evaluación local y con la evaluación a cargo de los gestores de aptitud.
Se proporcionan las configuraciones probadas en la Tabla 1. Cada 'FineGrainedGA' se ejecutó durante 30 iteraciones. Para el problema de clasificación, hemos usado una rejilla de tamaño 128x128 y dejamos que el algoritmo se ejecutase durante 300 iteraciones (debido a la incrementada complejidad del problema). El número de procesadores varió de 1 a 64. Todos los experimentos se realizaron en una SGI Origin 2000.
|
La curva de escala para los problemas binarios se muestra en la Figura 2 con evaluación local (dentro de cada 'FineGrainedGA') y en la Figura 3 con evaluación basada en gestores de aptitud. Los mejores resultados se obtuvieron con el algoritmo con evaluación local. Esto es natural, puesto que en el problema one-max la aptitud es calculada rápidamente y cualquier comunicación adicional implica sobrecarga adicional. Para la comunicación local, se obtuvieron incrementos de velocidad super lineales. Sin embargo, incluso con evaluación en gestores de aptitud, vemos que a medida que el tamaño del problema se incrementa, la mejora de velocidad se acerca a la mejora ideal, y que los resultados globales son muy cercanos a la curva ideal.
La curva de escala para el problema de clasificación se muestra en la Figura 4 con evaluación local y con evaluación basada en gestores de aptitud. En este problema, vemos que la evaluación realizada en gestores desemboca en una mejora bastante significativa del incremento de velocidad. Esto demuestra el razonamiento intuitivo que la distribución de evaluaciones y el dejar que los objetos 'FineGrainedGA' hagan su trabajo en el tiempo medio, produce un mejor aprovechamiento de la potencia de procesamiento en paralelo. Creemos que para problemas más grandes, el uso de un esquema jerárquico se amortizaría.
 |
 |
 |
Esta implementación puede usarse de dos formas principales. Primero, la implementación puede usarse para resolver varios problemas de optimización. Los problemas de cadenas binarias y los árboles de decision pueden resolverse usando la implemanción dada tal cual está.
Otro uso para la implementación es para el estudio del comportamiento del algoritmo genético en paralelo de grado fino. Varios aspectos del comportamiento son muy interesantes. Un ejemplo es el tiempo de sobrepaso (N. del T. takeover time), que es el tiempo que le lleva a un individuo superior sobrepasar a toda la población. Otros ejemplos incluyen el tiempo de mezcla, el tamaño de la población, el tiempo de convergencia, la tendencia genética, y la densidad de individuos en la rejilla. Estudiando estos diversos aspectos del comportamiento, el algoritmo podría estar relacionado con la teoría existente para el algoritmo genético con población global. A nuestro entender, no se han realizado estudios similares en el pasado.
El trabajo presentado no ha analizado el comportamiento de la mejora de velocidad para la evaluación distribuida entre los gestores. Un tema interesante sujeto a futuras investigaciones sería estudiar la eficiencia de la evaluación distribuida para diferentes problemas de optimización.
El algoritmo genético de grano fino es una alternativa interesante a otros algoritmos evolutivos que trabajan con una población global. El algoritmo genético de grano fino es un algoritmo especialmente interesante debido a su capacidad de escala a un número grande de procesadores.
Nuestra implementación es totalmente distribuida y asíncrona, lo que le permite escalar casi perfectamente incluso para un gran número de procesadores, y usa muy eficientemente los recursos en diferentes topologías de red. Los resultados empíricos confirmaron nuestra sospecha de que el algoritmo logra muy bien mejoras de velocidad. Creemos que el algoritmo continuaría ganando velocidad incluso con más procesadores, puesto que todo el trabajo está equitativamente repartido y no hay cuellos de botella. No obstante, deberían realizarse más experimentos para investigar el comportamiento de la implementación en distintas máquinas en paralelo, como clusters de PCs.
La elección de un esquema de evaluación se deja al usuario. El usuario es capaz de especificar si se usará evaluación local, un único nivel, o un esquema distribuido jerárquicamente. Dependiendo del tamaño y la complejidad del problema, diferentes esquemas pueden funcionar mejor que los otros.
Martin Pelikan es estudiante de doctorado (N. del T. Ph. D. student) en el Departamento de Ciencias de la Computación en la Universidad de Illinois, en Urbana-Champaign. Lleva trabajando desde 1995 en el diseño de algoritmos evolutivos y genéticos eficientes. Sus principales áreas de interés son la computación evolutiva, optimización de caja negra, inteligencia artificial y el aprendizaje de máquinas.
Prasanna V. Parthasarathy es estudiante graduado en el Departamento de Ingeniería General en la Universidad de Illinois en Urbana-Champaign. Tras su trabajo en la aplicación de algoritmos genéticos para mejorar la optimización durante sus estudios de graduado en ingeniería civil, trabaja ahora en la aplicación de algoritmos genéticos híbridos a problemas de optimización en ingeniería. Otras áreas de interés académico incluyen la computación en paralelo, la computación científica y análisis de elementos finitos.
Arun Ramraj es estudiante graduado en el Departamento de Ciencias de la Computación en la Universidad de Illinois en Urbana-Champaign.
Last Modified:
Location: www.acm.org/crossroads/espanol/xrds8-3/fineGrained.html