Orienteringsløbsproblemet løst med en genetisk algoritme

Cecilie Lyshøj Olander, Christian Johannesen, Jannick Hynding Petersen & Sofie Søe

Studenteropgave: Semesterprojekt

Abstrakt

This project utilizes a genetic algorithm to solve the orienteering problem. The theoretical foundation is the work of M. Fatih Tasgetiren, whose genetic algorithm has provided excellent results, which we try to replicate. As a start the authors translate a genetic algorithm for solving nonlinear minimization problems, written in C++ by Noyan Turkkan, into Java. It is then changed according to Tasgetirens principles to solve the orienteering problem. The resulting program is tested by running Tsiligirides’ test sets 1-4 and Chao’s test sets 64 and 66. Overall, it does not achieve as good results as Tasgetiren’s, as the results for some problems are a few percent below his. Still, in most problems it gives as good results and in certain problems it surpasses Tsiligirides’ and even Chao’s results. The algorithm has problems getting good results is in the middlesized problems, while the bigger the problem, the better results are achieved.

UddannelserDatalogi, (Bachelor/kandidatuddannelse) Bachelor el. kandidat
SprogDansk
Udgivelsesdato15 jun. 2012
VejledereKeld Helsgaun

Emneord

  • op
  • path planning
  • genetisk algoritme
  • orienteering problem
  • genetic algorithm
  • java
  • Turkkan
  • optimization
  • orienteringsløbsproblem
  • optimering
  • ga
  • Tasgetiren
  • ruteplanlægning