HEURISTICA

Autor: PANTRIGO FERNÁNDEZ JUAN JOSÉ.
Año: 2005.
Universidad: REY JUAN CARLOS [www.urjc.es].
Centro de lectura: ESCUELA SUPERIOR DE CIENCIAS EXPERIMENTALES Y TECNOLOGÍA.
Centro de realización: ESCUELA SUPERIOR DE CIENCIAS EXPERIMENTALES Y TECNOLOGÍA.

Resumen: En esta tesis doctoral se propone una nueva metodología para el desarrollo de algoritmos de optimización dinámica, denominada filtro de partículas metaheuristico. los problemas de optimización dinámica constituyen una generalización de los problemas de optimización en los que las variables relevantes del problema cambian en el tiempo. en estas condiciones, es necesario que los algoritmos de optimización dispongan de estrategias de adaptación a los cambios. en consecuencia, la hipótesis de trabajo que se ha planteado en esta tesis doctoral consiste en que "la combinación de estrategias de adaptación, predicción y optimización incrementa la eficiencia de la búsqueda de soluciones de alta calidad para problemas de optimización dinámica". Las metaheurísticas son algoritmos aproximados que se han aplicado con éxito a problemas de optimización, sin embargo, por regla general, este tipo de métodos no consideran la posibilidad de que la definición del problema cambie, y por lo tanto, no están concebidas para adaptarse a la dinámica de un sistema. por otro lado, existe una familia de métodos llamados algoritmos de estimación secuencial (o filtros de partículas), epecializados en la resolución de problemas dinámicos desde un punto de vista bayesfano. desafortunadamente, los filtros de particulas carecen de estrategias de optimización. si la hipótesis de trabajo es válida, tanto las metaheurísticas como los filtros de partículas deben representar un papel importante en optimización dinámica. El problema fundamental que se plantea en optimización dinámica se puede resumir en dos preguntas: ¿qué información de la historia del proceso es útil y se debe tener en cuenta en instantes sucesivos? y ¿cómo se transfiere esta información entre instantes sucesivos durante el proceso dinámico? puesto que existen algoritmos especializados en optimización y métodos orientados a la predicción en entornos dinámicos, parece razonable abordar estos problemas utilizando características de ambas metodologías. por este motivo, el objetivo fundamental de este trabajo de tesis ha sido "desarrollar una metodología para la hibridación de métodos de estimación secuencial y metaheuristicas poblacionales para su aplicación en la resolución de problemas de optimización dinámica". dicha metodología se ha denominado filtro de partículas meteurístico (metaheuristic particle fll ter - mpf). Como ejemplos de aplicación de la metodología propuesta se han construido cinco algoritmos denominados filtro de particulas con busqueda dispersa (scatter search particle fllter - sspf), filtro de partículas con reencadenamiento de trayectorias (path rellnking particle filter - prpf), filtro de particulas con algoritmos meméticos (memeticalgorithms particle filter - mapf), filtro de particulas con estimación de la distribución (estimation of distribution algorithm particle fil ter - edapf) y, por último, filtro de partículas con búsqueda local (local search particle fil ter - lspf), como extensión del ámbito de aplicación de mpf. los algoritmos , desarrollados se hanaplicado de manera efectiva a tres problemas de optimización dinámica: (i) al seguimiento de objetos articulados en secuencias de imágenes 2d, (ii)al seguimiento de uno o varios objetos en secuencias de imágenes 2d para suaplicación a interfaces de usuario basadas en visión artificial y (iii) al problema dinámico del viajante de comercio. en todos ellos, los algoritmos mpf has mostrado experimentalemente un comportamiento más eficiente y han obtenido soluciones de mejor calidad que los algoritmos con los que se han compa 8 rado al 2c9 menos sobre los conjuntos de datos utilizados.

Autor: LUQUE POLO GABRIEL JESÚS.
Año: 2005.
Universidad: MÁLAGA [www.uma.es].
Centro de lectura: INFORMÁTICA.
Centro de realización: INFORMÁTICA.

