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.

Derivada

La derivada df de una función f es otra función que expresa la tasa de cambio de f. Por ejemplo si tenemos una función que calcula la velocidad en el punto X y calculamos su derivada tendremos una función que calcula la aceleración (cambio de la velocidad) en el punto X. Otra forma de entenderla es como la pendiente en un punto. Si calculamos la derivada de la función fitness en un punto tendremos una función que nos dice cuánto varía y si aumenta o disminuye. Es decir nos da una pista clara de en qué sentido hay que moverse para aumentar o disminuir el valor de la función.

Esto también quiere decir que si la pendiente es 0 ya estás en un máximo o en un mínimo. Si calculas todos los puntos donde la derivada es 0 seguro que uno de ellos es el máximo o el mínimo que estás buscando. Desgraciadamente en muchos casos no es sencillo hallar esos puntos.

Siendo una herramienta tan útil vamos a ver cómo calcularlo. A muchos os sonará de haberlo estudiado y haber tenido que memorizar un montón de derivadas y luego aprender reglas de derivación (por partes, cambio de variables,…) Incluso puede que tener pesadillas con ellas. Pero los ordenadores no saben hacer ese tipo de derivadas. Con ellos hay que recurrir derivadas numéricas que son mucho más simples.

df(x) = f(x+h) – f(x-h) / 2*h

¿Cuanto es h? Lo ideal es que sea una cantidad lo más pequeña posible. Pero ojo con cantidades muy pequeñas y la precisión numérica de los lenguajes de programación que puede dar sorpresa. Cómo se puede ver en el código más abajo yo he fijado el valor por defecto a 0,001.

this.epsilon = epsilon || 0.001;

this.diff = function(x, f){
  return (f(x+this.epsilon)-f(x-this.epsilon))/(this.epsilon*2);
}

Para ir más allá de la primera derivada también hay fórmulas para calcularla numéricamente que son más exactas que el método que vamos a usar nosotros pero en este caso me ha parecido más interesante el siguiente método.

Tenemos una función diff(x,f) que calcula la derivada de f en el punto x. Si hacemos diff(3,diff(3,f)) calcularíamos la segunda derivada de la función f en el punto 3. Para la tercera tendríamos que hacer diff(3,diff(3,diff(3,f))). Para las siguientes derivadas creo que ya habéis entendido como funciona.

En lugar de escribir todas las funciones una detrás de otra en una larga cadena vamos a usar una función que lo haga por nosotros. Siendo el parámetro n el número de derivada que calculará.

this.diffN = function(n, x, f){
  if(n == 1)
    return this.diff(x,f);
  else
    return this.diffN(n-1, x, function(x){return that.diff(x,f)});
}

Gradiente

Ya hemos visto como funciona la derivada para una función f(x) en un punto A, ahora os estaréis preguntando «¿Cómo funciona la derivada para una función con más variables como f(x1, x2)?» ¿A qué os he leído la mente?. Esta vez el punto donde se calcula tiene dos coordenadas [A,B]. Se calculan dos derivadas respecto de x1 y respecto de x2. Lo de «respecto» significa que solo se va a calcular modificando esa varíable, la otra será estática.

df(x1,x2)/dx1 = f(x1-h,x2)-f(x1+h,x2)/2*h

Es decir dejamos el resto de las «equis» inalteradas.

El gradiente es el cálculo de la derivada respecto a «cada equis». Es decir que

G = [df(x1,x2)/dx1, df(x1,x2)/dx2];

Podemos calcular el segundo, tercer,…. gradiente calculando la correspondiente derivada.

Nuestra función para calcular el gradiente usando la función anterior para calcular la derivada numérica queda así:

this.gradN = function(n, x, f){
  G = [];
  for(var i = 0; i < x.length; ++i){
    var auxX = x.slice(0);
    var fdx = function(x){auxX[i] = x; return f(auxX);}
    G.push(this.diffN(n, auxX[i], fdx));
  }
  return G;
}

Para que el uso sea más intuitivo vamos a hacer una versión del primer gradiente sin el parámetro n (n=1)

this.grad = function(x, f){
return this.gradN(1,x,f);
}

Puedes ver todo el código en este repositorio de github.

Si ya hemos elegido nuestro algoritmo favorito y la función fitness que vamos a usar, lanzamos nuestro programa y surge un problema ¿Cuando páramos?.

