< Terug naar vorige pagina

Project

Data analyse bij het ontwerpen van algoritmen

De ontwikkeling val algoritmen om reken-technisch moeilijke optimalisatieproblemen te behandelen kent een lange geschiedenis. Belangrijke bijdragen werden reeds geleverd in het midden van de 20ste eeuw. Vandaag zijn hoog-performante optimalisatie-algoritmen vaak zelf van een even hoge complexiteit. Ze bestaan uit verschillende componenten die afgeleid werden volgens verschillende algoritmische benaderingen. De conceptuele diversiteit en de aanwezige alternatieven voor implementatie bemoeilijken het ontwerp van een algoritme. Dit is de bestaansreden van gereedschappen voor de ondersteuning van de ontwerper. Door de snelle toename in beschikbare computerkracht is het nu mogelijk om grote hoeveelheden data te vergaren over de performantie van algoritmen. Data analytische methodes kunnen dan gebruikt worden om het gedrag van de algoritmen zowel als de eigenschappen van de op te lossen problemen beter te begrijpen. Dit is dan weer nuttig bij het ontwerpen van algoritmen om tot top performantie te komen. De laatste decennia zijn de mogelijkheden van "data science" - een combinatie van machine-leren, statistiek en data-analyse - sterk toegenomen en dit creëert mogelijkheden voor het gebruik van deze technieken in een optimalisatiecontext. Automatische algoritme configuratie, algoritme selectie, hyperheuristieken met ingebouwde leermechanismen… zijn slechts voorbeelden van zeer actuele onderwerpen.

Deze verhandeling concentreert zich op het onderwerp "Data science voor optimalisatie". Meer in het bijzonder concentreren we ons op twee aspecten bij het ontwerp van een algoritme: automatische configuratie en analyse van algoritme-parameters op de performantie.

Gegeven een parametrisch algoritme met verschillende ontwerpbeslissingen voor elk van zijn componenten en gegeven een distributie van probleeminstanties, moet algoritme-configuratie toelaten om het beste ontwerp voor het algoritme te bekomen. Recent werden een aantal gereedschappen voorgesteld die deze taak automatiseren. In hoofdstuk 3 verbeteren we de efficiëntie van automatische algoritme-configuratie voor een metaheuristiek die gebaseerd is op lokaal zoeken met een verzameling nabuurschappen. Algoritme-parameters bepalen de waarschijnlijkheid om een bepaalde buurt te kiezen bij elke nieuwe iteratie. We stellen een methode voor om buurten te vinden die zich gelijkaardig gedragen. Deze worden dan gegroepeerd in clusters en krijgen één parameter. Hierdoor wordt het aantal parameters sterk gereduceerd.

In hoofdstuk 4 beschouwen we het verbeteren van de performantie van state-of-the-art automatische algoritme-configuratie software, met de naam irace. We gebruiken meta tuning om de parameters van irace op een verzameling configuratiebenchmarks te optimaliseren. Dit gebeurt met behulp van een automatische configurator. Deze procedure is enkel mogelijk door het gebruik van surrogaat modellen voor het gedrag van de algoritmen. De surrogaten zijn regressie modellen die de performantie van een algoritme voorspellen op basis van de eigenschappen van een instantie.

De performantie-dataset die bekomen wordt nadat een algoritme geconfigureerd werd, kan gebruikt worden om inzicht te verkrijgen in de impact van algoritme-parameters op de performantie. We bouwen een voorspeller voor de gegeven performantie-dataset. Deze wordt dan gebruikt om het belang van de parameters te analyseren. In hoofdstuk 5 demonstreren we het gecombineerde gebruik van drie technieken in deze context: voorwaartse selectie, fANOVA en ablatie-analyse. We gebruiken drie gevalstudies. Deze laten ons toe om de resultaten van de analyse te interpreteren en de voordelen van de combinatie van analysetechnieken te onderzoeken.

Datum:4 feb 2014 →  16 mei 2018
Trefwoorden:automated parameter tuning/configuration
Disciplines:Toegepaste wiskunde, Computerarchitectuur en -netwerken, Distributed computing, Informatiewetenschappen, Informatiesystemen, Programmeertalen, Scientific computing, Theoretische informatica, Visual computing, Andere informatie- en computerwetenschappen
Project type:PhD project