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
