See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/341371936

Literature Review on Genetic Algorithm

Article  in  International Journal of Research · June 2018

CITATIONS READS

0 1,183

1 author:

Shabnam Sangwan
Deenbandhu Chhotu Ram University of Science and Technology, Murthal
15 PUBLICATIONS   25 CITATIONS   

SEE PROFILE

Some of the authors of this publication are also working on these related projects:

cloud computing View project

genetic algorithm based hindi word sense disambiguation View project

All content following this page was uploaded by Shabnam Sangwan on 14 May 2020.

The user has requested enhancement of the downloaded file.

 International Journal of Research e-ISSN: 2348-6848
p-ISSN: 2348-795X
Available at https://edupediapublications.org/journals
Volume 05 Issue 16
June 2018

Literature Review on Genetic Algorithm

Aradhana Dahiya & Shabnam Sangwan
1
Department of Computer Science Gateway Institute of Engineering & Technology (SKITM),
Maharishi Dayanand University (MDU), Rohtak
[email protected]

2
Department of Computer Science Sat Kabir Institute of Technology and Management (SKITM),
Maharishi Dayanand University (MDU), Rohtak
[email protected]

Abstract— Genetic algorithm is a technique used for means that the genes from the highly adapted
estimating computer models based on methods individuals will spread to a growing number of
adapted from the field of genetics in biology. To use individuals in each following generation.
this technique, one encodes possible model behaviors
into ''genes". After each generation, the current models The combination of good characteristics from
are rated and allowed to mate and breed based on their different ancestors can sometimes produce super fit
fitness. In the process of mating, the genes are offspring, whose fitness is greater than that of either
exchanged, crossovers and mutations can occur. The parent. In this way, species evolve to become more
current population is discarded and its offspring forms and better suited to their environment. Genetic
the next generation. In this paper we will provide algorithms use a direct analogy to natural behavior.
review of different problems that can be solved by They work with a population of individuals, each
Genetic Algorithm approach. representing a possible solution to a given problem
[SIV08]. Each individual is assigned a fitness score
Keywords— Genetic Algorithm, Crossover operators, according to how good a solution to the problem it is.
Mutation Operators The highly fit individuals are given opportunities to
reproduce, by cross breeding with other individuals in
the population. This produces new individuals as
I. INTRODUCTION
offspring, which share some features taken from each
parent. The least fit members of the population are
Genetic Algorithms (GA’s) are adaptive methods less likely to get selected for reproduction, and so die
which may be used to solve search and optimization out.
problems. They are based on the genetic processes of
biological organisms. Over many generations, natural In this paper we will provide review of different
populations evolve according to the principles of problems that can be solved by Genetic Algorithm
natural selection and survival of the fittest, first clearly approach.
stated by Charles Darwin in The Origin of Species
[DAV91]. By mimicking this process, genetic II. LITERATURE REVIEW
algorithms are able to find solutions to real world
problems, if they have been suitably encoded. For The genetic algorithm belongs to the family of
example, GA’s can be used to design bridge structures, evolutionary algorithms, along with genetic
for maximum strength/weight ratio, or to determine programming, evolution strategies, and evolutionary
the least wasteful layout for cutting shapes from cloth. programming. Evolutionary algorithms can be
They can also be used for online process control, such considered as a broad class of stochastic optimization
as in a chemical plant, or load balancing on a multi- techniques. An evolutionary algorithm maintains a
processor computer system. population of candidate solutions for the problem at
hand. The population is then evolved by the iterative
The basic principles of GA’s were first laid down application of a set of stochastic operators. The set of
rigorously by Holland in 1975. [SIV08] GA’s simulate operators usually consists of mutation, recombination,
those processes in natural world which are essential to and selection or something very similar. Let’s discuss
evolution. Exactly which biological processes are some of the papers published that is related to the
essential for evolution, and which processes have little Genetic Algorithm in the past.
or no role to play is still a matter for research but the
basics are clear. In nature, individuals in a population Bryant [BRY00], here in this paper compared the
compete with each other for resources such as food, results, which come after applying many different
water and shelter. Also, members of the same group crossover and mutation operators devised for the
often compete to catch the attention of a mate. Those traveling salesman problem and it is concluded that
individuals which are most successful in surviving and operators that use heuristic information or a matrix
attracting mates will have relatively larger number of representation of the graph give the best results.
offspring’s. Poorly performing individuals will Genetic algorithms are an evolutionary technique that
produce few or even no offspring at all [MIT96]. This

Available online: https://edupediapublications.org/journals/index.php/IJR/ P a g e | 1142

 International Journal of Research e-ISSN: 2348-6848
