Information Sciences 156 (2003) 189–214
www.elsevier.com/locate/ins

On the harmonious mating strategy throughtabu search
Chuan-Kang Ting a, Sheng-Tun Li b, Chungnan Lee c,*a

Department of Computer Science and Engineering, National Sun Yat-Sen University,
Kaohsiung, TaiwanbDepartment of Information Management, National Kaohsiung First Universityof Science and Technology, 2 Juoyue Rd. Nantz District, Kaohsiung, TaiwancDepartment of Computer Science and Engineering, National Sun Yat-Sen University,
Kaohsiung, Taiwan
Received 15 March 2002; accepted 1 January 2003

Abstract
Genetic algorithms (GAs) are well-known heuristic algorithms and have been applied to solve a variety of complicated problems. When adopting GA approaches, twoimportant issues––selection pressure and population diversity––must be considered.
This work presents a novel mating strategy, called tabu genetic algorithm (TGA), whichharmonizes these two issues by integrating tabu search (TS) into GA’s selection. TGA
incorporates the tabu list to prevent inbreeding so that population diversity can be
maintained, and further utilizes the aspiration criterion to supply moderate selection
pressure. An accompanied self-adaptive mutation method is also proposed to overcome
the diﬃculty of determining mutation rate, which is sensitive to computing performance. The classic traveling salesman problem is used as a benchmark to validate theeﬀectiveness of the proposed algorithm. Experimental results indicate that TGA canachieve harmony between population diversity and selection pressure. Comparisonswith GA, TS, and hybrids of GA and TS further conﬁrm the superiority of TGA interms of both solution quality and convergence speed.
Ó 2003 Elsevier Inc. All rights reserved.

*

Corresponding author. Tel.: +886-7-5252000-4313; fax: +886-7-5254301.
E-mail addresses: d8834804@student.nsysu.edu.tw (C.-K. Ting), stli@ccms.nkfust.edu.tw (S.-T.
Li), cnlee@mail.nsysu.edu.tw (C. Lee).
0020-0255/$ - see front matter Ó 2003 Elsevier Inc. All rights reserved.
doi:10.1016/S0020-0255(03)00176-2

190

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214

Keywords: Genetic algorithm; Tabu search; Restrictive mating; Sexual selection;
Traveling salesman problem

1. Introduction
Genetic algorithms (GAs) are well-known heuristic algorithms based on theimitation of natural systems [1]. Their eﬀectiveness in search and optimization
problems has received extensive attention [2–5]. However, GA has its costs.
Whitley [6] pointed out that there are two major issues in designing GA: selection pressure and population diversity. Selection pressure leads GA to exploit information inside the ﬁtter individuals and results in more superioroﬀspring iteratively. The diversity in GA is attributed to the form of population, which contains a certain number of encoded individuals for exploration.
Nevertheless, a tradeoﬀ exists between population diversity and selection
pressure. Emphasis on selective pressure accelerates the optimization convergence but potentially causes premature convergence because of hastened loss ofdiversity. On the contrary, maintaining diversity can yield a better solution
quality, but often slows down the convergence speed due to the lack of selection pressure. Therefore, a good GA scheme must simultaneously address these
two issues. On one hand, GA must maintain certain diversity to explore theunvisited space, and on the other hand, it must have adequate selective pressure
to exploit the relevant solutions. Restated, GA should pursue a good balance
between exploration and exploitation in consideration of both convergence
speed and optimized solution quality.
In this paper, we present a novel heuristic optimization algorithm, calledtabu genetic algorithm (TGA), which incorporates the features of tabu search(TS) into GA. TS is another class of meta-heuristic algorithms, which are basedon explicit memory structures [7]. It uses memory to record the search trajectory and guide the search in order to consider both intensiﬁcation and diversiﬁcation. Many studies have veriﬁed the encouraging capability of TS in
combinatorial optimization problems [7–9]. In view of this, several researchers
proposed to incorporate TS with GA to enhance the search. Glover and Laguna [9] inceptively introduced the scatter search toward integrating GA and
TS. Then, several studies proposed various hybrids of GA and TS. For example, Handa and Kuga [10] considered the diﬀerence between the convergence speed of GA and TS in the ﬁrst half and that in the second half of thesearch process. They suggested an approach of concatenating GA and TS,
which switches the search to TS when GA stops improving solutions. Chin [11]attempted to increase the search intensity of TS with the convergence of GA’s
population. Another common way of hybridization is to regard TS as a local
enhancement for GA. This approach typically selects the best chromosome or

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214

191

random ones from GA’s population, and operates on them with TS to explore
their neighborhood for better solutions. These results generated by TS are thenincorporated into the GA’s population and evolution is resumed [12–15,17].
Nara [16] additionally utilized a tabu list to prohibit the mating of chromosomes, whose hamming distances are too close to each other. In general, mostof these hybrid approaches are based on running these two algorithms alternately and passing the computation results from one to the other. The original
structures of GA and TS are not modiﬁed in these approaches.
In contrast to running alternately, TGA implants characteristics of TS into
GA’s mating strategy. First, the memory structure in TS, the tabu list, is used
to record the trajectory of evolution and preclude certain mating in consideration of diversiﬁcation. Second, under the restriction of tabu list, the aspiration
criterion is applied to supply selection pressure for intensiﬁcation. By incorporating the tabu list and the aspiration criterion, the selection of GA is expected to achieve harmony in exploring the diverse population and exploiting
the superiors. Such a balance of exploration and exploitation has been shown
to be able to eﬀectively improve the performance of GA [2]. In addition to
selection, a self-adaptive mutation operator is proposed so that the mutation is
dynamically performed according to the situation of population rather than aﬁxed probability. This self-adaptation ability can also overcome the diﬃcultyof determining mutation rate, especially when the rate critically aﬀects theperformance.
The rest of this paper is organized as follows. In Section 2, related works onmating schemes are reviewed. In Section 3, we propose the TGA algorithm andgive detailed descriptions. Section 4 discusses the eﬀectiveness of TGA’s
schemes and the comparisons of performance with GA, TS, and hybrids of GA
and TS. Finally, conclusions are drawn in Section 5.

2. Related work
In the conventional GA, no mating strategy is applied to the results of selection; that is, parents are approved without any further examination after they
are chosen at random or just by ﬁtness. Indeed, mating in nature is more
complicated. For example, with respect to human beings, as well as speciﬁcfactors such wealth and appearance that objectively contribute to ﬁtness, some
implicit factors also potentially guide mating, such as race, bloodline, andothers. Inspired by this observation, a number of mating strategies for GA havebeen proposed to deal with the issues of population diversity or selection
pressure in a natural way. According to the adopted metrics used to measure
implicit factors, we classify these approaches into two major categories––
computation-based and memory-based mating strategies. They are reviewed
below.

192

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214

