tags: classical ai
In genetic algorithms we are having a cost function that we are trying to optimize, there also may be constraints that have to be satisfied.
“Between possible solutions”, because all offspring all solutions but not all of them are optimized solutions.
I don’t know what this has to do with the course but ok, also the dr is talking about evolution principle starting from 6:18, kinda sus.
Main idea
The main idea of genetic algorithms is optimization by simulating evolution of species through natural selection. Weak species die and good traits continue.
Some definitions
Fitness is like the cost function.
Working mechanism
When I don’t get the optimum solution from the current population, I select from them and do crossover and mutation, from my understanding crossover is like breeding to get the same traits as the parents and in mutation you try to get new traits.
There also should be also a way of termination if the optimum solution was not found, like maximum number of iterations.
Pseudo code of simple algorithm
How can chromosomes be represented
- Binary strings: strings of 1s and 0s, mostly used when the solution space consists of boolean decisions yes or no. Can be used when representing numbers, as the string can be converted to a number.
- Array of integers, used for encoding multiple distances.
- Array of letters
- Can be represented as real values, a good example is neural network weights
- Permutations representation, the same values are present but their position changes.
Parent Selection
Roulette wheel selection
There is wheel that looks like a roulette wheel, each individual gets a slice of the wheel but better individuals get a larger slice, then an individual is selected randomly to crossover.
Selection is done by generating a random number maybe between 0 and 1 and using that to represent which individual to select. The random generator represents the selection point in roulette.
Rank selection
Can work with negative fitness values, also works when fitness differs very much or differs very little which does not lead to early convergence. Each chromosome is given a rank based on their fitness value in descending order if I want the higher fitness and then roulette wheel is played.
To calculate the percentage, the rank of every chromosome or individual is divided by the total tum of ranks. for example if chromosome 1 has rank 5 and there is 6 chromosomes, then percentage is
Elitism
Copy the best chromosome directly to the next generation.
K-way tournament selection
Select K individuals randomly from the generation, and then select the best one of them to become a parent. Do it again to select another parent and go for crossover. Also works with negative fitness values.
Crossover
One-point crossover
Multi-point crossover
Select more points that one-point
Crossover in problems that have constraints, like no value can occur more than once, is done differently. When crossover is done, we iterate over the elements of the original individual and we only take the values that will appear once.
Mutation
Bit-flip mutation
in binary strings mutation can happen by inverting a bit in the chromosome binary string. We can also select two positions in the chromosome and interchange their positions, this is common in permutation based encoding like the sales-man problem and is known as swap mutation.
Random resetting
This is done in integer representation, a random gene is selected and set to a random permissible value.
NOTE: Mutation percentage is the probability that a mutation happens to a certain offspring. Understand this part from section. Also we have crossover percentage, a percentage that a crossover will happen between couples. Mutation probability is applied to genes while crossover is applied to couples.
Terminating Condition
Elimination of infeasible candidates
Benefits of GA
