Optimizaci贸n estoc谩stica: b煤squeda aleatoria en Java

    Introducci贸n

    La optimizaci贸n estoc谩stica se refiere a una categor铆a de algoritmos de optimizaci贸n que generan y utilizan puntos aleatorios de datos para encontrar una soluci贸n aproximada.

    Si bien los algoritmos de fuerza bruta nos brindan la mejor soluci贸n, son terriblemente ineficientes. Este no es un problema con conjuntos de datos m谩s peque帽os, pero la mayor铆a de los problemas de la vida real y los espacios de b煤squeda requieren una capacidad computacional tan enorme para ser resuelta en un marco de tiempo razonable que tales computadoras probablemente existir谩n m谩s all谩 de un futuro predecible.

    En tales casos, se debe utilizar un nuevo enfoque y, en lugar de buscar la mejor soluci贸n real, nos conformamos con una soluci贸n aproximada que funcione lo suficientemente bien para nosotros.

    Existen muchos m茅todos de optimizaci贸n y cada m茅todo se puede implementar a trav茅s de muchos algoritmos diferentes. Comenzaremos implementando el algoritmo de b煤squeda estoc谩stica menos eficiente e intuitivo: la b煤squeda aleatoria.

    En la b煤squeda de la eficiencia por encima de la correcci贸n absoluta, se han desarrollado muchos algoritmos aleatorios, que culminan con algoritmos evolutivos como los algoritmos gen茅ticos.

    B煤squeda aleatoria

    La b煤squeda aleatoria es el algoritmo de b煤squeda estoc谩stica m谩s simple y es muy intuitivo. Por ejemplo, digamos que estamos buscando el m谩ximo de una funci贸n. En lugar de forzar la soluci贸n, genera puntos aleatorios en una dimensi贸n del espacio de b煤squeda.

    Luego, procede a verificar cada uno de esos puntos comparando el fmax actual con el valor del punto en el que se encuentra, asign谩ndole un nuevo valor si es necesario. Despu茅s de pasar por todos los puntos generados, nos devuelve el fmax como soluci贸n aproximada.

    La desventaja de todos los algoritmos de b煤squeda estoc谩stica, y especialmente la b煤squeda aleatoria, es que pueden ser tan ineficientes como los algoritmos de fuerza bruta si no los equilibra.

    Cuantos m谩s puntos aleatorios utilice, m谩s cercana ser谩 la aproximaci贸n a la mejor soluci贸n absoluta, pero m谩s lento ser谩 el algoritmo. Con una cantidad infinita de puntos aleatorios, es solo un algoritmo de fuerza bruta normal.

    Aqu铆 hay una funci贸n generada por FooPlot como un ejemplo de c贸mo la b煤squeda aleatoria busca el m谩ximo / m铆nimo de una funci贸n:

    Aqu铆 hay 7 puntos generados aleatoriamente, donde casualmente el punto 7 est谩 ubicado en el valor x que devolver谩 el valor y m谩s bajo y 5 est谩 cerca del valor que devolver谩 el valor y m谩s alto, por ejemplo.

    Limitaremos el dominio de la funci贸n al rango de -1 a 2 y en ese rango, usando c谩lculos simples de la escuela secundaria, es f谩cil deducir que:

    $$
    f_ {max} = (0.73947, 0.23098) wedge f_ {min} = (1.71548, -2.79090)
    $$

    Dicho esto, dependiendo de la precisi贸n espec铆fica que est茅 buscando (95% por ejemplo), si la b煤squeda aleatoria se aproxima a algo entre (0.7, 0.2) y (0.75, 0.25) para el fmax y (1.65, -2.65) y (1.8, -2.9) para el fmin deber铆a ser una soluci贸n aproximadamente buena.

    Implementaci贸n

    Sigamos adelante e implementemos la b煤squeda aleatoria en Java. Primero, limitemos el dominio de nuestra funci贸n a {-1...2}:

    private static final double START_DOMAIN = -1;
    private static final double END_DOMAIN = 2;
    

    Luego, repliquemos la funci贸n de FooPlot, que por supuesto, devuelve y Residencia en x:

    private double function(double x) {
        return ((Math.pow(x, 2)-1)*((x-2)*Math.pow(x, 3)));
    }
    

    Finalmente, implementemos el algoritmo en s铆:

    public void randomSearch() {
        double startPosition = START_DOMAIN;
        double maxY = function(startPosition);
        double maxX = START_DOMAIN;
    
        for (int i = 0; i < 10; i++) {
            double random = ThreadLocalRandom.current().nextDouble(START_DOMAIN, END_DOMAIN);
    
            if (function(random) > maxY) {
                maxY = function(random);
                maxX = random;
            }
        }
    
        System.out.println("The maximum of the function f(x) is (" + maxX + ", " + maxY + ")");
    }
    

    La posici贸n inicial para la iteraci贸n es obviamente al comienzo del dominio. los maxY se calcula utilizando el function() m茅todo que hemos definido y el maxX tambi茅n se establece como el valor al inicio del dominio.

    Estos son los valores m谩ximos actuales, ya que a煤n no hemos evaluado nada m谩s. Tan pronto como les asignamos los valores predeterminados, mediante un for bucle, generamos un punto aleatorio entre el inicio y el final del dominio. Luego evaluamos si el punto aleatorio, pas贸 por el function(), es por cualquier cambio mayor que el actual maxY.

    Nota: Estamos usando un ThreadLocalRandom en lugar de un regular Random ya que ThreadLocalRandom puede funcionar mucho m谩s r谩pido que Random en un entorno de subprocesos m煤ltiples. En nuestro caso, no hace mucha diferencia, pero puede hacer una significativa. Adem谩s, es m谩s f谩cil definir un rango de doubles usando ThreadLocalRandom.

    Si lo es, el maxY est谩 configurado en el function(random) como devuelve el y valor y el maxX est谩 configurado en el random ya que ese es el que produjo el mayor y valor a trav茅s del function() m茅todo.

    Despu茅s de la for el ciclo termina, nos quedamos con maxX y maxY con ciertos valores, que son esencialmente una aproximaci贸n de lo que son los m谩ximos reales xey.

    Ejecutar este fragmento de c贸digo producir谩:

    The maximum of the function f(x) is (0.7461978805972576, 0.2308765022939988)
    

    Y comparando esto con los resultados reales, es bastante preciso, con unos miserables 10 puntos aleatorios. Si aumentamos el n煤mero de puntos aleatorios de 10 a 100, obtenemos el siguiente resultado:

    The maximum of the function f(x) is (0.735592753214972, 0.2309513390409203)
    

    No hay mucha mejora entre los dos, lo que demuestra que 100 iteraciones son completamente innecesarias. Si nos tomamos la libertad de reducirlo de 10 a 5, veremos que est谩 apagado:

    The maximum of the function f(x) is (0.6756978982704229, 0.22201906058201992)
    

    Nuevamente, dependiendo de sus necesidades de precisi贸n, esta podr铆a ser una soluci贸n aceptable.

    Cambiar el algoritmo para buscar un m铆nimo en lugar del m谩ximo es tan f谩cil como cambiar el > operador a un < operador en el if cl谩usula.

    Conclusi贸n

    A veces, una aproximaci贸n de la soluci贸n es lo suficientemente buena para sus necesidades y no necesita forzar a su m谩quina a encontrar la mejor soluci贸n posible.

    Este enfoque es extremadamente 煤til cuando se trata de problemas de gran complejidad computacional y puede mejorar el rendimiento de su programa en 贸rdenes de magnitud.

    Por supuesto, si no equilibra correctamente el algoritmo, terminar谩 con una soluci贸n ineficiente, as铆 que juegue con la cantidad de puntos aleatorios para obtener una eficiente.

    Etiquetas:

    Deja una respuesta

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