Tag: Genetic Algorithm Example Problems

Genetic Algorithm in AI | Operators | Working

Genetic Algorithm-

 

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.

 

Algorithm-

 

Genetic Algorithm works in the following steps-

 

Step-01:

 

  • Randomly generate a set of possible solutions to a problem.
  • Represent each solution as a fixed length character string.

 

Step-02:

 

Using a fitness function, test each possible solution against the problem to evaluate them.

 

Step-03:

 

  • Keep the best solutions.
  • Use best solutions to generate new possible solutions.

 

Step-04:

 

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.

 

Basic Operators-

 

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.

 

3. Mutation-

 

  • 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.

 

Flow Chart-

 

The following flowchart represents how a genetic algorithm works-

 

 

Advantages-

 

Genetic Algorithms offer the following advantages-

 

Point-01:

 

  • Genetic Algorithms are better than conventional AI.
  • This is because they are more robust.

 

Point-02:

 

  • 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.

 

Point-03:

 

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,

Watch this Video Lecture

 

Get more notes and other study material of Artificial Intelligence.

Watch video lectures by visiting our YouTube channel LearnVidFun.