Optimización estocástica: búsqueda aleatoria en Java

O

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.

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