his.sePublications
1920212223242522 of 47
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
Novelty Search och krav inom evolutionära algoritmer: En jämförelse av FINS och PMOEA för att generera dungeon nivåer med krav
University of Skövde, School of Informatics.
2019 (Swedish)Independent thesis Basic level (degree of Bachelor), 20 credits / 30 HE creditsStudent thesisAlternative title
Novelty Search and demands in evolutionary algorithms : A comparison between FINS and PMOEA for generating dungeon levels with demands (English)
Abstract [sv]

Evolutionära algoritmer har visat sig vara effektiva för att utveckla spelnivåer. Dock finns fortfarande ett behov av nivåer som både uppfyller de krav som spelen har, samt att nivåerna som skapas ska vara så olika som möjligt för att uppmuntra upprepade spelomgångar. För att åstadkomma detta kan man använda Novelty Search. Dock saknar Novelty Search funktioner som gör att populationen vill uppfylla de krav som nivåerna ska ha. Arbetet fokuserar därför på att jämföra två Novelty Search baserade algoritmer som båda uppmuntrar kravuppfyllning: Feasible Infeasible Novelty Search (FINS) och Pareto based Multi-objective evolutionary algorithm (PMOEA) med två mål: krav och Novelty Search.

Studien jämför algoritmerna utifrån tre värden: hur stor andel av populationen som följer de ställda kraven, hur bra dessa individer är på att lösa ett nivårelaterat problem samt diversiteten bland dessa individer. Utöver PMOEA och FINS implementeras även en Novelty Search algoritm och en traditionell evolutionär algoritm. Tre experiment genomförs där nivåernas storlek och antalet krav varierade.

Resultatet visar att PMOEA var bättre på att skapa fler individer som följde alla kraven och att dessa individer överlag var bättre på att optimera lösningar än vanlig Novelty Search och FINS. Dock hade FINS högre diversitet bland individerna än alla algoritmerna som testades. Studiens svaghet är att resultatet är subjektivt till algoritmernas uppsättning i artefakten, som sådan borde framtida arbeten fokusera på att utforska nya uppsättningar för att generalisera resultatet.

Place, publisher, year, edition, pages
2019. , p. 48
Keywords [en]
Feasible Infeasible Novelty Search, Pareto-based Multi-objective Evolutionary Algorithm
Keywords [sv]
Evolutionära algoritmer, Krav, Novelty Search
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:his:diva-17603OAI: oai:DiVA.org:his-17603DiVA, id: diva2:1346868
Subject / course
Informationsteknologi
Educational program
Computer Game Development - Programming
Supervisors
Examiners
Available from: 2019-09-03 Created: 2019-08-29 Last updated: 2019-09-03Bibliographically approved

Open Access in DiVA

Novelty Search och krav inom evolutionära algoritmer(2754 kB)2 downloads
File information
File name FULLTEXT01.pdfFile size 2754 kBChecksum SHA-512
b1383814c3f8bb5ff55db9e4ab0e824ede716b20f8914fef8697313e079896b1e9a9d697104ed348d5faa2bbf34ae8575b8d0e9dd308e3292a814907c56d1aed
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Bergström, Anton
By organisation
School of Informatics
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 2 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: 10 hits
1920212223242522 of 47
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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