Tema
Optimización aleatoria
- Machine Learning
- Nivel intermedio
Cuando la función objetivo no tiene gradiente útil, se optimiza con métodos que solo la evalúan, y los cuatro del temario son el ascenso de colinas con reinicios, el recocido simulado, los algoritmos genéticos y el procedimiento MIMIC.
Nombre en inglés
Randomized optimization
Intuición
Los cuatro métodos se distinguen por cuánta memoria guardan del pasado. El ascenso de colinas no recuerda nada más allá del punto actual, el recocido simulado recuerda solo la temperatura, los genéticos mantienen una población entera y MIMIC estima además la estructura de dependencias entre variables. Cuanta más memoria, menos evaluaciones hacen falta y más cuesta cada iteración, de modo que el ganador depende de lo cara que sea la función objetivo.
Fórmula
cruce de un punto en la posición 3 sobre 110|101 y 011|010 produce 110010 y 011101; mutacion invierte un bit con probabilidad p
Ejemplo resuelto
Se maximiza el número de unos en una cadena de 6 bits partiendo de 010010. El ascenso de colinas prueba los 6 vecinos a un bit, elige el que suba y llega a 111111 en 4 pasos con 24 evaluaciones. Un algoritmo genético con población de 10 y 5 generaciones gasta 50 evaluaciones para el mismo resultado, lo que en un problema sin óptimos locales es un desperdicio. La ventaja de la población aparece cuando el paisaje tiene trampas, como en el problema de cuatro picos.
Errores frecuentes
- Comparar métodos por número de iteraciones en lugar de por evaluaciones de la función objetivo, cuando una iteración de MIMIC gasta cientos de evaluaciones y una de ascenso de colinas gasta unas pocas.
- Usar una población demasiado pequeña en un algoritmo genético, con lo que la diversidad se pierde en pocas generaciones y el método degenera en una búsqueda local cara.
- Aplicar reinicios aleatorios y contar solo las evaluaciones del mejor reinicio, cifra que oculta el coste real del método y hace parecer barato lo que no lo es.
Ejercicio
Un ascenso de colinas con reinicios aleatorios hace 5 reinicios y cada uno consume 200 evaluaciones de la función objetivo. Calcula el presupuesto total y con qué presupuesto habría que comparar un recocido simulado.
Ver la solución
El presupuesto total suma 5 por 200 = 1000 evaluaciones. Una comparación honesta exige dar al recocido simulado las mismas 1000 evaluaciones, no las 200 de un reinicio ni un número de iteraciones parecido. Conviene además repetir la comparación con varias semillas, ya que los dos métodos son aleatorios y una sola ejecución no distingue una mejora real de la suerte.
Respuesta: 1000 evaluaciones para cada método.