Application1
Genetic Algorithms
1.Introduction
Today, GAs are used to resolve complicated optimization problems, like, timetabling, job shop scheduling, games playing.
2. A Simple Genetic Algorithm
An algorithm is a series of steps for solving a problem. A genetic algorithm is a problem solving method that uses genetics as its model of problem solving. It’s a search technique to find approximate solutions to optimization and search problems.
Basically, an optimization problem looks really simple.
GA handles a population of possible solutions.
3.Comparison of Genetic Algorithm with Other
Optimization Techniques
Genetic algorithm differs from conventional optimization techniques in many ways:
4.Applications of Genetic Algorithm
A few applications of GA are as follows:
Individuals
An individual is a single solution. A chromosome is subdivided into genes. A gene is the GA’s representation of a single factor for a control factor.
Fitness
The fitness of an individual in a genetic algorithm is the value of an objective function . For calculating fitness, the chromosome has to be first decoded and the objective function has to be evaluated.
5.1 Populations
A population is a collection of individuals
5.2.Encoding
Encoding is a process of representing individual genes. The process can be performed using bits, numbers, trees, arrays, lists or any other objects. The encoding depends mainly on solving the problem. For example, one can encode directly real or integer numbers.
5.2.1 Binary Encoding
5..2.2 Octal Encoding
5.2.3 Hexadecimal Encoding
5.2.4 Permutation Encoding (Real Number Coding)
5.2.5 Value Encoding
Breeding
The breeding process is the heart of the genetic algorithm. It is in this process, the search process creates new and hopefully fitter individuals. The breeding cycle consists of three steps:
a. Selecting parents.
b. Crossing the parents to create new individuals (offspring or children).
c. Replacing old individuals in the population with the new ones.
5.3 Selection
Selection is the process of choosing two parents from the population for crossing. After deciding on an encoding, the next step is to decide how to perform selection i.e
5.3 .1 Roulette Wheel Selection
5.3 .2 Random Selection
5.3 .3 Rank Selection
5.3 .4 Tournament Selection
5.4 Crossover (Recombination)
Crossover is the process of taking two parent solutions and producing from them a child. After the selection (reproduction) process, the population is enriched with better individuals. Reproduction makes clones of good strings but does not create
new ones. Crossover operator is applied to the mating pool with the hope that it creates a better offspring. Crossover is a recombination operator that proceeds in three steps:
5.4 .1 Single Point Crossover
5.4.2 Two Point Crossover
5.4.3 Multi-Point Crossover (N-Point crossover)
5.4.4 Uniform Crossover
5.4.5 Three Parent Crossover
5.4.6 Precedence Preservative Crossover (PPX)
5.4.7 Ordered Crossover
5.4.8 PartiallyMatched Crossover (PMX)
5.6.Mutation
After crossover, the strings are subjected to mutation. Mutation prevents the algorithm to be trapped in a local minimum. Mutation plays the role of recovering the lost genetic materials as well as for randomly disturbing genetic information. Mutation of a bit involves flipping a bit, changing 0 to 1 and vice-versa.
5.7 Replacement
Replacement is the last stage of any breeding cycle. Two parents are drawn from a fixed size population, they breed two children, but not all four can return to the population, so two must be replaced i.e., once off springs are produced, a method must determine which of the current members of the population, if any, should be replaced by the new solutions.
5.7.1 Random Replacement
5.7.2 Weak Parent Replacement
5.7.3 Both Parents
5.8 Search Termination (Convergence Criteria)
In short, the various stopping condition are listed as follows:
Example:Maximizing a Function
Consider the problem of maximizing the function, f(x) = x2
where x is permitted to vary between 0 to 31. The steps involved in solving this problem are as follows:
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .