Monte Carlo tree search en instantieruimteanalyse voor het 0-1 knapzak probleem

De wetenschappelijke gemeenschap toont de laatste jaren een stijgende interesse in machine learning algoritmes die worden toegepast in de context van combinatorische optimalisatie. Typisch hangt de performantie van een combinatorisch optimalisatiealgoritme sterk af van de mate waarin dat algoritme de combinatorische eigenschappen van het specifieke probleem kan uitbuiten. Dit manifesteert zich bijvoorbeeld in de noodzaak om een probleem op een geschikte manier te modelleren zodat de overeenkomstige zoekruimte efficiënt kan worden doorlopen. Analoog kan men verwachten dat machine learning algoritmes die worden toegepast in de context van combinatorische optimalisatie ook combinatorische eigenschappen moeten uitbuiten om goed te presteren. Dit is echter niet vanzelfsprekend aangezien deze machine learning algoritmes zelden ontwikkeld zijn met in het achterhoofd combinatorische optimalisatie als doel. In deze thesis onderzoeken we in welke mate huidige state-of-the-art praktijken voor het 0-1 knapzak probleem kunnen worden verbeterd door combinatorische kennis te integreren in het Monte Carlo tree search algoritme en de instantieruimteanalyse methodologie.

We onderzoeken deze vraag op basis van twee casestudy’s. De eerste casestudy concentreert zich op het Monte Carlo tree search algoritme: een populair reinforcement learning algoritme dat voornamelijk gebruikt wordt in de context van het spelen van spellen om te leren om goede zetten te spelen. We demonstreren dat het algoritme licht kan worden aangepast om combinatorische optimalisatieproblemen op te lossen door een zoekruimteboom te doorlopen. We onderzoeken hoe verschillende vormen van combinatorische informatie in het algoritme kunnen geïntegreerd worden om de zoekruimte efficiënt te doorlopen. Het resulterende algoritme wordt geïnstantieerd voor twee problemen uit de literatuur (het 0-1 knapzak probleem en het kadekraanplanningsprobleem met beperkingen omtrent niet kruisen) en de performantie ervan wordt vergeleken met de state-of-the-art algoritmes voor beide problemen.

De tweede casestudy is opgebouwd rond de instantieruimteanalyse methodologie, die kan gebruikt worden om verschillende eigenschappen van probleeminstanties te analyseren op basis van een representatie van die instanties als vectoren van features. Een generator voor 0-1 knapzak probleeminstanties wordt voorgesteld. Deze generator dwingt een aantal combinatorische eigenschappen af gerelateerd aan de inclusiegewijs maximale oplossingen van deze instanties. We vergelijken de moeilijkheid van de resulterende instanties met de moeilijkste instanties uit de literatuur en
onderzoeken hun locatie in de instantieruimte. Nieuwe 0-1 knapzak features gebaseerd op inclusiegewijs maximale oplossingen worden gedefinieerd en nieuwe structurele resultaten worden bewezen die ons toelaten om polynomiale en pseudopolynomiale algoritmes te formuleren om ze uit te rekenen. We vergelijken deze features met bestaande features uit de literatuur, voeren een instantieruimteanalyse uit en onderzoeken in welke mate de features gerelateerd zijn aan de moeilijkheid van een probleeminstantie.