Undersøgelse af en genetisk algoritme: Study of a genetic algorithm

Sanne Bjerg, Tanja Josefsen, Pernille Hviid Petersen, Claus Daldorph Nielsen & Rasmus Rasmussen

Studenteropgave: Semesterprojekt

Abstrakt

Denne rapport har til formål, at undersøge hvordan ændringer i tre forskellige parametre i den genetiske algoritme - crossoverraten, mutationsraten og populationsstørrelsen - påvirker algoritmens effektivitet. Undersøgelsen tager udgangspunkt i forsøg med to forskellige implementeringer af den genetiske algoritme, der er konstrueret til at løse tre optimeringsproblemer, to rygsækproblemer af forskellig problemstørrelse og en minimering af energien i en Lennard-Jones modelvæske. Forsøgene med hver af implementeringerne analyseres hver for sig med henblik på at undersøge hvordan de tre parametre påvirker den pågældende implementering. Efterfølgende foretages en sammenligning af de tre analyser med det formål at opnå indsigt i hvorvidt der kan udledes nogle generelle tendenser ud fra denne sammenligning. Resultatet af denne sammenligning sammenholdes derefter med en analyse af skemateoremet, som er et teorem der forsøger at forklare hvorfor og hvordan genetiske algoritmer fungerer, for til sidst at undersøge om tendenserne, der er observeret ved forsøgene, stemmer overens med dette teorem. Det er blevet konkluderet, at de tre parametre påvirker de to implementeringer af den genetiske algoritme på tilnærmelsesvist samme måde. Der er gode indikationer på, at tendenserne der er observeret, vil være de samme for andre implementeringer af den genetiske algoritme. Tendenser der er observeret til understøtter skemateoremet.

UddannelserBasis - Naturvidenskabelig Bacheloruddannelse, (Bachelor uddannelse) Basis
SprogDansk
Udgivelsesdato1 jun. 2006

Emneord

  • Genetiske algoritmer
  • Lennard-Jones modelvæske
  • mutationsrate
  • crossoverrate
  • skemateorem
  • populationsstørrelse
  • rygsækproblem