2.1. Computation-based mating
The most common computation-based approach is to distinguish the degreeof similarity among individuals by calculating genotype or phenotype characteristics, and then mate the individuals according to diﬀerent strategies.
Genotype holds the information embedded in individuals; thus it is used to
specify mating individuals. Hamming distance is the most popular metric forsimilarity (or dissimilarity) between two individuals. De Jong [18] introduced
the concept of niching and subsequently presented the crowding method to
remove the most similar individual when a new one enters a subpopulation.
The sharing function [2] takes ﬁtness as a resource and distributes it over all
niches, which are delimited by individuals’ similarity. Instead of sharing theresources, Petrowski [19] suggested the clearing policy, which encourages thewinner to take all resources in a niche. Mauldin [20] proposed the k-bits decreasing uniqueness method in which members of a population must have atleast k-bits of diﬀerences. The method decreases this uniqueness with evolution. Thus, population diversity is controlled and premature convergence is
avoided.
The work on incest prevention [21] introduced a direct way for mating to
restrain assimilation from premature convergence. It suggested that individuals
with a short hamming distance might be related. Hence mating is only allowed
if their hamming distance is above a threshold, which decreases as evolution
proceeds. The results show that incest prevention can really avoid premature
convergence and improve the solution at the expense of convergence speed.
Shimodaira [22] employed the concept of incest prevention in survival selection
and increased the diversity by giving individuals with farther hamming distances from the best solution a higher probability of survival. Incorporatingwith tournament selection, correlative tournament selection (CTS) [23] chooses
the mate with higher ﬁtness and hamming distance from a set of candidates.
Fernandes and Rosa [24] introduced an analogous concept, called negative
assortative mating, into GA with varying population size (GAVaPS). They
found that the number of candidates was directly proportional to the performance of the Royal Road function [25]. Bian et al. [26] proposed a strategy ofchoosing diﬀerent crossover methods on the basis of the couple’s hamming
distance in order to prevent premature convergence.
In contrast to incest prevention, De et al. [27] tried to mimic inbreeding in
nature and proposed assortative mating, which restricts individuals to matewith one separated by a minimal hamming distance. They stated that thisstrategy could enhance exploitation and reduce the disruption of schema.
Experimental results demonstrated the strategy’s eﬀectiveness over both conventional GA and incest prevention in certain problems. The work in [28]used diﬀerent assortative mating strategies to deal with vector quantization
problems, and obtained an opposite outcome: positive assortative mating

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214

193(inbreeding) did not improve GA performance and was inferior to negative
assortative mating (incest prevention). That work revealed that an all-out eﬀort
on selection pressure, such as inbreeding, might lead to premature convergence
due to the rapid loss of diversity.
Another signiﬁcant ﬁeld in computation-based mating concerns individuals’
phenotype information. Phenotype enables individuals to be evaluated by theirexternal or expressed features; mating strategies can be based on such information. The most straightforward metric is ﬁtness. Fitness scaling [2] provides
a stable rating and a simple way to prevent super-ﬁt individuals from dominating the population and causing premature convergence. Another way to use
ﬁtness is to devise mating schemes according to the diﬀerences in individuals’
ﬁtness. The phenotypic assortative mating in [27] exactly measures the similarity by ﬁtness. Chakraborty and Chakraborty [29] judged the allowance ofmating by a normal function of the normalized ﬁtness. This function gives ahigher probability of crossover to the partner with a closer ﬁtness.
In addition to ﬁtness, Ronald [30] proposed the concept of seduction, which
can be viewed as a secondary ﬁtness function. It encourages GA to consider
more phenotypic features in mating strategies. For example, the ﬁrst parent canbe selected according to ﬁtness, and the second by seduction based on theRoyal Road function. Ratford et al. [31] extended the use of seduction for aparallel GA to combine the eﬀects of incest prevention and assortative mating.
Mori et al. [32] restated the objective as minimizing free energy. Entropy, deﬁned by the loci of genes, can be regarded as the phenotypic estimate considered in the mating scheme.
2.2. Memory-based mating
Incest prevention through genotypic or phenotypic metrics has been shownto maintain population diversity and improve the solution. However, thesecomputation-based mating schemes must distinguish individuals’ similarities atthe cost of additional computation. Furthermore, the employed metrics signiﬁcantly inﬂuence the results of mating. Motivated by human beings’ ancestry, a supplementary memory structure is appended to individuals to enable
their ancestry to be recognized. Consequently, the determination of incest isneutral to the genotype or phenotype metrics, and does not require extra
computation to measure similarity.
Craighurst and Martin [33] considered the family tree to disallow incest byadhering to the ancestry-based incest law. The levels of the incest law deﬁne
diﬀerent numbers of members in a family tree among whom mating is forbidden. A higher level of the incest law corresponds to a more widely encompassing restriction. Experimental results validated its eﬀectiveness on
solution quality and diversity maintenance. Although the incest law yieldedsatisfactory results, it slowed convergence and was sensitive to the mutation

194

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214

rate. Fernandes and coworkers [24,34] further implemented this ancestry table
upon GA with variable population size for preserving diversity. The non-incest
method obtained better outcomes than the simple GA when applied to theRoyal Road function. The improvement increased with the level of incest
prevention. The capability of maintaining genetic diversity was also ensured.
Another way of using additional memory tags to handle diversity is to view
the subpopulation as a race. Mating is allowed only between individuals withthe same racial tag. The coexistence of diverse races (subpopulations) enables
individuals to be distributed in a more dispersed fashion and certain diversity
to be maintained; meanwhile, the evolution within respective races can also
improve the solution quality. These characteristics make it adequate to solve
multi-modal problems and reduce the computational cost of measuring distance, as required, for example, by the sharing function. Spears [35] devised
three subpopulation schemes to control mating in diﬀerent ways. The results
show that replacing distance metrics with tag bits to estimate similarity is
feasible. Ryan [36] proposed the races genetic algorithm (RGA), which applies
crossbreeding among diﬀerent races by a meta-GA in order to improve thepossibility of convergence toward global peaks. Bandyopadhyay and Pal[39,40] developed the genetic algorithm with chromosome diﬀerentiation(GACD). GACD distinguishes chromosomes into two categories (M and F),labeled by two class bits, and allows crossover only between diﬀerent categories. GACD’s superior performance was veriﬁed through many function optimization and pattern classiﬁcation problems.
Although memory-based mating schemes can prevent premature convergence and relieve computational overhead in determining bloodline, they havesome ﬂaws. First, from the viewpoint of maintaining diversity, restricted matinghas side eﬀects on the selection pressure; that is, an over-restricted strategy
diminishes the selection pressure and then results in slower convergence.
Therefore, designing a harmonious way to restrain mating without sacriﬁcing
selection pressure is very important. Second, the aforementioned works [24,33]
demonstrate that ancestry-based mating schemes are sensitive to mutation rate.
Hence, a self-adaptive mutation is suggested to overcome the diﬃculty of determining the rate and to enhance the solution quality. This paper focuses ondeveloping a novel mating scheme to meet the above requirements.

