SHORT
PAPER: THE APPLICATIONS OF GENETIC ALGORITHMS
Abdul Wahab
Faculty of Computer
Science
Griffith College
South Circular Road
Dublin 8, Co. Dublin, Ireland
1 Abstract
A Genetic Algorithm (GA) is a search technique
used in computing to find exact or approximate solutions to optimization and
search problems [5]. Genetic Algorithm is a method that makes solutions
to difficult problems on the base of laws of natural selection. This method is
described in detail and the applications of this method are also discussed in this
short paper.
2 Introduction
GA is an abstraction from Darwin’s evolution theory
[Darwin, 1859].
In nature, organisms develop by natural selection and the recombination and
mutation of genes in mating. And Genetic Algorithm follows this basic concept
[3]. As GA is base on the law of natural selection. Here I have compared these
both concepts.
Natural Selection:
• A population of
organisms undergoes natural selection
• Natural selection
identifies which individuals among those organisms are fit and which are unfit.
• The fit grow and
developed vigorously and have more offspring than the unfit
• The offspring are
statistically fit because they inherit more genes from the fit.
• The population
evolve to be more fit.
Now if we look at the Genetic Algorithm:
• A number of
candidate designs are evaluated by objective function.
• Objective function
first evaluates and then identifies which designs are good and which are bad.
• Good designs thrive
and passed on most of their information to the newly generated designs.
• The design pool
evolves to be better.
• These newly
generated designs are statistically good because they inherit more of the
information from good designs [1].
If we look at
nowadays world the Optimization (choosing the best element from some set of
available alternatives [5]) design is
everywhere. We optimize materials composition for better properties, also we
optimize manufacturing processes for lower cost and we optimize network
architecture for higher communication rate [1]. Genetic Algorithms have been
used to optimize a wide variety of problems.
3 How Genetic Algorithms Work
For
solving a given problem, a GA has an input which can be encoded in different
ways, different possible solutions to this problem which are usually randomly
created and the fitness function which allows the different possible solutions
to be evaluated. GA takes these solutions and evaluates each one, take only
those solutions which seem to play some role in the problem solution and delete
those which don’t play any role [9].
The
procedure of GA I have explained by a flowchart taken from Yao Zhou thesis [1].
This process is
categorized into three.
Representation:
3.1
Encoding Design
Before solving a
problem by using a genetic algorithm, a way must be found of encoding
any potential solution to the problem. This could be either as a string of real
numbers or as a binary bit string [1, 6].
x = (010…110)
3.2
Define Fitness
Function
Each has to be tested and assign fitness score to each
chromosome according to how much good they are solving the problem [1, 6].
Initialization:
3.3
Initialize Population
Calculate the expected number of copies of each
chromosome, which will be presented in the mating pool [1,6].
P(x) = {X1, X2… Xn}
Iteration:
3.4
Evaluate Design
The population
consists of chromosomes that best satisfy the problem conditions and will hence
form the basis of the next generation [1,6].
F(X) =?
3.5
Selection
Select two members from the
current population. The chance of selection of chromosomes is proportional to
the chromosomes fitness [1, 6].
Adjust shares for x
based on F(x)
(More shares for good
chromosomes)
3.6
Crossover
A gene is selected at random
point of the chromosome and crossover is performed at that point of chromosomes
by swapping all the genes after that point. Dependent on the crossover
rate crossover the bits at random point from each chosen chromosome.
This is simply the chance that two chromosomes will swap their bits. A good
value for this is around 0.7. [1, 6].
3.7
Mutation
Step through the chosen
chromosomes bits and flip dependent on the mutation rate where mutation rate is the chance that a bit within a
chromosome will be flipped (0 becomes 1, 1 becomes 0). This is usually a very
low value for binary encoded genes, say 0.001 [1, 6].
4 Applications
Traditional methods of search
and optimization are too slow in finding a solution in a very complex search
space, even implemented in supercomputers. Genetic Algorithm is a robust search
method requiring little information to search effectively in a large or
poorly-understood search space [8].
Genetic
algorithms can be applied to a wide range of problems which are scheduling,
strategy planning etc [2]. There are many numbers of applications of GA and
this number is growing day by day.
4.1
Scheduling
Scheduling
can be defined as a problem of finding the optimal sequence to execute a finite
set of operations such that a
certain set of constraints are not violated. A scheduler maximizes the
utilization of individuals or machinery and minimizes the time required for the
completion of entire process. When more than one operation are assigned for an
individual or machine at a given time then conflicts can occur or conflicts can
also arises when the schedule utilizes resources more than the available. GA
implement solution such kind of problems in scheduling.
Descriptions of GA applications in the domain of
scheduling can be found in a number of papers.
Job Shop Scheduling with
Genetic Algorithms by Lawrence Davis, describes the scheduling of work in a job
shop composed of a number of workstations. A simple GA and encoding scheme is
outlined that optimizes the scheduling of jobs at the stations to minimize cost
and maximize profit [4, 10].
4.2 Economics and Finance
Finance is a is a broad area. The possible problems
in this domain are applicable to genetic algorithms are, Economic Forecasting,
Investment Analysis and Credit Approval [4].
A Genetic System for Learning Models of Consumer Choice, by David P.
Greene and Stephen Smith in Genetic Algorithms and their Applications explain
how a GA can be used to discover rules that people use to identify acceptable
and unacceptable products [4, 11].
4.3 Software Engineering
There are two possible GA applications in the
software engineering one is software synthesis and other is software optimization.
In
“Evolving a Computer Program to Generate Random Numbers Using the Genetic
Programming Paradigm” by John R. Koza, demonstrates that random number
generators can be genetically breed with near optimal performance [4,12].
A Genetic Algorithm for Database Query Optimization
by K Bennett, M. Ferris and Y. Ioannidis, presents a method for applying
adaptive GA’s to performing complex query optimization tasks in a relational
database [4, 12].
4.4 Graphics
In graphics systems often automatically
arrange graphic objects on the screen according to some aesthetic criteria. And
this is especially applicable to Computer Aided Software Engineering (CASE) and
Computer Aided Design (CAD) applications [4]. The graphics layout can be optimized
by GA in these applications.
in Genetic
Algorithms + Data Structures = Evolution Programs by Zbigniew Michalewicz.
Describes how a GA can be used to produce aesthetically pleasing drawing of
directed graphs on a computer screen [4, 14].
4.5 Robotics
Different robots are designed differently on
the basis of job it done. Therefore there are a number of different designs.
GAs can be programmed to search a range of optimal designs and specific
components for each specific use. GA’s have been applied to optimizing robot
movement [4, 7].
A Genetic
Algorithm Applied to Robot Trajectory Generation by Yuval Davidor, describes
the control of a robot arm using a genetic algorithm to search for optimal
trajectories [4, 15].
4.6 Telecommunications
In
today’s world routing of information through a complex communications network
is an extremely important problem which is full of computer networks, cellular
networks, and packet switching networks [4]. GAs are developed which will allow for dynamic and
anticipatory routing of circuits for telecommunications networks. These check
the instability of your system and establish re-routing as needed. Using more
than one GA circuit-search at a time, soon your interpersonal communications
problems may really be all in your head rather than in your telecommunications
system. There are other GAs which are being developed to optimize placement and
routing of cell towers for best coverage and ease of switching. Some
researchers have addressed this tough problem using GA’s [4, 7].
Genetic
Algorithms in Communication Link Speed Design by Lawrence Davis and Susan
Coombs in Genetic Algorithms and their Applications, describes that GA applied
to the task of finding low cost sets of packet switching communication network
links [4, 16].
4.7 Forecasting
The predicting future behaviour from
historical data is known as forecasting. There are different types of
forecasting problems which are applicable to GA’s such as weather, earthquakes,
horse racing, etc [4].
In “A SEAGUL
Visits the Race Track” by Michael de la Maza, describes a GA system for
handicapping horses based on historical data [4, 17].
4.8 Engineering and Design
Design includes many
time consuming parameters and that’s why optimizing such designs is a difficult
for even expert engineers. The GA can help
the engineers in design by quickly narrowing in on close to optimal designs
given certain user specified design constraints [4]. These GAs uses as optimizing the design of
heat exchangers, robot gripping arms, flywheels, satellite booms, turbines, and
just about any other computer-assisted engineering design application [8].
In “Genetic
Algorithms in Parametric Design of Aircraft” by Mark Bramlette and E. Bouchard,
explains that how a GA can be used to optimize the parameters governing certain
aspects of air craft design [4, 18].
4.9 Neural Networks
The computer
programs which simulate the workings of the nervous system in order to solve
various problems are defined as neural networks. Many of the problems where
neural nets have been applied are similar to those listed here for GA
applications. But GAs have also been applied for creating better neural
networks. Applications include both the training and the optimal design of a
neural network [4].
In “A
connectionist algorithm for genetic search” by David Ackley, an architecture
for function maximization is proposed which uses principles from neural nets
and GA’s [4, 19].
5
Conclusion and Future
Genetic
algorithms are very good to solve complex problems where normal algorithms are
either too slow or are not good enough to come up with good solutions. By
looking at the applications GA has proven better with solutions or
optimizations of certain problems which are difficult for programmers or
engineers to do on their own due to complexity or difficulty. Again looking to
the applications it has been used in a wide range of problems and proven
successfully at most.
If we take the example of a robot, to create a
fully functional robot that act closer to human behaviour and also can learn on
itself, as problems grow more complex, GA may be the only way to solve certain
types of problems in the future [9].
6
References
[2]Marcus Randall, “The Future And Applications Of Genetic
Algoritms”, Faculty of Engineering and Applied Science, Griffith
University - Gold Coast.
[3]Wouter Caarls, “Genetic Algorithm And
Visualization”, Faculty of Science, University of Amsterdam, 2002.
[4]Salvatore R. Mangano, “A
Genetic Algorithm White Paper”.
[5]http://en.wikipedia.org/wiki/Genetic_algorithm
[6]http://www.ai-junkie.com/ga/intro/gat2.html
[7]http://brainz.org/15-real-world-applications-genetic-algorithms/.
[8]http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/tcw2/report.html#Vis_Concl
[9]Alexandre Weffort Thenorio,
“Genetic Algorithms ”.
[10]
Lawrence
Davis, “Job Shop Scheduling
with Genetic Algorithms”, First International Conference on Genetic Algorithms
and their Applications.
[11]
David
P. Greene and Stephen Smith, “A Genetic System for Learning Models of Consumer
Choice”, Proceedings of the Second International Conference on Genetic Algorithms.
[12]
John
R. Koza, “Evolving a Computer Program to Generate Random Numbers Using the
Genetic Programming Paradigm”, Proceedings of the Fourth International
Conference on Genetic Algorithms.
[13]
K
Bennett, M. Ferris and Y. Ioannidis , “A Genetic Algorithm for Database Query
Optimization”, Proceedings of the Fourth International Conference on Genetic
Algorithms.
[14]
P.
Eades and X. Lin and Zbigniew Michalewicz, “Genetic Algorithms + Data
Structures = Evolution Programs”.
[15]
Yuval
Davidor , “A Genetic Algorithm Applied to Robot Trajectory Generation” Handbook of Genetic Algorithms.
[16]
Lawrence
Davis and Susan Coombs, “Genetic Algorithms in Communication Link Speed
Design”, Proceedings of the Second International Conference on Genetic
Algorithms.
[17]
Michael
de la Maza , “A SEAGUL Visits the Race Track”, Proceedings of the Third
International Conference on Genetic Algorithms.
[18]
Mark
Bramlette and E. Bouchard, “Genetic Algorithms in Parametric Design of
Aircraft”, Genetic Algorithms.
[19]
David
Ackley, “A connectionist algorithm for genetic search”, Proceedings of the
First International Conference on Genetic Algorithms and their Applications.
[20]
No comments:
Post a Comment