Supervised Learning(Part-10)

 Genetic Algorithm


Genetic Algorithms(GAs) are adaptive heuristic search algorithms that belong to the larger part of evolutionary algorithms. Genetic algorithms are based on the ideas of natural selection and genetics. These are intelligent exploitation of random search provided with historical data to direct the search into the region of better performance in solution space. They are commonly used to generate high-quality solutions for optimization problems and search problems.

Genetic algorithms simulate the process of natural selection which means those species who can adapt to changes in their environment are able to survive and reproduce and go to next generation. In simple words, they simulate “survival of the fittest” among individual of consecutive generation for solving a problem. Each generation consist of a population of individuals and each individual represents a point in search space and possible solution. Each individual is represented as a string of character/integer/float/bits. This string is analogous to the Chromosome.

Foundation of Genetic Algorithms

Genetic algorithms are based on an analogy with genetic structure and behavior of chromosome of the population. Following is the foundation of GAs based on this analogy –
Individual in population compete for resources and mate
Those individuals who are successful (fittest) then mate to create more offspring than others
Genes from “fittest” parent propagate throughout the generation, that is sometimes parents create offspring which is better than either parent.
Thus each successive generation is more suited for their environment.

Search space

The population of individuals are maintained within search space. Each individual represent a solution in search space for given problem. Each individual is coded as a finite length vector (analogous to chromosome) of components. These variable components are analogous to Genes. Thus a chromosome (individual) is composed of several genes (variable components).




Fitness Score

A Fitness Score is given to each individual which shows the ability of an individual to “compete”. The individual having optimal fitness score (or near optimal) are sought.

The GAs maintains the population of n individuals (chromosome/solutions) along with their fitness scores.The individuals having better fitness scores are given more chance to reproduce than others. The individuals with better fitness scores are selected who mate and produce better offspring by combining chromosomes of parents. The population size is static so the room has to be created for new arrivals. So, some individuals die and get replaced by new arrivals eventually creating new generation when all the mating opportunity of the old population is exhausted. It is hoped that over successive generations better solutions will arrive while least fit die.

Each new generation has on average more “better genes” than the individual (solution) of previous generations. Thus each new generations have better “partial solutions” than previous generations. Once the offsprings produced having no significant difference than offspring produced by previous populations, the population is converged. The algorithm is said to be converged to a set of solutions for the problem.

Operators of Genetic Algorithms

Once the initial generation is created, the algorithm evolve the generation using following operators –
1) Selection Operator: The idea is to give preference to the individuals with good fitness scores and allow them to pass there genes to the successive generations.
2) Crossover Operator: This represents mating between individuals. Two individuals are selected using selection operator and crossover sites are chosen randomly. Then the genes at these crossover sites are exchanged thus creating a completely new individual (offspring). For example –





3) Mutation Operator: The key idea is to insert random genes in offspring to maintain the diversity in population to avoid the premature convergence. For example –





The whole algorithm can be summarized as –
1) Randomly initialize populations 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


Example problem and solution using Genetic Algorithms

Given a target string, the goal is to produce target string starting from a random string of the same length. In the following implementation, following analogies are made –
Characters A-Z, a-z, 0-9 and other special symbols are considered as genes
A string generated by these character is considered as chromosome/solution/Individual

Fitness score is the number of characters which differ from characters in target string at a particular index. So individual having lower fitness value is given more preference.



Why use Genetic Algorithms
  1. They are Robust
  2. Provide optimization over large space state.
  3. Unlike traditional AI, they do not break on slight change in input or presence of noise

Application of Genetic Algorithms
  1. Genetic algorithms have many applications, some of them are –
  2. Recurrent Neural Network
  3. Mutation testing
  4. Code breaking
  5. Filtering and signal processing
  6. Learning fuzzy rule base etc

Comments

Post a Comment

Popular posts from this blog

Supervised Learning(Part-5)

Image
  Decision Trees (Continued) Attribute Selection Measures If the dataset consists of N attributes then deciding which attribute to place at the root or at different levels of the tree as internal nodes is a complicated step. By just randomly selecting any node to be the root can’t solve the issue. If we follow a random approach, it may give us bad results with low accuracy. For solving this attribute selection problem, researchers worked and devised some solutions. They suggested using some criteria like : Entropy, Information gain, Gini index, Gain Ratio, Reduction in Variance Chi-Square These criteria will calculate values for every attribute. The values are sorted, and attributes are placed in the tree by following the order i.e, the attribute with a high value(in case of information gain) is placed at the root. While using Information Gain as a criterion, we assume attributes to be categorical, and for the Gini index, attributes are assumed to be continuous. Entropy Entropy is a me
Read more

Supervised Learning(Part-2)

Image
  Support Vector Machine A Support Vector Machine (SVM) is a discriminative classifier formally defined by a separating hyperplane. In other words, given labeled training data, the algorithm outputs an optimal hyperplane which categorizes new examples.  In two dimensional space this hyperplane is a line dividing a plane in two parts where in each class lay in either side. Suppose given plot of two label classes on graph as shown in image. You might have come up with something similar to following image (image B). It fairly separates the two classes. Any point that is left of line falls into black circle class and on right falls into blue square   In real world application, finding perfect class for millions of training data set takes lot of time. This is called regularization parameter.  Two terms regularization parameter and gamma are tuning parameters in SVM classifier. Varying those we can achieve considerable non linear classification line with more accuracy in reasonable amount of
Read more

Convolutional Neural Networks(Part-2)

Image
  Cross- Correlation Cross-correlation  is a  measure of similarity  of two series as a function of the displacement of one relative to the other. This is also known as a  sliding  dot product  or  sliding inner-product . It is commonly used for searching a long signal for a shorter, known feature. It has applications in  pattern recognition ,  single particle analysis ,  electron tomography ,  averaging ,  cryptanalysis , and  neurophysiology .  Steps followed in Cross- Correlation Take two matrices with same dimensions. Multiply them one by one, element by element (i.e , not the dot product, just the simple multiplication). Sum the elements together. VGG16 VGG16 is a convolutional neural network model proposed by K. Simonyan and A. Zisserman from the University of Oxford in the paper “Very Deep Convolutional Networks for Large-Scale Image Recognition”.  The model achieves 92.7% top-5 test accuracy in ImageNet,  which is a dataset of over 14 million images belonging to 1000 classes. A
Read more