3. Tabu genetic algorithm
The proposed TGA is built upon the evolutionary structure of GA and therestrictive characteristics of TS. Rather than alternately running GA and TS,
the mating schemes of GA are combined with a memory structure and thesearch strategy of TS to augment the salient features of both algorithms simultaneously.

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214

195

Fig. 1 illustrates the ﬂowchart of the proposed approach in which mostprocedures of TGA follow the original architecture of GA. If the part of TS,
highlighted in gray, is ignored, TGA degenerates into a simple GA. The
components of TS supervise the reproduction of GA. After being produced bygenetic operators, each pair of oﬀspring undergoes the steps of TS, speciﬁcally,
the tabu list and aspiration criterion, to check whether their parents are allowed to mate. If the mating does not violate the tabu restriction or is good

TGA1. Initialization

TGA2. Evaluation

TGA3. New
generation

TGA4. Select parent.1
TGA5. Select parent.2

TGA6. Crossover

Tabu Search
No

TGA7. Tabu?
Yes

AcceptYes

TGA8. Aspiration?
No

No TGA11. Sub-population

filled?

TGA9. Deadlock?

Yes

Yes

TGA12. Survive
TGA10. Mutation
TGA13. Evaluation

No

TGA14. Termination?
TGA
complete

Fig. 1. Flowchart of TGA.

No

Reject196

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214

enough to meet the aspiration criterion, it is classiﬁed as acceptable and thechildren are delivered to the subpopulation. Otherwise, the reproduced children are rejected and this mating process returns to the step of selecting a mate.
Such a process is repeated until the mating is acceptable. Namely, courtshipcontinues until a potential parent ﬁnds its ideal mate. If the number of trials
exceeds a predeﬁned threshold, the attempt is classiﬁed as a deadlock. In such acase, the selected individuals will be mutated. They are then regarded as acceptable and delivered to the subpopulation as well.
In TGA, besides the partial variation of the original GA process, thecomponents of TS should be redesigned. The following subsections consider
the design approaches in great detail.
3.1. Representation
In TGA, a clan number is introduced into chromosomes to identify individuals. Additionally, a tabu list is appended to each chromosome in order torecord the trajectory of evolution and carry out the TS strategy. Therefore, achromosome in TGA is represented as a triple, (G; k; T ), where G is a set oforiginal genes; k is a clan number of chromosome, and T is a set of tabu list.
The clan number k is assigned uniquely at the initialization stage. During
reproduction oﬀspring inherit the clan number k from one of its parents.
Chromosomes with the same clan number indicate that they have the sameancestry; namely, they are genetically identical by descent [41,42].
The tabu list T records several clans that are forbidden to mate. In contrast
to a unitary table used in the conventional TS, tabu list T with clan number k isappended to the end of the genes in each chromosome. Such a new chromosome structure thus can accommodate the form of multiple agents in a population and the evolution in GA. Fig. 2 presents an example of representation
for the traveling salesman problem (TSP). The genes represent a sequence of
cities that the salesman must visit. An additional clan (7) with the tabu list (2,8) carries the evolutionary information of this chromosome.
3.2. Tabu list
The tabu list adopted in TGA contributes to preventing incest in a memorybased manner. Within the mating pool, each successful mating in GA can be

8

26

7

16

……

genes (cities for TSP)

22

7
clan

2

8
tabu list

Fig. 2. Example of representation for TSP.

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214

197

regarded as a move in TS. Just as TS uses the tabu list to prevent some moves
from being trapped in local optima, TGA utilizes it to track propagation andforbid incest. Accordingly, assimilation caused by inbreeding can be avoided,
and the loss of population diversity can be restrained during evolution.
In practice, if one ignores internal processes of recombination such as
crossover and mutation, the external behaviors of selection and reproduction
can be viewed as a move. Like the move in TS, the selection is monitored andrestricted by the tabu list; restated, mating with a chromosome labeled as tabu
is forbidden. Formally, the following function can be deﬁned to determine
whether two chromosomes Ci ðGi ; ki ; Ti Þ and Cj ðGj ; kj ; Tj Þ are tabu.
true; if ki 2 Tj or kj 2 Ti ;TabuðCi ; Cj Þ ¼
ð1Þ
false; otherwise:
In contrast to the incest law [33], prohibitive context in TGA is updated
when the parents mate, instead of when the oﬀspring inherit their genes. In
TGA, after a successful mating, each parent updates its tabu list with themate’s clan so that the marriage is traceable. Oﬀspring then inherit the clan andthe updated tabu list entirely from one of the parents, rather than from a
combination of both parents. Therefore the restriction in TGA is more concerned with the mating relationship than ancestry.
Oﬀspring in TGA inherit the clan identiﬁcation from one of its parents. This
rule diﬀers from that of incest law, which assigns each individual a unique
identiﬁcation. In other words, the tabu list of TGA plays the role of the patrilineal or matrilineal clan pedigree, which tracks of the trajectory of marriage
and inheritance, and prevents incest in a broad sense that includes the stepfather or stepmother.
The size of a tabu list is proportional to the size of the population, and canbe deﬁned as follows:
NT ¼ d  N ;ð2Þ

where NT is the size of the tabu list in TGA, d is the parameter of proportionality (0 6 d < 1), and N is the size of the population. The parameter of
proportionality, d, controls the tendency of the search toward exploration or
exploitation. A larger proportion corresponds to a larger tabu list, and thus alonger history for tracking and prohibition makes the selection stricter inpreventing inbreeding and encourages mating with new mates. Consequently,
the search focuses on exploration. On the contrary, a smaller parameter of
proportionality loosens the restriction and supports the search exploitation. As
the proportion decreases to zero, TGA degenerates into GA.
The operation of updating the tabu list works as a queue: a newly forbidden
clan is inserted in the ﬁrst position of the tabu list, and the other clans are
shifted to the right by one rank. The formerly last clan will be released from thetabu list and regains the qualiﬁcation to be mated. This process meets the198

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214

5 Insert tabu clan

8 2 6......

5 7 2 8 1
move

8 2 6

......

5 7

5 2 8

1
releaseFig. 3. Updating the tabu list in TGA.

