Solucionando un problema multi-objetivo usando un algoritmo genético

El problema

El problema abstracto

Un problema de optimización multi-objetivo a resolver empleando un algoritmo genético o una estrategia evolutiva.

El problema concreto

Hallar la mejor ruta para recorrer todas y cada una de 20 ciudades, pasando a lo más una vez por cada una y retornando a la ciudad de origen, minimizando:

1. Distancia total recorrida.
2. Riesgo total incurrido.

El problema en detalle

Pueden ver los detalles del problema a resolver en este enlace.

Solucionando el problema

Usamos un algoritmo genético, y lo siguiente:

Un nuevo enfoque de optimización multi-objetivo

Al menos para mí lo es, ya que en una simple inspección no encontré referencias al respecto en el ámbito de la computación evolutiva y la ideé por mi cuenta (sin embargo es muy probable que alguien más ya haya pensado esto en problemas de optimización en general...)

Una imagen vale más que mil palabras:

Hemos considerado la función objetivo g1 como el eje de las ordenadas, y la función objetivo g2 como el eje de las abscisas. En este plano vive la función r, que dependiendo del individuo x y la ponderación o importancia que damos a g1 o g2 para evaluarle, traza un arco de elipse.

Ahora veamos la siguiente imagen:

• Hemos trazado los arcos de elipse completos de varios individuos, obteniendo las elipses respectivas.
  
  • En verde la del mejor individuo hipotético, rojo la del peor individuo hipotético, amarillo y café para individuos buenos en un objetivo y malos para el otro, y en azul la de un individuo que es bueno en ambos objetivos.
    
  • Mientras mejor cumpla un individuo ambos objetivos, más circular será el arco trazado (asumiendo que los objetivos están a la misma escala).
    
• Ninguna elipse puede salir del círculo de radio 1, por la forma en que construimos las funciones g1 y g2.
  
• Toda elipse de cualquier individuo:
  
  • Está circunscrita por la elipse del peor individuo hipotético.
    
  • Circunscribe la elipse del mejor individuo hipotético.
    
• ¿Qué caracteriza la elipse del mejor individuo respecto a la del peor individuo?
  
  • Su área es muchísimo menor (inicialmente se me vino a la cabeza la longitud del arco, pero no existe una fórmula simple para calcularla como sí la hay del área.)
    
    • Se puede, pues, extender la idea, y establecer que un individuo es mejor que otro si el área de su elipse es menor que el área de la elipse del otro.

El área de una elipse de semiejes a y b es PI * a * b, en nuestro caso dado un individuo cualquiera, PI * g1(x) * g2(x). Despreciando la constante a la hora de comparar individuos distintos, nos quedamos con g1(x) * g2(x), que geométricamente es el área del cuadrado formado por los semiejes de la elipse, y sería nuestra función objetivo.
Todo el análisis anterior puede extenderse a más dimensiones: si fueran 3 objetivos, pensaríamos en el volumen de las elipsoides, y con 4+ dimensiones, en el hiper-volumen de las hiper-elipses.


Problema: al implementar esta función objetivo, notamos que los individuos evolucionan haciendo que g2 → 0 en muy pocas generaciones. Entonces la evolución deja de ocurrir porque g(x) = 0 sin importar si el individuo x se acerca o no a 0 en g1.
Solución: Una solución simple es modificar la función objetivo de la siguiente manera

g(x) = (g1(x) + 1)(g2(x) + 1)

Ahora cuando un x llega a 0 por g2, se puede seguir evolucionando.
Esta función tiene como recorrido los reales del 1 al 4.
El efecto geométrico es que la más pequeña de las elipses de un individuo (cuando g1(x) y g2(x) es 0) es un círculo de radio 1, y la optimización consistiría en que elipses de semiejes con valores entre 1 y 2 tratan de acercarse a este círculo ideal.

Las ventajas de este enfoque son:

• No hay que efectuar modificaciones adicionales a un algoritmo genético estándar.
  
• Es simple y fácil de calcular.
  
• No hay que preocuparse de las ponderaciones, ya que implícitamente considera todas las ponderaciones posibles.
  
• Se puede escalar a más dimensiones.

Para mayores detalles de cómo solucionamos este problema, pueden abrir este enlace.

La solución

La solución es un programa en Java.
He aquí el código y un manual de usuario.

Evaluación de la solución

Nos alegra haber nuevamente generado la mejor solución (he borrado los apellidos de mis compañeros para preservar su privacidad):

Estoy consultando porqué nos bajaron una décima en la sección parámetros de ejecución, que es en esencia lo mismo de este otro problema en donde sacamos máxima calificación.
...
Se corrigió el malentendido, así que nos subieron a un 7,0.







***
Esperando que a alguien le sirva esta información, saluda cordialmente,

Juan Carlos San Martín