Autor: Sergio González Martín
Programa: Doctorat de Societat de la Informació i el Coneixement
Idioma: anglès
Directors: Dr. Ángel Alejandro Juan Pérez i Dr. Daniel Riera Terrén
Departament / Institut: Internet Interdisciplinary Institute (IN3)
Matèries: Informàtica, Teoria general de l'anàlisi combinatòria, Teoria de grafs
Paraules clau: Heurístiques aleatòries i esbiaixades, Optimització, Aplicacions reals, Metaheurístiques, Simulació
Àrea de coneixement: Ciència de la Computació i Intel·ligència Artificial

+ Enllaç al projecte

Resum

La majoria de metaheurístiques tenen una component aleatori, que normalment es basa en l'aleatorització uniforme –per exemple, l'ús de la distribució de probabilitat uniforme per a fer seleccions aleatòries. D'altra banda, el marc Multi-start biased randomization of classical heuristics with adaptive local search (MIRHA) proposa l'ús d'aleatorització esbiaixada (no uniforme) per al disseny d'algorismes metaheurístics alternatius –per exemple, 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 generar solucions competitives (gairebé òptimes).

Els algorismes dissenyats amb el marc MIRHA permeten obtenir solucions d'alta qualitat a problemes realistes en temps de computació raonables. A més, tendeixen a usar un nombre reduït de paràmetres, cosa que els fa simples d'implantar i configurar en la majoria d'aplicacions pràctiques. El marc s'ha aplicat amb èxit en diversos problemes d'encaminament i planificació. Un dels objectius principals d'aquesta tesi és desenvolupar nous algorismes, basats en el marc esmentat, per a solucionar problemes d'optimització combinatòria que poden ser d'interès per a la indústria de les telecomunicacions.