Optimización Estocástica: Búsqueda Aleatoria en Java

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 aproximar una solución. En este artículo, exploraremos el más simple: búsqueda aleatoria, en Java.

Introducción

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 grande para resolverse 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 Búsqueda estocástica menos eficiente y más intuitivo: Búsqueda aleatoria.

En la búsqueda de la eficiencia sobre la corrección absoluta, se han desarrollado muchos algoritmos aleatorios, que culminan con algoritmos evolutivos como Algoritmos genéticos.

Búsqueda aleatoria {#búsqueda aleatoria}

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 aplicar fuerza bruta a 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 f~max~ 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 f~max~ como solución aproximada.

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

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 regular de fuerza bruta.

Aquí hay una función generada por FooPlot como ejemplo de cómo Búsqueda aleatoria busca el máximo/mínimo de una función:

function

Aquí hay 7 puntos generados aleatoriamente, donde coincidentemente 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 *y más alto * valor, para un ejemplo.

Limitaremos el dominio de la función al rango de -1 a 2 y en ese rango, usando cálculo simple de la escuela secundaria, es fácil deducir que:

$$
f_{máx} = (0,73947, 0,23098) \cuña f_{mín} = (1,71548, -2,79090)
$$

Dicho esto, dependiendo de la precisión específica que esté buscando (95 %, por ejemplo), si Random Search se aproxima a algo entre (0.7, 0.2) y (0.75, 0.25) para el *f~max~ * y (1.65, -2.65) y (1.8, -2.9) para f~min~ debería ser una solución aproximadamente buena.

Implementación

Avancemos e implementemos la búsqueda aleatoria en Java. Primero, vinculemos el dominio de nuestra función a {-1...2}:

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

Luego, vamos a replicar la función de FooPlot, que por supuesto, devuelve y basado en x:

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

Finalmente, implementemos el algoritmo en sí:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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 de la iteración es obviamente al comienzo del dominio. El maxY se calcula utilizando el método function() que hemos definido y el maxX también se establece como el valor al comienzo 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, a través de un bucle for, generamos un punto aleatorio entre el inicio y el final del dominio. Luego evaluamos si el punto aleatorio, pasado a través de la función(), es por algún cambio mayor que el maxY actual.

Nota: Estamos usando un ThreadLocalRandom en lugar de un Random normal, 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 ‘dobles’ usando ‘ThreadLocalRandom’.

Si es así, el maxY se establece en la función (aleatoria) ya que devuelve el valor y y el maxX se establece en random ya que ese es el que produjo la mayor valor y a través del método function().

Después de que termina el ciclo for, nos quedan maxX y maxY con ciertos valores, que son esencialmente una aproximación de lo que son los máximos reales x e y.

Ejecutar este fragmento de código producirá:

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

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

1
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:

1
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 de un máximo es tan fácil como cambiar el operador > a un operador < en la cláusula if.

Conclusión

A veces, una aproximación de la solución es lo suficientemente buena para sus necesidades y no necesita obligar 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 solución eficiente.