martes, 26 de septiembre de 2017

Algoritmos Genéticos

Los Algoritmos Genéticos son una de las más conocidas y originales técnicas de resolución de problemas dentro de lo que se ha definido como "Computación Evolutiva" (o "Algoritmos Evolutivos"), término que agrupa a los Algoritmos Genéticos, las Estrategias Evolutivas y la Programación Evolutiva. En realidad todas estas técnicas son muy parecidas y comparten muchos aspectos.

Un Algoritmo Evolutivo es una técnica de resolución de problemas inspirada en la evolución de los seres vivos.

En un Algoritmo Evolutivo se define una estructura de datos que admita todas las posibles soluciones a un problema.

Cada uno de los posibles conjuntos de datos admitidos por esa estructura será una solución al problema. Unas soluciones serán mejores, otras peores.

Solucionar el problema consistirá en encontrar la solución óptima, y por tanto, los Algoritmos Evolutivos son en realidad un método de búsqueda.

Pero un método de búsqueda muy especial, en el que las soluciones al problema son capaces de reproducirse entre sí, combinando sus características y generando nuevas soluciones.

En cada ciclo se seleccionan las soluciones que más se acercan al objetivo buscado, eliminando el resto de soluciones. Las soluciones seleccionadas se reproducirán entre sí, permitiendo de vez en cuando alguna mutación o modificación al azar durante la reproducción.


VENTAJAS DE LOS ALGORITMOS GENÉTICO

 • Una clara ventaja es que los algoritmos genéticos son intrínsicamente paralelos, es decir, operan de forma simultánea con varias soluciones, en vez de trabajar de forma secuencial como las técnicas tradicionales. 

Esto significa que mientras técnicas tradicionales sólo pueden explorar el espacio de soluciones hacia una solución en una dirección al mismo tiempo, y si la solución que descubren resulta subóptima, no se puede hacer otra cosa que abandonar todo el trabajo hecho y empezar de nuevo. Sin embargo, los algoritmos genéticos simplemente desechan esta solución subóptima y siguen por otros caminos. 

• Cuando se usan para problemas de optimización resultan menos afectados por los máximos locales (falsas soluciones) que las técnicas tradicionales. Muchos algoritmos de búsqueda pueden quedar atrapados en los óptimos locales: si llegan a lo alto de una colina del paisaje adaptativo, descubrirán que no existen soluciones mejores en las cercanías y concluirán que han alcanzado la mejor de todas, aunque existan picos más altos en algún otro lugar del mapa, situación que no sucede para algoritmos genéticos. 

• Otra ventaja es su habilidad para manipular muchos parámetros simultáneamente. Resulta interesante en caso de tener varios objetivos a resolver. 

• No necesitan conocimientos específicos sobre el problema que intentan resolver. 
Realizan cambios aleatorios en sus soluciones candidatas y luego utilizan la función de aptitud para determinar si esos cambios producen una mejora o no.

 • Resulta sumamente fácil ejecutarlos en las modernas arquitecturas masivas en paralelo. 

• Usan operadores probabilísticos, en vez de los típicos operadores determinísticos de las otras técnicas. 

DESVENTAJAS DE LOS ALGORITMOS GENÉTICOS 

• Definir una representación del problema. El lenguaje utilizado para especificar soluciones candidatas debe ser robusto, debe ser capaz de tolerar cambios aleatorios que no produzcan constantemente errores fatales o resultados sin sentido. Se puede solucionar mediante la definición de los individuos como listas de números donde cada número representa algún aspecto de la solución candidata. 

• Pueden tardar mucho en converger, o no converger en absoluto, dependiendo en cierta medida de los parámetros que se utilicen -tamaño de la población, número de generaciones… 

• Pueden converger prematuramente debido a una serie de problemas. Si un individuo que es más apto que la mayoría de sus competidores emerge muy pronto en el curso de la ejecución, se puede reproducir tan abundantemente que merme la diversidad de la población demasiado pronto, provocando que el algoritmo converja hacia el óptimo local que representa ese individuo, en lugar de rastrear el paisaje adaptativo lo bastante a fondo para encontrar el óptimo global. Esto es un problema especialmente común en las poblaciones pequeñas, donde incluso una variación aleatoria en el ritmo de reproducción puede provocar que un genotipo se haga dominante sobre los otros. 


 APLICACIONES DE LOS ALGORITMOS GENÉTICOS 

La aplicación más común de los algoritmos genéticos ha sido la solución de problemas de optimización, en donde han mostrado ser muy eficientes. Sin embargo, no todos los problemas pudieran ser apropiados para esta técnica. Se recomienda en general tomar en cuenta las siguientes características del mismo antes de intentar usarla:

 Su espacio de búsqueda debe estar delimitado dentro de un cierto rango. 
• Debe poderse definir una función de aptitud que nos indique qué tan buena o mala es una cierta respuesta. 
• Las soluciones deben codificarse de una forma que resulte relativamente fácil de implementar en la computadora. 

Dentro de los distintos problemas de optimización podemos encontrar unas áreas de aplicación:

• Diseño por computadora de nuevos materiales que cumplan múltiples objetivos. 
• Optimización del la carga de containers. 
• Asignación de procesos en topologías de redes con procesamiento distribuido. 
• Ubicación de archivos en sistemas de almacenamiento distribuido. 
• Diseño de circuitos integrados. 
• Optimización de la infraestructura de telefonía celular. 
• Ingeniería Aeroespacial. 
• Juegos. 
• Robótica


No hay comentarios:

Publicar un comentario