requirement of degeneration of tabu tenure, as deﬁned in TS [24]. Fig. 3 illustrates the operation of updating the tabu list in TGA.
Fig. 4 depicts a more complete process in which TGA applies the tabu list ina permutation problem. The process can be divided into two parts: the left part
performs the genetic operators on the genes as in the conventional GA, and theright part handles the clan and the tabu list according to TS. In the right part,
TGA ﬁrst checks whether the mating is acceptable. If the mating does not
violate the tabu restriction or satisﬁes the aspiration criterion, it is classiﬁed as
acceptable and the reproduced children will be passed to the oﬀspring population. Thereafter, the tabu list is updated in two stages. First, each parent adds
the clan number of its mate to its tabu list. This kind of tabu list prevents
duplicated mating, which leads to the decreasing of diversity in oﬀspring
population. Second, the oﬀspring copies the updated clan number and the tabu
list from one of its parents. It inherits the information about ancestry to prevent inbreeding from causing assimilation, which would severely reduce thediversity of the population.
3.3. Aspiration criterion
As well as the tabu list, the aspiration criterion is another measure used
to judge mating. The criterion is designed to allow superior solutions tooverride the tabu restriction. Assuming that the ﬁtness of oﬀspring Ci0 is Fi0
and that the best solution so far obtained is S; then the aspiration criterion isdeﬁned as,true; if Fi0 > S;
AspirationðCi0 Þ ¼
ð3Þ
false; otherwise:

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214
3 5 1 4 2 6 5 8 2parent 1

1 4 5 2 6 3 7 1 6 2parent 2199

3 5 1 4 2 6 5 7 8 2
after
reproduction

1 4 5 2 6 3 7 5 1 6

clan

genes

TABU ?
3 5 1 4 2 6

1 4 5 2 6 3

5 8 2

7 1 6 2TABU ?

updatedtabu list

crossover
update TABU
5 6 1 4 2 3

3 1 5 2 6 4

5 7 8 27 5 1 6

update TABU

genes

clan

5 6 1 4 2 3 5 7 8 2
offspring3 1 5 2 6 4 7 5 1 6Fig. 4. Operations in TGA.

If a trial mating could produce the oﬀspring superior to the best solution so far,this mating is allowed despite its being taboo. The criterion thereby encourages
intensiﬁcation under the consideration of diversiﬁcation. Consequently, theaspiration criterion supplies a moderate selection pressure to overcome theslow convergence, which is the cost of maintaining diversity. Thus it can bringmating into harmony between selection pressure and population diversity. The
next section discusses experiments to validate the eﬀectiveness of the aspiration
criterion.
3.4. Self-adaptive mutation
In nature, the probability of mutation is typically not ﬁxed. Organisms
undergo mutation to adapt to the environment, especially when they suﬀer agreat environmental change. Therefore, the mutation rate should depend on
the organism’s surroundings. In GA, the mutation rate is generally deﬁned as aﬁxed probability. This kind of setting does not support proper response to achange in environment and does not reﬂect the reality of nature. The strategy
of adaptive parameters has been shown to be a promising way to enhanceevolutionary algorithms [43–46]. Additionally, as stated in previous work

200

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214[24,33], the performance of memory-based incest prevention is sensitive to themutation rate. It is suggested that a self-determined mutation is necessary.
Accordingly, we propose a self-adaptive mutation to determine the mutation
rate in response to the changing environment.
In TGA, when the population diversity is too low to achieve an acceptablecouple, the selection will be repeated indeﬁnitely, causing a deadlock. Technically, according to genetic drift [2,41,42], the number of clans, or the diversity, inevitably shrinks with evolution. The population will eventually converge
to a single member or clan. Then, chromosomes can no longer support successful mating, and deadlock occurs. To avoid this, a threshold (TH) is used tolimit the number of repeated trial mating (r). When an individual courts more
often than this threshold allows, but still cannot ﬁnd an acceptable mate, it isdetermined that deadlock has occurred.

true; if r P TH;
Deadlock ¼
ð4Þ
false; otherwise:
At this time the mutation operator is performed to vitalize the population to
remedy the lack of diversity. Hence, TGA dynamically and adaptively performs the mutation operator according to population diversity. The probability of mutation, triggered by deadlock, varies with evolution, and istherefore not ﬁxed. Moreover, mutation disrupts genetic information and so
the mutated individual is viewed as newborn and is assigned a new clan
number. The clan identiﬁcation thus can correspond with the genetic information. The characteristics of dynamic adaptation in response to population
circumstances are expected to enhance performance.
3.5. TGA algorithm
Based on the above deﬁnitions and discussion, the proposed algorithm TGA
is formulated as follows.
Algorithm TGA. Assume that the population P consists of N chromosomes
C1 ; . . . ; CN , with ﬁtness F1 ; . . . ; FN , respectively. The best ﬁtness S is recorded ineach generation t. The genetic operators are performed to produce oﬀspring
C10 ; . . . ; CN0 , and the deadlock criterion TH is deﬁned to prevent inﬁnite loop.
The algorithm terminates at tmax generations, at which point the obtained best
ﬁtness S is the optimized result.
TGA1. [Initialization.] Set t
0, and initialize population Pt .
TGA2. [Evaluation.] Evaluate population Pt and result in F1 ; . . . ; FN . Set
SmaxðF1 ; . . . ; FN Þ.
TGA3. [New generation.] Set n
0 and r0. (Where n is the number of
produced oﬀspring, and r is the repeated times of deadlock.)
TGA4. [Select parent 1.] Set i
randomð1; . . . ; N Þ. (Select parents Ci .)TGA5. [Select parent 2.] Set j
randomð1; . . . ; N Þ. (Select parents Cj .)C.-K. Ting et al. / Information Sciences 156 (2003) 189–214

201[Crossover.] Set p randomð Þ. If p > pc , ðCi0 ; Cj0 Þ CrossoverðCi ; Cj Þ.
[Tabu?] If TabuðCi ; Cj Þ ¼ false, go to step TGA11. (Check parents Ci
and Cj to see if they are forbidden to mate.)
TGA8. [Aspiration?] If AspirationðCi0 ; Cj0 Þ ¼ true, go to step TGA11. (Checkif oﬀspring Ci0 or Cj0 can override the tabu criterion.)
TGA9. [Deadlock?] Set r
r þ 1. If r < TH, go to step TGA5.
TGA10. [Mutation.] ðCi0 ; Cj0 Þ
MutationðCi0 ; Cj0 Þ. (If deadlock occurs, performthe mutation to activate the subpopulation.)
TGA11. [Subpopulation ﬁlled?] Insert the oﬀspring Ci0 and Cj0 into Ptþ1 , and setnn þ 2. If n < N , set r
0 and return to step TGA4.
TGA12. [Survive.] Set Ptþ1
SurviveðPt ; Ptþ1 Þ and tt þ 1.
TGA13. [Evaluation.] Evaluate population Pt , and set S
maxðF1 ; . . . FN Þ.
TGA14. [Termination?] If t < tmax , return to step TGA3. Otherwise the algorithm TGA is complete.

TGA6.
TGA7.

4. Performance evaluation
In this paper, several comprehensive experiments are conducted to evaluate
the performance of TGA. The impacts of the elements of TGA––tabu list,
aspiration criterion, and self-adaptive mutation––are ﬁrst investigated. The
variation in population diversity is also examined to verify the diversiﬁcation.
The superiority of TGA is then conﬁrmed by comparing its performance withthat of GA, TS, and hybrids of GA and TS.
The traveling salesman problem (TSP), a classical combinatorial optimization problem, is used as a benchmark to evaluate performance. This
problem involves a number of random cities, and the objective is to ﬁnd theshortest path that passes through every city once. In the experiments, thecities are generated according to the 8th DIMACS Implementation Challenge[37] for generalization and comparability. Chromosomes are encoded by theclassical permutation representation [2,3], as illustrated in Fig. 2. A population size of 100 chromosomes is used. The crossover operator adopted here
follows the partially matched crossover (PMX), which is commonly used tohandle TSP for GA [2]. The mutation operator follows the displacement
mutation [3], which randomly displaces an arbitrary section of chromosomes.
In the experiments on TGA, the probability of crossover (Pc ) is set to 1.0, andthat of mutation is neglected because an adaptive mechanism is used to determine when the mutation should be performed. Each experiment includes 20
trials. The following subsections provide more details of the evaluation experiments. Section 4.1 examines the eﬀect of the tabu list on GA’s convergence and population diversity. Section 4.2 presents the impact of theaspiration criterion upon intensiﬁcation of TGA. Section 4.3 reveals therole of self-adaptive mutation to improve TGA’s performance. Section 4.4

202

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214

compares the performance of GA, TS, Hybrids of GA and TS, and the
proposed TGA.
4.1. Tabu list
In TGA, the tabu list supports diversiﬁcation. Its restrictive characteristics
protect diversity through strategic mating and further prevent premature
convergence. Several experiments are performed on the tabu list to conﬁrm theeﬀectiveness. In these experiments, TGA denotes that the aspiration criterionand self-adaptive mutation in TGA are both disabled in order to remove theirinﬂuences on selection pressure and mutation. At ﬁrst, the probability ofmutation (PM ) is set to zero in order to identify the eﬀect of the tabu list on
convergence. As illustrated in Fig. 5, though both GA and TGA are trapped
into premature convergence due to the lack of mutation, TGA yields better
solutions than GA. This improvement is attributed to the tabu list that canmaintain diversity during evolution. Second, the performance is compared in a
general situation, in which the mutation rate is set to a ﬁxed probability,
PM ¼ 0:005, for both GA and TGA. Fig. 5 shows that TGA converges more
slowly than GA. Such a defect is expected because the tabu list attempts to
5e+07
GA (pM=0)
TGA** (pM=0)
TGA* (pM=0)
GA (pM=.005)
TGA** (pM=.005)
TGA* (pM=.005)
TGA

4.5e+07

4e+07

Tour Length

3.5e+07

3e+07

2.5e+07

2e+07

1.5e+07

1e+07

5e+06
0

200

400

600

800

1000

Generation

Fig. 5. Comparison of convergence of GA and TGA, both without mutation (PM ¼ 0) and with
mutation (PM ¼ 0:005), at the city number c ¼ 100. *: TGA without self-adaptive mutation; **:TGA without aspiration criterion and self-adaptive mutation.

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214

203

maintain diversity at the expense of the selection pressure. The next subsection
discusses an aspiration criterion, accompanied with the tabu list, to complement selection pressure and thereby overcome this defect.
A measurement of the variation in the population diversity during evolution
is required to quantify the capacity of maintaining diversity. With respect toorder-based encoding, the metrics must account for cyclic and inverse characteristics. Accordingly, Ronald [38] proposed a distance function to measuresuch a cyclic-TSP as,
di;j ¼ l  ei;j ;ð5Þwhere di;j is Ronald’s proposed distance between two chromosomes Ci and Cj ; lis the number of genes, which equals the number of cities, c; ei;j is the numberof common edges between the corresponding tours constituted by two chromosomes. Furthermore, the degree of diversity in the whole population, D, canbe deﬁned as,
D¼

N
N
X
X
2
di;j :N ðN  1Þ i¼1 j¼iþ1

ð6Þ

Fig. 6 plots the variation of population diversity with and without mutation
for GA and TGA. A higher degree corresponds to a more diverse population.
The degree of population diversity for TGA declines more slowly than that for
GA, independently of whether mutation is performed. This result conﬁrms thefact that selection with the tabu list restrains inbreeding from leading to assimilation and a monotonous population. This outcome demonstrates thatTGA with the tabu list can retard the lost of diversity.
Next, the impact of the size of tabu list on the performance of TGA isconsidered. The parameter of proportionality, d, determining the size of tabu
list, is experimentally changed from 0.1 to 0.6 in increments of 0.1. Two
population sizes (N ¼ 20 and N ¼ 100) are tested. The other parameters arecrossover rate ðPc Þ ¼ 1:0, aspiration criterion enabled, and self-adaptive mutation enabled. Table 1 lists the number of deadlocks per generation and thepercentage of deadlock occurrences in each selection. The results demonstratethat the probability of deadlocks increases with the parameter of proportionality till d ¼ 0:4. When the parameter exceeds 0.4, the probability is nearlyﬁxed. Fig. 7 shows an outcome consistent with the direct proportionality between the probability of deadlock and the size of tabu list in Table 1. Moreover, this ﬁgure shows that the probability of deadlock increases as evolution
proceeds, rather than being uniform. This phenomenon occurs in response to
the decreasing diversity. Section 4.3 further examines the interaction between
the probability of deadlock and self-adaptive mutation.
The eﬀect of diﬀerent sizes of tabu list on convergence is also examined. Fig.
8 depicts the convergence of TGA for diﬀerent parameters of proportionality

204

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214
100
GA (pM=0)
TGA** (pM=0)
GA (pM=.005)
TGA** (pM=.005)

Degree of Diversity

80

60

40

20

0
0

200

400

600

800

1000

Generation

Fig. 6. Comparison of population diversity between GA and TGA both without mutation(PM ¼ 0) and with mutation (PM ¼ 0:005), at c ¼ 100. **: TGA without aspiration criterion andself-adaptive mutation.

Table 1
Average number of deadlocks per generation for various d at c ¼ 100
d

0.1

0.2

0.3

0.4

0.5

0.6

Number of deadlocks at N ¼ 20
Number of deadlocks at N ¼ 100
Percentage of deadlocks at N ¼ 20
Percentage of deadlocks at N ¼ 100

1.72
15.68
17.2%
31.3%

5.86
30.32
58.6%
60.6%

7.61
35.20
76.1%
70.4%

8.19
36.80
81.9%
73.6%

8.46
37.24
84.6%
74.5%

8.46
36.97
84.6%
73.9%



Percentage ¼ (number of deadlocks)/(number of selections).

of the tabu list with a population size of 100. Although the algorithm with aproportionality parameter exceeds 0.4 performs as well as one with d ¼ 0:4, it
takes more time to check the tabu condition, thus being less eﬃcient. For thisreason, the parameter of proportionality, d ¼ 0:4, is suggested and adopted infollowing experiments.
4.2. Aspiration criterion
The experimental results in Section 4.1 have shown the capacity of the tabu
list to maintain population diversity. However, the tabu list achieves this goal

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214

205

100

Probability of Deadlock Occurrence (%)

Delta=0.1
Delta=0.2
Delta=0.4
Delta=0.6
80

60

40

20

0
0

200

400

600

800

1000

Generation

Fig. 7. Variation in probability of deadlock occurrence for diﬀerent proportionality parameters (d).
1.2e+07
Delta=0.1
Delta=0.2
Delta=0.4
Delta=0.6

Tour Length

1.1e+07

1e+07

9e+06
200

300

400

500
Generation

600

700

800

Fig. 8. Convergence with diﬀerent parameters of proportionality of the tabu list at c ¼ 100,
N ¼ 100.

206

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214

through restrictive mating at the expense of selection pressure. It causes thesearch to focus on exploration and mitigate exploitation, and then leads toslower convergence. The aspiration criterion is proposed to supply moderate
selection pressure to yield a good balance between exploration and exploitation.
Experiments are conducted on TGA with and without the aspiration criterion to verify the algorithm’s eﬀectiveness. At ﬁrst the oﬀspring has higher
probability to meet aspiration criterion. As evolution proceeds, the oﬀspring isharder and harder to be superior to the best solution, and the aspiration thus
occurs less often. In terms of the inﬂuence on convergence speed, Fig. 5 showsthat TGA with the aspiration criterion, TGA , converges faster in spite of theapplication of mutation. Without mutation, TGA with the aspiration criterion
converges faster at the cost of solution quality. The reason is that the lack ofmutation reduces diversiﬁcation although the tabu list provides a mechanism
to maintain diversity. This makes TGA with the aspiration criterion tend toover-exploitation and causes premature convergence. The other results with
mutation (PM ¼ 0:005) validate this inference. TGA with the aspiration criterion (TGA ) converges faster than GA and TGA without the aspiration criterion (TGA ). Moreover, it does not suﬀer from premature convergencebecause diversiﬁcation is maintained by mutation.
4.3. Self-adaptive mutation
In TGA, self-adaptive mutation dynamically performs the mutation operator in response to population diversity rather than with a ﬁxed probability.
Mutation is performed to activate the population and continue the evolution
when the diversity is so low that the individual cannot ﬁnd an acceptable mate.
A threshold number of trial mating determines whether the diversity is too low
and when mutation should be performed. A higher threshold gives individuals
more opportunities to ﬁnd an acceptable mate, but too many trials may increase the time taken in mating. As well as the deadlock threshold, the size ofthe tabu list also aﬀects the occurrence of deadlock. The descriptions in Section
3.2 and the results in Section 4.1 indicate that a larger tabu list restricts mating
more. Thus, the number of trails is prone to exceed the deadlock threshold, andthe chances of deadlock are correspondingly increased. The size of tabu list is
set as 0.4 of the population size according to the suggestion in Section 4.1 for abetter performance.
The sensitivity of the deadlock threshold (TH) to the search performance isinvestigated as follows. Fig. 9 plots the convergence and the consumed time isgiven in parentheses. These results show that the performance increases withthe level of threshold, as does the consumed time. Thus the threshold can be
determined as follows: a lower threshold is suited to faster convergence at theexpense of solution quality, whereas a higher threshold obtains better solution

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214

207

Fig. 9. Comparison of diﬀerent levels of deadlock thresholds (TH) at c ¼ 100, N ¼ 100.

but slower convergence. In the following experiments, the highest threshold,equaling the population size, N , is adopted for a better solution quality. Furthermore, the worthiness of taking this extra computation eﬀort is veriﬁed in
Section 4.4.
Fig. 10 compares diﬀerent mutation rates with self-adaptive mutation. In thecase of ﬁxed probabilities of mutation, the performance deteriorates with themutation rate as the rate exceeds 0.002. Eventually the search approaches arandom search when the mutation rate increases beyond 0.01. However, theresults in this ﬁgure clearly demonstrate that TGA with self-adaptive mutation
outperforms TGA with any ﬁxed mutation rate. In terms of solution quality
and convergence speed, the self-adaptation not only overcomes the diﬃculty ofdetermining an optimal mutation rate, but its dynamically adaptive nature alsoenhances the performance.
The variation in the mutation occurrence probability for self-adaptive
mutation is further examined. As Fig. 11 shows, self-adaptation involves dynamic mutation rather than mutation with a ﬁxed probability. Initially, the208

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214

Fig. 10. Comparison of diﬀerent mutation rates (PM ) and self-adaptive mutation at c ¼ 100,
N ¼ 100.

probability is low. As the information contained inside the population is exploited stepwise, diversity is gradually lost. The population eventually becomes
uniform and stops improving. Hence, the self-adaptive mutation in TGA is
performed with increasing frequency as a gradually strengthening force toactivate the population. The outcome presented in Fig. 11 is consistent withthis suggestion. The improved performance further conﬁrms the eﬀectivenessof this self-adaptive mutation strategy.
4.4. Performance comparison
TGA is compared with GA, TS, and GA + TS, which alternately run GA
and TS, to further establish the better performance of TGA. The 100-city
TSP is used as benchmark [37]. The population size (N ) is set to 100 chromosomes. For GA, GA + TS, and TGA, the crossover operator adopted hereis PMX; the mutation operator is displacement mutation. TS sequentiallyC.-K. Ting et al. / Information Sciences 156 (2003) 189–214

209

Fig. 11. Variation in the probability of mutation occurrence during evolution at c ¼ 100, N ¼ 100.

performs the move operator on all adjacent solutions to generate the neighborhood, and the best solution is selected as the current solution. The optimal
parameters, obtained by our many experiments, are set as crossover rateðPc Þ ¼ 1:0 and mutation rate ðPM Þ ¼ 0:002 for GA, and the tabu list has size
12 for TS. The hybrid approach, (GAn1 þ TSn2 ), alternately runs n1 generations of GA and n2 generations of TS. Three settings are proposed tosimulate the typical hybrid of GA and TS: GA10 + TS10, GA100 + TS100,
and GA100 + TS10. Their parameters are set as those of GA and TS. In
regard to TGA, it uses the same population size and crossover rate as GA,
but dynamically performs the proposed self-adaptive mutation. The size ofthe tabu list for TGA is set to 0.4 of the population size, as suggested in
Section 4.1. Experiments run 1000 generations and 20 trials for each set ofparameters.
Table 2 compares solution quality. TGA achieved the best solution on average. t-test is further used to test for statistical signiﬁcance of the diﬀerence.
The null and alternative hypotheses are as follows.

