Algoritmo de optimización de recocido simulado en Java

El recocido simulado es un algoritmo de optimización evolutiva basado en el recocido en metalurgia. En este artículo, implementaremos el recocido simulado en Java para resolver el problema del viajante de comercio.

Introducción

Recocido simulado es un algoritmo evolutivo inspirado en el recocido de la metalurgia. Es un proceso estrechamente controlado en el que un material metálico se calienta por encima de su temperatura de recristalización y se enfría lentamente.

El recocido exitoso tiene el efecto de reducir la dureza y la energía libre termodinámica del metal y altera su estructura interna de tal manera que las estructuras cristalinas dentro del material quedan libres de deformación. . El resultado final es una pieza de metal con mayor elasticidad y menos deformaciones, lo que hace que el material sea más trabajable.

Este proceso sirve como inspiración directa para otro algoritmo de optimización. Simulamos el proceso de recocido en un espacio de búsqueda para encontrar un óptimo global aproximado. El enfriamiento lento en este algoritmo se traduce como una menor probabilidad de aceptar una solución peor que la solución actual a medida que se explora lentamente el espacio de búsqueda.

Dicho esto, Recocido simulado es una metaheurística probabilística que se usa para encontrar una solución aproximadamente buena y, por lo general, se usa con espacios de búsqueda discretos.

En este artículo, lo usaremos en un espacio de búsqueda discreto: en el problema del viajante de comercio.

