title: Optimalisatiealgoritme
text: 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.