Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A comparison of Intelligent Water Drops and Genetic Algorithm for maze solving
KTH, School of Electrical Engineering and Computer Science (EECS).
KTH, School of Electrical Engineering and Computer Science (EECS).
2018 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
En jämförelse av Intelligenta Vattendroppar och Genetisk Algoritm för att lösa labyrinter (Swedish)
Abstract [en]

Evolutionary and swarm based algorithms are subsets of bio-inspired algorithms where    Genetic Algorithm (GA) belongs to the former and Intelligent Water Drops (IWD) to the latter.      In this report we investigate their ability to solve mazes with different complexity.    As performance measures we compare solution quality and success rates.    We find that IWD outperforms GA on mazes of low complexity but results deteriorate quickly as maze complexity increases. GA produces more stable results, better solution quality and a higher success rate for high complexity mazes. Some potential improvements inspired by other works are discussed. We conclude that examining different improvements through stronger subordinate problem-specific heuristics is of interest.

Abstract [sv]

Inom de bio-inspirerade algoritmerna finns bland annat evolutionära och svärmbaserade algoritmer. Genetisk Algoritm (GA) tillhör den förra och Intelligenta Vattendroppar (IWD) den senare. I denna rapport undersöker vi dessa två algoritmers förmåga att lösa labyrinter av olika komplexitet. För att mäta prestandan jämförs lösningskvaliteten samt andelen lösningar där destinationen nås. Vi finner att     IWD utpresterar GA för labyrinter av låg komplexitet men resultaten försämras snabbt när komplexitetgraden stiger. För labyrinter av högre komplexitet producerar GA stabilare resultat med bättre lösningskvalitet och högre andel acceptabla lösningar. Några möjliga förbättringsåtgärder som inspirerats av andras rapporter diskuteras. Sammanfattningsvis fastslår vi att vidare undersökning av olika förbättringar genom starkare underordnade problemspecifika heuristiker är intressant.

Place, publisher, year, edition, pages
2018.
Series
TRITA-EECS-EX ; 2018:213
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-229737OAI: oai:DiVA.org:kth-229737DiVA, id: diva2:1214267
Subject / course
Computer Science
Supervisors
Examiners
Available from: 2018-07-10 Created: 2018-06-06 Last updated: 2018-07-10Bibliographically approved

Open Access in DiVA

fulltext(564 kB)1 downloads
File information
File name FULLTEXT02.pdfFile size 564 kBChecksum SHA-512
cb1cc9c1bb6066bfd13631c9fcd3ea6774f416266acef546df19aa93bb5d5a8f021c742dd16139562e02bfa6dd8e520c32dc396541c9b885413d7ce40a7e5997
Type fulltextMimetype application/pdf

By organisation
School of Electrical Engineering and Computer Science (EECS)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 1 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 8 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf