Genetische algoritmen en het handelsreizigersprobleem

artikel door Mark Kooijman

Een negentiende-eeuwse Ierse wiskundige, sir William Rowan Hamilton, bedacht het volgende probleem: 'Gegeven een aantal steden (N), met bekende afstanden daartussen, wat is de kortste route waarlangs al deze steden worden bezocht met het terugkeren naar de beginstad?' Het probleem oogt op het eerste gezicht niet onoplosbaar, maar naarmate het aantal steden groeit, wordt de tijd dat het kost om de oplossing te vinden exponentieel langer. Een efficiëntere manier om een antwoord te berekenen is volgens het genetische algoritme. Deze methode heeft zijn oorsprong in de evolutie en geeft geen exacte oplossingen voor problemen maar benadert deze in grote mate. Hoe dit in de natuur werkt en kan worden toegepast op het handelsreizigersprobleem wordt nauwgezet uitgelegd in het volgende artikel van Mark Kooijman.

Mark Kooijman studeert momenteel af in scheikunde aan de Universiteit Utrecht.

lees het artikel