Simulated Annealing

Lokaal of absoluut?

In sommige gevallen van optimalisatie, zijn er simpelweg te veel mogelijkheden om een exacte oplossing te bepalen. Toch kan dan nog wel een benaderd optimum worden bepaald. In ons geval gaat het erom of de cellen aan een gunstige processor zijn toegewezen. Dit kunnen we bepalen door een verandering in de verdeling aan te brengen en de kosten daarvoor en -na te vergelijken. We nemen at random een cel en één buurcel. We kijken of het verwisselen van deze twee cellen gunstig is. Wanneer een minimum gezocht wordt, kan dit op twee manieren:

We zouden telkens de verandering kunnen aanbrengen als de kosten daardoor minder worden en stoppen als de kosten meer worden of gelijk blijven.
Hierbij is het risico echter nogal groot dat je in een lokaal minimum terechtkomt en daarna dus niet verder kijkt. Deze methode wordt ook wel greedy genoemd.

Simulated Annealing

Hiervoor heeft Simulated Annealing een oplossing. Wanneer een verandering geen verbetering van de kosten oplevert, wordt deze met een bepaalde kans toch toegestaan. De kans op toelating is proportioneel aan de 'verslechtering'; bij drastische verslechteringen wordt de verandering met een heel kleine kans toegestaan. Wanneer de verandering een verbetering is, wordt deze altijd toegestaan. Om te bepalen hoe groot de verbetering of verslechtering is, worden de kosten voor en na de eventuele verandering bepaald. Nu worden de kansen door de volgende formules gegeven:

In de literatuur (bijv. in [1]) staat voor beide kansen nog een factor 1/b. Dit is de kans dat één bepaalde buursituatie wordt gekozen. In ons geval wordt er al willekeurig één van de vier buurcellen gekozen en heeft de factor 1/b geen invloed meer op het wel of niet wisselen.

De echte truc van Simulated Annealing zit hem in het volgende detail:
In bovenstaande formule is T de zogenaamde afkoelingsconstante. Deze constante bepaalt hoe 'scherp' de toelatingskans voor een verandering is. Deze wordt aanvankelijk groter genomen dan het verwachte maximale kostenverschil tussen twee opeenvolgende situaties. Nu proberen we een groot aantal keren veranderingen aan te brengen. Hierna verlagen we de waarde van T, zodat de toelatingskans aangescherpt wordt. Ook nu wordt weer een groot aantal veranderingen geprobeerd, waarna T weer verlaagd wordt. Dit proces herhaalt zich ook een groot aantal malen. Een verslechtering wordt dus steeds minder vaak toegelaten, zodat je steeds dichter bij een absoluut minimum komt. De kunst is nu, om een goede afkoelsnelheid te bepalen, ofwel: hoe snel T te verlagen. In het practicum-gedeelte zullen we met verschillende waarden experimenteren.