¿Cuál es la relación entre Monte-Carlo Method y Evolutionary Algorithms? A primera vista, parecen ser métodos de simulación no relacionados que se utilizan para resolver problemas complejos. ¿Para qué tipo de problemas es más adecuado? ¿Pueden resolver el mismo conjunto de problemas? ¿Cuál es la relación entre los dos (si hay uno)?Comparar y contrastar el método de Montecarlo y los algoritmos evolutivos
"Monte Carlo" es, en mi experiencia, un término muy sobrecargado. La gente parece usarlo para cualquier técnica que use un generador de números aleatorios (optimización global, análisis de escenarios (Google "simulación Excel Monte Carlo"), integración estocástica (the Pi calculation que todo el mundo usa para demostrar MC). Creo, porque mencionó algoritmos evolutivos en su pregunta, que está hablando de las técnicas de Monte Carlo para la optimización matemática: tiene algún tipo de función de acondicionamiento físico con varios parámetros de entrada y desea minimizar (o maximizar) esa función.
Si su función se comporta bien (hay un mínimo global único al que llegará sin importar con qué entradas empiece), entonces es mejor que use una técnica de minimización determinada, como el método de gradiente conjugado. Muchas técnicas de clasificación de aprendizaje automático implican encontrar parámetros que minimicen al mínimo cuadrados error para un hiperplano con respecto a un conjunto de entrenamiento. La función que se minimiza en este caso es un espacio parabólico liso, bien conducido en n dimensiones. Calcula el gradiente y rueda cuesta abajo. Pan comido.
Sin embargo, si sus parámetros de entrada son discretos (o si su función de acondicionamiento físico tiene discontinuidades), ya no es posible calcular gradientes con precisión. Esto puede suceder si su función de acondicionamiento físico se calcula utilizando datos tabulares para una o más variables (si la variable X es menor que 0.5 use esta tabla, use esa tabla). Alternativamente, puede tener un programa que obtuvo de la NASA que está compuesto por 20 módulos escritos por diferentes equipos que usted ejecuta como un trabajo por lotes. Usted lo suministra con la entrada y escupe un número (creo caja negra). Dependiendo de los parámetros de entrada con los que comience, puede terminar en un mínimo falso. Las técnicas de optimización global intentan abordar este tipo de problemas.
Algoritmos Evolutivos forman una clase de global optimization técnicas. Las técnicas de optimización global generalmente implican algún tipo de "escalada" (que acepta una configuración con una función de acondicionamiento físico más alta (peor)). Esta escalada suele implicar algo aleatorio/estocástico/montecarlo. En general, es más probable que estas técnicas acepten configuraciones menos óptimas desde el principio y, a medida que la optimización progresa, es menos probable que acepten configuraciones inferiores.
Los algoritmos evolutivos se basan libremente en analogías evolutivas. El recocido simulado se basa en analogías al recocido en metales. Las técnicas de enjambre de partículas también están inspiradas en sistemas biológicos. En todos los casos, debe comparar los resultados con un muestreo aleatorio simple (a.k.a. "monte carlo") de configuraciones ... esto a menudo arrojará resultados equivalentes.
Mi consejo es comenzar usando una técnica determinística basada en gradiente ya que generalmente requieren muchas menos evaluaciones de funciones que las técnicas estocásticas/monte-carlo. Cuando escuches pasos de pezuña, piensa que los caballos no son cebras. Ejecute la optimización desde varios puntos de inicio diferentes y, a menos que tenga que lidiar con un problema particularmente desagradable, debería terminar con aproximadamente el mismo mínimo. De lo contrario, podría tener cebras y debería considerar el uso de un método de optimización global.
Bueno, creo que los métodos de Monte Carlo es el nombre general de estos métodos que usan números aleatorios para resolver problemas de optimización. De esta manera, incluso los algoritmos evolutivos son un tipo de método de Monte Carlo si usan números aleatorios (y de hecho lo hacen).
Otros métodos de Monte Carlo son: metrópolis, Wang-Landau, temple paralelo, etc
Otoh, los métodos evolutivos utilizan 'técnicas' tomado de la naturaleza, como mutación, cross-over, etc.
+1 Buena respuesta, pero la de Frank fue más completa. – Gili
I me gusta tu respuesta, pero parece incompleta. Mencionó cómo funcionan los algoritmos evolutivos, pero no discutió explícitamente para qué tipo de problemas son más adecuados. Discuta también el Método Monte-Carlo con mayor detalle. – Gili
"La gente parece usarlo (Montecarlo) para cualquier técnica que use un generador de números aleatorios". ¿Es esta una definición válida? ¿O estás insinuando que Montecarlo significa algo más? – Gili
@Gili Para citar el artículo de Wikipedia que vinculó, "los métodos de Monte Carlo (o los experimentos de Monte Carlo) son una clase de algoritmos computacionales que se basan en el muestreo aleatorio repetido para calcular sus resultados". Mi punto es simplemente que MC describe una CLASE de algoritmos. En el contexto de la optimización global, los algoritmos evolutivos son uno de los muchos enfoques de optimización de Monte Carlo (esto es, estocástico). – Frank