GENETIC ALGORITHM
INTRODUCTION
A genetic algorithm may be a heuristic search method utilized in AI and computing. It’s used for locating optimized solutions to look problems based on the theory of natural selection and evolutionary biology. Genetic algorithms are excellent for exploring through large and complicated data sets. they’re considered capable of finding reasonable solutions to complex issues as they’re highly capable of solving unconstrained and constrained optimization issues.
It is encouraged by Charles Darwin’s theory of natural evolution. This algorithm reflects the method of natural selection where the fittest individuals are selected for replica so as to supply offspring of following generation.
Genetic algorithms are used to produce high-quality solutions to optimization and search problems by tally on biologically inspired operators like mutation, crossover and selection.
Basic terminologies: Before further discussion on Genetic Algorithms, it is essential to be familiar with some basic terminology.
· Population: it’s a subset of all the possible (encoded) solutions to the given problem. The population for a GA is analogous to the population for human beings except that rather than human beings; we’ve Candidate Solutions representing human beings.
· Chromosomes: A chromosome is one such solution to the given problem.
· Gene: one element position of a chromosome is a gene.
· Allele: it’s the worth a gene takes for a specific chromosome.
· Genotype: Genotype is that the population within the computation space. in the computation space, the solutions are represented in an exceedingly way which may be easily understood and manipulated employing a computer system .
· Phenotype: Phenotype is that the population within the world solution space during which solutions is represented during a way they’re represented in world situations.
· Fitness Function: A fitness function simply defined may be a function which takes the answer as input and produces the suitability of the answer as the output. In some cases, the fitness function and therefore the objective function could also be an equivalent, while in others it’d vary supported the matter.
· Genetic Operators: These alter the genetic composition of the offspring. These include crossover, mutation, selection, etc.
HOW IS IT USED IN ARTIFICIAL INTELLIGENCE?
Yes, Genetic algorithms are a part of AI.
· An ability that’s commonly attributed to intelligence is problem-solving.
· Improving the training from its previous experiences
· Artificial intelligence is often defined as “replicating intelligence, or parts of it, a minimum of in appearance, inside a computer”.
· Genetic algorithms are computational problem-solving tools (generation over generation, they evolve and that they learn).
WORKING
Genetic Algorithm works on a population consisting of some solutions where the population size (pop-size) is that the number of solutions. Each solution is termed individual. Each individual solution features a chromosome. The chromosome is represented as a collection of parameters (features) that defines the individual. Each chromosome features a set of genes. Each gene is represented as a string of 0s and 1s. Also, each individual features a fitness value. To pick the most effective individuals, a fitness function is employed. The results of the fitness function is that the fitness value representing the standard of the answer. The upper the fitness value the upper the standard the answer.
ALGORITHM
A genetic algorithm differs from a optimization, derivative-based, classical algorithm in two ways:
· A genetic algorithm generates a population of points in each iteration, whereas a classical algorithm generates one point at each iteration.
· A genetic algorithm selects succeeding population by computation using random number generators, whereas a classical algorithm selects subsequent point by deterministic computation.
1) Randomly initialize population’s p
2) Determine fitness of population
3) Until convergence repeat:
a) Select parents from population
b) Crossover and generate new population
c) Perform mutation on new population
d) Calculate fitness for new population
FLOW OF ALGORITHM
PROCESS
1. Initialization
Randomly generate a population with multiple chromosomes. Gene is that the smallest unit and may be mentioned as a group of characteristics (variables). We aim to hitch the Genes to get the Chromosomes (solution). The chromosome itself represents one candidate solution abstractly. The generation of Chromosome is user-defined (combining the numbers between 0 and 5 or combination of 0s or 1s i.e. binary numbers).
2. Defining the fit function
Now we’d like to define the evaluation criteria for best chromosomes (solution). Fitness function assigns the fitness score to each chromosome, which represents the goodness of the answer. Let’s say the fitness function is that the sum of all the genes. Hence, the chromosome with the utmost sum is that the fittest.
3. Selection
Individuals with good fitness scores are preferred and permitted to pass their genes to the successive generations. Here are a number of the methods of parent selection-
1. Roulette Wheel Selection
2. Rank Selection
3. Steady State Selection
4. Tournament Selection
5. Elitism Selection
4. Crossover
This represents mating between individuals. Selection operator is used to select the two individuals and crossover sites are chosen randomly. Then the genes at these crossover sites are exchanged thus creating a totally new individual (offspring).
1. Single point crossover.
2. k-point crossover (k ≥ 1)
3. Uniform crossover.
5. Mutation
The key idea is to insert random genes in offspring to take care of the range in population to avoid the premature convergence.
These steps are repeated until the termination criterion is met.
When to apply Genetic Algorithm:
· There are multiple local optima
· The objective function isn’t smooth (so derivative methods can’t be applied)
· Number of parameters is extremely large
· Objective function is noisy or stochastic
ADVANTAGES OF GENETIC ALGORITHM
· Concept is straightforward to know
· Modular, break away application
· Answer gets better with time
· Inherently parallel; easily distributed
· Genetic algorithms work on the encoded version of potential solutions’ parameters, rather the parameters themselves, i.e. chromosomes.
· Genetic algorithms use fitness score, which is obtained from fitness functions, without other derivative or auxiliary information
DISADVANTAGES
· Genetic Algorithms aren’t best fitted to simpler problems where the derivative information is quickly available.
· Fitness value gets evaluated on a group of generations, and this will be an upscale process for a particular number of problems using Genetic Algorithms.
· If a Genetic algorithm isn’t put to use within the best manner, it’s going to not converge to an optimal solution.
APPLICATIONS
· Optimization: it is used to maximize or minimize a given objective function under given set of constraints.
· Neural networks: Genetic algorithms are also used to train neural networks, particularly recurrent neural networks.
· Parallelization: Genetic algorithms also have very good parallel capabilities, and prove to be very effective means in solving certain problems, and also provide a good area for research.
· Machine Learning: Genetics based machine learning (GBML) is a niche area in machine learning.
· DNA Analysis: Genetic algorithms have been used to determine the structure of DNA using spectrometric data about the sample.
