Existen problemas de optimización tan complejos que no es posible encontrar un algoritmo que los resuelva. Encontrar una solución óptima para un sistema que depende de dos o tres variables o condicionales puede resultar trivial, pero ¿Y cuando son cien variables? ¿O más? Para estos casos, los algoritmos genéticos nos permiten aproximar, de forma inteligente, una solución válida.
¿Qué es un algoritmo genético?
Los algoritmos genéticos son algoritmos evolutivos que usan principios de la biología, concretamente de la teoría de la evolución de Darwin (mutación, selección natural, reproducción, etc.) para evolucionar una serie de soluciones candidatas hasta una solución lo suficientemente óptima como para ser seleccionada como válida.Explicado de forma simple, consiste en generar una serie de posibles soluciones, de forma aleatoria, y simular su comportamiento en el sistema para obtener un resultado. Dichos resultados son contrastados entre sí, seleccionando los que han obtenido mejores resultados. Estas soluciones seleccionadas se mutan aplicando ligeras variaciones aleatorias, o se cruzan, simulando la reproducción (de dos soluciones padre se extrae una solución hija, que contenga parámetros de ambas). Esta nueva generación de soluciones vuelve a pasar por el proceso: es simulada, seleccionada y mutada tantas veces como sea necesario hasta que se obtenga un valor aceptable.
Aplicación de los algoritmos genéticos
Los algoritmos genéticos pueden solucionar algo tan mundano como sentar a los invitados a una boda (intentando minimizar los conflictos), o tan complejo como optimizar el rendimiento de motores o supercomputadores. Sin embargo, existen una serie de condiciones que un problema a optimizar ha de cumplir para ser abordable desde un algoritmo genético:
- La solución del problema debe poder codificarse en una serie de variables (conocida como cromosoma o fenotipo, emulando la genética) que permita su mutación y/o cruzamiento.
- El problema ha de ser simulable: debe poder codificarse un programa que permita, tomando cada solución o fenotipo, obtener un resultado.
- Los resultados de la simulación deben ser medibles. Debe poder codificarse un algoritmo (la fitness function) que permita evaluar que una solución es mejor que otra.
La NASA por ejemplo, los ha utilizado para diseñar antenas para aplicaciones en los que los requisitos de diseño eran rigurosos, conflictivos o inusuales, para los cuales ninguno de los tipos de antena existentes eran adecuados.
Otras aplicaciones de la programación evolutiva son el encuadre de agendas y planificaciones, optimización de espacio en almacenes, contenedores, etcétera, o el diseño de topologías de distribución de aguas, de circuitos impresos o de redes computacionales.
Ejemplo de aplicación
Por aclarar el algoritmo, propondremos un ejemplo de aplicación: el clásico Problema del viajante.
El Problema del Agente Viajero (TSP por sus siglas en inglés) o problema del viajante, responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿Cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y regresa a la ciudad origen?
Aunque existen multitud de soluciones para este problema, para resolverlo desde un enfoque evolutivo, podríamos seguir la siguente serie de pasos.
Generación de fenotipos
Generamos una serie de soluciones aleatorias. Cada una de ellas es una lista de ciudades, por orden de visita.
Ver ejemplo:
a: 1 -> 4 -> 2 -> 3 -> 5 -> 1
b: 1 -> 5 -> 4 -> 3 -> 2 -> 1
c: 1 -> 2 -> 4 -> 5 -> 3 -> 1
[...]Simulación
Para cada lista de ciudades, simulamos el camino del viajante de ciudad en ciudad. Como resultado obtendremos la distancia total recorrida para cada lista aleatoria de ciudades.
Ver ejemplo:
a: 3 + 3 + 4 + 3 + 6 = 19 km
b: 6 + 3 + 7 + 4 + 2 = 22 km
c: 2 + 3 + 3 + 3 + 6 = 17 km
[...]Extinción y supervivencia del mas fuerte
Podemos encontrar soluciones no válidas: en este ejemplo, no es posible viajar de la ciudad 2 a la ciudad 5. Cualquier solución que tenga tal tramo sería inválida.
Eliminaríamos también las soluciones peores, las que implican una mayor distancia. Por tanto, nos quedaríamos con aquellas soluciones se consideran mejores, las que implican una menor distancia total recorrida.
Ver ejemplo:
Mejores soluciones:
a y c
Eliminadas por ser menos óptimas
bMutación
Hacemos cambios aleatorios en las soluciones, por ejemplo cambiando el orden de viaje entre algunas ciudades.
Ver ejemplo:
c: 1 -> 2 -> [4 -> 5] -> 3 -> 1
c': 1 -> 2 -> [5 -> 4] -> 3 -> 1Reproducción sexual
Tomamos dos soluciones y las combinamos, de forma que la lista de ciudades combinadas tenga tramos de soluciones de las que hereda.
Ver ejemplo:
a: [1 -> 4 -> 2] -> 3 -> 5 -> 1
+
c: 1 -> 2 -> 4 -> [5 -> 3 -> 1]
=
ac : [1 -> 4 -> 2 ] -> [5 -> 3 -> 1]
Este proceso podría hacerse más inteligente, por ejemplo, seleccionando los tramos mas óptimos de cada antecesor, para que fueran heredados por su descendencia.
Repetición del proceso.
Volvemos a simular cada una de las nuevas soluciones, ya sean fruto de la mutación, de la reproducción, o de ambas. Obtendremos de nuevo sus resultados, que volveremos a comparar entre sí eliminando las peores y seleccionando las mejores.
Finalización del proceso.
El proceso llegaría a su fin, en cuyo caso aceptaríamos la mejor solución encontrada hasta el momento cuando se cumplan una o varias de las condiciones:
- El tiempo asignado al proceso se cumpla: podemos tener un número máximo de evoluciones, o un tope de tiempo de procesamiento para encontrar una solución.
- Se detecte una meseta: esto es cuando se detecte un estancamiento del proceso en el que nuevas soluciones no mejoran el resultado.
- Se llegue a una solución aceptable: si disponemos de un criterio de mínimos podemos terminar el proceso cuando se encuentre una solución que lo cumpla.
En resumen
Los algoritmos genéticos son una potente herramienta que, imitando la selección natural, nos permiten dar una solución óptima, o al menos aceptable, a problemas de optimización que por su complejidad no pueden ser solucionados con un algoritmo tradicional.
