Resumen de Applications of Biased Randomization and Simheuristic Algorithms to Arc Routing and Facility Location Problems
Sergio González Martin
La 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.
