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:
- Distancia total recorrida.
- 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
