2024-03-29T13:47:32Zhttps://www.tdx.cat/oai/requestoai:www.tdx.cat:10803/67812017-09-01T08:28:01Zcom_10803_183col_10803_225
TDX (Tesis Doctorals en Xarxa)
author
Pastor, Rafael
authoremail
rafael.pastor@upc.edu
authoremailshow
false
director
Corominas Subias, Albert
2011-04-12T15:23:27Z
2009-10-27
1999-10-23
9788469274071
http://www.tdx.cat/TDX-0219109-105251http://hdl.handle.net/10803/6781
B.46816-2009
Actualmente, aunque existen procedimientos específicos para resolver de forma óptima algunos problemas concretos de optimización combinatoria, la mayoría se deben solucionar con técnicas generales de exploración del espacio de soluciones, y más concretamente mediante procedimientos de exploración enumerativos en árboles y grafos de búsqueda.<br/><br/>Se analizan los procedimientos de este tipo expuestos en la literatura, tanto en el área de la investigación operativa como en el de la inteligencia artificial, se realiza un estudio crítico que muestra las controvertidas y confusas relaciones que existen entre estas estrategias de resolución, para proponer, en último término, la necesidad de una formalización general que englobe a todas ellas.<br/><br/>Concretamente, los objetivos y aportaciones de esta tesis son los siguientes:<br/><br/>- Recopilación, análisis y crítica de diferentes procedimientos, estrategias de resolución y formulaciones generales de dichas técnicas expuestas en la literatura.<br/><br/>- Propuesta y formalización de branch and win: un metalgoritmo de exploración de grafos que engloba a los diversos procedimientos de búsqueda (branch and bound, programación dinámica, A*, etc.), y que, además, incorpora la posibilidad de utilizar las nuevas herramientas que se están desarrollando en el campo de la inteligencia artificial (técnicas de consistencia y de propagación local de restricciones).<br/><br/>- Diseño y proposición de nuevos procedimientos híbridos a partir de branch and win, resultado de la combinación de los ya existentes y de la incorporación de diversas ideas de carácter general.<br/><br/>Las hipótesis de trabajo adoptadas presentan las siguientes implicaciones. Por un lado no se resuelven problemas combinatorios con datos aleatorios, ni aquéllos que deben resolverse dentro de un entorno dinámico. Y, por otro, tampoco se formalizan los procedimientos bidireccionales ni los basados en representaciones AND/OR (cabe destacar, sin embargo, que en este caso no se restringe de ninguna manera los problemas combinatorios que es posible resolver).<br/><br/>La originalidad de la tesis reside en el diseño de branch and win, cuyas características principales son: es general, integrador, realista (incorpora aspectos importantes en la resolución de problemas industriales), utiliza terminología clara, dinámico (en función de la evolución de la arborescencia y/o del entorno) y derivador de otros procedimientos.<br/><br/>Se ha realizado una implementación informática del metalgoritmo propuesto para dos conocidos problemas de optimización combinatoria (flow shop y cubrimiento), que ha permitido validar la generalidad de branch and win, así como obtener una serie de recomendaciones sobre la conveniencia de probar la adecuación de un conjunto de estrategias: invertir tiempo en la búsqueda de una solución inicial de calidad, utilizar funciones de evaluación y selección dinámicas, utilizar "en cascada" diversos procedimientos del mismo tipo, uso de procedimientos de reducción y de resolución heurísticos en los vértices intermedios de la arborescencia, incorporación de procedimientos de exploración de entornos al obtener una nueva solución factible, etc.<br/><br/>En cuanto a las posibles extensiones y derivaciones de esta tesis, existe un gran campo de investigación abierto en la dirección de probar, para diferentes problemas de optimización combinatoria, nuevos procedimientos híbridos, que se pueden obtener al combinar y utilizar de diversas maneras los elementos que forman branch and win. Esta investigación se concretaría en ensayar el impacto de los diferentes elementos que forman el metalgoritmo propuesto, con el objetivo de encontrar reglas generales para la resolución efectiva de diferentes problemas de optimización combinatoria o de familias de problemas de características similares.
spa
artificial intelligence
branch and bound
combinatorial optimization
branch and win
Metalgoritmo de optimización combinatoria mediante la exploración de grafos.
info:eu-repo/semantics/doctoralThesis info:eu-repo/semantics/publishedVersion
URL
https://www.tdx.cat/bitstream/10803/6781/1/TRPM1de3.pdf
File
MD5
e8830c6ff11f3872e3f94db4f17d9b73
9433998
application/pdf
TRPM1de3.pdf
URL
https://www.tdx.cat/bitstream/10803/6781/2/TRPM2de3.pdf
File
MD5
1cc4e181bc26d56885120835ef53fb3b
9221426
application/pdf
TRPM2de3.pdf
URL
https://www.tdx.cat/bitstream/10803/6781/3/TRPM3de3.pdf
File
MD5
c8d59d771e8fe60a057a5b37e9ec0aef
7911721
application/pdf
TRPM3de3.pdf
URL
https://www.tdx.cat/bitstream/10803/6781/4/TRPM3de3.pdf.txt
File
MD5
a82a43265c02bf2e29f117203cce76e8
221720
text/plain
TRPM3de3.pdf.txt
URL
https://www.tdx.cat/bitstream/10803/6781/5/TRPM2de3.pdf.txt
File
MD5
02faa4f0e6cc1b8b8a7fd560051e827a
298122
text/plain
TRPM2de3.pdf.txt
URL
https://www.tdx.cat/bitstream/10803/6781/6/TRPM1de3.pdf.txt
File
MD5
cc02b9c68d0531078ea7d1288298efd4
275300
text/plain
TRPM1de3.pdf.txt