Lo fácil sería decir que cuando alcancemos el resultado deseado, pero eso no es siempre posible o al menos no en un tiempo que sea razonable. Así que tendremos que quedarnos con una buena aproximación. ¿Pero cual es una buen aproximación? Hay veces que lo sabemos, sabemos que resultado nos tiene que dar al función fitness para que la solución sea suficiente para nosotros. ¿Pero que pasa si no sabemos cuando ha llegado al máximo o al mínimo de la misma?. Con las metaheurísticas siempre nos quedaremos con la duda. No podemos saber si hemos encontrado el punto optimo o nos hemos quedados atrapados en un máximo/mínimo local. Todo dependerá de nuestras necesidades y conocimiento del espacio de búsqueda.

Para reducir este problema hay que intentar explorar lo máximo posible el espacio de búsqueda. El punto optimo puede esconderse en cualquier rincón que nos dejemos sin mirar. Pero claro si estamos usando una metaheurística es porque no conocemos el espacio de búsqueda y es muy grande como para que lo exploremos.

Una de las condiciones más usadas en el caso de desconocimiento total es fijar de antemano un número de iteracciones. Es útil cuando tenemos un tiempo o recursos limitados para calcular la solución. Sin embargo puede darse el caso de que el tiempo no sea tan limitante, aunque tampoco nos apetezca tener al algoritmo iterando durante varias veces la vida del universo. En ese caso se puede fijar un umbral de «mejora». De tal manera que si durante un número determinado de iteracciones el resultado no ha mejorado la solución por encima de ese umbral se para la ejecución ya que se considera que el tiempo invertido no compensa la mejora obtenida.

Por último la que me atrevería a decir que es la condición más usada pero que ningún libro habla de ella. Ir mostrando datos en pantalla y que el usuario decida cuando terminar la ejecución. Puede parecer una solución «poco inteligente» pero durante las pruebas de un algoritmo para ver qué tal se comporta con un problema o viendo si se puede afinar su configuración puede ahorrar mucho de tiempo.

De todas formas muchas veces nos obsesionamos con encontrar el resultado optimo y en la vida real muchas veces basta con una aproximación que ni siquiera sea muy buena.
 

Si hay una metaheurística de ascender montañas tiene que haber otra de bajarlas. El descenso del gradiente se basa en usar el gradiente de guía para encontrar el mínimo de una función. El gradiente indica la pendiente máxima en un punto y hacia donde tenemos que dirigirnos para ascender (a favor del gradiente) o descender (en contra del gradiente). Sabiendo eso solo hay que moverse en la dirección indicada por el gradiente. ¿Cuanto? Ahí está el problema. Si el paso es muy grande podrías pasarte el mínimo y si es muy corto puedes acabar dando un gran número de pasos. Cómo lo de dar un gran número de pasos solo es un problema cuando lo haces con papel y lápiz y los ordenadores no se cansan de caminar (siendo cada paso una iteración del algoritmo) es preferible el segundo caso. Cada vez que se llega a un nuevo punto se calcula el gradiente en ese punto y se avanza en esa nueva dirección.

Supongamos que aún con nuestras precauciones de dar pasitos pequeños nos pasamos del mínimo. ¿Cómo podemos saberlo?. En la imagen de debajo se puede ver un ejemplo. Primero empezamos a «rebotar» de un lado a otro de la función, mientras el valor decrezca vamos bien. El problema surge si el valor aumenta (en la imagen el paso del punto f al g) . En ese caso hemos de volver al punto anterior, reducir el tamaño del paso y seguir probando hasta que se obtenga un valor fitness menor.

Lo ideal sería llegar a un punto donde la pendiente sea 0 (eso indica que es un máximo o un mínimo). Pero en la practica no siempre es posible y al final hemos de depender de las condiciones habituales, llegar a una solución lo suficientemente próxima a la ideal, alcanzar cierto numero de iteraciones o llegar a un tamaño de paso tan pequeño que no merezca la pena continuar.

Ya hemos visto como calcular de forma numérica la derivada y el gradiente. Ahora hemos de aplicar ese conocimiento para calcular el gradiente de la función fitness. Como el descenso del gradiente esta pensado para minimizar, hemos de elegir una función fitness que a menor valor mejor resultado.

Cada nueva coordenada seria la antigua coordenada menos el valor de la derivada de la funcion para esa coordenada multiplicado por el tamaño del paso Kstep.

cordX = cordX – (Kstep * dF/dx)

O lo que es lo mismo en código:

var grad = diff.grad(cords, this.model.calculateFitness);
for(var i = 0; i < this.parameters.dimensions; ++i){
  cords[i] -= this.parameters.step*grad[i];
}

Si el nuevo valor de fitness es menor adoptamos esas coordenadas como nueva solución, si es mayor reducimos el tamaño del paso y volvemos a probar:

if(newFitness < this.fitness){
this.cords = newCords;
this.fitness = newFitness;
} else {
this.parameters.step *= this.parameters.reduceStep;
}

El código completo puede verse aqui.