Transcript Slide 1

Effect of Modified Permutation Encoding Mutation in
Genetic Algorithm
Sandeep Bhowmik
Archana Jha
Sukriti Sinha
Department of Computer Science & Engineering,
Hooghly Engineering & Technology College, Hooghly, India
ICII 2012, 01-02 December, Kolkata, India
Effect of Modified Permutation Encoding Mutation in Genetic Algorithm
 Introduction
• Genetic Algorithm is one important Artificial Intelligence
procedure.
• Based on the theory of natural selection and evolution.
• Application of GA is being examined in different field of Science
and Technology.
• Search for approximate solutions in optimization problems where
solution space is huge.
• We investigate the Mutation process of GA.
ICII 2012, 01-02 December, Kolkata, India
Effect of Modified Permutation Encoding Mutation in Genetic Algorithm
 Introduction
• Search is for a chromosome that will disturb the arrangement of
the elements (genes) the most.
• A chromosome of size N has been considered.
• Each element of the chromosome is an integer indicating the new
position of the current genes in the chromosome.
ICII 2012, 01-02 December, Kolkata, India
Effect of Modified Permutation Encoding Mutation in Genetic Algorithm
 Introduction
• The fitness function of the chromosomes is calculated on the basis
of the sum of total variation (length of displacement) of each
gene.
• The objective is to maximize the fitness value so that when the
chromosome is applied it can shuffle the arrangement of
elements.
ICII 2012, 01-02 December, Kolkata, India
Effect of Modified Permutation Encoding Mutation in Genetic Algorithm
• In the permutation encoding mutation two frame of genes (having
one or more chromosomes) will swap their place.
• We consider a frame of length F (>1).
• So two randomly generated positions at least has to be at a
distance of F.
ICII 2012, 01-02 December, Kolkata, India
Effect of Modified Permutation Encoding Mutation in Genetic Algorithm
 Our Goal
• Search for a good pattern.
• To analyze the effect of the size of frame in mutation.
• Performance has been analyses statistically in terms of Fitness
value of the chromosomes.
ICII 2012, 01-02 December, Kolkata, India
Effect of Modified Permutation Encoding Mutation in Genetic Algorithm
 Fitness function
•
•
•
•
The fitness function evaluates the quality of the solutions.
A displacement of an element (gene) in a string (chromosome) is the length it
has been shifted from its original position.
The fitness is the sum of displacement of all the genes in a chromosome.
Selection allows chromosome with higher fitness to appear with higher
probability in the next generation.
Initial index of ‘A’ is 2
New index of ‘A’ is 14
Displacement of ‘A’ is (14-2) or 12
ICII 2012, 01-02 December, Kolkata, India
Effect of Modified Permutation Encoding Mutation in Genetic Algorithm
 Key Selection
1. Randomly generate initial population of 100 chromosomes among N!
options
2. Repeat until increase in fitness value stops for a sufficient no of
generations
3. Repeat for 100 times (to populate new generation of 100 offspring)
o Randomly selected 10 individuals from the current population
o Calculate the fitness of each selected individual
o Select the chromosome with the best fitness value
o Breed new generation through mutation and give birth to new
offspring
o Select the better one between these two for the next generation
4. Select the best chromosome in terms of fitness from the final
population. This selected chromosome is the ‘key’ in our encryption
process.
ICII 2012, 01-02 December, Kolkata, India
Effect of Modified Permutation Encoding Mutation in Genetic Algorithm
Frame sizes used in test cases test cases for different chromosomes.
ICII 2012, 01-02 December, Kolkata, India
Effect of Modified Permutation Encoding Mutation in Genetic Algorithm
Minimum and maximum fitness values achieved using different sizes of frame
in mutation process with chromosomes of size 16 bytes.
ICII 2012, 01-02 December, Kolkata, India
Effect of Modified Permutation Encoding Mutation in Genetic Algorithm
 Relationship between Fitness values and Frame Size of chromosome.
ICII 2012, 01-02 December, Kolkata, India
Effect of Modified Permutation Encoding Mutation in Genetic Algorithm
Minimum and maximum fitness values achieved using different sizes of frame
in mutation process with chromosomes of size 24 bytes.
ICII 2012, 01-02 December, Kolkata, India
Effect of Modified Permutation Encoding Mutation in Genetic Algorithm
 Relationship between Fitness values and Frame Size of chromosome.
ICII 2012, 01-02 December, Kolkata, India
Effect of Modified Permutation Encoding Mutation in Genetic Algorithm
Minimum and maximum fitness values achieved using different sizes of frame
in mutation process with chromosomes of size 32 bytes.
ICII 2012, 01-02 December, Kolkata, India
Effect of Modified Permutation Encoding Mutation in Genetic Algorithm
 Relationship between Fitness values and Frame Size of chromosome.
ICII 2012, 01-02 December, Kolkata, India
Effect of Modified Permutation Encoding Mutation in Genetic Algorithm
 Conclusion
• There is not much deviation in the fitness values of the generated
chromosomes for frames of length up to one third the length of
the chromosome.
• There is a sharp decrease in fitness afterwards.
• Permutation encoding mutation when performed by swapping
two individual genes (ie. single gene mutation), gives the
optimum fitness of the chromosomes.
ICII 2012, 01-02 December, Kolkata, India
Effect of Modified Permutation Encoding Mutation in Genetic Algorithm
 References
•
•
•
•
•
•
•
A. Noda, Y. Hirai, Y. Kodama, W. Kretzschmar, K. Hamasaki, Y. Kusunoki, H. Mitani, H. Cullings, N.
Nakamura, “Easy detection of GFP-positive mutants following forward mutations at specific gene locus in
cultured human cells”, Mutation Research/Genetic Toxicology and Environmental Mutagenesis, Vol. 721,
Issue 1, pp. 1-118, 2011.
I. De Falco, A. Della Cioppa, E. Tarantino, “Mutation-based genetic algorithm: performance evaluation”,
Applied Soft Computing, Vol. 1, Issue 4, pp. 285-299, Elsevier, 2002.
A. Eiben, Z. Michalewicz, M. Schoenauer, J. Smith, “Parameter control in evolutionary algorithms”,
Studies in Computational Intelligence, Vol. 54, pp. 19-46, Springer, 2007.
R.C.P. Silva, R. A. Lopes, F. G. Guimarães, “Self-Adaptive Mutation in the Differential Evolution”,
Genetic and Evolutionary Computation, pp. 1939-1946, ACM, 2011.
S. Bhowmik, S. Acharyya, “Image Cryptography: The Genetic Algorithm Approach”, in Computer
Science & Automation Engineering, Vol. 2, pp. 223-227, IEEE Press, 2011.
John H Holland, “Adaptation in Natural and Artificial Systems”, 2nd edition, MIT Press, 1992.
Ye Li, Yan Chen, “A Genetic Algorithm for Job-Shop Scheduling”, Journal of Software, Vol. 5, No 3, pp.
269-274, 2010.
ICII 2012, 01-02 December, Kolkata, India