Algoritmo de optimización de recocido simulado en Java

A

Introducción

El recocido simulado es un algoritmo evolutivo inspirado en el recocido de la metalurgia. Es un proceso muy 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 energía libre termodinámica del metal y alterando su estructura interna de modo que las estructuras cristalinas del interior del material se vuelvan libres de deformaciones. El resultado final es una pieza de metal con mayor elasticidad y menos deformaciones, lo que hace que el material sea más manejable.

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 de este algoritmo se traduce en 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, el recocido simulado es una metaheurística probabilística que se utiliza para encontrar una solución aproximadamente buena y normalmente se utiliza con espacios de búsqueda discretos.

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

Recocido simulado

Modelo matemático

El concepto clave en el recocido simulado es la energía. Ya hemos mencionado que el proceso de recocido conduce a un material con un estado de menor energía. 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, E1 (estado actual) y E2 (siguiente estado), 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 manera monótona debido a algunas características específicas 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 mayor que el nivel de energía del estado actual. En este caso, la probabilidad de saltar del estado E1 a un estado de mayor energía E2 está determinada por la probabilidad:

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

Dónde k representa el 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, normalmente 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 (p. Ej. (x=1;y=-2)), representa uno de los estados:

 

Crédito: Wikipedia

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

En algunos casos, sin embargo, es posible que queramos permitir que el algoritmo acepte soluciones peores 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, podemos 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}})
$$

dónde 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 enormemente porque permite que el algoritmo busque soluciones en un vasto espacio de soluciones y salte de un óptimo local si encuentra alguna.

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

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

 

Crédito: Wikipedia

Motivación

Ahora que hemos cubierto el funcionamiento interno del algoritmo, veamos un ejemplo motivacional 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 minimicemos 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 el que recorramos las ciudades:

 

Crédito: TutorialsPoint

Dos recorridos diferentes para el 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!, dónde 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 entonces representarían 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:

Implementación

Para comenzar a resolver el problema del vendedor ambulante (TSP), primero debemos crear algunas estructuras de datos iniciales. Para TSP, esto significa crear clases auxiliares City, Toury Util.

Clases de ayudantes

los City la clase es bastante simple. Representa una ciudad en un espacio bidimensional con el x y y coordenadas que recibe a través del constructor.

public class City {

    private int x;
    private int y;

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

    // Getters and toString()
}

los Tour La clase es un poco más compleja, pero la única lógica “real” aquí ocurre en el getTourLength() método. 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:

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 de ayuda que debe mencionarse es la Util clase que contiene el probability() y distance() métodos:

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 tour.

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

Implementación de recocido simulado

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

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 circuito principal, bajando lentamente la temperatura en un factor de enfriamiento.

En cada iteración del ciclo, generamos una solución vecina intercambiando 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 temperatura alta 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 posibles recorridos (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:

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 antihorario. 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 ningún tipo de problema (ver Teorema sin 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.

About the author

Ramiro de la Vega

Bienvenido a Pharos.sh

Soy Ramiro de la Vega, Estadounidense con raíces Españolas. Empecé a programar hace casi 20 años cuando era muy jovencito.

Espero que en mi web encuentres la inspiración y ayuda que necesitas para adentrarte en el fantástico mundo de la programación y conseguir tus objetivos por difíciles que sean.

Add comment

Sobre mi

Últimos Post

Etiquetas

Esta web utiliza cookies propias para su correcto funcionamiento. Al hacer clic en el botón Aceptar, aceptas el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad