In Artificial Intelligence,
- Genetic Algorithm is one of the heuristic algorithms.
- They are used to solve optimization problems.
- They are inspired by Darwin’s Theory of Evolution.
- They are an intelligent exploitation of a random search.
- Although randomized, Genetic Algorithms are by no means random.
Genetic Algorithm works in the following steps-
- Randomly generate a set of possible solutions to a problem.
- Represent each solution as a fixed length character string.
Using a fitness function, test each possible solution against the problem to evaluate them.
- Keep the best solutions.
- Use best solutions to generate new possible solutions.
Repeat the previous two steps until-
- Either an acceptable solution is found
- Or until the algorithm has completed its iterations through a given number of cycles / generations.
The basic operators of Genetic Algorithm are-
1. Selection (Reproduction)-
- It is the first operator applied on the population.
- It selects the chromosomes from the population of parents to cross over and produce offspring.
- It is based on evolution theory of “Survival of the fittest” given by Darwin.
There are many techniques for reproduction or selection operator such as-
- Tournament selection
- Ranked position selection
- Steady state selection etc.
2. Cross Over-
- Population gets enriched with better individuals after reproduction phase.
- Then crossover operator is applied to the mating pool to create better strings.
- Crossover operator makes clones of good strings but does not create new ones.
- By recombining good individuals, the process is likely to create even better individuals.
- Mutation is a background operator.
- Mutation of a bit includes flipping it by changing 0 to 1 and vice-versa.
- After crossover, the mutation operator subjects the strings to mutation.
- It facilitates a sudden change in a gene within a chromosome.
- Thus, it allows the algorithm to see for the solution far away from the current ones.
- It guarantees that the search algorithm is not trapped on a local optimum.
- Its purpose is to prevent premature convergence and maintain diversity within the population.
The following flowchart represents how a genetic algorithm works-
Genetic Algorithms offer the following advantages-
- Genetic Algorithms are better than conventional AI.
- This is because they are more robust.
- They do not break easily unlike older AI systems.
- They do not break easily even in the presence of reasonable noise or if the inputs get change slightly.
While performing search in multi modal state-space or large state-space,
- Genetic algorithms has significant benefits over other typical search optimization techniques.
To gain better understanding about Genetic Algorithm & its Working,
Get more notes and other study material of Artificial Intelligence.
Watch video lectures by visiting our YouTube channel LearnVidFun.