Genetic algorithms (GA) were formally introduced in the United States in the 1970s by John Holland at University of Michigan. The continuing price/performance improvements of computational systems has made them attractive for some types of optimization. In particular, genetic algorithms work very well on mixed (continuous and discrete), combinatorial problems. They are less susceptible to getting 'stuck' at local optima than gradient search methods. But they tend to be computationally expensive.
To use a genetic algorithm, you must represent a solution to your problem as a genome (or chromosome). The genetic algorithm then creates a population of solutions and applies genetic operators such as mutation and crossover to evolve the solutions in order to find the best one(s).
Genetic Algorithms (GA) use principles of natural evolution. There are five important features of GA:
Encoding possible solutions of a problem are considered as individuals in a population. If the solutions can be divided into a series of small steps (building blocks), then these steps are represented by genes and a series of genes (a chromosome) will encode the whole solution. This way different solutions of a problem are represented in GA as chromosomes of individuals.
Fitness Function represents the main requirements of the desired solution of a problem (i.e. cheapest price, shortest route, most compact arrangement, etc). This function calculates and returns the fitness of an individual solution.
Selection operator defines the way individuals in the current population are selected for reproduction. There are many strategies for that (e.g. roulette–wheel, ranked, tournament selection, etc), but usually the individuals which are more fit are selected.
Crossover operator defines how chromosomes of parents are mixed in order to obtain genetic codes of their offspring (e.g. one–point, two–point, uniform crossover, etc). This operator implements the inheritance property (offspring inherit genes of their parents).
Mutation operator creates random changes in genetic codes of the offspring. This operator is needed to bring some random diversity into the genetic code.In some cases GA cannot find the optimal solution without mutation operator.
Problem :
Solution :
Given Information :
Four integer coefficient varying in between
0 to 9. [Correction on Question from three int to four].
a0,a1,a2,a3.
Function Y = f(x)
= a3x^3 + a2x^2 + a2x +a0
Y follows
x : 1 2 3
y : 7 6 2
Fitness of Y =
In Generation 0 : Chromosome set [
0 | 0 | 0 | 0 ]
Population Size is four
[ 0 | 0 | 0 | 0 ]
[ 0 | 0 | 0 | 0 ]
[ 0 | 0 | 0 | 0 ]
[ 0 | 0 | 0 | 0 ]
Finding Out Generation 1 :
Fitness :
y1 = Use the fitness formula of Y
= 0.002624 [As all value are same make highest value from first] [first highest]
y2 =
= 0.002624 [second highest]
y3 =
= 0.002624 [third highest]
y4 =
= 0.002624 [fourth highest]
Selection :
As it is said that 2nd highest and 2nd lowest value will be a pair and other two will be other pair. So after selection data will be like below :
y2 = 0.002624 [second highest] == [ 0 | 0 | 0 | 0 ]
y3 = 0.002624 [third highest] == [ 0 | 0 | 0 | 0 ]
y1 = 0.002624 [first highest] == [ 0 | 0 | 0 | 0 ]
y4 = 0.002624 [fourth highest] == [ 0 | 0 | 0 | 0 ]
Crossover :
In question it was predefined to swap the left most bit of chromosome . So , after swapping the left most bit of chromosome :
y2 == [ 0 | 0 | 0 | 0 ]
y3 == [ 0 | 0 | 0 | 0 ]
y1 == [ 0 | 0 | 0 | 0 ]
y4 == [ 0 | 0 | 0 | 0 ]
Mutation:
One bit is selected randomly. The selected bit is incremented or decremented with at most 2 . If the result of mutation make a bit larger than 9 , the value of the is set to 0 and if smaller than 0 set to 9. And no chromosome is permitted to apper more than in each generation.
y2 == [ 0 | 0 | 9 | 0 ] [ Select 3rd number bit and do -1 ]
y3 == [ 0 | 1 | 0 | 0 ] [ Select 2nd number bit and do +1 ]
y1 == [ 0 | 0 | 0 | 2 ] [ Select 4rd number bit and do +2 ]
y4 == [ 2 | 0 | 0 | 0 ] [ Select 1st number bit and do +2 ]
Generation 1 is :
[ 0 | 0 | 9 | 0 ]
[ 0 | 1 | 0 | 0 ]
[ 0 | 0 | 0 | 2 ]
[ 2 | 0 | 0 | 0 ]
And Generation 1 is the population for finding out Generation 2.
Finding Out Generation 2 :
Fitness :
y1 =
= 0.002688 [third highest]
y2 =
= 0.002700 [second highest]
y3 =
= 0.002610 [fourth highest]
y4 =
= 0.006134 [first highest]
Selection :
As it is said that 2nd highest and 2nd lowest value will be a pair and other two will be other pair. So after selection data will be like below :
y2 = 0.002700 [second highest] == [ 0 | 1 | 0 | 0 ]
y3 =
0.002688 [third highest] == [ 0 | 0 | 9 | 0 ]
y1 =
0.002610 [fourth highest] == [ 0 | 0 | 0 | 2 ]
y4 =
0.006134 [first highest] == [ 2 | 0 | 0 | 0 ]
Crossover :
In question it was predefined to swap the left most bit of chromosome . So , after swapping the left most bit of chromosome :
y2 == [ 0 | 1 | 0 | 0 ]
y3 == [ 0 | 0 | 9 | 0 ]
y1 == [ 2 | 0 | 0 | 2 ]
y4 == [ 0 | 0 | 0 | 0 ]
Mutation:
One bit is selected randomly. The selected bit is incremented or decremented with at most 2 . If the result of mutation make a bit larger than 9 , the value of the is set to 0 and if smaller than 0 set to 9.And no chromosome is permitted to apper more than in each generation.
y2 == [ 0 | 1 | 0 | 2 ] [ Select 4rd number bit and do +2 ]
y3 == [ 0 | 0 | 7 | 0 ] [ Select 3rd number bit and do -2 ]
y1 == [ 2 | 0 | 1 | 2 ] [ Select 3rd number bit and do +1 ]
y4 == [ 0 | 0 | 2 | 0 ] [ Select 3rd number bit and do +2 ]
Generation 2 is :
[ 0 | 1 | 0 | 2 ]
[ 0 | 0 | 7 | 0 ]
[ 2 | 0 | 1 | 2 ]
[ 0 | 0 | 2 | 0 ]
Continue to do same process depending on how many generation you have to find out.
