Búscalo aquí:

Algoritmos Genéticos Paralelos

Como es bien sabido, la selección natural es un mecanismo ejercido por la naturaleza sobre todos los individuos de una especie por el cual el más apto tiene mayores posibilidades de sobrevivir y de transmitir sus cualidades genéticas que los hacen ser los más adecuados a sus descendientes. En la computación hay una disciplina que se basa en este principio: La Computación Evolutiva.

La Computación Evolutiva hace uso de los llamados algoritmos evolutivos, los cuales son técnicas que incorporan dentro de su estructura y funcionamiento conceptos como selección natural, competición, reproducción y mutación.

Los algoritmos genéticos (AG) son algoritmos evolutivos que encuentran la solución óptima a un problema en un espacio de posibles soluciones sin la necesidad de hacer dicha búsqueda en todo el espacio. Su fortaleza se encuentra en la selección de posibles soluciones más fuertes aplicando dos procesos distinguidos: el cruce y la mutación.

Hay mucha documentación y trabajos en los que se dan soluciones a diversos problemas, sin embargo, según [Nowostawski] [Alba] los AG presentan 3 desventajas:

1.      Para mantener grandes poblaciones de individuos se necesita mucha memoria y puede tornarse ineficiente abordar problemas con estos  requerimientos de manera secuencial.


2.      Al afrontar problemas complejos, la evaluación de la función de fitness puede ser muy costosa en tiempo de mputo y el lapso demandado por una ejecución completa de un AG podría ser inaceptable (en situaciones  extremadamente complejas, se han reportado casos de hasta un año).


3.    Los   AG   secuenciales   pueden   converger   prematuramente   hacia   valores subóptimos.


Debido a estos 3 problemas es que se plantea paralelizar la ejecución de los AG dando lugar a los Algoritmos Genéticos Paralelos (AGP), los cuales son clasificados de acuerdo a las siguientes taxonomías:


Paralelismo Maestro - Esclavo: Utiliza una única población centralizada controlada por el procesador maestro, el mismo que se encarga de la selección y asignación de cada uno de los eclavos, quienes reciben uno a uno varios individuos a los cuales evaluan, cruzan y mutan para finalmente devolver los resultados al maestro.


Paralelismo mediante subpoblaciones estáticas con migración: Existen varias poblaciones (demes) que evolucionan independientemente intercambiando entre ellas individuos (migración). si un individuo migra de una subpoblación a otra existente, entonces el AGP adopta el "modelo de islas" (ver figura superior derecha). 

Paralelismo mediante subpoblaciones estáticas solapadas sin migración: Similar al anterior con la radical diferencia de la ausencia de migración..en lugar de esto se usa el solapamiento para compartir material genético entre subpoblaciones (ver figura izquierda).

AG masivamente paralelos: Asignan - en el caso ideal- un procesador a cada individuo, es por eso que son usados en arquitecturas con un gran número de procesadores.

Sin duda alguna que los AGP brindarán un gran soporte y s econvertirán en una de las mejores alternativas para la solución de problemas en el que se manejan grandes cantidades de datos, los cuales además requieren otra cantidad grande de operaciones.


[Nowostawski] M. Nowostawski and R. Poli (1999). Genetic Algorithm Taxonomy. In Preceedings of the Third International Conference on Knowledge based Intelligen Information Engineering Systems KES’99, pages 88-92. IEEE Computer Society.

[Alba] E. Alba and C. Cotta (2006).  Tutorial  on  Evolution  Computation. Disponible   en   http://www.lcc.uma.es/~ccottap/semEC/ec.html.   

6 comentarios:

  1. Saludos, la implementacion de este tipo de algoritmos involucra algun trabajo directo en el Sistema Operativo o es independiente?? existen herramientas que te permitan la programación de este tipo de algoritmos??

    ResponderEliminar
  2. La programación en paralelo requiere que el programador tenga el control necesario de los procesos, por eso, de alguna manera el sistema operativo sobre el que se trabaje tiene mucho que ver.

    Particularmente realice algunos programas en paralelo básicos usando la distro Debian de Linux.

    ResponderEliminar
  3. Saludos Jorge, Crees que se puede trabajar el G.A.Paralelo con MATLAB?

    ResponderEliminar
  4. Con lo que respecta a la implementacion de un algoritmo genetico paralelo en matlab no creo haya inconvenientes, pero el problema creo que surgiria al tratar de hacerlo funcionar en un entorno paralelo real, con matlab tradicional no estoy seguro que los resultados sean eficientes, pero me parece haber visto algunas librerias o paquetes de Matlab que permiten agregarle esta caracteristica, todo sería cuestión de buscar en la pagina de Matlab.

    ResponderEliminar
  5. Hola Jorge y saludos, Haz trabajado con el GaTools de MATLAB 2007a para el caso de Multiobjetivos, Maximizar y Minimizar una función, digamos una función en base a los pesos de cada variable. Si tuvieras ejemplos seria excelente...Gracias de antemano por la respuesta.

    ResponderEliminar
  6. Particularmente no he tenido la oportunidad de trabajar con GaTools de MATLAB 2007 :(

    ResponderEliminar

Bienvenido a jcGeorge's Blog!!!

Por favor deja tu comentario, consulta o sugerencia, procura mantener habilitado tu perfil de Blogger o deja un enlace a tu blog o web.

Gracias por leer este blog!!!

Related Posts Plugin for WordPress, Blogger...