Optimización estocástica mediante métodos de Monte Carlo

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.Ingeniería de Telecomunicació