Please use this identifier to cite or link to this item:

http://hdl.handle.net/10609/43881
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGonzález Martín, Sergio-
dc.contributor.otherUniversitat Oberta de Catalunya. Internet Interdisciplinary Institute (IN3)-
dc.date.accessioned2015-09-04T11:41:21Z-
dc.date.available2015-09-04T11:41:21Z-
dc.date.issued2015-03-13-
dc.identifier.urihttp://hdl.handle.net/10609/43881-
dc.description.abstractLa majoria de metaheuristiques tenen una component aleatori, que normalment està basada en aleatorització uniforme ¿i.e., l¿ús de la distribució de probabilitat uniforme per fer seleccions aleatòries. Per altra banda, el marc Multi-start biased Randomization of classical Heuristics with Adaptive local search proposa l¿ús de aleatorització esbiaixada (no uniforme) per al disseny de algoritmes metaheuristics alternatius ¿i.e., l¿ús de distribucions de probabilitat esbiaixades com la geomètrica o la triangular. En algunes situacions, aquesta aleatorització no uniforme ha obtingut una convergència més ràpida a la solució quasi òptima. El marc MIRHA també inclou un pas de cerca local per a millorar les solucions generades durant el procés iteratiu. A més, permet afegir passos de cerca adaptats al problema, com cache (memòria) o splitting (dividir i conquerir), que permeten la generació de solucions competitives (quasi òptimes). Els algoritmes dissenyats amb el marc MIRHA permeten obtenir solucions d¿alta qualitat a problemes realistes en temps de computació raonables. A més, tendeixen a utilitzar un nombre reduït de paràmetres, el que els fa simples d¿implementar i configurar en la majoria d¿aplicacions pràctiques. El marc s¿ha aplicat exitosament a diversos problemes d¿enrutament i planificació. Un dels principals objectius d¿aquesta tesi és desenvolupar nous algoritmes , basats en el marc mencionat, per solucionar problemes d¿optimització combinatòria que poden ser d¿interès a la industria de les telecomunicacions.ca
dc.description.abstractLa mayoría de metaheurísticas tienen un componente aleatorio, que normalmente está basada en aleatorización uniforme -ie, el uso de la distribución de probabilidad uniforme para hacer selecciones aleatorias. Por otra parte, el marco Multi-start Biased Randomization of classical heurística with Adaptive local search propone el uso de aleatorización sesgada (no uniforme) para el diseño de algoritmos metaheurísticos alternativos -ie, el uso de distribuciones de probabilidad sesgadas como la geométrica o triangular. En algunas situaciones, esta aleatorización no uniforme ha obtenido una convergencia más rápida en la solución casi óptima. El marco MIRHA también incluye un paso de búsqueda local para mejorar las soluciones generadas durante el proceso iterativo. Además, permite añadir pasos de búsqueda adaptados al problema, como caché (memoria) o splitting (dividir y conquistar), que permiten la generación de soluciones competitivas (casi óptimas). Los algoritmos diseñados con el marco MIRHA permiten obtener soluciones de alta calidad a problemas realistas en tiempo de computación razonables. Además, tienden a utilizar un número reducido de parámetros, lo que los hace simples de implementar y configurar en la mayoría de aplicaciones prácticas. El marco se ha aplicado exitosamente a varios problemas de enrutamiento y planificación. Uno de los principales objetivos de esta tesis es desarrollar nuevos algoritmos, basados ¿¿en el marco mencionado, para solucionar problemas de optimización combinatoria que pueden ser de interés en la industria de las telecomunicaciones.es
dc.description.abstractMost metaheuristics contain a randomness component, which is usually based on uniform randomization ¿i.e., the use of the Uniform probability distribution to make random choices. However, the Multi-start biased Randomization of classical Heuristics with Adaptive local search framework proposes the use of biased (non-uniform) randomization for the design of alternative metaheuristics -i.e., the use of skewed probability distributions such as the Geometric or Triangular ones. In some scenarios, this non-biased randomization has shown to provide faster convergence to near-optimal solutions. The MIRHA framework also includes a local search step for improving the incumbent solutions generated during the multi-start process. It also allows the addition of tailored local search components, like cache (memory) or splitting (divide-and-conquer) techniques, that allow the generation of competitive (near-optimal) solutions. The algorithms designed using the MIRHA framework allows to obtain ¿high-quality¿ solutions to realistic problems in reasonable computing times. Moreover, they tend to use a reduced number of parameters, which makes them simple to implement and configure in most practical applications. This framework has successfully been applied in many routing and scheduling problems. One of the main goals of this thesis is to develop new algorithms, based in the aforementioned framework, for solving some combinatorial optimization problems that can be of interest in the telecommunication industry.en
dc.format.mimetypeapplication/pdf-
dc.language.isoeng-
dc.publisherUniversitat Oberta de Catalunya. Internet Interdisciplinary Institute (IN3)-
dc.rightsLa consulta d'aquesta tesi queda condicionada a l'acceptació de les següents condicions d'ús: La difusió d'aquesta tesi per mitjà del repositori de la UOC ha estat autoritzada pels titulars dels drets de propietat intel.lectual únicament per a usos privats emmarcats en activitats d'investigació i docència. No s'autoritza la seva reproducció amb finalitats de lucre ni la seva difusió i posada a disposició des d'un lloc aliè al repositori de la UOC i/o al servei TDX. Aquesta reserva de drets afecta tant al resum de presentació de la tesi com als seus continguts. En la utilització o cita de parts de la tesi és obligat indicar el nom de la persona autora.-
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/es/-
dc.subjectheurístiques aleatòries i esbiaixadesca
dc.subjectoptimitzacióca
dc.subjectaplicacions realsca
dc.subjectmetaheurístiquesca
dc.subjectsimulacióca
dc.subjectHeurísticas Aleatorias y Sesgadases
dc.subjectOptimizaciónes
dc.subjectAplicaciones Realeses
dc.subjectMetaheurísticases
dc.subjectSimulaciónes
dc.subjectBiased Randomized Heuristicsen
dc.subjectOptimizationen
dc.subjectReal applicationsen
dc.subjectMetaheuristicsen
dc.subject.lcshDissertations, Academicen
dc.titleApplications of Biased Randomization and Simheuristic Algorithms to Arc Routing and Facility Location Problems-
dc.typeinfo:eu-repo/semantics/doctoralThesis-
dc.subject.lemacTesis i dissertacions acadèmiquesca
dc.subject.lcshesTesis y disertaciones académicases
dc.contributor.directorJuan Pérez, Ángel Alejandro-
dc.contributor.directorRiera Terrén, Daniel-
Appears in Collections:Doctoral Thesis

This item is licensed under a Creative Commons License Creative Commons