07/12/2018


Optimaliseren met heuristieken

 

In de vorige blog in deze reeks beschreef mijn collega Jacob Jan met behulp van een praktijkvoorbeeld hoe de optimale oplossing voor een wiskundig probleem kan worden gevonden. In de praktijk komt het echter ook voor dat de optimale oplossing niet kan worden gevonden, of pas na lang wachten. Het probleem is dan vaak te groot om exact op te lossen. Om toch in een relatief korte tijd een goede oplossing te vinden, kun je heuristieken toepassen. Heuristieken verschaffen algemene richtlijnen over mogelijke oplossingen en besparen veel tijd en moeite door de complexiteit van de oplossingsmethode te beperken. Er bestaan verschillende soorten heuristiek, waaronder constructieve heuristiek en de lokale zoekmethode. Constructieve heuristieken resulteren in een oplossing zonder dat daarvoor een startoplossing voor nodig is, er wordt namelijk een oplossing geconstrueerd. Dit zijn veelal greedy algoritmes, waarbij met simpele regels een oplossing kan worden gevonden. Vaak ligt deze oplossing nog ver van de optimale oplossing. Voor een voorbeeld zie de afbeelding hieronder, waarin een oplossing is gevonden voor een ‘travelling salesman’ probleem. In dit probleem is de doelfunctie om alle punten te bezoeken en zo min mogelijk afstand af te leggen. Het is meteen duidelijk dat onderstaande oplossing niet de optimale oplossing is!

Daarom zijn er ook algoritmes die vanuit een opgegeven startoplossing proberen de oplossing te verbeteren, dit zijn ‘local search’ heuristieken. Een veel gebruikte local search heuristiek is ‘simulated annealing’. Deze methode is vernoemd naar de Engelse term ‘annealing’ (uitgloeien), welke wordt gebruikt in de metaalbewerking. In onderstaande oplossing is simulated annealing toegepast op de startoplossing van het ‘travelling salesman’ probleem.

Simulated annealing

Een simulated annealing algoritme probeert een startoplossing te verbeteren door een groot aantal wijzigingen op de oplossing door te voeren. Er wordt een temperatuur gedefinieerd die langzaam daalt. Bij een hoge temperatuur wordt met een grotere kans wijzigingen geaccepteerd die de oplossing zullen verslechteren. Naarmate de temperatuur daalt, zal de kans dat een verslechtering wordt geaccepteerd ook dalen. Als een wijziging de oplossing verbetert, wordt de wijziging altijd geaccepteerd. Het is nodig om ook verslechteringen van de oplossing te accepteren om uit lokale optima te komen. Een voorbeeld hiervan zie je in onderstaande afbeelding, waarin bij elke iteratie de huidige oplossing wordt afgebeeld. Zoals je kunt zien wordt op het begin nog erg veel verslechteringen geaccepteerd, maar na een tijd convergeert de oplossing naar een lokaal optimum. Hoewel het niet gegarandeerd is dat het globale optimum wordt gevonden, is de best gevonden oplossing vaak erg dichtbij het globale optimum.

De essentie van het simulated annealing algoritme kan in slechts een aantal regels code worden geschreven. Wat het zo moeilijk maakt, is dat er bijzonder veel parameters zijn die gekozen moeten worden. Het aantal iteraties, start temperatuur, eind temperatuur, snelheid van het dalen van de temperatuur en ga zo maar door. Daarnaast is het essentieel dat de wijzigingen die worden berekend in elke iteratie de oplossing ook echt verbeteren. Zo komt het vaak voor dat er verschillende soorten wijzigingen, ook wel buurruimtes genoemd, worden geprobeerd om tot een betere oplossing te komen. De buurruimtes kunnen verschillende complexe wisselingen bevatten. Als met behulp van de buurruimtes van elke startoplossing de optimale oplossing kan worden gemaakt, heet dit ‘optimum connected’. Als er in het 'travelling salesman' probleem van voorheen bijvoorbeeld twee trucks zouden zijn die de locaties moeten langsrijden en de enige buurruimte bestaat uit een wisseling waarbij locatie A door truck A in plaats van truck B wordt bereden en locatie B door truck A in plaats van truck B, dan is dit niet optimum connected. Het aantal locaties dat een truck langs rijdt staat dan namelijk vast. Het is hierbij ook nodig dat een locatie van truck kan worden gewisseld zonder dat daarvoor een andere locatie in de plaats komt. De keuze van buurruimtes is dus vitaal voor het vinden van een goede oplossing.

 

Toepassingen

Bij CQM gebruiken we de methode al jaren in verschillende projecten. Problemen in onder andere transportplanning, warehouse logistiek en personeelplanning zijn met behulp van simulated annealing efficiënt opgelost.

 

Is optimalisatie een interessante toepassing van data science voor uw bedrijf? 

Neem dan contact op met Arno van den Eijnden.

 

Ook interessant om te lezen:

 

 

Arno van den Eijnden
Arno van den Eijnden helpt je graag verder Neem contact op