Publication: Optimización estocástica mediante métodos de Monte Carlo
Loading...
Identifiers
Publication date
2011-04
Defense date
2011-04-15
Authors
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Este proyecto se propone investigar las potencialidades de los métodos de optimización estocástica, y su estrecha relación con los métodos de muestreo aleatorio (también conocidos como
métodos de Monte Carlo).
Las principales fases del proyecto han sido cuatro:
Una primera fase de estudio bibliográfico profundo y exhaustivo, en la que se buscó y examinó una cantidad considerable de información sobre algoritmos de optimización estocástica,
con el fin de asimilar el mayor conocimiento posible. Una vez hecho esto, se clasificaron
los algoritmos más interesantes en cuanto a facilidad de implementación, flexibilidad y
robustez. Se han buscado métodos potentes que no necesiten de excesiva información del
problema para ser aplicados. Fáciles tanto en implementación como en concepto, y por
último, flexibles o generales, ya que son capaces de resolver un abanico de problemas muy
amplio.
La segunda fase del proyecto se concentró en investigar la relación existente entre los
métodos estocásticos de optimización y los métodos de muestreo de variables aleatorias.
En mucho casos, los métodos de optimización hallan la explicación teórica de su óptimo
funcionamiento en los métodos de muestreo. Fue nuestra misión en esta fase del trabajo
encontrar bases teóricas consistentes, que evidenciaran la relación entre estos dos tipos de
técnicas, y explicarán como se llega a estos resultados satisfactorios analíticamente.
En el transcurso de la tercera fase se ha intentado identi car los pasos claves que unen
todos los algoritmos de optimización estudiados, de modo que se pudieran establecer las
semejanzas entre los mismos, así como los rasgos distintivos. Esta fase tenía como objetivo, el poder diseñar nuevos algoritmos; intentando fusionar las características positivas de
distintas filosofías de optimización, con el fin de mejorar las técnicas ya existentes.
En la cuarta y última fase se implementaron algunos de los algoritmos seleccionados como
más interesantes y se comprobó su funcionamiento para un problema real. Esta implementación sirvió para ver de forma práctica los conceptos estudiados y sacar las conclusiones
pertinentes. Es importante resaltar que aunque las pruebas se realizaron para resolver un
problema especifico (y teórico), el código puede usarse en cualquier tipo de problema distinto.
El proyecto está estructurado de modo que en el Capítulo 3 se introducirá el problema de
optimización a resolver y se analizarán los diferentes algoritmos de muestreo existentes. Además,
se evidenciarán las importantes relaciones entre optimización y muestreo. En el Capítulo 4 se
explicará el funcionamiento de las cadenas de Markov y se tratará en profundidad el algoritmo
Metropolis-Hastings. Esta técnica de muestreo es la más útil en el sentido de que ha sido el método
que ha llevado a los investigadores a desarrollar mayor cantidad de técnicas de optimización y de
mayor éxito. El Capítulo 5 está dedicado a los métodos estocásticos de optimización, intentando
focalizar la atención en las técnicas, a nuestro juicio, más interesantes. A su vez, dada la jungla
de métodos que se pueden considerar estocásticos, se realizará una clasi cación de los mismos
lo más clara y sencilla posible. En el Capítulo 6 se implementarán los algoritmos Simulated
Annealing y Acelerated Random Search para la optimización de una función de coste complicada.
Se realizarán pruebas con todos los parámetros que intervienen en los mismos con el fi n de analizar
el comportamiento de estas técnicas. Por último, en el Capítulo 7 se mostrarán las conclusiones
obtenidas en este proyecto y se darán ideas sobre las posibles lineas futuras de investigación.
Description
Keywords
Optimización matemática, Métodos estocásticos, Método de Monte Carlo, Algoritmos de optimización estocástica