Algoritmo de optimizaci贸n de recocido simulado en Java

    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.

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *