spinner

Bioinspírate y evoluciona hacia tu óptimo

Una pequeña introducción al mundo de la optimización y cómo utilizar ideas evolutivas para aproximar diferentes problemas.

La naturaleza como fuente de inspiración

Siempre me he preguntado cómo fue el proceso de innovación hasta la creación de la rueda. Me imagino a un muy lejano antepasado intentando arrastrar algo demasiado pesado, dejando un surco por el suelo. Hasta que en un momento, descansado de su pesada labor, vio rodar cuesta abajo una piedra o un tronco que sin duda eran incluso mayores que su carga. Y en este momento surgió la duda a nuestro primigenio observador. ¿Cómo puede eso bajar por sí mismo y a mi me cuesta tanto? Desde esa observación, a rodar cargas sobre troncos,  y posteriormente sobre ruedas, solo era cuestión de tiempo. Lo que quiero evidenciar con esta historia es que la naturaleza siempre ha sido y será fuente de inspiración para nuevas creaciones. Al fin y al cabo, es lo único que conocemos.

Como curiosidad, la historia de la rueda no ha quedado ahí. Actualmente y gracias a la matemática, tenemos nuevas formas que ruedan no tan obvias como un círculo o una esfera. Por ejemplo el esfericón y el oloide. Si tenéis curiosidad, os dejo unos videos de esfericones, oloides e incluso anti-oloides ¡También los podéis imprimir en 3D para probarlos!

La naturaleza es inmensa, así que vamos a centrarnos en los seres vivos.  Éstos pueden entenderse como la forma de materia que más rápidamente se adapta al entorno. Ya estamos en el área bio-inspirada, y de aquí han salido cosas como máquinas voladoras inspiradas en las aves, trajes de baño inpirados en la piel del tiburón, redes neuronales inspiradas en el cerebro y especializadas en visión… En este artículo vamos a intentar vislumbrar la estrategia que siguen todos ellos para aprender a resolver problemas de optimización.

Optimización

Un problema de optimización matemática, consiste en encontrar el elemento o solución que maximiza o minimiza, un criterio.

Ejemplos:

  1. Dame el valor x que maximiza el valor en la parábola f(x) = -3*x² + 5*x + 3
  2. Quiero 100kg de carne para hacer hamburguesas por el mejor precio sin que la cantidad total de grasa supere el 25%.
    • La carne 1 cuesta 0.8€/kg y tiene un 20% de grasa.
    • La carne 2 cuesta 0.6€/kg y tiene un 32% de grasa.
    • ¿Cuánta carne debo comprar de cada tipo?
  3. Dime las coordenadas (lat,long) del punto más profundo del océano.

Aunque todos son problemas de optimización y se pueden plantear en términos similares, la forma óptima de resolverlos varía enormemente ya que no tienen la misma dificultad. Hagamos el ejercicio de resolverlos.

1. Solución analítica

Al ser una función sencilla (en rojo: -3*x² + 5*x + 3), con solo un máximo local, podemos resolverlo de forma analítica. Es decir, hallamos la fórmula que lo resuelve (en azul: -6x+5) derivando la función original. Igualamos a cero y resolvemos (en naranja). De forma que el punto 0.833 maximiza la función con un valor de 5.083.

Solución analítica al problema de la parábola.

2. Solución con método conocido (optimización lineal)

La característica de este tipo de problemas es que se pueden modelar como maximizar una función de acuerdo a unas restricciones lineales. No tienen un procedimiento que dé la solución directamente de forma analítica. Sin embargo, se puede resolver de una forma eficiente con técnicas de programación lineal.

Hay muchos tipos de problema que caen dentro de esta casuística y se conoce un método eficiente para resolverlos.

3. Solución compleja

La clave de este problema es que no conocemos la función a minimizar, la forma que tiene el fondo del océano. Con lo que los métodos anteriores no aplican. Podríamos intentar solucionarlo con una aproximación por fuerza bruta, que nos llevaría a medir la profundidad en puntos aleatorios y quedarnos con el mejor. Obviamente cuantas más mediciones realicemos, más probable es que demos con un buen punto, pero nunca tendríamos la garantía de que es el más profundo del océano. Muchos problemas de optimización prácticos e interesantes caen dentro de esta categoría (¡porque los sencillos ya están resueltos!). Por ejemplo:

  • Elegir los valores de los parámetros libres de un modelo matemático para que se ajuste lo mejor posible a los datos. Problemática de encontrar algoritmos de entrenamiento eficientes (optimizadores) para modelos de «machine learning».
  • Elegir mejor la mejor topología de una red neuronal artificial para un problema determinado.
  • Componer una canción que sea un superventas este verano.
  • Seleccionar un conjunto de valores de bolsa que maximicen las ganancias en un horizonte determinado, o que tengan ganancias minimizando los riesgos.
  • Diseñar una estructura lo suficientemente resistente para una tarea y que minimice el peso, como un ala de un avión.

