Metaheurísticas. Dame soluciones aceptables y no te líes.
Muchos problemas a los que estamos acostumbrados se nos presentan con una ecuación o varias ecuaciones y ante las condiciones que configuran el problema nos disponemos a evaluar la expresión, realizar un par de ajustes o cálculos por aquí y por allá, y así poder obtener finalmente el resultado solicitado. Como por ejemplo en la ecuación de la posición de la partícula en el estudio cinemático del movimiento:
Sin embargo, la gran mayoría de problemas que se nos puedan presentar en la realidad del día a día tienen unos inconvenientes que hay que tener en cuenta
- No son sencillos de modelar matemáticamente
- Aún teniendo una expresión matemática que los modele (con mayor o menor fidelidad con la realidad), el requerimiento de potencia computacional para resolverlos es excesivamente elevado
- Es posible, además, que el problema no tenga una solución (pero que aún así sea relevante encontrar la mejor aproximación posible a la solución)
Es decir, puede que hayamos conseguido sintetizar las necesidades de nuestro problema y haber planteado un conjunto de ecuaciones que lo modele, pero si el tiempo y energía necesarios para poder realizar los cálculos sobrepasa unos ciertos límites, el resultado pierde valor por muy preciso que sea.
Por ejemplo, pensemos en los sensores de posición que tiene un coche y que nos avisan con un pitido cuando estamos aparcando si nos aproximamos demasiado a un obstáculo. El programa que procesa la información que le aportan esos sensores realiza una serie de cálculos para determinar que en efecto un objeto se encuentra en las proximidades de la carrocería de nuestro coche, pero ¿hasta qué punto es necesario que dicho cálculo sea preciso y haga un mapeo exhaustivo de todo el detalle que captan las cámaras y determine exactamente todas las posiciones relativas de todos los elementos respecto al coche?. Recordemos que estos cálculos se realizan mientras aún estamos dando marcha atrás, y si los cálculos que han de activar el pitido que nos avisa tardan demasiado, en vez de escuchar el pitido, escucharemos el golpetazo contra el coche de detrás.
Lo que la mayoría de estos sistemas hacen es realizar una serie de cálculos que, sin buscar la solución exacta del problema, nos aporten una solución lo suficientemente buena en un tiempo de respuesta rápido.
Hablaremos por lo tanto de técnicas metaheurísticas cuando nos refiramos a procesos que apliquen este tipo de funcionamiento lógico a la hora de buscar soluciones. En las que, bien por la complejidad de resolución del problema o por los recursos necesarios para hacerlo, es preferible desarrollar un modelo aproximado y de poco consumo que ofrezca resultados aceptables.
Y recordemos, hay ocasiones en que dicha solución exacta no existe.
El siguiente gráfico nos muestra una recopilación de diferentes técnicas metaheurísticas que se emplean para la resolución de problemas complejos:
Algoritmos evolutivos. Una receta darwiniana para buscar soluciones.
Como vemos en la imagen de arriba, existen muchos y distintos tipos de técnicas para buscar soluciones buenas y aproximadas para problemas de dificil solución. Una de estas técnicas son los algoritmos evolutivos. Vamos por partes:
- Un algoritmo es un proceso que repite una serie de pasos a lo largo de varias iteraciones.
- Un ejemplo cotidiano de algoritmo podría ser una receta de cocina, donde tenemos una serie de pasos a seguir para poder elaborar nuestra comida (cortar en juliana la verdura, sofreir en la sartén, añadir el caldo y cocer removiendo cada 5 minutos...).
- Otro ejemplo de algoritmo sería el proceso de división que nos enseñan de pequeños en el colegio, y en el que mediante pasos iterativos vamos construyendo el "árbol" debajo del dividendo y que nos permite obtener el cociente de la división y el valor del posible resto.
Vale, está claro, ¿pero qué pinta Darwin aquí?
- La teoría de la evolución nos explica cómo los diferentes entes biológicos que componen (o han formado parte) del mundo han ido evolucionando, cambiando, a lo largo de los años hasta tener la forma que conocemos hoy día.
- Por otra parte, la selección natural es el proceso evolutivo que nos explica que aquellos individuos que tenían mejores características para adaptarse al medio en que vivían eran los que más posibilidades tenían de sobrevivir y, por lo tanto, de reproducirse y perpetuar sus características dentro de la especie.
Entonces, ¿qué es un algoritmo evolutivo?
Un algoritmo evolutivo es aquel que se basa en los principios de la evolución y la selección natural para, a lo largo de las distintas iteraciones, optimizar sus resultados generando soluciones de una iteración a la siguiente utilizando aquellos valores que mejores soluciones han aportado hasta el momento, simulando el comportamiento de las especies naturales en los procesos biológicos de evolución.
Quizá la mejor manera de ilustrar el funcionamiento básico de los algoritmos evolutivos sea con un ejemplo, el del problema del viajante.
En el problema del viajante (TSP - Travelling Salesman Problem en inglés), nos encontramos ante el problema de secuenciación que ha de resolver un comercial que tiene que recorrer una serie de ciudades sin repetir el paso por ninguna de ellas, regresando en su último viaje a la ciudad de origen e invirtiendo el menor tiempo posible en su recorrido.
Supongamos un caso sencillo, con tres ciudades A, B, C para las que tenemos los siguientes tiempos necesarios para ir de una a otra:
- A → B = 5
- A → C = 1
- B → A = 5
- B → C = 4
- C → A = 7
- C → B = 8
Y los posibles resultados que nos podríamos encontrar serían:
- A → B → C → A = 5 + 4 + 7 = 16
- A → C → B → A = 1 + 8 + 5 = 14
- B → A → C → B = 5 + 1 + 8 = 14
- B → C → A → B = 4 + 7 + 5 = 16
- C → A → B → C = 7 + 5 + 4 = 16
- C → B → A → C = 8 + 5 + 1 = 14
Para los datos de este ejemplo, vemos que hay tres opciones que le suponen un menor consumo de tiempo, por lo que en función de tener que salir desde A, B o C, nuestro viajante ya podría saber cuál sería la ruta más óptima en cada caso.
Supongo que te habrás percatado, pero a medida que aumentemos el número de ciudades las combinaciones posibles aumentan considerablemente. En particular, para este caso el total de posibles recorridos corresponde con el factorial del número de ciudades.
- 1! = 1
- 2! = 2
- 3! = 6
- 4! = 24
- 5! = 120
- 6! = 720
- 7! = 5040
- 8! = 40320
- 9! = 362880
- 10! = 3628800
Es decir, si tuviéramos que evaluar el posible recorrido óptimo para 10 ciudades tendríamos que evaluar 3.6 millones de posibilidades para luego elegir la mejor, imagínate cuántas harían falta para 20, 30 o 100 ciudades (de hecho, no lo imagines, calcula el factorial) .
Es aquí donde los algoritmos evolutivos vienen al rescate y nos permitirán obtener una solución buena (o incluso la mejor) ahorrándonos tiempo de cálculo y quebraderos de cabeza. Dentro de las diferentes técnicas que abarcan los algoritmos evolutivos, vamos a plantear de manera esquemática cómo afrontar este problema haciendo uso de un algoritmo genético.
Estos algoritmos se basan en los conceptos de genética y los mecanismos evolutivos y de selección natural para ir mejorando las soluciones encontradas a lo largo de las diferentes iteraciones que se realizan. Esto quiere decir que no es necesario evaluar todos los posibles resultados para luego elegir el mejor. Por el contrario, generaremos un número reducido de posibles resultados de manera aleatoria, y en cada iteración elegiremos los que mejores resultados nos han dado para combinarlos entre sí y generar una nueva tanda de posibles soluciones, confiando en que al heredar las propiedades de las mejores soluciones previas, los nuevos resultados generados nos den un resultado mejor, de modo que iteración tras iteración nos acerquemos a una solución al problema lo más óptima posible.
Las soluciones que se evalúan en cada paso del algoritmo se asemejan a genes o cromosomas. Por ejemplo, para un problema con 7 ciudades (A, B, C, D, E, F, G), algunas posibles soluciones serían las siguientes, donde la secuencia de elementos nos indica el orden en el que se visitará cada ciudad:
- (A, B, C, D, E, F, G)
- (A, C, B, D, E, F, G)
- (C, D, E, F, G, A, B)
- (F, G, A, C, D, E, B)
- ...
Por lo tanto el primer paso de nuestro algoritmo es construir una
población inicial de individuos (soluciones) incial desarrolladas normalmente de
forma aleatoria pero asegurándonos de que el resultado sea una solución
válida (en este caso, que no pase 2 veces por la misma ciudad y que las
recorra todas)
Una vez lo tenemos, comienza el proceso
evolutivo, y a lo largo de las diversas generaciones de nuestra
población (las iteraciones del algoritmo) iremos evolucionando nuestro
conjunto de soluciones de la siguiente manera:
- Seleccionar las mejores soluciones de la generación anterior. Este proceso puede abordarse de varias maneras en f unción de la configuración del problema y del algoritmo en cuestión.
- Para el conjunto de individuos escogidos en el punto anterior, se realizarán una serie de combinaciones de cruce entre dichos "padres" que darán lugar a los "hijos" que compartirán la información genética de ambos progenitores. Es posible que alguna de estas soluciones generadas experimente algún tipo de mutación que varíe ligeramente el resultado obtenido tras el cruce.
- Cruce (crossover): se realiza una mezcla de los cromosomas de las dos soluciones padres que generarán una o dos soluciones hijo. Aunque existen distintos tipos de formalismos de cruce, cada problema presenta unas características específicas que han de tenerse en cuenta para evitar generar soluciones no factibles (aunque podrían permitirse, pero nos haría perder tiempo al generar soluciones malas)
- Mutación: se modifica al hazar algún componente de alguna de las soluciones generadas (por ejemplo, intercambiar el orden de paso por las ciudades A y G). Los beneficios de realizar mutaciones (en baja proporción) es que permite amplicar las posibles soluciones que aún no se han visitado, ya que según se haya diseñado el proceso de cruce cabe la posibilidad de "quedarnos encerrados" en el mismo nicho del espacio de búsqueda.
- Actualizar la población actual para generar la nueva lista de "padres" para la siguiente generación. Aquí pueden plantearse varias opciones:
- Erradicar totalmente la generación previa y únicamente quedarnos con la nueva generación de soluciones (asumiendo el riesgo de perder buenas soluciones si las soluciones generadas no son mejores que las anteriores)
- Mezclar en la población resultante a los mejores individuos de la población de padres y la población de hijos (nos permite mantener las mejores soluciones, pero con el riesgo de perder diversidad y que podamos quedarnos atascados en una solución óptima a nivel local)
- Mantener una lista de "las mejores soluciones" paralela a la población de de la generación actual, lo que nos permite no perder las mejores soluciones encontradas hasta el momento
- Evaluar nuestras soluciones para ver cuáles son las mejores.
Tras el número de iteraciones que se desee realizar, este proceso irá evolucionando a nuestra solución hasta darnos con un conjunto de soluciones resultados que en ocasiones serán los resultados óptimos, y en su defecto serán muy buenas aproximaciones a la mejor solución.
El concepto de algoritmo genético fue introducido por John Holland en 1975 en su libro Complex Adaptive Systems. Adaptation in Natural and Artificial Systems An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence
La siguiente imagen nos muestra el pseudo código de un algoritmo genético tal y como Holland lo planteó y que se asemeja el proceso que hemos descrito más arriba.
Sé que puede que para algunos este contenido sea un poco complicado, y que a otros les haya sabido a poco. En futuras entradas hablaré más en detalle de algún ejemplo de algoritmo y sus elementos aplicados a la resolución de problemas concretos que espero sean de interés.
Referencias
Si quieres ver un paper real donde se afronta la solución del problema del viajante:
Para saber más sobre técnicas y procesos de optimización, en el siguiente enlace puedes encontrar un magnífico (y largo) libro escrito por Thomas Weise:
