International Journal of Emerging Technology and Advanced Engineering

Website: www.ijetae.com (ISSN 2250-2459, Volume 2, Issue 5, May 2012)

An Overview of methods maintaining Diversity in Genetic

Algorithms
Deepti Gupta1, Shabina Ghafir2
1
Student (M.Tech 3 yr), Jamia Hamdard, New Delhi, India
2
Assistant professor, Jamia Hamdard, New Delhi, India
1
[email protected]
2
[email protected]
Abstract - Genetic algorithm is a search & optimization It works in a iterative manner by successively applying
method based on the Darwin’s principle of Survival of the these three operators in each generation till a termination
fittest. It is an abstraction of complex natural genetics and criterion is satisfied [3].GA is the method of solving
natural selection process. Genetic algorithm is based on the problems by utilizing the processes of selection, crossover
principle of natural selection for reproduction and various
and mutation.
evolutionary operations as crossover and mutation. Two
controlling factors that need to be balanced in the process of
selection are Genetic Diversity and Selective Pressure. II. WORKING OF GA
Population Diversity can be controlled by a means of ways as Genetic Algorithm is started with a set of solutions
Fitness sharing, Deterministic crowding and so many other. In (represented by chromosomes) called population. Solutions
this paper we are providing a brief knowledge about variety
from one population are taken and used to form a new
of methods maintaining population Diversity.
population. This is motivated by a hope, that the new
Keywords-Genetic algorithms (GA), Diversity, Population population will be better than the old one [2]. Solutions
convergence, Selection, Crossover, and Fitness function. which are selected to form new solutions (offspring) are
selected according to their fitness - the more suitable they
I. INTRODUCTION are the more chances they have to reproduce. This is
repeated until some condition (for example number of
Genetic Algorithm is adaptive heuristic based on ideas
populations or improvement of the best solution) is
of natural selection and genetics. Genetic algorithm is one
satisfied. A Simple GA working principle is shown in
of the most known categories of evolutionary algorithm.
following Figure 1.The steps of simple Genetic Algorithm
Genetic Algorithm is based on the mechanics of biological
are described below here.
evolution initially developed by John Holland University of
Michigan (1970‟s) and further carried by De Jong and A. Basic Genetic Algorithm
Goldberg. Genetic Algorithm was designed to understand Start: Generate random population of n chromosomes.
processes in natural systems it was developed to design
artificial systems retaining the robustness and adaptation Fitness: Evaluate the fitness f(x) of each chromosome x in
properties of natural systems. Although Randomized, GAs the population.
is by no means random, instead they exploit historical New population: Create a new population by repeating
information to direct the search into the region of better following steps until the new population is complete.
performance within the search space [5]. Selection: Select two parent chromosomes from a
A GA works with a number of solutions (collectively population according to their fitness as the fitness is better,
known as population) in each iteration which is chosen the bigger chance to be selected by using various selection
randomly. These solutions are usually coded in binary schemes.
strings. Every solution or individual is assigned a fitness Crossovers: With a crossover probability crossover the
which is directly related to the objective function of the parents to form a new offspring (children). If no crossover
search and optimization problem. Thereafter, the was performed, offspring is an exact copy of parents.
population of individual is modified to a new population by
applying three operators similar to natural genetic Mutation: With a mutation probability mutate new
operators-reproduction, crossover, and mutation. offspring at each locus (position in chromosome).

56
 International Journal of Emerging Technology and Advanced Engineering
Website: www.ijetae.com (ISSN 2250-2459, Volume 2, Issue 5, May 2012)
Accepting: Place new offspring in a new population. Some factors that could influence the initial population
Replace: Use new generated population for a further run of or that should be taken into account when an initial
algorithm. population is generated randomly: the search space, the
fitness function, the diversity, the problem difficulty, the
Test: If the end condition is satisfied, stop, and return the
selection pressure, and the number of individuals [6].We
best solution in current population else move to Loop step.
are discussing only two important factors here.
Loop: Go to fitness step.
 Diversity
1. Formulate initial population
2. Randomly initialize population  Selective pressure
3. Repeat A. Diversity
4. Evaluate objective function The maintenance of a diverse solution population is
5. Find fitness function required to ensure that the solution space is adequately
6. Apply genetic operators searched, especially in the earlier stages of the optimization
7. Reproduction process. Population Diversity is considered as the primary
8. Crossover reason for premature convergence. So a very homogeneous
9. Mutation Population is found i.e. little Population Diversity is
10. until stopping criteria considered as the major reason for a Genetic Algorithm to
Figure 1: The Working Principle of a Simple Genetic Algorithm premature converge [4].Premature convergence occurs
when the population of a GA reaches such a suboptimal
In contrast to local search methods, genetic algorithms
state that the genetic operators can no longer produce
are based on a set of independent operators such as
offspring that outperform their parents.
selection, crossover and mutation controlled by a
probabilistic strategy. Genetic algorithms are a sub B. Selective Pressure
category of evolutionary algorithm. Evolutionary The tendency to select only the best members of the
algorithms are used to solve problems that do not already current generation to propagate to the next is required to
have a well defined efficient solution [4]. Genetic direct the GA to an optimum.
algorithms have been used to solve optimization problem. Too much selective pressure can lower the genetic
diversity so that the global optimum is overlooked & GA
III. FACTORS INFLUENCING GENETIC ALGORITHM converges to a local optimum. Too little selective pressure
If population is not chosen intelligently it become prohibits GA to converge to an optimum in a reasonable
difficult to find the correct solution of the problem whether time [28]. So a proper balance between Genetic Diversity
in the case of initial population selection or the selection of and Selective Pressure is to be maintained for the GA to
population for the next generation. Some factors to take converge in a reasonable time to a global optimum.
into account when the initial population is generated
randomly are mentioned in the following figure 2. IV. Methods For Maintaining Diversity
Population Diversity is qualitatively used for study the
premature convergence. Degree of population diversity
leads directly to premature convergence [7]. Techniques for
diversifying a population typically reduce selection
pressure, selection noise or operator disruption. Diversity-
preserving mechanisms can help the optimization in two
ways. A diverse population is able to deal with multimodal
functions and can explore several hills in the fitness
landscape simultaneously. Diversity-preserving methods
can therefore support global exploration and help to locate
several local and global optima. Methods for preserving
diversity are mentioned as below.
Figure 2: Factors affecting the initial population

57
 International Journal of Emerging Technology and Advanced Engineering
Website: www.ijetae.com (ISSN 2250-2459, Volume 2, Issue 5, May 2012)
A. Nitching Keep-best maintains the best parent and the best
A. De Jong introduced [8] the niching concept. A niche offspring in order to introduce good new genetic
can be viewed as a subspace in the environment that can material into the population.
support different types of life. For each niche, the physical  Correlative family based selection chooses the best
resources are finite and must be shared among the fitness individual as first survivor from each family
population of that niche. Nitching methods tend to achieve then calculate distance of other family members with
a natural emergence of niches and species in the search the highest fitness individual choosen and whosoever
space. Nitching methods maintain population diversity and is minimum distant from the best individual is chosen
permit the GA to investigate many peaks in parallel. On the as the survival for the next generation.
other hand, they prevent the GA from being trapped in C. Restricted Mating
local optima of the search space [25].
The restricted mating applies conditions such as
B. Crowding restriction or encouragement, to select an individual and its
De Jong subsequently presented the crowding concept mate partner. For example, the difference between pairs
to eliminate the most similar individual when a new one measured by the Hamming distance is used [9] for
enters a subpopulation. Crowding is one of the methods choosing the individuals for mating.
that is based upon the restriction on selection methods. It is D. Sharing
again of various types.
Sharing method is the most frequently used technique
 As in standard crowding, only a fraction of the global for maintaining population diversity. It is inspired by
population specified by a percentage G (generation natural ecosystem [10]. Each individual is forced to share
gap) reproduces and dies each generation. In this its fitness value to its neighbours. The survival probability
crowding scheme, an offspring replaces the most of an individual depends on its fitness value and its
similar individual (in terms of genotypic comparison) difference from others in the neighbourhood. Sharing must
taken from a randomly drawn subpopulation of size be used with the less biased selection methods. It tends to
CF (crowding factor) from the global population [8]. encourage search in unexplored area of the space. It comes
 Worst among most similar replacement policy [17] with the limitation of more computation cost and priori
follows three steps. Firstly Cf crowding groups are knowledge of how far apart the optima are. Petrowski [26]
created by randomly picking Cs crowding group size suggested the clearing policy which encourages the winners
individuals (with replacement) per group from the to take all resources in a niche.
population. Second one individual from each group
E. By Multiploidy
that is most similar to offspring is identified. This
gives Cf individuals that are candidate for replacement In nature many life form have poly-poid genotypes
by virtue their similarity to offspring .The off spring (multiploid) which consists of multiple sets of
will replace one of them. From this group of most chromosomes with some mechanism for determining which
similar candidates pick the one with the lowest fitness gene is expressed [11]. Multiploid GA is able to recover
to die and be replaced by the offspring. from early genetic drift where good genes become lost in
 Another type of crowding assumes that the parents the initial selection process. It is useful in those cases
would be one of the members of the population where useful genetic material may otherwise be
nearest to the new elements. In this way a family irretrievably lost.
competition is held. These methods include F. Ranked space
deterministic crowding, keep best reproduction [19]
Ranked space method is another strategy [12]. This
and correlative family based selection [18].
embeds the diversity maintaining mechanism approach
 In deterministic crowding offspring compete directly explicitly by the use of two ranks in the selection process