Resumen: El objetivo de esta tesis es el desarrollo de técnicas metaheurísticas paralelas eficientes para la resolución de problemas con aplicación real. Para ello, inicialmente se ha realizado un estudio sobre el estado del arte actual en el campo de las metaheurísticas, centrándonos principalmente en el dominio de los métodos paralelos. Una vez comprendidas las ventajas y limitaciones de los modelos propuestos en el pasado, y basadas en este conocimiento, se han realizado diferentes propuestas algorítmicas paralelas como extensiones de los modelos más eficientes en la literatura. Estos modelos han sido estudiados en profundidad tanto en un aspecto teórico (estudiando las influencias de los principales parámetros en su convergencia) como en un aspecto experimental, analizando su comportamiento sobre diferentes plataformas paralelas. Basado en el conocimiento adquirido en estas dos últimas fases, se abordó la resolución de diferentes problemas combinatorios con diferentes características pero que comparten como característica diferenciada su gran dificultad y su aplicación real. En concreto se han abordado el diseño de circuitos, el etiquetado léxico del lenguaje natural, el problema de ensamblado de fragmentos de ADN, problemas de planificación y asignación de trabajadores y otros problemas de diferentes campos. Entre las principales aportaciones que se pueden descartar es la mejora en el estado del arte de muchos de los problemas abordas (diseño de circuitos, etiquetado léxico, â¦), así como el aumento en el conocimiento sobre diferentes aspectos algorítmicos de los métodos paralelos (estudios sobre la convergencia de los modelos distribuidos, estudio de la influencia del acoplamiento en las técnicas metaheurísticas paralelas, ..)..

Autor: SEQUEIRA CARDOSO PEDRO JORGE.
Año: 2006.
Universidad: SEVILLA [www.us.es].
Centro de lectura: E.T.S. DE INGENIERÍA INFORMÁTICA.
Centro de realización: E.T.S. DE INGENIERÍA INFORMÁTICA.

Resumen: El estudio de soluciones meta-heurísticas basadas en el paradigma del Ant Colony Optimization (ACO) para el Múltiple Objetive Minimum Spanning Trees y los problemas combinatorios relacionados es la principal preocupación de esta investigación. En la clasificación comúnmente validada de la complejidad de los problemas, se clasifica el problema de las Múltiple Minimum Spanning Trees como NP-completo. Además, como en la generalidad de los problemas de optimización con múltiples objetivos, la solución de un problema Múltiple Objetive Minimum Sapnning Trees es un conjunto de soluciones de compromiso en el sentido que para mejorar uno de los objetivos es necesario por lo menos el empeorar uno los otros, lo que es una preocupación importante en un punto de vista práctico. En la primera parte de la investigación, se hace un análisis teórico del problema para complementar los resultados conocidos. Este análisis corrobora el hecho que en la práctica el uso de métodos exactos de solucionar los problemas Múltiple Objetive Minimum Spanning Trees se aplica solamente en circunstancias especificas. Esto implica que le uso de métodos de aproximación se debe considerar como alternativa para solucionar el problema. Particularmente, se proponen dos métodos basados en el paradigma del ACO: el Múltiple Objetive Network optimization based on an ACO (MONACO) y el Depth ANT Explorer - DANTE. EL MONACO utiliza un conjunto de los rastros de fermonas y heurísticas específicas para aproximar el conjunto de Pareto. El DANTE es una mejora del MONACO que aplica un procedimiento de búsqueda en profundidad basado en las mejores soluciones que se obtienen durante el proceso, de modo a mejor explotar el espacio de la búsqueda. Los métodos propuestos son testados con problemas de múltiples objetivos seleccionados mejorando los resutlados obtenidos previamente por otros autores. Para testar algoritmos MONACO y DANTE sobre el problema del Múltiple Objective Minimum Spanning Trees se ha propuesto la librería/repositorio de problemas de redes con múltiples objetivos, establecidos sobre un conjunto sistematizado de generadores para las redes. Los resultados obtenidos con MONACO y DANTE son comparados con los resultados obtenidos con los métodos de Fuerza Bruta y de Medias Ponderadas.