p-ISSN: 2348-795X
Available at https://edupediapublications.org/journals
Volume 05 Issue 16
June 2018

uses crossover and mutation operators to solve assignment in a population. It’s been tested on many
optimization problems using a survival of the fittest test cases and showed good result.
idea. They have been used successfully in a variety of
different problems, including the traveling salesman Molga [MOL05] suggested in this paper on “Test
problem. In the traveling salesman problem the aim is functions for optimization needs” provides the review
to find a tour of all nodes in a weighted graph so that of literature benchmarks (test functions) commonly
the total weight is minimized. The traveling salesman used in order to test optimization procedures dedicated
problem is NP-hard but has many real world for multidimensional, continuous optimization task.
applications so a good solution would be useful. Special attention has been paid to multiple-extreme
functions, treated as the quality test for opposing
Enrietch [ERA00] in this paper “Evolutionary optimization methods (GA, SA, TS etc.). Quality of
algorithms” introduced that Evolutionary Algorithms optimization procedures (those already known and
are stochastic optimization techniques based on the those newly proposed) are frequently evaluated by
principles of natural evolution. An overview of these using common standard literature benchmarks. There
techniques is provided with the general functioning of are several classes of such test functions, all of them
EA’s, and gives an outline of the main families into are continuous, which are, first is unimodal, convex,
which they be divided. Subsequently, it analyzes the multidimensional, second is multimodal, two-
different components of an EA, and provides some dimensional with a small number of local extremes,
examples on how these can be instantiated. In the end third is multimodal, two-dimensional with huge
it finished with a glimpse of the numerous number of local extremes and the last is multimodal,
applications of these techniques. Various techniques multidimensional with huge number of local extremes.
are Evolutionary Programming, Evolutionary Where, class first contains nice functions as well as
strategies, Genetic programming and Genetic malicious cases, causing poor or slow convergence to
Algorithms. The basic differences between these single global extreme. Class second is intervening
paradigms lie in the nature of the representation between first and third and last is used to test quality
schemes, the reproduction operators and selection of standard optimization procedures in the unfriendly
methods. environment, namely that having few local extremes
with single global one. Classes third and fourth are
Madureira [MAD02], suggested GA for the resolution recommended to test quality of intelligent resistant
of real world scheduling problems, and proposed a optimization methods.
coordination mechanism. Because of frequently
changing dynamic environments, providing efficient Omar [OMA06], proposed a method of solving job-
production management and timely delivery are one of shop scheduling using GA. They generated an initial
the hard to solve problems. Scheduling is to allocate a population randomly including the result obtained by
set of machines to perform a set of jobs within a some well known priority rules such as shortest
certain time period, and the goal of scheduling is to processing time and longest processing time. From
find an appropriate allocation schedule which there the population will go through the process of
maximizes certain performance measure. For the reproduction, crossover and mutation to create a new
implementation issues, the solutions are encoded by population for the next generation until some stopping
natural representation, and the order crossover criteria defined were reached. In the paper, the
operator is used. They used the inversion mechanism numbers of generations are used as stopping criterion.
as mutation operator. Finally, Madureia et al. solved In crossover and mutation, the critical block
dynamic scheduling problem using a set of static neighborhood is used and the distance measured to
scheduling schemes by GA, and they showed the help evaluate the schedules. Result has shown that the
feasibility of GA in Job-Shop scheduling problem. implementation of critical block neighborhood and the
distance measured can lead to the same result obtain
Sandstrom [SAN02] suggested the GA which is by other methods.
applied for assigning task priorities and offset to
guarantees that real time timing constraints. Assigning Dr. Rakesh Kumar [RKU10] suggested in his paper on
timing constraint to task is not trivial problem in real- “Genetic Algorithm approach to Operating system
time system. They showed how timing constraints be process scheduling problem”. Scheduling in operating
mapped to attributes of periodic tasks running on systems has a significant role in overall system
standard preemptive RTOS (Real-Time Operating performance and throughput. An efficient scheduling
System). They used GA because of the GA’s ability to is vital for system performance. The scheduling is
generate a result that satisfies a subset of the timing considered as NP hard problem .The power of genetic
constraints in cases where it is impossible to fulfill all algorithm is used to provide the efficient process
constraints. GA, the mechanism of natural selection, scheduling. The aim is to obtain an efficient scheduler
gradually improves individuals timing constraints to allocate and schedule the process to CPU.

Available online: https://edupediapublications.org/journals/index.php/IJR/ P a g e | 1143

 International Journal of Research e-ISSN: 2348-6848
p-ISSN: 2348-795X
Available at https://edupediapublications.org/journals
Volume 05 Issue 16
June 2018

