Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/351| Caracterización de grafos de búsqueda para problemas de optimización combinatoria Search graphs characterization for combinatorial optimization problems | |
| Everardo Gutiérrez López | |
| CARLOS ALBERTO BRIZUELA RODRIGUEZ | |
| Acceso Abierto | |
| Atribución | |
| Graphs theory,Combinatorial problmes,Grafos de búsqueda,Problemas combinatorios | |
| La existencia de problemas de optimización combinatoria para los cuales no se conocenalgoritmos que puedan resolver cualquier caso en un tiempo razonable ha motivado eldesarrollo de métodos alternativos que permitan obtener soluciones aceptables desde unpunto de vista práctico. Una de esas alternativas son los algoritmos denominados debúsqueda local, los cuales se han utilizado exitosamente en varias aplicaciones reales.La predicción del desempeño de los métodos de búsqueda local para resolver problemasde optimización combinatoria pertenecientes a la clase NP-difícil es una problemática aunpor resolverse. Para ello se debe considerar que la definición de vecindario es un aspectoclave en los algoritmos de búsqueda local, y por cada problema ? puede existir más deun vecindario N cada uno de los cuales genera su propia estructura, es decir, su grafo debúsqueda. Debido a la complejidad que representa el obtener esa predicción, la mayoría delos trabajos previos se han concentrado en caracterizar, de forma teórica y experimental, ladificultad de casos específicos, o de vecindarios específicos, al ser atacados con el paradigmade búsqueda local. Los estudios experimentales han propuesto principalmente la definiciónde medidas de dificultad que permitan diferenciar los casos sencillos de los difíciles.La primera parte de este trabajo presenta un análisis experimental sobre un conjuntode problemas pertenecientes a la clase NP-difícil, lo cual denominamos aquí comocaracterización de grafos de búsqueda. Los experimentos consisten en analizar laspropiedades de los grafos de búsqueda para los casos de los problemas propuestos utilizandotres medidas de dificultad: longitud de correlación (CL), estructura de big valley (BV ) ypropiedad de expansión local (LE). El poder de predicción de estas medidas se analizapara una búsqueda local voraz simple (SGLS) y una búsqueda local iterativa (ILS), alser aplicadas a casos de los problemas: asignación cuadrática (QAP), localización de radiobases (BSL), agente viajero (T SP) y flujo de tareas (F SP)Los resultados obtenidos muestran cómo ninguna de las medidas de dificultad resultó serun buen predictor del desempeño de los algoritmos de búsqueda local utilizados sobre todoslos conjuntos de casos de los problemas de prueba. A pesar de que las tres medidas predicenadecuadamente el desempeño de las búsquedas locales para los casos del QAP, no logranhacer lo mismo para los casos del T SP y BSL, mostrando que no son aplicables a cualquier problema NP-difícil. Una contribución importante de este trabajo, es el establecimiento depreguntas cuyas respuestas permitirían obtener un mejor entendimiento de las capacidadesde predicción de las medidas analizadas.La segunda parte aborda la propuesta de un nuevo algoritmo de optimización multiobjetivo.Se propone adoptar el algoritmo “Go With the Winners” (GWW), el cual esutilizado para verificar la propiedad de expansión local (LE) en grafos de búsqueda, paratratar con problemas multi-objetivo. Se ha probado que el GWW es capaz de encontrarel óptimo global, con alta probabilidad, realizando un muestreo uniforme de los grafos debúsqueda que poseen la propiedad de LE. En este trabajo se propone una versión multiobjetivodel algoritmo GWW al cual se le agregan métodos básicos de búsqueda localcomo mecanismo de escape de los frentes no-dominados. Los resultados muestran que elalgoritmo propuesto obtiene resultados competitivos tanto en su versión original como ensus versiones híbridas. The existence of combinatorial optimization problems for which there are no knownalgorithms that can solve any instance efficiently, has motivated the development ofalternative methods to obtain acceptable solutions for specific sets of instances. One ofsuch alternatives are the local search (LS) algorithms, which have been successfully usedin practice.Performance prediction for local search methods dealing with optimization problemsbelonging to the NP-hard class is an open problem. When dealing with such problem weneed to take into account how the neighborhood is defined since it is a key aspect in thelocal search performance. Moreover, for each problem ? there could be more than oneneighborhood N and each one of them generates its own search graph on which the searchis performed. Performance prediction represents a complex problem and previous attemptshave focused only on characterizing, theoretically and experimentally, specific instancesor specific neighborhoods difficulty when tackled with the local search paradigm. Theexperimental studies have proposed difficulty measures with the aim of separating hardinstances from the easy ones.The first part of this work presents an experimental analysis over a set of test problemsbelonging to the NP-hard class, we call this analysis search graph characterization. Theexperiments focus on analyzing the search graphs characteristics for a set of instances byusing three difficulty criteria: Correlation Length (CL), Big Valley structure (BV ), andLocal Expansion (LE) property. The prediction power of these criteria are analyzed for aSimple Greedy Local Search (SGLS) and the Iterated Local Search (ILS), when they areapplied to instances of the Quadratic Assignment Problem (QAP), Base Station Location(BSL), Traveling Salesman Problem (T SP), and the Flow Shop Problem (F SP).The obtained results show that none of the analyzed difficulty measures is a goodperformance predictor for the local search algorithms used over the set of analyzed instances.Although the three criteria predict well the LS performance for the QAP instances, theyfail to do so for the T SP and BSL instances, showing that they are not applicable to anyNP-hard problem. An important contribution of this research, regarding these measures,ivis the statement of questions whose answers would allow us to have a better understandingof their prediction capability.The second part deal with the proposal of a new multi-objective optimization algorithm.We propose to adopt the “Go With the Winners” (GWW) algorithm, which is used to verifythe LE expansion property of search graphs, to deal with multi-objective combinatorialproblems. It has been shown that the GWW is able to find the global optimum withhigh probability by performing a uniform sampling of search graphs that have the LEproperty. This uniformity is a desirable property for multi-objective algorithms, thereforewe propose a multi-objective version of the go with the winners (MOGWW) and we addlocal search methods to generate a hybrid version to escape from non-dominated traps andimprove its performance. Experimental results show that the proposed algorithm performscompetitively both in its original and hybrid versions. | |
| CICESE | |
| 2009 | |
| Tesis de doctorado | |
| Español | |
| Gutiérrez López,E.2009.Caracterización de grafos de búsqueda para problemas de optimización combinatoria.Tesis de Doctorado en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.xiii, 117 pp. | |
| CIENCIA DE LOS ORDENADORES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 181261.pdf | Versión completa de la tesis | 1.41 MB | Adobe PDF | Visualizar/Abrir |