Todos estos problemas tienen en común que no conocemos, o al menos no podemos aproximar, lo suficientemente bien, la función que queremos optimizar (la ciencia llega hasta donde llega). Afortunadamente, sí que podemos probar cualquier solución candidata que tengamos, con lo que podemos hacernos una idea de lo buena que es en relación a otras que hayamos probado. Podemos ver qué canción se vendió más, qué conjunto de acciones dieron mejores resultados, qué diseño de ala aguanta y hace que gaste menos el avión (si se parte a lo mejor no).

¿No sería bueno tener un método para aproximar este tipo de problemas? Al fin y al cabo, tener una solución siempre será mejor que no tener nada.

Optimización natural

Allá por el s.XIX, Charles Darwin se dio cuenta de que la naturaleza tenía implícito su propio optimizador para determinar qué seres vivos dominan un territorio (dame la forma viviente que mejor se desenvuelve en estas condiciones). Había nacido la teoría de la evolución.

El mundo natural no es un ente racional con un propósito deliberado como puede serlo un humano, y sin embargo funciona. ¿Por qué? ¿Cuáles son las reglas de este optimizador?

  • Cada especie (o forma viviente) es fértil y tendrá descendencia.
  • Las poblaciones suelen mantener estable el número de individuos.
  • Los recursos son limitados pero estables en el tiempo.
  • Hay variabilidad entre los individuos de una especie.
  • Los individuos traspasan sus características a su descendencia.
  • Existe una selección natural. Los individuos menos aptos tendrán menos probabilidad de tener descendencia.

Tenemos ante nosotros un algoritmo de optimización para el problema más complejo que se nos pueda ocurrir. Ya no estamos hablando de la forma de la función del problema sino de que ni siquiera conocemos la totalidad del mismo o cómo sería una solución. ¿Podemos aprovecharlo?

Análisis del algoritmo

Podemos aprovecharlo si somos capaces de modelar nuestro escenario de optimización en los términos propuestos. Veamos cómo:

1. Población inicial

Para empezar, debemos generar una población o conjunto de soluciones candidatas. Cuanto más diversa sea esa población, más candidatas se explorarán porque menos suposiciones sobre la solución final estamos haciendo. También es cierto que si tenemos algún conocimiento o heurística que nos indique un punto de comienzo ventajoso, podemos aprovecharlo para alcanzar la convergencia del algoritmo antes y no perder el tiempo en candidatas no prometedoras. Por ejemplo, en el caso de la canción superventas, podríamos partir de canciones que hubiesen funcionado en el pasado, o guiarnos por características comunes que agraden al público: compás, tiempo, escala de notas, temática, estilo…

2. Selección natural

Debemos asignar un valor a cada individuo de la población que represente lo apto que es como solución. Esta es la parte más costosa ya que nos requiere probar la solución candidata y ver su desempeño. En el mejor de los casos en un simulador, en el peor, en el mundo real.

Ejemplos:

  • En el problema del mar, sería medir la profundidad en la coordenada propuesta.
  • En el problema de la bolsa, jugarse el dinero con los valores seleccionados.
  • En el problema de la red neuronal, medir el desempeño del modelo creado con la topología propuesta.

A la función que le asigna una puntuación a cada solución candidata se le suele llamar función de fitness (aptitud, idoneidad). Ya hemos visto que definir una función de fitness puede ser imposible, teniendo que recurrir a costosas pruebas. Y es que es precisamente en este punto donde se mete gran parte del conocimiento del problema para guiar al algoritmo hacia una convergencia.

3. Reproducción

Los candidatos con mayor puntuación deberían tener una probabilidad mayor de tener descendencia. La idea es que la combinación de las mejores soluciones candidatas de una población dé como resultado una nueva generación o población de soluciones candidatas que de media sea sea mejor. Si esto no fuera cierto, tendríamos un problema y no hallaríamos convergencia.

Cuantas soluciones candidatas deben combinarse (número de padres) y de qué forma para generar un individuo de la nueva generación es algo que es muy dependiente del problema. Por ejemplo, en la naturaleza tenemos la reproducción sexual (dos elementos dan lugar a un tercero) que se combinan seleccionando elementos concretos del ADN (genes). Pero también existe la reproducción asexual. Si se mantiene la idea de que la solución resultante debería combinar lo mejor de los padres en una suerte de vigor híbrido no hay razón para pensar que no estemos optimizando.

Esta parte es pura probabilidad, así que no vale con escoger los n mejores padres, ya que en la naturaleza la probabilidad de reproducción nunca es cero o uno; existen los accidentes y los golpes de suerte.