with their respective parents. In every generation the called the quality rank and the diversity rank [29]. The
population is partitioned into pairs of individuals. combination of these two ranks is used to influence the
These pairs are then recombined and mutated. Every selection probability. With this approach, the fitter
offspring then competes with one of its parents and individual is selected and at the same time the population
may replace it if the offspring is not worse [7]. diversity is maintained.

58
 International Journal of Emerging Technology and Advanced Engineering
Website: www.ijetae.com (ISSN 2250-2459, Volume 2, Issue 5, May 2012)
G. DCGA L. Replacement method
In the DCGA (Diversity control oriented GA) the There are various replacement strategies try to maintain
structures for the next generation are selected from the diversity. It can be categorized as Worst among most
merged population of parents and their offspring similar replacement, Family competition replacement
eliminating duplicates based on a selection probability, scheme.
which is calculated using the hamming distance between
M. Using Tabu Multi parent Genetic Algorithm
the candidate structure and the structure with the best
fitness value and is larger for structures with larger The Tabu multi parent genetic algorithm (TMPGA) is
hamming distances. The idea is to exploit those worse presented. The mating of multiple parents in TMPGA is
solutions instead of discarding them by maintaining restricted by the strategy of tabu search [20]. The tabu list
diversity of structures in the population [13]. is used for preventing incest and maintaining the diversity
of population.
H. Elitist
N. CSGA
Elitist is one of the method [14] in which best two of
these four (parent and offspring) go to the next generation. CSGA (complementary surrogate genetic algorithm)
No separate selection and recombination phase but only a CSGA has the diversity-maintenance feature without an
competition in each family which typically consist of two explicit mutation. The special feature of the CSGA is the
mating parents & their offspring. Best two of each family inclusion of complementary surrogate set (CSS) into the
survive & are included in the next population. This method population. The CSS is an individual or a set of individuals
can very rapidly increase the performance of GA because it adding to the population for guaranteeing that each bit
prevents loosing the best found solutions. Good solutions position of the whole population is diverse (not all „0‟ or all
found are never lost unless even better solutions are „1‟)[21] .
created. O. Fitness Uniform Selection Scheme
I. Injection In the FUSS (fitness uniform selection scheme) lowest
Injection strategy is another method [15]. Here fix point and highest fitness values in the population are (Let assume
injection is used for certain number of generations. Inject the representation) min f and max f respectively [22, 29].
new random number to the population to maintain the The FUSS will select a fitness f uniformly in the interval [f
population diversity. The injection strategy should be min, f max]. Then the individual with fitness value nearest
carefully designed to avoid overlapping to the genes that to f is selected. The FUSS maintains diversity better than a
have occupied the feasible slot. With it a sorting strategy is standard selection scheme since a distribution over the
also introduced. fitness value is used. Therefore, the higher and the lower
fitness individuals are mixed in the selection.
J. Removal of genotype or fitness duplicate Except all these above methods there are still more ways
One simplest way to enforce diversity within the like Primal dual GA, Dual population GA, Multipopulation
population is not to allow genotype duplicates. It prevents GAs, radius based methods [23],clustering [24], Adaptation
identical copies from entering the population as a natural of mutation rate, incest prevention [27], incest prevention
way of ensuring diversity. One another restrictive in survival selection [13] , negative assortative mating[30].
mechanism is to avoid a fitness duplicate that is multiple All of these methods try to maintain diversity within the
individuals with the same fitness [7]. population so that global result may achieved in a
proportionate balance time.
K. MOEA
A multi-objective evolutionary algorithm [16] keeping V. CONCLUSION
diversity of the population is the algorithmThis makes use
of a metric based on entropy to measure the diversity of the Genetic Algorithms are highly effective in searching a
population. large, poorly defined search space even in the presence of
difficulties such as high-dimensionality, multi-modality,
discontinuity and noise.

59
 International Journal of Emerging Technology and Advanced Engineering
