Linking the dynamics of genetic algorithms to the encoding of information
(2016) FYTK02 20161Computational Biology and Biological Physics - Undergoing reorganization
Department of Astronomy and Theoretical Physics - Undergoing reorganization
- Abstract
- Genetic algorithms are complex constructs often used as heuristic search methods in contexts ranging from combinatorial optimisation to in silico evolution. They draw inspiration from the principles of biological evolution by utilizing the concepts of mutation, reproduction and selection in order to improve a population of solutions. The solutions are often represented as abstract data sequences, e.g. as binary strings, though it has been shown that the choice of encoding alters the performance of the search.
In this thesis, the dynamics of four types of encodings used to evolve a set of integers are investigated: the previously researched bijective Binary and Gray code maps, as well as an introduced encoding scheme which includes... (More) - Genetic algorithms are complex constructs often used as heuristic search methods in contexts ranging from combinatorial optimisation to in silico evolution. They draw inspiration from the principles of biological evolution by utilizing the concepts of mutation, reproduction and selection in order to improve a population of solutions. The solutions are often represented as abstract data sequences, e.g. as binary strings, though it has been shown that the choice of encoding alters the performance of the search.
In this thesis, the dynamics of four types of encodings used to evolve a set of integers are investigated: the previously researched bijective Binary and Gray code maps, as well as an introduced encoding scheme which includes non-coding data, denominated the consensus map. Coding parts of the consensus sequences are signified by pre-determined start sequences, after which subsequent code is interpreted via either the Binary or the Gray code scheme.
The performance of the genetic algorithm is measured by the ability to solve four problems with different search spaces. The dynamics are also investigated by identifying the effects the encodings have on the distribution of cost effects due to point mutations, as well as by the ability to produce good solutions under a range of different mutation rates.
It is found that the bijective maps give rise to similar distributions of cost effects, but significantly different performances. The consensus encodings instead allow for higher robustness with respect to different mutation rates, as well as a robustness towards highly negative effects due to point mutations. It is also shown that having an encoding–decoding map which allows for both smaller and larger steps in phenotype-space is an important part of being able to produce good solutions in a range of cases. (Less) - Popular Abstract (Swedish)
- Genetiska algoritmer utgör en grupp sökalgoritmer som hämtar inspiration från evolutionära processer i biologiska sammanhang. Genom att låta populationer av enskilda datasekvenser, exempelvis strängar av ettor och nollor, representera olika lösningar till ett givet problem, och sedan successivt låta datasekvenserna utbyta information sinsemellan, samt att genom mutationer modifiera dem, är det möjligt att producera optimala eller väldigt goda lösningar till problemet i fråga; allt som principiellt behövs är ett sätt att tolka en datasekvens och ett sätt att utvärdera hur bra eller dålig den i sammanhanget är. Populationer kan också växa, reduceras eller förändras innehållsmässigt över tidssteg -- så kallade generationer -- under sökningen.... (More)
- Genetiska algoritmer utgör en grupp sökalgoritmer som hämtar inspiration från evolutionära processer i biologiska sammanhang. Genom att låta populationer av enskilda datasekvenser, exempelvis strängar av ettor och nollor, representera olika lösningar till ett givet problem, och sedan successivt låta datasekvenserna utbyta information sinsemellan, samt att genom mutationer modifiera dem, är det möjligt att producera optimala eller väldigt goda lösningar till problemet i fråga; allt som principiellt behövs är ett sätt att tolka en datasekvens och ett sätt att utvärdera hur bra eller dålig den i sammanhanget är. Populationer kan också växa, reduceras eller förändras innehållsmässigt över tidssteg -- så kallade generationer -- under sökningen. Vanligtvis ges populationsmedlemmar som utvärderats som bättre lösningar än andra större utrymme att föröka sig eller överleva, så att en partiskhet gentemot högpresterande datasekvenser förekommer, i enlighet med selektionstrycket inom just biologisk evolution.
På så vis skiljer sig genetiska algoritmer från många andra sökalgoritmer, som istället ofta använder sig av direkt matematiska metoder för att hitta bättre lösningar. Detta gör dem i synnerhet lämpliga för problem där det inte existerar någon direkt bakomliggande matematisk konstruktion, eller då det är ovanligt svårt att formulera den. De stora likheterna med biologisk evolution medför också att genetiska algoritmer kan användas som verktyg för att förstå just evolutionära processer, som ofta är oerhört komplexa och icke-intuitiva.
Det har dock visat sig att hur en lösning utläses från en datasekvens -- eller motsvarande, hur informationen i sekvensen är inkodad -- spelar roll för hur väl algoritmen presterar. Olika typer av informationsinkodningar medför också olika typer av evolutionär dynamik, vilket har konsekvenser för på vilket sätt populationen av lösningar successivt blir bättre.
För att ytterligare förstå på vilket sätt inkodningen är av vikt, och vilken sorts dynamik som medföljer en viss representation av information, undersöks i denna uppsats olika inkodningar och konsekvenserna som dessa får för mutationseffekter på datasekvenserna. Att i högre grad förstå denna komplexa dynamik kan i slutändan förhoppningsvis medföra en djupare förståelse för funktionerna hos genetiska strängar i framför allt datavetenskapliga sammanhang, men också hos deras motparter i naturen. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/8879332
- author
- Åhl, Henrik LU
- supervisor
-
- Carl Troein LU
- Adriaan Merlevede LU
- organization
- course
- FYTK02 20161
- year
- 2016
- type
- M2 - Bachelor Degree
- subject
- keywords
- Genetic algorithms, evolution, dynamics, encoding, encoding of information, genetic, string, binary, gray code, consensus, algorithm, optimisation, genotype, phenotype, genome, evolutionary algorithms, fitness, search space
- report number
- LU TP 16-29
- language
- English
- id
- 8879332
- date added to LUP
- 2016-06-14 14:02:18
- date last changed
- 2017-10-06 16:12:30
@misc{8879332,
abstract = {{Genetic algorithms are complex constructs often used as heuristic search methods in contexts ranging from combinatorial optimisation to in silico evolution. They draw inspiration from the principles of biological evolution by utilizing the concepts of mutation, reproduction and selection in order to improve a population of solutions. The solutions are often represented as abstract data sequences, e.g. as binary strings, though it has been shown that the choice of encoding alters the performance of the search.
In this thesis, the dynamics of four types of encodings used to evolve a set of integers are investigated: the previously researched bijective Binary and Gray code maps, as well as an introduced encoding scheme which includes non-coding data, denominated the consensus map. Coding parts of the consensus sequences are signified by pre-determined start sequences, after which subsequent code is interpreted via either the Binary or the Gray code scheme.
The performance of the genetic algorithm is measured by the ability to solve four problems with different search spaces. The dynamics are also investigated by identifying the effects the encodings have on the distribution of cost effects due to point mutations, as well as by the ability to produce good solutions under a range of different mutation rates.
It is found that the bijective maps give rise to similar distributions of cost effects, but significantly different performances. The consensus encodings instead allow for higher robustness with respect to different mutation rates, as well as a robustness towards highly negative effects due to point mutations. It is also shown that having an encoding–decoding map which allows for both smaller and larger steps in phenotype-space is an important part of being able to produce good solutions in a range of cases.}},
author = {{Åhl, Henrik}},
language = {{eng}},
note = {{Student Paper}},
title = {{Linking the dynamics of genetic algorithms to the encoding of information}},
year = {{2016}},
}