Ejemplos:

  • En el mar nos interesaría tener solo un padre y explorar los alrededores. No tiene sentido hacer la media de varios puntos situados en diferentes océanos.
  • Para la topología de una red neuronal, con dos padres podríamos establecer un punto en el que combinamos la primera parte de uno y la restante del otro en una especie de algoritmo genético.
  • En la bolsa, podríamos combinar los elementos de diferentes carteras valores, ya que son independientes entre sí.

4. Mutación

En este punto ya tenemos una nueva generación que con suerte será en promedio mejor que la anterior. ¿Qué pasaría si tenemos reproducción asexual y repetimos el proceso el suficiente número de veces? Exacto, todas las soluciones candidatas deberían ser el mismo elemento (el hijo es igual que el padre) y encima proveniente de la población inicial. Sería lo mismo que coger la solución más apta de la solución inicial. Lo cual es claramente subóptimo. Para evitar este tipo de resultados, lo ideal es establecer una tasa de mutación que modifica levemente a cada candidato de la solución. Puede hacerlo mejor o peor, pero lo que se intenta con esto es ganar diversidad en la exploración de posibles soluciones. Nos interesa que en la primeras poblaciones la tasa de mutación sea alta para explorar más y a medida que construimos nuevas generaciones, vaya decayendo para que los buenos resultados no varíen mucho y converjamos. La forma de conseguirlo es establecer una tasa de decrecimiento exponencial en la probabilidad de mutación.

Ejemplos:

  • En el mar nos interesa mucho explorar los alrededores de cada solución candidata, esto es lo que garantiza la mutación.
  • En la topología de la RN, podemos variar el número de neuronas por capa.
  • En la bolsa, podemos variar levemente la implicación en cada producto. Suponemos que las acciones son independientes.

5. Repetición del ciclo

¡Y ya hemos terminado! Ahora solo necesitamos tiempo (como la naturaleza) y repetir los pasos 2,3 y 4 hasta que estemos satisfechos.

Espera, hay algo que no cuadra…

6. Convergencia del algoritmo

¿Cuándo parar? A diferencia de la naturaleza, ¡nosotros no tenemos tiempo infinito! El propósito es optimizar algo en un tiempo determinado. Pues ahí está la clave, coge la mejor o mejores soluciones de la última generación de soluciones candidatas que se generaron. También existe la posibilidad de que el algoritmo converja, esto es que se consiga uno o varios máximos parecidos y todas las soluciones candidatas sean igual de aptas con lo que no se generen poblaciones mejores que las anteriores. Esto es detectable en el proceso y es un buen momento para parar el proceso iterativo.

Sea como fuere, la construcción de la solución final va a ser una solución de compromiso que debería ser lo suficientemente buena para el problema.

Conclusión

Hemos visto la problemática de la optimización, la razón de ser un algoritmo bio-inspirado evolutivo y una pseudo implementación. También hemos discutido ciertos aspectos de diseño que afectan a la búsqueda de la solución. Solo queda la evaluación.

Ventajas:

  • Es una aproximación genérica e intuitiva a los problemas de optimización.
  • Es mejor que probar aleatoriamente soluciones, así que tiene su hueco en problemas realmente difíciles.
  • Es muy flexible, queda a discreción del implementador el tomar las decisiones.
  • El funcionamiento es muy intuitivo y el modelado del problema es más sencillo que con otros métodos.
  • Parece intuitivo pensar que en algún  momento debería converger y llegar a algún tipo de solución.
  • Se presta a ser paralelizado masivamente, cosa bastante interesante en el mundo de las GPUs, los problemas de Big Data y la computación distribuida.
  • A falta de una mejor opción, puede servir de punto de partida en una comparativa.

Inconvenientes:

  • En general es lento en comparación con otros métodos. La clave está en si se tienen los recursos (conocimiento) para utilizar otros métodos.
  • No es una bala de plata, que ya sea lento implica que puede serlo mucho más si la implementación no es eficiente.
  • Generalmente modelar un problema no es sencillo, ni tampoco tener en cuenta el efecto de las decisiones tomadas.
  • Al ser probabilístico, no está claro cuándo hemos llegado a una solución y menos, que sea la mejor.

Por último, quiero decir que el fondo del mar cambia lentamente, con lo que lo podemos considerar estático; y en cambio, la bolsa es un entorno dinámico con multitud de factores (algunos aleatorios) que le afectan. Esto implica que la función de ajuste para el segundo problema puede variar más rápidamente de lo que mejora una población y estar ante un entorno caótico sin convergencia.

Retando al lector

A continuación, dejo un ejercicio mental para el confiado lector que ya conoce los entresijos de un algoritmo evolutivo.

¿Serías capaz plantear una solución al primer problema (el del máximo de la parábola) con un algoritmo evolutivo?

Fuente de imagen principal: Unsplash

Las opiniones vertidas por el autor son enteramente suyas y no siempre representan la opinión de BBVA Next Technologies.

¿Quieres saber que más cosas hacemos en BBVA Next Technologies?