directional searches into the GA process. These local

H. Nazif [HNA09] suggested in his paper on “A searches are based on using the method of steepest
Genetic Algorithm on Single Machine Scheduling descent (SD), the Newton-Rampson method (NR), a
Problem to Minimize Total Weighted Completion derivative-free directional search method (DFDS), and
Time”. In this paper, he addresses a single machine a method that combines SD with DFDS. Some
family scheduling problem where there are multiple benchmark functions, such as a low-dimensional
jobs. Each job is characterized by a processing time function versus a high-dimensional function, and a
and an associated positive weight, are partitioned into relatively uneven function versus a very uneven
families and setup time is required between these function, are employed to illustrate the improvement
families. For this problem, he propose a genetic of these proposed methods through a Monte Carlo
algorithm using an optimized crossover operator simulation study using a split-plot design. A real
designed by an undirected bipartite graph to find an problem related to the multi-response optimization
optimal schedule which minimizes the total weighted problem is also used to illustrate the improvement of
completion time of the jobs in the presence of the these proposed methods over the traditional GA and
sequence independent family setup times. over the method implemented in the Design-Expert
statistical software package. Our results show that the
Snehal Kamalapur [SKA06] suggested in his paper on GA can be improved both in accuracy and in
“Efficient CPU Scheduling: A Genetic Algorithm computational efficiency in most cases by
based Approach “that Operating system's performance incorporating a local directional search into the GA
and throughput are highly affected by CPU process.
Scheduling. The scheduling is considered as an NP
problem. An efficient scheduling improves system
performance. In her paper she presents and evaluates a III. ADVANTAGES, LIMITATIONS AND APPLICATIONS
method for process scheduling. In this paper, she OF GENETIC ALGORITHM
discussed the use of genetic algorithms to provide
efficient process scheduling. And evaluate the A. Advantages of Genetic Algorithm
performance and efficiency of the proposed algorithm
in comparison with other deterministic algorithms and The advantages of genetic algorithm are:
in a way that optimises some performance by 1. Parallelism.
simulation. 2. Liability.
3. Solution space is wider.
S.Ramya [SRA10] suggested in his paper on 4. The fitness landscape is complex.
“Window Constrained Scheduling of Processes in 5. Easy to discover global optimum.
Real Time CPU Using Multi Objective Genetic 6. The problem has multi objective function.
Algorithm “a new approach to window constrained 7. Only uses function evaluations.
scheduling, suitable for weakly-hard real-time systems. 8. Easily modified for different problems.
The originally developed algorithm, called Virtual 9. Handles noisy functions well.
Deadline Scheduling (VDS) that attempts to guarantee 10. Handles large, poorly understood search spaces
m out of k deadlines are serviced for real-time jobs easily.
such as periodic CPU tasks. VDS is capable of 11. Good for multi-modal problems, returns a group of
generating a feasible window constrained schedule solutions.
that utilizes 100% of resources. However, when VDS 12. Very vigorous to difficulties in the evaluation of
either services a job or switches to a new request the objective function.
period, it must update the corresponding virtual 13. They are more resistant to becoming trapped in
deadline. This updation is a bottleneck for the local optima.
algorithm, which increases the time complexity. 14. They perform very well for large-scale
Further, when VDS tries to solve the problem of delay optimization problems.
the number of context switches increases. Context 15. Can be employed for a wide variety of
switching and delay are two conflicting criteria. By optimization problems.
using Multi Objective Genetic Algorithm a trade off
can be achieved between the context switching and the B. Limitations of Genetic Algorithm
delay. We design our algorithm in such a way that it
also overcomes the problem of updation, which is an The limitation of genetic algorithm includes:
additional overhead in the original VDS algorithm. 1. The problem of identifying fitness function.
2. Definition of representation for the problem.
Birch [BIR09], in this paper presents four different 3. Premature convergence occurs.
versions of computationally efficient genetic
algorithms by incorporating several different local

Available online: https://edupediapublications.org/journals/index.php/IJR/ P a g e | 1144

 International Journal of Research e-ISSN: 2348-6848
p-ISSN: 2348-795X
Available at https://edupediapublications.org/journals
Volume 05 Issue 16
June 2018