210

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214

Table 2Average (X ) and standard deviation (S) of best solutions
X
S

GA

TS

GA10 + TS10

GA100 + TS100

GA100 + TS10

TGA

11935491
49955712795811
1068378

10533845
43316510283457
65362510051794
4462108724187356133

Table 3Results of statistical test for signiﬁcance (a ¼ 0:05)
X

Y

df

t

tdf;0:05

H0

TGA

GA
TS
GA10 + TS10
GA100 + TS100
GA100 + TS1034.35 (35)23.17 (24)
36.63 (37)29.37 (30)36.23 (37))23.41)16.17)14.43)9.37)10.40)1.645)1.711)1.645)1.645)1.645

RejectRejectRejectRejectRejectdf: degrees of freedom.



H0 : X  Y P 0;
H1 : X  Y < 0:

TGA is tested as X with other algorithms as Y to conﬁrm the superiority of
TGA. Table 3 displays the statistical results of t-test, based on the data in Table
2. Given a signiﬁcance level (a) of 0.05, each t value is less than the criticalvalue tdf;0:05 ; the null hypothesis is thus rejected. These results establish that thesuperiority of TGA over other algorithms (GA, TS, and hybrids) in terms ofsolution quality is statistically signiﬁcant.
Fig. 12 compares the convergence of TGA with that of GA, TS, andGA + TS. The plot shows that TGA outperforms the three hybrid approaches,
which nevertheless yielded superior solutions to those obtained by running GA
or TS individually. Moreover, TGA and GA + TS converge faster than GA,
but slower than TS in the ﬁrst half of convergence.
The comparative results in Fig. 12 concern convergence speed in number of
iterations. However, an algorithm may spend more time on computation, while
nevertheless converging faster with respect to iterations. Each algorithm conducts a diﬀerent number of computations in each iteration, and so comparing
speeds only by iterations is unfair. Thus, the time taken in each generation,
instead of the number of iterations, is recorded and represented on the x-axis.
Each algorithm takes 20 trials to obtain the average trajectory of the convergence.
Fig. 13 compares convergence speed in terms of running time. Clearly, theinterval between two TGA samples is longer than that between two GA
samples, indicating that TGA takes more time in each generation. However,
TGA still converges faster than GA in spite of requiring more computation.
This improvement suggests that the TGA strategy does make evolution more

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214

211

5e+07
GA
TS
GA10+TS10
GA100+TS100
GA100+TS10
TGA

4.5e+07

4e+07

Tour Length

e+07

3e+07

2.5e+07

2e+07

1.5e+07

1e+07

5e+06
0

200

400

600

1000

800

Generation

Fig. 12. Comparison of GA, TS, GA + TS, and TGA in terms of generations at c ¼ 100, N ¼ 100.
5e+07
GA
TS
GA10+TS10
GA100+TS100
GA100+TS10
TGA

4.5e+07

4e+07

Tour Length

3.5e+07

3e+07

2.5e+07

2e+07

1.5e+07

1e+07

5e+06
0

20

40

60

80

100

120

140

Time (sec)Fig. 13. Comparison of GA, TS, and TGA in terms of running time at c ¼ 100, N ¼ 100.

212

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214

eﬃcient; in other words, it enhances intensiﬁcation. Also, a solution of higher
quality reﬂects the eﬀectiveness of the diversiﬁcation in TGA. Consequently,
the extra computation cost of TGA is worthwhile in terms of solution quality
and convergence speed.
5. Conclusions
This work presents a novel heuristic optimization algorithm, called TGA,
which incorporates the characteristics of TS into the mating strategy of GA.
First, an additional memory structure, which consists of a clan number and atabu list, is appended to each chromosome to record the trajectory of evolution
as a basis for the mating strategy. The tabu list contributes TGA to maintain
diversity through broad-sense incest prevention. Second, the aspiration criterion for overriding the restriction of tabu list is used to supply a moderate
selection pressure and to overcome the retardation caused by restrictive mating. As well as promoting intensiﬁcation and diversiﬁcation in the mating
strategy, TGA applies a self-adaptive mutation approach to dynamically perform the mutation operator according to the situation of the population. The
traveling salesman problem is used as a benchmark to evaluate TGA. The
comprehensive experimental results conﬁrm the eﬀectiveness of the elements of
TGA: tabu list, aspiration criterion, and self-adaptive mutation. The comparisons demonstrate that TGA outperforms GA, TS, and conventional hybrids of GA and TS, in terms of solution quality and convergence speed. Thesefavorable results show that the tabu list and the aspiration criterion constitutea harmonious mating strategy for TGA in regard to population diversity andselection pressure. They also show that the self-adaptive mutation in TGA
eﬀectively enhances the performance. Altogether, these results demonstrate thesuperiority of TGA due to the integration of tabu search and genetic algorithm
in the mating strategy.
Acknowledgements
The authors would like to thank the reviewers for their valuable comments.
This research was supported by National Science Council of Taiwan, undercontract NSC90-2416-H-327-012.
References[1] J.H. Holland, Adaptation in Natural and Artiﬁcial Systems, University of Michigan Press,
1975.
[2] D.E. Goldberg, Genetic Algorithm in Search, Optimization, and Machine Learning, AddisonWesley Publishing Company Inc., 1989.

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214

213[3] L. Davis, Handbook of Genetic Algorithms, Von Nostrand Reinhold, 1991.
[4] M. Gen, R. Cheng, Genetic Algorithms and Engineering Design, A Wiley-Interscience
Publication, 1997.
[5] K.F. Man, K.S. Tang, S. Kwong, Genetic Algorithms, Springer-Verlag, London, 1999.
[6] D. Whitley, The GENITOR algorithm and selection pressure: Why rank-based allocation of
reproductive trials is best, in: Proceedings of 3rd International Conference on Genetic
Algorithms, San Mateo, CA, 1989, pp. 116–121.
[7] F. Glover, M. Laguna, Tabu Search, Kluwer Academic Publishers, 1997.
[8] D.T. Pham, D. Karaboga, Intelligent Optimisation Techniques: Genetic Algorithms, Tabu
search, Simulated Annealing and Neural Networks, Springer-Verlag, London, 2000.
[9] F. Glover, J.P. Kelly, M. Laguna, Genetic algorithms and tabu search: Hybrid for
optimization, Comput. Oper. Res. 22 (1) (1995) 111–134.
[10] K. Handa, S. Kuga, Pollycell placement for analog LSI chip designs by genetic algorithms andtabu search, IEEE Int. Conf. Evol. Comput. 2 (1995) 716–721.
[11] A.J. Chin, H.W. Kit, A. Lim, A new GA approach for the vehicle routing problem, in:Proceedings of the 11th IEEE International Conference on Tools with Artiﬁcial Intelligence,
1999, pp. 307–310.
[12] S. Abdinnour-Helm, A hybrid heuristic for the uncapacitated hub location problem, Eur. J.
Oper. Res. (106) (1998) 489–499.
[13] A.H. Mantawy, Y.L. Abdel-Magid, S.Z. Selim, Integrating genetic algorithms, tabu search,and simulated annealing for the unit commitment problem, IEEE Trans. Power System 4 (3)(1999) 829–836.
[14] C.F. Liaw, A hybrid genetic algorithm for the open shop scheduling problem, Eur. J. Oper.
Res. (124) (2000) 28–42.
[15] L. Ozdamar, S.I. Birbil, Hybrid heuristics for the capacitated lot sizing and loading problem
with setup times and overtime decisions, Eur. J. Oper. Res. (110) (1998) 525–547.
[16] K. Nara, Genetic algorithm for power systems planning, in: Proceedings of the Fourth International Conference on Advances in Power System Control, Operation and Management, 1997.
[17] Y. Liu, L. Ma, J. Zhang, GA/SA/TS hybrid algorithms for reactive power optimization, IEEE
Power Eng. Soc. Summer Meeting 1 (2000) 245–249.
[18] K.A. De Jong, An analysis of the behavior of a class of genetic adaptive systems, Doctoral
Dissertation, University of Michigan, Ann Arbor, 1975.
[19] A. Petrowski, A new selection operator dedicated to speciation, in: Proceedings of the SeventhInternational Conference on Genetic Algorithms, 1997, pp. 144–151.
[20] M.L. Mauldin, Maintaining diversity in genetic search, Proc. Natl. Conf. AI 31 (1984) 247–250.
[21] L.J. Eshelman, J.D. Schaﬀer, Preventing premature convergence in genetic algorithms by
preventing incest, in: Proceedings of the Fourth International Conference on Genetic
Algorithms, 1991, pp. 115–122.
[22] H. Shimodaira, DCGA: a diversity control oriented genetic algorithm, IEEE International
Conference on Tools with Artiﬁcial Intelligence, 1997, pp. 367–374.
[23] K. Matsui, New selection method to improve the population diversity in genetic algorithms,
IEEE Int. Conf. Systems, Man, Cybernet. 1 (1999) 625–630.
[24] C. Fernandes, A. Rosa, A study on non-random mating and varying population size in genetic
algorithm using a royal road function, in: Proceedings of IEEE Congress on Evolutionary
Computation, Seoul, South Korea, 2001.
[25] M. Mitchell, S. Forrest, J.H. Holland, The royal road for genetic algorithms: Fitness
landscapes and GA performance, in: Proceedings of the First European Conference on
Artiﬁcial Life, 1992.
[26] R. Bian, Z. Chen, Z. Yuan, Improved crossover strategy of genetic algorithms and analysis of
its performance, in: Proceedings of the Third World Congress on Intelligent Control andAutomation, 2000, pp. 516–520.

214

C.-K. Ting et al. / Information Sciences 156 (2003) 189–214[27] S. De, S.K. Pal, A. Ghosh, Genotypic and phenotypic assortative mating in genetic algorithm,
Inform. Sci. 105 (1998) 209–226.
[28] C. Fernandes, R. Tavares, C. Munteanu, A. Rosa, Assortative mating in genetic algorithms forvector quantization problems, Proc. ACM SAC 2001 (2001) 361–365.
[29] I. Chakraborty, B. Chakraborty, Ideal marriage for ﬁne tuning in GA, in: Proceedings of IEEE
International Conference Systems, Man, and Cybernetics, vol. 1, 1999, pp. 631–636.
[30] E. Ronald, When selection meets seduction, in: Proceedings of the Sixth International
Conference on Genetic Algorithms, 1995, pp. 167–173.
[31] M. Ratford, A. Tuson, H. Thompson, An investigation of sexual selection as a mechanism forobtaining multiple distinct solutions, Emerg. Technol. (1997).
[32] N. Mori, J. Yoshida, H. Tamaki, H. Kita, Y. Nishikawa, A thermodynamical selection rule forthe genetic algorithm, Proc. IEEE Int. Conf. Evol. Comput. 1 (1995) 188–192.
[33] R. Craighurst, W. Martin, Enhancing GA performance through crossover prohibitions basedon ancestry, in: Proceedings of the Sixth International Conference on Genetic Algorithms,
1996, pp. 130–135.
[34] C. Fernandes, R. Tavares, A. Rosa, niGAVaPS––Outbreeding in genetic algorithms, in:Proceedings of the 2000 ACM Symposium on Applied Computing, 2000, pp. 477–482.
[35] W.M. Spears, Simple subpopulation schemes, in: Evolutionary Programming Conference,
1994, pp. 296–307.
[36] C. Ryan, Racial harmony and function optimization in genetic algorithms––The races genetic
algorithm, in: Proceedings of EP’95. The MIT Press.
[37] 8th DIMACS Implementation Challenge: The Traveling Salesman Problem, http://www.research.att.com/~dsj/chtsp/index.html.
[38] S. Ronald, Distance functions for order-based encodings, IEEE Int. Conf. Evolut. Comput.
(1997) 49–54.
[39] S. Bandyopadhyay, S.K. Pal, Incorporating chromosome diﬀerentiation in genetic algorithms,
Informat. Sci. 104 (1998) 293–319.
[40] S. Bandyopadhyay, S.K. Pal, Pattern classiﬁcation with genetic algorithms: Incorporation ofchromosome diﬀerentiation, Pattern Recogn. Lett. 18 (1997) 119–131.
[41] P.W. Hedrick, Genetics of Population, Jones & Bartlett Publishers, 2000.
[42] D.L. Hartl, A.G. Clark, Principles of Population Genetics, Sinauer Associates, 1997.
[43] M. Srinivas, L.M. Patnaik, Adaptive probabilities of crossover and mutation in genetic
algorithms, IEEE Trans. Systems, Man, Cybernet. 24 (4) (1994) 656–667.
[44] S.K. Pal, S. Bandyopadhyay, C.A. Murthy, Genetic algorithms for generation of classboundaries, Man, and Cybernetics, IEEE Trans. Systems 28 (6) (1998) 816–828.
[45] R. Hinterding, Z. Michalewicz, A.E. Eiben, Adaptation in evolutionary computation: asurvey, IEEE Int. Conf. Evolut. Comput. (1997) 65–69.
[46] A.E. Eiben, R. Hinterding, Z. Michalewicz, Parameter control in evolutionary algorithms,
IEEE Trans. Evolut. Comput. 3 (2) (1999) 124–141.