Lecture1
Genetic Algorithms
1.Introduction
In 1975, Holland developed this idea in his book “Adaptation in natural and artificial systems”. He described how to apply the principles of natural evolution to optimization problems and built the first Genetic Algorithms. Holland’s theory has been further developed and now Genetic Algorithms (GAs) stand up as a powerful tool for solving search and optimization problems. Genetic algorithms are based on the principle of genetics and evolution.The power of mathematics lies in technology transfer: there exist certain models and methods, which describe many different phenomena and solve wide variety of problems. GAs are an example of mathematical technology transfer: by simulating evolution one can solve optimization problems from a variety of sources. 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.
The gene pool should be as large as possible so that any solution of the search space can be engendered. Generally, the initial population is generated randomly. Then, the genetic algorithm loops over an iteration process to make the population evolve.
Each iteration consists of the following steps:
• SELECTION: The first step consists in selecting individuals for
reproduction. This selection is done randomly with a probability
depending on the relative fitness of the individuals so that best
ones are often chosen for reproduction than poor ones.
• REPRODUCTION: In the second step, offspring are bred by the
selected individuals. For generating new chromosomes, the
algorithm can use both recombination and mutation.
• EVALUATION: Then the fitness of the new chromosomes is
evaluated.
• REPLACEMENT: During the last step, individuals from the old
population are killed and replaced by the new ones.
The algorithm is stopped when the population converges toward
the optimal solution.
The basic genetic algorithm is as follows:
• [start] Genetic random population of n chromosomes (suitable
solutions for the problem)
• [Fitness] Evaluate the fitness f(x) of each chromosome x in the
population
• New population] Create a new population by repeating following
steps until the New population is complete
- [selection] select two parent chromosomes from a population
according to their fitness ( the better fitness, the bigger
chance to get selected).
- [crossover] With a crossover probability, cross over the parents to
form new offspring ( children). If no crossover was performed,
offspring is the exact copy of parents.
- [Mutation] With a mutation probability, mutate new offspring at
each locus(position in chromosome)
- [Accepting] Place new offspring in the new population.
• [Replace] Use new generated population for a further sum of the
algorithm.
• [Test] If the end condition is satisfied, stop, and return the best
solution in current population.
- • [Loop] Go to step2 for fitness evaluation.
Based on the foregoing discussion, the important criteria for GA approach can be formulated as given below:
- Completeness: Any solution should have its encoding
- Non redundancy: Codes and solutions should correspond one to
one
- Soundness: Any code (produced by genetic operators) should
have its corresponding solution
-Characteristic perseverance: Offspring should inherit useful
characteristics from parents.
3.Comparison of Genetic Algorithm with Other
Optimization Techniques
4.Applications of Genetic Algorithm
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .