Universidad de Granada Digibug
 

Repositorio Institucional de la Universidad de Granada >
1.-Investigación >
Tesis >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10481/42206

Title: Soft Computing en problemas de optimización dinámicos
Authors: Fajardo Calderín, Jenny
Direction: Pelta, David Alejandro
Masegosa Arredondo, Antonio David
Collaborator: Universidad de Granada. Departamento de Ciencias de la Computación e Inteligencia Artificial
Issue Date: 2016
Submitted Date: 21-Dec-2015
Abstract: La presente investigaci´on se centra en el estudio, dise˜no y evaluaci´on de esquemas de portafolio basados en metaheur´ısticas para abordar problemas de optimizaci´on din´amicos de tipo combinatorio. Se tuvieron en cuenta las ideas de adaptaci´on, cooperaci´on y aprendizaje que consideramos indispensables en este contexto. En ese sentido los objetivos planteados fueron: Realizar un estudio en profundidad en el ´ambito de la Soft Computing, de cara a identificar las t´ecnicas que se utilizan para resolver problemas de optimizaci´on din´amicos, incluyendo las diferentes posibilidades de hibridaci´on de t´ecnicas. Dise˜nar un portafolio de algoritmos que integre t´ecnicas de adaptaci´on, cooperaci´on y aprendizaje, para resolver problemas de optimizaci´on din´amicos. Validar el funcionamiento del portafolio de algoritmos con respecto a algoritmos del estado del arte sobre problemas de optimizaci´on din´amicos combinatorios de prueba y reales. Proponer una librer´ıa de software para facilitar la reutilizaci´on y aplicaci´on de metaheur ´ısticas en la resoluci´on de problemas de optimizaci´on estacionarios y din´amicos. Para alcanzar estos objetivos se propusieron, por un lado un portafolio de algoritmos que incorpora mecanismos de aprendizaje, y por otro, una bater´ıa de experimentos sobre problemas din´amicos de optimizaci´on, para validar su funcionamiento. La primera contribuci´on de la tesis consiste en un portafolio de algoritmos, que dispone de un conjunto de metaheur´ısticas. En cada iteraci´on selecciona cu´al de ellas aplicar mediante un enfoque basado en cr´editos que act´ua como un esquema de aprendizaje. Los experimentos se realizaron sobre cinco problemas “artificiales” a los que se les indujo dinamismo mediante el operador XOR, para diferentes escenarios de severidad y frecuencia de cambio. Los objetivos de la experimentaci´on fueron evaluar el rendimiento del portafolio con diferentes esquemas de aprendizaje; evaluar el rendimiento de los algoritmos individuales que componen el portafolio, frente al propio portafolio; y finalmente, comparar la mejor variante de aprendizaje del portafolio con dos algoritmos de la literatura que han mostrado un muy buen rendimiento en estos problemas. Los resultados del m´etodo propuesto fueron significativamente mejores en la mayor´ıa de los problemas, lo que demuestra que el enfoque del portafolio de algoritmos con un esquema de aprendizaje simple, proporciona buenos resultados para resolver PODs. Por otro lado, se aplic´o el portafolio al problema de m´axima cobertura din´amico (DMCLP). Dicho problema tiene como objetivo encontrar la ubicaci´on de instalaciones que maximiza la demanda cubierta, es decir, la demanda que se encuentra dentro de un determinado tiempo o distancia de cobertura. Partiendo de la variante cl´asica de DMCLP se definieron dos variantes nuevas: DMCLP-AC y DMCLP-LocF, las cuales consisten en incorporar costos por apertura/cierre de instalaciones de un periodo a otro y en fijar la ubicaci´on de las instalaciones a lo largo del tiempo, respectivamente. Para la resoluci´on de estos problemas se emple´o un portafolio compuesto por tres m´etodos de Recocido Simulado propuestos en la literatura, y que hab´ıan reportado muy buenos resultados. En la experimentaci´on, se compar´o el portafolio con los algoritmos individuales que lo componen y de forma general, se pudo concluir que el portafolio fue mejor que los m´etodos individuales en cada una de las instancias de prueba utilizadas. Cabe destacar que los resultados del portafolio de algoritmos para las tres variantes del DMCLP muestran que este tipo de esquemas son capaces de crear sinergias entre los m´etodos que lo componen. Por ´ultimo, todos los algoritmos, m´etodos y problemas utilizados durante el desarrollo de la tesis se incorporaron en una librer´ıa de software llamada BiCIAM, que incluye diferentes algoritmos para resolver problemas de optimizaci´on tanto mono-objetivo como multi-objetivo, y tanto est´aticos como din´amicos. BiCIAM le permite a los investigadores centrarse en el dise˜no del problema y el an´alisis de los resultados, reduciendo el esfuerzo de programaci´on. Adem´as dispone de una gran cantidad de algoritmos ya implementados, por lo que disminuye el nivel de conocimiento requerido a la hora de realizar un estudio en esta tem´atica.
Sponsorship: Tesis Univ. Granada. Departamento de Ciencias de la Computación e Inteligencia Artificial
Publisher: Universidad de Granada
Keywords: Soft computing
Redes neuronales
Inteligencia artificial
Programación heurística
Optimización combinatoria
Sistemas expertos
UDC: 681.3
3304
URI: http://hdl.handle.net/10481/42206
ISBN: 9788491254775
Rights : Creative Commons Attribution-NonCommercial-NoDerivs 3.0 License
Citation: Fajardo Calderín, J. Soft Computing en problemas de optimización dinámicos. Granada: Universidad de Granada, 2016. [http://hdl.handle.net/10481/42206]
Appears in Collections:Tesis

Files in This Item:

File SizeFormat
25642157.pdf6.5 MBAdobe PDFView/Open
Recommend this item

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Valid XHTML 1.0! OpenAire compliant DSpace Software Copyright © 2002-2007 MIT and Hewlett-Packard - Feedback

© Universidad de Granada