ga short intro

September 23, 2023

introduction

Genetic algorithm or GA is an algorithm for optimization, which can avoid to land on local optimum in while searching global otimum ( Binus, 2018 ).
This heuristic search is inspired by Charles Darwin’s theory of natural evolution, which reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation ( Mallawaarachchi, 2017 ).
It is intelligent exploitation of random search provided with historical data to direct the search into the region of better performance in solution space, where it commonly used to generate high-quality solutions for optimization problems and seach problems ( overide, 2023 ).

applications

One of the major applicaton of GA is the travelling salesman problem and this algorithm is also widely used in the field of robotics ( Pedamkar, 2023 ).
At least there are 10 real-life applications of GA, which are traveling salesman problem, vehicle routing problem, financial markets, manufacturing system, mechanical engineering design, data clustering and mining, image processing, neural networks, wireless sensor networks, and medical science ( Verma, 2022 )
There is also a list of applications of GA categorized according to the fields, e.g. i) natural sciences, mathematics, and computer science, ii) earth sciences, finance and economics, iii) social sciences, iv) industry, management, and engineering, v) biological science and bioinformatics, vi) general applications, vii) physics, and viii) others ( Wikipedia, 2023 ).

terminology

There are some terms used in GA ( Muthee, 2021 ), which are
- Population, which is a subset of all probable solutions that can solve the given problem,
- Chromosome, which is one of the solution in the population,
- Gene, which is an element in a chromosome,
- Allele, which is the value give to a gene in a specific chromosome,
- Fitness function, that maps the solution to its suitability in solving the problem,
- Genetic operators, which are used to change the genetic composition of next generation from information of previous generation.
Other term is individual, which is encoded in a chromosome ( Ray, 2016 ).

schematic

Hierarchical relations between allele, gene, chromosome, and population can be illustrated as follow

Notice that in this case allele has only two possible values, which are 0 and 1.

chromosome

Each chromosome has two representation ( Gad, 2018 )
- genotype, which is the set of genes representing the chromosome,
- fenotype, which is the actual physical representation of the chromosome.
Solution in phenotype space or actual solution space is encoded to solution in genotype space or computational space, and it is decoded back in opposite direction ( Tutorials Point, 2023 ).

flowchart subgraph I["Individual"] direction LR G --"decoding"---> F F --"encoding"---> G F(["Phenotype space
(actual solution space)

a solution"]) G(["Genotype space
(computational space)

11001010"]) end style I rx:50, ry:50;

flowchart

How GA works can be simplified as follow ( Sharma, 2022 )

flowchart TB B --> PI --> FC --> o1a o1b --> SC SC --"N"--> S --> o2a SC --"Y"--> SR --> E o2b --> GO --> o3a C -.- M o3b --> FC FC["Fitness
calculation"] SC{"Stop
criteria"} B(["Begin"]) E(["End"]) o1a(("1")) o1b(("1")) o2a(("2")) o2b(("2")) o3a(("3")) o3b(("3")) S["Selection"] subgraph PI["Population initialization"] direction TB FS --"encoding"--> GS FS(["Phenotype space
e.g. 1st route,
2nd route, .."]) GS(["Genotype space
e.g. 1928564370",
1234056789, ..]) end subgraph GO["Genetic operations"] direction LR C["Crossover"] M["Mutation"] end subgraph SR["Show result"] direction TB GS2 --"decoding"--> FS2 FS2(["Phenotype space
e.g. best route"]) GS2(["Genotype space
e.g. 6438570192".]) end style PI rx:20, ry:20; style GO rx:20, ry:20; style SR rx:20, ry:20;

Operators are used in encoding-decoding, selection, crossover and mutation.

operators

There are four operator categories used in GA during the search process, which are ( Katoch et al., 2021 )

Encoding: binary, octal, hexadecimal, permutation, value, tree;
Selection: roulette wheel, rank, tournament, Boltzmann, stochastic unversal;
Crossover: single point, k-point, uniform, partially mapped, order, precedence preserving, shuffle, reduced surrogate, cycle;
Mutation: displacement, inversion, scramble, bit flipping, reversing.

encoding

There are some encoding techniques in Genetic Algorithm, e.g. binary, value, and order ( Garg, 2021 ).
There encoding schemes in Genetic Algorithm accompanied with the analysis ( Kumar, 2013 ).
Different problem may require different encoding ( Samanta, 2016 ).
A proper genetic encoding will enable an efficient computational implementation ( Gaggero, 2020 ).

codes

Optimization of sum of square $x$ using roulette selection, single point crossover, and mutation is available in Python ( Shirol & Iriondo, 2021 ).
Modification of string to match target string using crossover and mutation is available in C++ and Python ( overide, 2023 ).
Maximazing array to make all elements one and a continues function is available in Python ( Brownlee, 2021 )
Implementation Traveling salesman problem is available in JavaScript ( Doglio, 2023 ).
Application of GA for particles driving themselves around a track is available in JavaScript ( Garrigan, 2021 ).
GA for population whose target is to type a certain string is available in JavaScript ( This Dot, 2019 ).