Recocido simulado {#recocido simulado}

Modelo matemático

El concepto clave en el recocido simulado es energía. Ya hemos mencionado que el proceso de recocido conduce a un material con un estado de energía más bajo. Este estado de menor energía es el resultado de un proceso lento de enfriamiento del material desde una temperatura alta (es decir, un nivel de energía alto) hacia una temperatura más baja (es decir, un nivel de energía bajo).

Para un material dado, podemos definir dos estados de energía, E~1~ (estado actual) y E~2~ (estado siguiente), y su diferencia:

$$
\ Delta E = E_2-E_1
$$

En general, el proceso de recocido dará como resultado transiciones de estados de mayor a menor energía, es decir, donde ΔE < 0. Tales transiciones siempre ocurren con la probabilidad 1 ya que son de nuestro interés para encontrar las mejores soluciones posibles.

A veces, durante el proceso, sin embargo, la energía no puede seguir disminuyendo de forma monótona debido a algunos detalles de la estructura interna del material. En tales casos, es necesario un aumento de energía antes de que el material pueda continuar disminuyendo su energía.

Si ΔE > 0 , el nivel de energía del siguiente estado es más alto que el nivel de energía del estado actual. En este caso, la probabilidad de saltar del estado E~1~ a un estado de mayor energía E~2~ está determinada por la probabilidad:

$$
P(\Delta E) = exp({\frac{-\Delta E}{k \cdot T}})
$$

Donde k representa la Constante de Boltzmann y T es la temperatura actual del material. Al cambiar la temperatura del material, vemos que el nivel de energía del material también cambia.

Simulación del modelo de recocido

Para simular el proceso de recocido, comenzamos en algún estado inicial, que se determina aleatoriamente al comienzo del algoritmo. A partir de este punto, deseamos alcanzar el estado óptimo, típicamente un valor mínimo o máximo. Tanto el estado inicial como el óptimo (junto con todos los demás estados) existen dentro de nuestro espacio de búsqueda que se caracteriza por el problema que estamos tratando de resolver.

La analogía del modelo de energía descrito anteriormente en el contexto del recocido simulado es que estamos tratando de minimizar una determinada función objetivo que caracteriza nuestro problema de optimización. Esta función representa esencialmente el nivel de energía del material que estamos tratando de minimizar. Por lo tanto, la idea de minimizar los niveles de energía se reduce a minimizar la función objetivo de nuestro problema de optimización.

Veamos un ejemplo muy simple de un problema de optimización. En caso de que nuestro problema sea encontrar el mínimo de una función cuadrática, la función en sí representa el espacio de búsqueda y cada uno de los puntos (por ejemplo, (x=1;y=-2)), representa uno de los estados:

quadratic function
[Crédito: Wikipedia]{.pequeño}

Para que sea posible encontrar nuevas soluciones, debemos aceptarlas de acuerdo con algunas reglas predefinidas. En el ejemplo anterior, preferiríamos $x=1$ a $x=2$ ya que nos acercaría al mínimo.

En algunos casos, sin embargo, es posible que queramos permitir que el algoritmo acepte peores soluciones para evitar posibles óptimos locales.

Para permitir que el algoritmo acepte nuevas soluciones que son mejores o aparentemente peores pero que nos ayudarán a evitar los óptimos locales, podemos usar las probabilidades previamente definidas del algoritmo de recocido simulado: en caso de que nuestra nueva solución sea mejor que nuestra solución actual, siempre lo aceptará.

En caso de que la nueva solución sea peor, la aceptaremos con cierta probabilidad:

$$
P = exp({-\frac{f(s_2)-f(s_1)}{T_k}})
$$

donde s es alguna solución y Tk es la temperatura en el k-ésimo paso del algoritmo.

Observe cómo esta expresión es análoga a la anterior que describe el proceso de recocido con niveles de energía. La diferencia es que aquí, en lugar de niveles de energía, tenemos valores de función.

Además, al disminuir lentamente la temperatura durante la duración del algoritmo, estamos disminuyendo la probabilidad de aceptar peores soluciones. En las primeras etapas, esta aceptación de peores soluciones podría ayudarnos inmensamente porque permite que el algoritmo busque soluciones en un amplio espacio de soluciones y salte de un óptimo local si encuentra alguno.

Al disminuir la temperatura (y, por lo tanto, la probabilidad de aceptar peores soluciones), estamos permitiendo que el algoritmo se enfoque lentamente en un área específica que idealmente contiene la solución óptima. Este proceso de enfriamiento lento es lo que hace que el algoritmo sea bastante efectivo cuando se trata de óptimos locales.

Aquí hay una excelente visualización de cómo se analiza el espacio de búsqueda:

simualted annealing gif
[Crédito: Wikipedia]{.pequeño}

Motivación

Ahora que hemos cubierto el funcionamiento interno del algoritmo, veamos un ejemplo motivador que seguiremos en el resto de este artículo.

Uno de los problemas de optimización más famosos es el Problema del vendedor ambulante. Aquí tenemos un conjunto de puntos (ciudades) que queremos atravesar de tal manera que se minimice la distancia total de viaje.

Esto se puede representar como una función ya que tendríamos una distancia total diferente dependiendo del orden en que atravesemos las ciudades:

traveling salesman problem tour differences
[Crédito: TutorialesPunto]{.small}

Dos recorridos diferentes para un mismo trazado de ciudades. La función en este caso representa la distancia total recorrida.

Ahora, si hacemos algunos cálculos matemáticos simples, deduciremos que el número total de combinaciones para atravesar todas las ciudades es N!, donde N es el número de ciudades. Por ejemplo, si tenemos tres ciudades, habría seis combinaciones posibles:

1 -> 2 -> 3
1 -> 3 -> 2
2 -> 1 -> 3
2 -> 3 -> 1
3 -> 1 -> 2
3 -> 2 -> 1

Una de estas combinaciones tendría categóricamente la distancia más corta y una de ellas tendría la más larga.

Estos dos valores representarían entonces nuestros óptimos globales, es decir, mínimo global y máximo global. Como deseamos encontrar la distancia total más corta, optamos por encontrar el mínimo global:

global and local optimums and minimums of a function

Implementación

Para comenzar a resolver el problema del viajante de comercio (TSP), primero debemos crear algunas estructuras de datos iniciales. Para TSP, esto significa crear clases auxiliares City, Tour y Util.

Clases auxiliares

La clase Ciudad es bastante simple. Representa una ciudad en un espacio bidimensional con las coordenadas x e y que recibe a través del constructor.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public class City {

    private int x;
    private int y;

    public City(int x, int y) {
        this.x = x;
        this.y = y;
    }

    // Getters and toString()
}

La clase Tour es un poco más compleja pero la única lógica "real" aquí ocurre en el método getTourLength(). Partimos de la primera ciudad de nuestro recorrido y comenzamos a recorrer la lista. Calculamos la distancia entre cada par de ciudades vecinas y la sumamos a la distancia total.

Al final del método, hemos calculado la distancia total de nuestro recorrido:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Tour {
    private List<City> cities;
    private int distance;

    public Tour(List<City> cities) {
        this.cities = new ArrayList<>(cities);
        Collections.shuffle(this.cities);
    }
    public City getCity(int index) {
        return cities.get(index);
    }

    public int getTourLength() {
        if (distance != 0) return distance;

        int totalDistance = 0;

        for (int i = 0; i < noCities(); i++) {
            City start = getCity(i);
            City end = getCity(i + 1 < noCities() ? i + 1 : 0);
            totalDistance += Util.distance(start, end);
        }

        distance = totalDistance;
        return totalDistance;
    }

    public Tour duplicate() {
        return new Tour(new ArrayList<>(cities));
    }

    public int noCities() {
        return cities.size();
    }

    // Getters and toString()
}

La última clase auxiliar que debe mencionarse es la clase Util que contiene los métodos probability() y distance():

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public class Util {
    public static double probability(double f1, double f2, double temp) {
        if (f2 < f1) return 1;
        return Math.exp((f1 - f2) / temp);
    }

    public static double distance(City city1, City city2) {
        int xDist = Math.abs(city1.getX() - city2.getX());
        int yDist = Math.abs(city1.getY() - city2.getY());
        return Math.sqrt(xDist * xDist + yDist * yDist);
    }
}

El primer método es esencialmente la implementación de nuestro modelo matemático mencionado anteriormente. Si la duración del segundo recorrido es más corta que la duración del primer recorrido, mantendremos el primer recorrido. De lo contrario, devolveremos la probabilidad de aceptar el segundo recorrido.

El método distance() calcula y devuelve la distancia euclidiana entre las dos ciudades dadas.

Implementación de recocido simulado

Con nuestros ayudantes fuera del camino, avancemos e implementemos el algoritmo en sí:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class SimulatedAnnealing {
    private static double temperature = 1000;
    private static double coolingFactor = 0.995;

    public static void main(String[] args) {
        List<City> cities = new ArrayList<>();

        City city1 = new City(100, 100);
        cities.add(city1);

        City city2 = new City(200, 200);
        cities.add(city2);

        City city3 = new City(100, 200);
        cities.add(city3);

        City city4 = new City(200, 100);
        cities.add(city4);

        Tour current = new Tour(cities);
        Tour best = current.duplicate();

        for (double t = temperature; t > 1; t *= coolingFactor) {
            Tour neighbor = current.duplicate();

            int index1 = (int) (neighbor.noCities() * Math.random());
            int index2 = (int) (neighbor.noCities() * Math.random());

            Collections.swap(next.getCities(), index1, index2);

            int currentLength = current.getTourLength();
            int neighborLength = neighbor.getTourLength();

            if (Math.random() < Util.probability(currentLength, neighborLength, t)) {
                current = neighbor.duplicate();
            }

            if (current.getTourLength() < best.getTourLength()) {
                best = current.duplicate();
            }
        }

        System.out.println("Final tour length: " + best.getTourLength());
        System.out.println("Tour: " + best);
    }
}

Comenzamos agregando algunas ciudades a una lista. Para simplificar, agregamos cuatro ciudades que representan un cuadrado. Luego creamos un nuevo recorrido y comenzamos a recorrer el bucle principal, bajando lentamente la temperatura por un factor de enfriamiento.

En cada iteración del ciclo, generamos una solución vecina al intercambiar aleatoriamente dos ciudades en nuestro recorrido actual. Al usar el método de probabilidad, el algoritmo determina si la solución vecina será aceptada o no.

Cuando el algoritmo recién comienza, la alta temperatura hará que la probabilidad de aceptación sea mayor, lo que hará que sea más probable que aceptemos al vecino como nuestra próxima solución. A medida que la temperatura disminuye lentamente, también lo hace la probabilidad.

Esto tendrá el efecto de saltar inicialmente a través de varias permutaciones de recorridos posibles (incluso los malos) porque podrían llevarnos a una solución más óptima en el futuro.

El resultado final del programa se muestra a continuación:

1
2
Final tour length: 400
Tour: [(100, 100), (200, 100), (200, 200), (100, 200)]

El mejor recorrido encontrado por el algoritmo es el que comienza en la esquina inferior izquierda y luego va en sentido contrario a las agujas del reloj. Esto da la duración mínima del recorrido de 400.

Conclusión

El recocido simulado es un algoritmo muy atractivo porque se inspira en un proceso del mundo real. Como otros Algoritmos Evolutivos, tiene el potencial de resolver algunos problemas difíciles.

Sin embargo, ningún algoritmo es perfecto e ideal para cualquier tipo de problema (ver No hay teorema de almuerzo gratis). Esto significa que debemos ser inteligentes al elegir qué algoritmo usar y cuándo. A veces, la respuesta es obvia. Pero a veces, se necesita tiempo y esfuerzo para descubrir realmente qué técnicas dan los mejores resultados posibles en la práctica.