Optimalisatiealgoritme

Een optimalisatiealgoritme is een algoritme dat gebruikt wordt bij het vinden van de optimale oplossing van problemen die een zeer grote oplossingsruimte hebben. De zeer grote oplossingsruimte maakt het ondoenlijk om alle mogelijke oplossingen uit te proberen. In het Operationeel onderzoek worden deze algoritmen toegepast op bedrijfskundige vraagstukken.

Er kunnen geen grenzen gegeven worden aan de verhouding tussen de kwaliteit van de gevonden oplossing en de kwaliteit van de optimale oplossing. Dit in tegenstelling tot benaderingsalgoritmen.

Lineaire optimalisatiealgoritmen

Wanneer alle elementen van een optimaliseringsprobleem lineaire expressies zijn, dan is er slechts een globaal optimum en geen verdere lokale optima. In dit geval kunnen lineaire algoritmen gebruikt worden, zoals de simplexmethode.

Globale optimalisatiealgoritmen

Globale optimalisatiealgoritmen worden gebruikt wanneer de oplossingsruimte zeer grillig is (zeer veel lokale optima).

Een aantal gebruikte methoden zijn

• Genetisch algoritme
• Simulated annealing
• Mierenkoloniealgoritme
• Gerandomiseerde optimalisatie

Het grote voordeel is dat globale optimalisatiealgoritmen niet blijven steken in lokale optima en zo een groot deel van de oplossingsruimte kunnen bekijken. Hierdoor zijn ze echter vrij langzaam. Verder is het niet altijd duidelijk hoe het algoritme precies aan de oplossing komt en bovendien hoeft de gevonden oplossing nog niet eens een lokaal optimum te zijn.

Lokale optimalisatiealgoritmen

Lokale optimalisatiealgoritmen worden gebruikt:

• wanneer de oplossingsruimte slechts een beperkt aantal minima heeft
• men slechts geïnteresseerd is in een lokaal optimum
• er al een redelijke beginoplossing is (bijvoorbeeld uit een globaal optimalisatiealgoritme)

Enkele gebruikte methoden zijn

• Newton-Raphson
• Steepest descent
• Tabu search
• Variable Metric

Het grote voordeel van lokale optimaliseringsmethoden is dat ze eenvoudig te doorgronden zijn. Bovendien zijn ze vergeleken met globale optimalisatiealgoritmen vrij snel. Ze hebben echter een zeer groot nadeel wanneer de oplossingsruimte grillig is: ze blijven steken in het eerste lokale optimum dat ze tegenkomen. Dit kan een zeer slechte oplossing zijn. Bovendien is de reproduceerbaarheid van het resultaat hierdoor zeer klein; een kleine afwijking in de beginsituatie kan leiden tot een groot verschil in resultaat.