Genetic Algorithm

* terminology

chromosome: the answer of question, form of output of model

gene: basic component of chromosome

encoding: form of answer -> chromosome

decoding: chromosome -> form of answer

 

fitness: the score of how much each chromosome is fit to environment at that time point

-> fitness function: use to get score of each chromosome

 

Core concept of genetic algorithm - select chromosomes of high fitness, utilize crossover and mutation in multiple generation, and find chromosome with the highest fitness: solving optimization problem

 

Algorithm:

1) select parameters: N(number of chromosomes in one generation), pc( rate of crossover), pm(rate of mutation), M(number of generation)

2) determine the fitness function
for + equation, fitness=0 for unpossible chromosome

3) randomly generate chromosomes of first generation (initial state)

4) calculate fitness of first generation chromosomes

5) select a pair of chromosomes with high fitness -> apply rate of crossover, mutation to get a pair of next generation chromosome 
=> repeat 5) N times 

6) repeat 4),5) (M-1) times to get chromosomes of Mth generation and the optimal chromosome

Ex) first group -> 0000,0101,0111,1000,1001, fitness function -> f(x)=13x-x^2

 

* as M increases, the fitness along generation shows saturation

* pm < 0.01, to increase genetic diversity of chromosomes, get out of local optima and find global optima

 

Ex1) determining emergency surgery schedule

-> 10 surgeries, encoding: 011010001 - doing 2,3,5,9 surgery

maximum surgery time is 8h, f(x)=sum of emergency degrees of selected surgeries

=> N=200, pc=0.9, pm=0.005, M=300 

=> best solution - 0111100110, 2,3,4,5,8,9 surgeries

 

Genetc Algorithm: finding optima in given envirionment, with experimental iteration

Use this algorithm when the environment context is complex and the fitness function contains conditional statement with equations! We can also use GA in finding optimal hyperparameter set of DNN model or reward function in RL model