Algoritmo genético

Los algoritmos genéticos (AG) funcionan entre el conjunto de soluciones de un problema llamado fenotipo, y el conjunto de individuos de una población natural, codificando la información de cada solución en una cadena, generalmente binaria, llamada cromosoma. Los símbolos que forman la cadena son llamados genes. Cuando la representación de los cromosomas se hace con cadenas de dígitos binarios se le conoce como genotipo. Los cromosomas evolucionan a través de iteraciones, llamadas generaciones. En cada generación, los cromosomas son evaluados usando alguna medida de aptitud. Las siguientes generaciones (nuevos cromosomas), son generadas aplicando los operadores genéticos repetidamente, siendo estos los operadores de selección, cruzamiento, mutación y reemplazo.

Cuándo usar estos algoritmos

Los algoritmos genéticos son de probada eficacia en caso de querer calcular funciones no derivables (o de derivación muy compleja) aunque su uso es posible con cualquier función.

Deben tenerse en cuenta también las siguientes consideraciones:

Si la función a optimizar tiene muchos máximos/mínimos locales se requerirán más iteraciones del algoritmo para 'asegurar' el máximo/mínimo global.

Si la función a optimizar contiene varios puntos muy cercanos en valor al óptimo, solamente podemos 'asegurar' que encontraremos uno de ellos (no necesariamente el óptimo).

Funcionamiento de un algoritmo genético básico

Un algoritmo genético puede presentar diversas variaciones, dependiendo de cómo se decide el reemplazo de los individuos para formar la nueva población.

Desventajas y limitaciones

Entre otras podemos mencionar:

Para problemas de alta complejidad la función de evaluación puede tornarse demasiado costosa en términos de tiempo y recursos. Por ejemplo existen casos en la vida real para los cuales recrear una simulación de la solución propuesta por una iteración puede tardar muchos días y consumir gran cantidad de procesamiento y recursos asociados.

Puede haber casos en los cuales dependiendo los parámetros que se utilicen para la evaluación el algoritmo podría no llegar a converger en una solución óptima o bien terminar en una convergencia prematura con resultados no satisfactorios (la convergencia prematura podría significar una convergencia en un óptimo local o punto arbitrario afectando los resultados a largo plazo).

Se dice que no poseen una buena escalabilidad con la complejidad, por ejemplo para sistemas que están compuestos por muchas variables, componentes o elementos su respectivo espacio de búsqueda crece de manera exponencial debido entre otras cosas a las relaciones que puedan surgir, por lo tanto el problema del diseño de una aeronave debe desglosarse en representaciones simples, como perfiles aerodinámicos, tomando en cuenta que la recombinación de los elementos puede perjudicar el rendimiento individual.

La 'mejor' solución lo es solo en comparación a otras soluciones por lo que no se tiene demasiado claro un criterio de cuándo detenerse ya que no se cuenta con una solución específica.

No es recomendable utilizarlos para problemas que buscan respuesta a problemas que convergen en soluciones simples como Correcto/Incorrecto ya que el algoritmo difícilmente convergerá y el resultado será tan válido como escogerlo al azar.

El diseño, la creación de la función de aptitud (fitness) y la selección de los criterios de mutación entre otros, necesitan de cierta pericia y conocimiento del problema para obtener buenos resultados.