Búscalo aquí:

Premio Loebner 2008


Este año se llevó a cabo la 18º versión del Premio Loebner, esta vez hubieron 6 participantes: Alice, Brother Jerome, Elbot, Eugene Goostman, Jabberwacky y Ultra Hal, los cuales fueron sometidos al Test de Turing el 12 de octubre en la Universidad de Reading (Reino Unido).

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.   

Related Posts Plugin for WordPress, Blogger...