Genetic algorithms
Metodický koncept k efektivní podpoře klíčových odborných kompetencí s využitím cizího jazyka
ATCZ62 - CLIL jako výuková strategie na vysoké škole
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Genetic algorithm
•The heuristic process belongs to evolutionary algorithms
•It belongs to artificial intelligence
•Applying knowledge from evolutionary biology seeks to solve complex problems for which there is no
exact algorithm
•It mimics the techniques of evolutionary biology
•Heredity
•Mutation
•Natural selection
•Crossover

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Genetic algorithm
•Principle:
1.Initialization – generate 0th generation
2.Begining of cycle– Choose (randomly) several individuals from whole population based on fitness
score
3.Make new generation
• crossover - „swap“ parts of few individuals
• mutation – randomly change some genes
• reproduction – copy individuals without changes
4.Calculate fitness of new generation
5.Termination- Repeat from point 2 until the termination condition is reached

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Genetic algorithm
•Terminology:
•Phenotype – individual
•Genotype, genome, chromosome - representation of phenotype
•Chromosome - divided into individual linearly-ordered genes (i-th chromosome gene of the same type
represents the same characteristic)
•Alleles - Various gene values
•Fitness value - ranging from 0-1, expresses the quality of each individual
•Individuals can be encoded (genetically described) in different ways
•By way of description, it may be important for the success or failure of solving a particular task

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Genetic algorithm
•Example:
•Oth generation (fitness value = # of „1“):
1.0100011011 f=0,5
2.0101000100 f=0,3
3.1010110000 f=0,4
4.1110111000 f=0,6

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Genetic algorithm

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Genetic algorithm
•Crossover
•Parents exchange parts of theirs code
•Simplest method– one point crossover
•Place for cutting – randomly chosen
•X: 010001|1011
•Y: 111011|1000
•P: 0100011000 f=0,3
•Q: 111011 1011 f=0,8
•Crossover at more points, more than two parents

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Genetic algorithm
•Mutation
•Random change of the random gene in an individual
•Very low probability
1.0100011011 ⇒ 0101011011
2.0101000100 ⇒  0101100100
3.1010110000 ⇒  1010110100
4.1110111000 ⇒ 1010111000
•It is possible to reach properties which are not in the original generation

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Genetic algorithm
•Termination
•This generational process is repeated until a termination condition has been reached. Common
terminating conditions are:
•A solution is found that satisfies minimum criteria
•Fixed number of generations reached
•Allocated budget (computation time/money) reached
•The highest ranking solution's fitness is reaching or has reached a plateau such that successive
iterations no longer produce better results
•Manual inspection
•Combinations of the above