¿Cómo debo entender los “Teoremas de no almuerzo gratis para la optimización”?

Imagine un espacio de búsqueda “típico”: hay una o más regiones donde los valores máximos tienden a congregarse, una o más regiones donde los valores mínimos tienden a congregarse, y en su mayor parte el valor de cualquier punto en la superficie de búsqueda estará cerca de Los valores de sus vecinos.

Ahora imagine un espacio de búsqueda donde el valor en cualquier punto no está correlacionado por completo con los puntos vecinos. Quizás una función de “ruido blanco”:

Ahora imagine el conjunto de todos los espacios de búsqueda posibles. Una pequeña fracción se comportará tan bien como en el ejemplo anterior, una pequeña fracción no estará correlacionada por completo como en el segundo ejemplo, y la gran mayoría tendrá alguna combinación de ambos: habrá puntos que no “parecerán aleatorios” , a pesar de que lo son.

Lo que dice el teorema “sin almuerzo gratis” es que ” el rendimiento promedio de cualquier par de algoritmos en todos los posibles problemas [es decir, espacios de búsqueda] es idéntico “. Podría pensar que usar un algoritmo de descenso de la colina para encontrar un máximo global sería una idea terrible, y para el pequeño subconjunto de espacios de búsqueda que generalmente consideramos, eso es cierto. Pero cuando considera todos los espacios de búsqueda, el descenso de la colina es tan malo (o tan bueno) como cualquier otro algoritmo .

(Existen algunas restricciones en la definición de “algoritmo”, IIRC. Un algoritmo que solo considera un solo punto aleatorio y se detiene debería ser peor que un algoritmo que considera dos puntos aleatorios y se detiene. Creo que siempre y cuando los dos algoritmos consideren un número igual de puntos únicos, el teorema es válido).

¿Cómo describirías el algoritmo de Quora usando una ecuación?

Si sabemos cómo funciona un algoritmo de hash de contraseña en particular, ¿por qué no podemos simplemente crear una contraseña que genere el mismo hash?

¿Qué significa 'estructuras de datos de dimensión única' en programación?

¿Con qué frecuencia los desarrolladores de iOS requieren estructuras de datos y diseño de algoritmos?

¿Cómo puede cooperar un sistema distribuido para determinar las reglas de su entorno?

NO Almuerzo gratis El teorema simplemente conocido como teorema de la NFL fue propuesto por “David H. Wolpert y William G. Macready” en 1997. En los algoritmos de optimización de propósito general, se ha vuelto importante entender la relación entre qué tan bien funciona un algoritmo y la optimización problema en el que se ejecuta. Consideremos un problema de optimización de encontrar una aguja perdida en una habitación. Supongamos que hay 10 personas encontrando la aguja. Siempre preferimos dividir a nuestro equipo en grupos e ir primero en una dirección diferente y luego combinar los grupos para buscar en la mejor dirección y finalmente encontrar la aguja. Este es el problema que debe abordarse mediante algoritmos de optimización explorando primero el espacio de búsqueda y luego explotando el espacio de búsqueda. Hay otros problemas como el problema del vendedor ambulante, la escalada y otros. Por lo tanto, todos los problemas necesitan algoritmos de optimización y se han propuesto muchos algoritmos en este contexto.

El teorema de la NFL allana el camino para abordar este problema, ya que cualquier problema de optimización puede ser que un algoritmo esté bien y el otro no. Entonces, si vamos con el teorema de la NFL, establece que si un algoritmo no es apto para un problema en particular, otro podría serlo. Esto ha llevado al investigador en el campo de la optimización a derivar nuevos algoritmos y aplicarlos específicamente a su problema en consideración.

Rohit Salgotra

No sé mucho sobre este tema, ya que nunca lo estudié formalmente con ningún detalle real.

La esencia del concepto, como me enseñaron, es que cualquier optimización / ajuste que realice a un algoritmo que se base en alguna estructura en la instancia del problema necesariamente hará que ese algoritmo funcione peor en algunas otras instancias del problema, donde esa estructura no es No presente.

En la práctica, este teorema no importa demasiado, siempre que la estructura que está explotando sea presente en todas las instancias de problemas que le interesen.

Estoy interesado en leer una respuesta mejor que esta, así que volví a hacer la pregunta =)

Rohit Salgotra

Tal vez pueda construir una función objetiva donde la escalada tenga un mejor desempeño que la bajada. Y aquí está mi código escrito en c ++

Aquí está la función objetivo que construí, en esta función, hay un máximo global, un mínimo global y un mínimo local, el mínimo global está muy cerca del máximo global (dentro del radio de búsqueda utilizado por ambos algoritmos para generar vecinos) pero lejos lejos con el mínimo local.

doble prueba_f2 (doble n)
{
// rango de búsqueda [-1000, 1]
si (n <-1000 || n> 1)
{
cerr << "fuera del rango de búsqueda, n =" << n << endl;
salir (EXIT_FAILURE);
}
más si (-1000 <= n && n <0)
retorno n + 1000;
más si (0 <= n && n <0.0001)
retorno -10000000 * n + 999;
más
volver -1;
}

Como en la mayoría de las regiones de búsqueda, la función es una función lineal simple, con un punto de partida aleatorio, es muy probable que el descenso de la colina quede atrapado en el óptimo local, mientras que para la escalada, puede encontrar fácilmente el máximo global y luego encontrar mínimo global en su próxima etapa de generación de vecinos.

La escalada y la bajada se definen en el siguiente código

#include
#include
#include
#include
#include
usando el espacio de nombres estándar;
#define LOWER_BOUND -1000
#define UPPER_BOUND 1
motor mt19937_64 (random_device {} ());
uniform_real_distribution distr (LOWER_BOUND, UPPER_BOUND);
doble colina (uint32_t iter_n
, función const & f
, función const y cmp)
{
doble punto_inicio = distr (motor);
cout << "El punto de partida es" << punto_inicio << endl;
doble best_x = punto_inicial;
doble best_y = f (punto_inicial);
para (uint32_t iter = 0; iter {
valor doble = f (punto_inicial);
bool mejorado = falso;
doble r = 0.1;
vector vecinos;
neighbours.push_back (punto_inicio + r);
neighbours.push_back (punto_inicio – r);
if (vecinos [0]> UPPER_BOUND)
vecinos [0] = UPPER_BOUND;
if (vecinos [1] vecinos [1] = LOWER_BOUND;
vector neighbour_values (neighbours.size ());
transformar (neighbours.begin ()
, neighbours.end ()
, neighbour_values.begin (), f);
para (size_t i = 0; i {
if (cmp (neighbour_values [i], valor))
{
punto_inicio = vecinos [i];
valor = vecinos_valores [i];
mejorado = verdadero;
}
if (valores_nacionales [i] {
best_x = vecinos [i];
best_y = neighbour_values [i];
}
}
si (! mejorado)
{
// si no se encuentra una solución mejor, realice un salto aleatorio
punto_inicio = distr (motor);
}
}
return best_x;
}
double hill_climbing (uint32_t iter_n, const function & f)
{
return hill (iter_n, f, Greater_equal ());
}
double hill_descending (uint32_t iter_n, const function & f)
{
return hill (iter_n, f, less_equal ());
}