Combinar varias metaheurísticas

Si ajustar una metaheurísticas ya cuesta. ¿Por qué querríamos sufrir el doble para hacerlo con dos?. Hay varios motivos, el principal es que una metaheurística no se comportan bien en todo el espacio de soluciones del problema y por ello se usan varias.

Un caso es que una metaheurística se puede comportar muy bien para calcular parte de la solución pero no toda. Entonces algunos de sus valores los calcularemos usando una metaheurística dejando intactos aquellas partes de la solución para los que no funciona a los que posteriormente aplicaremos la segunda metaheurística que al igual que la anterior no alterará la parte para la que no funciona. Este proceso tiene que repetirse varias veces permitiendo que ambas partes evolucionen de forma conjunta.

Otro caso en que resulta útil aplicar una segunda metaheurística es cuando tenemos una que funciona muy bien explorando el espacio de soluciones y encontrando la zona donde se encuentra el máximo pero muy mal para precisar el valor de este. En ese caso se usa una metaheurística para acercarnos al máximo y cuando ha terminado aplicamos otra para precisar el resultado.

Ahora el problema es como combinar varias metaheurísticas ya que algunas funcionan con mutiles soluciones y otras con una sola.

Empezamos por el caso más intuitivo, el de que ambas metaheurísticas recurran a una población de varios individuos. Aquí las opciones son varias:

  • Cada metaheurística se ejecuta de forma separa con sus propia población de soluciones y cada cierto tiempo se intercambian soluciones entre ellas.
  • Ambas metaheurística actúan sobre las mismas soluciones y compiten entre ellas. Solo las mejores soluciones pasan a formar parte de la población
  • Intercalar metaheurísticas. Aplicamos una durante varias iteracciones  una y luego iteramos varias veces con la otra.

Para el caso de combinar dos metaheurísticas que trabajan con un solo resultado todas las opciones se limitan a usar primero una y luego la otra. Este proceso puede repetirse varias veces o realizarse solo una vez.

Para el caso de combinar metaheurísticas con población y las que trabajan mejorando una única solución:  

  • Tras cada ciclo de la metaheurística orientada a población se aplica la otra metaheurística a los individuos nuevos tratando de mejorarlos
  • Otra opción es usar la metaheristica individual como función de modificación/creación de nuevo individuos.

Un ejemplo muy habitual de combinar metahurísticas es en el caso de los algoritmos genéticos, tras haber generado los nuevos individuos usando los operadores de mutación y/o cruce  y antes de que compitan con el resto de la población se trata de mejorar los nuevos individuos usando alguna metaheurísticas que explore el espacio cercano a cada individuo tratando de encontrar el máximo local.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.