Metalgoritmo de optimización combinatoria mediante la exploración de grafos.

Author

Pastor, Rafael

Director

Corominas Subias, Albert

Date of defense

1999-10-23

ISBN

9788469274071

Legal Deposit

B.46816-2009



Department/Institute

Universitat Politècnica de Catalunya. Departament d'Organització d'Empreses

Abstract

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.

Keywords

artificial intelligence; branch and bound; combinatorial optimization; branch and win

Subjects

51 - Mathematics

Documents

TRPM1de3.pdf

8.996Mb

TRPM2de3.pdf

8.794Mb

TRPM3de3.pdf

7.545Mb

 

Rights

ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.

This item appears in the following Collection(s)