Website: www.ijetae.com (ISSN 2250-2459, Volume 2, Issue 5, May 2012)
Stochastic searching, intrinsically parallel nature with [16] Xiaoning Shen, Min Zhang, Tao Li, “A Multi-objective
global perspective makes Genetic Algorithm of use. Optimization Evolutionary Algorithm Addressing Diversity
Maintenance”
Maintaining diversity of individuals within a population is
necessary for the long term success of any evolutionary [17] Manuel Lozano,Francisco Herrera,Jose ramon cano,”Replacement
strategies to preserve useful diversity in SSGA”.
system. So a balance between population diversity and
[18] K. Matsui,”New selection methods to improve population diversity
selective pressure is to be maintained for finding an optimal in GA”.
solution in reasonable time. Genetic diversity helps a [19] K.Wilese, S.D.Goodwin, Convergence characteristics of keep
population adapt quickly to changes in the environment and best Reproduction, Selected areas in cryptography”.
it allows the population to continue searching for [20] C. K. Ting & H. K. Buning, (2003) “A mating strategy for multi-
productive niches, thus avoiding becoming trapped at local Parent genetic algorithms by integrating tabu search”, in
optima. Thus improving diversity in GAs makes GA more Proceedings of the 2003 Congress on Evolutionary Computation,
useful efficient way to solve problems. So GAs is applied pp. 1259-1266.
to a wide variety of searching and optimization problems in [21] I.K. Evans, (1997)“Enhancing recombination with the
Complementary surrogate genetic algorithm”, In Proceedings of
various fields from science, engineering and technology. the IEEE International Conference on Evolutionary computation, pp.
97-102.
REFERENCES
[22] M. Hutter, (2002) “Fitness uniform selection to preserve genetic
[1] Kalyanmoy Deb. “Genetic Algorithm in search and optimization: Diversity”, In Proceedings of the 2002 Congress on Evolutionry
The technique and application”. Computation, pp, 783-788.
[2] Mir Asif iquebal” Genetic Algorithms and their application, ”An [23] O. M. Shir and T. B¨ack, ”Niching in Evolution Strategies”. In 2005
overview ”. Genetic and Evolutionary Computation Conference (GECCO
[3] Goldberg D.E. (1989) “Genetic Algorithm in search, optimization ‟2005), volume 1, pages 915–916, New York, USA, June 2005.
and machine learning”. ACM Press.
[4] Darrell Whitely, “An overview of evolutionary algorithms: Practical [24] F. Streichert, G. Stein, H. Ulmer, and A. Zell. A Clustering Based
issues and common pitfalls”. Niching EA for Multimodal Search Spaces. In Artificial Evolution,
[5] R.Sivraj, Dr. Ravichandran, “A Review of selection methods in 6th international Conference, Evolution Artificielle, EA 2003,
Genetic Algorithm “. Revised Selected Papers,pages 293–304, Marseille, France, Oct.
2004. Springer-Verlag. Lecture Notes in Computer Science Vol.
[6] Pedro A. Diaz-Gomez and Dean F. Hougen, “Initial Population for 2936.
Genetic Algorithms: A Metric Approach”.
[25] Bruno Sareni and Laurent Kr¨ahenb¨uhl ”Fitness Sharing and
[7] Tobias Friedrich, Pietro S. Oliveto, Dirk Sudholt, carsten witt, Niching Methods Revisited”.
“Analysis of Diversity-Preserving Mechanisms for Global
Exploration”. [26] A.Petrowski, “A New selection operator dedicated to speciation”, In
Proceeding of the seventh international conference on Genetic
[8] K. A. DeJong, “An analysis of the behavior of a class of genetic Algorithm,1997,pp. 144-151.
adaptative systems,” Ph.D. dissertation, Univ. of Michigan, Ann
Arbor, 1975. [27] L.J.Eshelman, J.D.Schaffer, “Preventing premature convergence in
genetic algorithms by preventing incest”, In Proceedings of fourth
[9] L. J. Eshelman & J. D. Schaffer, (1991) “Preventing premature International conference on genetic algorithm 1991,pp. 115-122.
convergence in genetic algorithms by preventing incest”, In
Proceedings of the Fourth International Conference on Genetic [28] SAS/IML User‟s guide 9.3 vol 1 chapter 20 page 501-505.
Algorithms, pp. 115-122 . [29] Chaiwat Jassadapakorn and Prabhas Chongstitvatana, “Self
[10] D. E. Goldberg & J. Richardson, (1987) “Genetic algorithms with adaptation mechanism to control the diversity of the population in
sharing for multimodal function optimization”, In Proceedings of Genetic Algorithm”.
the Second International Conference on Genetic algorithms and [30] C.Fernandes , A Rosa , “A Study on non-random mating and varying
their application, pp. 41-49. population size in genetic algorithm using a royal road function” ,in
[11] Emma Collingwood, David Corne Peter Ross “Useful Diversity Proceedings of IEEE congress on evolutionary computation, Seoul,
via Multiploidy”. South Korea,2001.

[12] P. H. Winston, (1992) Artificial Intelligence, Addison- Wesley.

[13] Hisashi Shimodaira, “DCGA: A Diversity Control Oriented
Genetic Algorithm”.
[14] Goldberg, D.E. and K. Deb ”A Comparative analysis of selection
schemes used in GA ”.
[15] Abu Bakar,Md. Sultan, Ramlan Mahmod,MD Nasir Sulaiman &
Md. Rizam abu bakar“Maintaing diversity for Genetic algorithm:
A case of timetabling problem”.

60