4. The problem of choosing the various parameters [3]. [MIT96] Mitchell, Melanie
like the size of the population, mutation rate, cross (1996). An Introduction to Genetic
over rate, the selection method and its strength.
5. Cannot use gradients.
Algorithms. MIT Press.
6. Cannot easily incorporate problem specific [4]. BRY00] Bryant, Kylie (2000).
information.
Genetic Algorithms and the Traveling
7. No effective termination point.
9. Not effective for smooth unimodal functions. Salesman Problem, in Proceedings of 1st
10. Needs to be coupled with a local search technique. GNT Regional Conference on Mathematics,
11. Have trouble finding the exact global optimum. Statistics and Applications.
C. Applications of Genetic Algorithm [5]. [COE00] Coello, Carlos (2000).
An updated survey of GA-based
Genetic algorithms have been used for difficult multiobjective optimization techniques, ACM
problems (such as NP-hard problems), for machine Computing Surveys, vol. 32, no. 2, pp. 109-
learning and also for evolving simple programs. They
have been also used for some art works, for evolving 143.
pictures and music. A few applications of GA are as [6]. [HAN00] Hanne, Thomas (2000).
follows:
Global multiobjective optimization using
 Strategy planning.
 Robot trajectory planning. evolutionary algorithms. Journal of
 TSP and sequence scheduling. Heuristics, vol. 6, no. 3, pp. 347-360.
 Function Optimizations. [7]. [MAD02] Madureira, A., Ramos, C.,
 Control–gas pipeline, missile evasion.
& Silva, S. Carmo, (2002). A Coordination
 Aircraft design and communication networks.
 Scheduling–manufacturing. Mechanism for Real World Scheduling
 Machine Learning–Designing neural Problems using Genetic Algorithms.
networks, both architecture and weights, Evolutionary Computation, in Proceedings of
improving classification algorithms. the 2002 CEC, vol. 1, pp. 175 –180.
[8]. [MOL05] Molga, M. & Smutnicki, C.
IV. CONCLUSION (2005). Test functions for optimization needs,
The basic concept of GAs is designed to simulate
in Proceedings of 4th Conference on Genetic
processes in natural system necessary for evolution, Algorithms.
specifically those that follow the principles first laid
[9]. [OMA06] Omar, M., Baharum,
down by Charles Darwin of survival of the fittest. As
such they represent an intelligent exploitation of a A., & Hasan, Y. Abu (2006). A Job-Shop
random search within a defined search space to solve a Scheduling Problem (JSSP) Using Genetic
problem. Genetic Algorithms has been widely studied, Algorithm ,in Proceedings of 2nd IMT-GT
experimented and applied in many fields in Regional Conference on Mathematics,
engineering worlds. In this paper we have studied
Statistics and
different problems that can be solved by Genetic
Algorithm approach. [10]. [INA06] Inazawa, H. &
Kitakaze, K. (2006). Locus-Shift Operator
REFERENCES for Function Optimization in Genetic
Algorithms. Complex Systems Publications,
Inc.
[1]. [GOL89] Goldberg, D. E. (1989).
Genetic Algorithms in Search, Optimization, [11]. [SKA06] Snehal Kamalapur
and Machine Learning. Boston: Addison- (2006).Efficient CPU Scheduling: A Genetic
Wesley. Algorithm based Approach. IEEE, pp.206-
207
[2]. [DAV91] Davis, L. (1991).
Handbook of Genetic Algorithm. Von [12]. [DEH08] Dehuri, S. et al. (2008).
Nostrand Reinhold, Newyork. Application of elitist multi-objective genetic

Available online: https://edupediapublications.org/journals/index.php/IJR/ P a g e | 1145

 International Journal of Research e-ISSN: 2348-6848
p-ISSN: 2348-795X
Available at https://edupediapublications.org/journals
Volume 05 Issue 16
June 2018

algorithm for classification rule generation,

Applied Soft Computing, pp. 477–487.
[13]. [SIV08] Sivanandam, S. N. &
Deepa, S. N. (2008). Introduction to Genetic
Algorithms. Springer.
[14]. [BIR09] Birch, J. B. & Wan, W.
(2009). An Improved Genetic Algorithm
Using a Directional Search. Tech report
presented at Virginia Polytechnic Institute
and State University, Blacksburg.
[15]. [HNZ09] H. Nazif(2009). A
Genetic Algorithm on Single Machine
Scheduling Problem toMinimise Total
Weighted Completion Time. European
Journal of Scientific Research,Vol.35 No.3,
pp.444-452
[16]. [RKU10] Dr. Rakesh
Chawla(2010). Genetic Algorithm approach
to Operating system process scheduling
problem. International Journal of ngineering
Science and Technology, pp. 4247-4252
[17]. [SRA10] S. Ramya[2010] “Window
Constrained Scheduling of Processes in Real
Time CPU Using Multi Objective Genetic
Algorithm“ International Journal of
Computer Applications Volume 1, pp.86-90

Available online: https://edupediapublications.org/journals/index.php/IJR/ P a g e | 1146

View publication stats