Expert Systems with Applications 37 (2010) 1879–1886

Contents lists available at ScienceDirect

Expert Systems with Applications
journal homepage: www.elsevier.com/locate/eswa

Multi-parent extension of partially mapped crossover for combinatorial
optimization problems
Chuan-Kang Ting a,*, Chien-Hao Su b, Chung-Nan Lee bab

Department of Computer Science and Information Engineering, National Chung Cheng University, Chia-Yi 62102, Taiwan
Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung 80424, Taiwan

a r t i c l e

i n f oKeywords:
Genetic algorithms
Multi-parent crossoverPartially mapped crossover (PMX)
Combinatorial optimization
Traveling salesman problem (TSP)a b s t r a c t
This paper proposes the multi-parent partially mapped crossover (MPPMX), which generalizes the partially mapped crossover (PMX) to a multi-parent crossover. The mapping list and legalization of PMX
are modiﬁed to deal with the issues that arise from the increase of parents in PMX. Experimental results
on ﬁve traveling salesman problems show that MPPMX signiﬁcantly improves PMX by up to 13.95% inmean tour length. These preferable results not only demonstrate the advantage of the proposed MPPMX
over PMX, but also conﬁrm the merit of using more than two parents in crossover.
Ó 2009 Elsevier Ltd. All rights reserved.

1. Introduction
Genetic algorithms (GAs) (Holland, 1975) have effectively
solved a variety of combinatorial and numerical optimization problems. The operators in GAs include the selection, crossover, mutation, and survivor. Crossover is the most salient GA operator. It
produces offspring by recombining parental genetic material. Traditionally, the number of parents used in crossover is two. Thisidea is reasonable because, to the best of our knowledge, no organisms on Earth apply multi-parent reproduction. In computer simulations, nevertheless, it is not necessary to limit the number ofparents for crossover to two. This idea, to use more than two parents in crossover, is then implemented as multi-parent crossover.
The GAs that use multi-parent crossover are named multi-parent
genetic algorithms (Ting, 2005).
Beyond two parents in binary-coded GAs, Eiben et al. proposed
scanning crossover (Eiben, Raué, & Ruttkay, 1994) and diagonalcrossover (Eiben & van Kemenade, 1997; Eiben, van Kemenade, &Kok, 1995) as the generalization of uniform crossover and onepoint crossover, respectively. Their experimental results on several
test functions show that, in terms of success rate, both scanningcrossover and diagonal crossover outperform their two-parent versions, namely uniform crossover and one-point crossover. Mühlenbein, Schomisch, and Born (1991) and Voigt and Mühlenbein(1995) introduced the concept of global recombination into GAs
as gene pool recombination. Instead of two parents, gene pool
recombination samples the genes for crossover from the gene pool,* Corresponding author.
E-mail addresses: ckting@cs.ccu.edu.tw (C.-K. Ting), b8934018@student.nsysu.
edu.tw (C.-H. Su), cnlee@cse.nsysu.edu.tw (C.-N. Lee).
0957-4174/$ - see front matter Ó 2009 Elsevier Ltd. All rights reserved.
doi:10.1016/j.eswa.2009.07.082

which consists of several pre-selected parents. Studies indicatethat gene pool recombination and its variants are easier to analyze
and can converge faster than two-parent recombination. Tsutsui
and Jain (1998) proposed multi-cut crossover and seed crossover,wherein multi-cut crossover generalizes the classic two-pointcrossover and achieves empirically better performance compared
to diagonal crossover.
For real-coded GAs, Tsutsui and Ghosh (1998) presented a seriesof multi-parent crossovers: center of mass crossover, multi-parent
feature-wise crossover, and seed crossover. They showed thatthese multi-parent crossovers can lead to better performance,
though this performance is problem-dependent. Another multiparent crossover, simplex crossover (Tsutsui, Yamamura, & Higuchi, 1999), generates offspring using the simplex sampled frommultiple parents. Experimental results show that this method performs well with three or four parents on multimodal and epistatic
problems. Kita, Ono, and Kobayashi (1999) introduced multiple
parents into unimodal normal distribution crossover to enhancethe diversity of the offspring. This multi-parent extension of unimodal normal distribution crossover exhibits an improvement insearch ability on highly epistatic problems. Gong and Ruan
(2004) proposed the ﬁtness-weighted crossover. It gives the ﬁtter
parents a bigger inﬂuencing factor, which is used to determine
the contribution of parents to their offspring.
The above literature demonstrates the superiority of multi-parent crossover over two-parent crossover. The effectiveness of these
multi-parent crossover operators is validated mostly on numerical
optimization problems (Eiben, 2002; Ting, 2005; Tsutsui & Jain,
1998). As for combinatorial optimization problems, there exists
only the adjacency based crossover (Eiben et al., 1994). Nevertheless, experimental results point out that using more than two parents in adjacency based crossover has no tangible beneﬁt. Effective

1880

C.-K. Ting et al. / Expert Systems with Applications 37 (2010) 1879–1886

multi-parent crossover for combinatorial optimization problems isstill lacking.
This paper proposes the multi-parent partially mapped crossover(MPPMX) for combinatorial optimization problems. Speciﬁcally,
MPPMX generalizes the partially mapped crossover (PMX) (Goldberg & Lingle, 1985), which is widely used for combinatorial optimization problems, e.g., Drechsler, Becker, and Göckel (1997),
Skliarova and Ferrari (2002) and Tseng, Wang, and Shih (2007).
The traveling salesman problem (TSP) is an important representative of combinatorial optimization problems. Many practical problems, such as scheduling (Ho & Ji, 2009; Pan & Huang, 2009),
manufacturing control system (Skliarova & Ferrari, 2002), and bioinformatics (Ezziane, 2006), can be transformed into the TSP. In
this paper, the evaluation of the proposed MPPMX will focus on
the performance on the TSP.
The remainder of this paper is organized as follows. Section 2
gives a brief review of GAs for combinatorial optimization problems. In Section 3, we describe in detail the proposed MPPMX. Section 4 presents a performance evaluation. Finally, conclusions are
drawn in Section 5.
2. Genetic algorithms for combinatorial optimization problems
The basic idea of GAs is to enhance candidate solutions by simulating the mechanisms of natural evolution, such as selection,
crossover, and mutation. The operation of crossover is subject tochromosome representation, which can be binary, integer, real,or order.
Order (or permutation) is the most common representation ofchromosomes with combinatorial optimization problems thatGAs have to tackle. In a 9-city TSP, for example, a visiting schedule
5–9–7–4–1–2–8–3–6 can be simply represented as a chromosome
in the form of order (5, 9, 7, 4, 1, 2, 8, 3, 6). GAs that use order representation for chromosomes are called order-based GAs.
Even though order representation facilitates GAs to handle
combinatorial optimization problems, it also causes an intrinsic
constraint in the operation of chromosomes, because no duplicate
numbers are allowed in a chromosome. Therefore, the crossoverfor binary-coded GAs, such as one-point, two-point, and uniform
crossovers, cannot be directly applied to order-based GAs. Fig. 1
illustrates the failure of two-point crossover for the TSP. The

two-point crossover yields duplicate genes 1, 2, 5 in Offspring 1
and 4, 6, 7 in Offspring 2. Thus, both offspring are illegal, i.e. infeasible for being a visiting schedule.
To address the issue of the legality of an order, several crossover
operators for order-based GAs are proposed. Partially mappedcrossover (PMX) (Goldberg & Lingle, 1985) is one of the most popular and effective crossovers for order-based GAs to deal with combinatorial optimization problems, especially the TSP. In view of theoperation, PMX can be regarded as a modiﬁcation of two-pointcrossover but additionally uses a mapping relationship to legalize
offspring that have duplicate numbers. The algorithm of PMX is given below.
Algorithm 1. Partially mapped crossover (PMX)
1. Substring selection: Cut each parent into two substrings, and then select one substring for each parent at
random.
2. Substring exchange: Exchange the two selected substrings to produce proto-offspring.
3. Mapping list determination: Determine the mapping
relationship based on the selected substrings.
4. Offspring legalization: Legalize proto-offspring with themapping relationship.

Fig. 2 illustrates how PMX legalizes the offspring in Fig. 1. Assume that the selected substrings in Step 1 are [4 3 7 6] for Parent
1 and [1 2 5 3] for Parent 2. These two substrings are then exchanged to produce proto-offspring in Step 2. Note that the proto-offspring are possibly illegal. Steps 3 and 4 in PMX then ﬁx
the illegal offspring. In Step 3, the mapping relationship is established according to the selected substrings, e.g., ‘1’ to ‘4’, ‘2’ to ‘3’
until ‘6’, and ‘5’ to ‘7’ in Fig. 2. To legalize the proto-offspring, thefourth step of PMX replaces the duplicates genes with the corresponding genes in the mapping relationship.
Mutation is another important operator in GAs. This operator
changes a small amount of genes to activate the population diversity. Several mutation operators have been proposed for orderbased GAs. This study adopts the well-known swap mutation(Syswerda, 1991), which swaps genes at two randomly chosen loci.
3. Multi-parent partially mapped crossover

Fig. 1. Failure of two-point crossover in order-based GAs.

In light of the considerable success of PMX in combinatorial
optimization problems, this paper proposes the multi-parent partially mapped crossover (MPPMX) to extend PMX into a multi-parent crossover for better performance. Satisfying the legality ofoffspring is key to the design of the crossover for order-based representation. The increase of parents, however, complicates thedetermination of the mapping relationship and the legalization

Fig. 2. Example of PMX.

C.-K. Ting et al. / Expert Systems with Applications 37 (2010) 1879–1886

process in PMX. For this, we have devised an approach for MPPMX,
wherein it constructs a unique mapping relationship in order tolegalize the proto-offspring reproduced from more than twoparents.
The proposed MPPMX follows the four-step procedure of PMX,
as shown in Algorithm 1. Nonetheless, MPPMX constructs a unique
circular list as the basis of mapping the relationship for all parents,
which is different from the mapping list of PMX. Detailed descriptions of each step are given in the following subsections.
3.1. Substrings selection
For an n-parent MPPMX, the substrings selection imitates npoint crossover. It randomly selects n crossover points to cut each1881

parent into n þ 1 substrings. Fig. 3 illustrates the case of three parents. The substrings selection cuts each parent into four substringsat three random crossover points.
3.2. Substrings exchangeThis step exchanges the selected substrings to create proto-offspring. The method for exchanging substrings is analogous withthat of multi-cut crossover (Tsutsui & Jain, 1998). As shown in
Fig. 4, MPPMX picks and recombines the substrings from each parent in a diagonal way to form an offspring. Note that both PMX andMPPMX have one-child and multiple-children versions, where theone-child version can be simply obtained by randomly choosing
one from n children.
3.3. Mapping list determination

Fig. 3. Substrings selection.

Fig. 4. Substrings exchange.

Determining the mapping list is the key point in MPPMX. To
construct a mapping list for more than two parents, MPPMX mustﬁrst randomly choose a parent as the start parent, and a locus as thestart locus. Second, a parent different from the start parent is thenchosen at random as the end parent. The end locus is the locus inwhich the gene in the end parent is the same as the gene at thestart locus. Next, a parent different from the end parent is picked
at random to serve as the start parent for the next round. The geneof the new start parent at the locus corresponding to the end locus
is determined as the element of the mapping list. This process repeats until the mapping list is completed. The pseudocode of the
mapping list determination is presented in Fig. 5.
Fig. 6 gives an example of mapping list determination in
MPPMX. First, Parent 2 is randomly chosen as the start parent
and the second locus as the start locus. The gene ‘4’ at the start locus is therefore the ﬁrst element of the mapping list. Afterwards,
Parent 1 is randomly chosen as the end parent, and its third locus
is the end locus because the gene at this locus corresponds to ‘4’.

Fig. 5. Pseudocode of mapping list determination.

1882

C.-K. Ting et al. / Expert Systems with Applications 37 (2010) 1879–1886

Fig. 6. Example of mapping list determination in MPPMX.

Next, we randomly choose Parent 3 as the second start parent. By
mapping from Parent 1 to 3 at the third locus, gene ‘8’ is determined to be the second element of the mapping list, as shown in
Fig. 6b. Through this process, we can obtain a unique mapping list
for the three parents.
In MPPMX, a deadlock may occur when there is no parent qualiﬁed to be a start parent. When this happens, MPPMX breaks thedeadlock by randomly choosing a gene from all that are available
as the next start parent and start locus. Fig. 6h shows that MPPMX
encounters a deadlock when there is no suitable start parent for
the element ‘2’. MPPMX would then randomly choose gene ‘3’ atParent 2 as the next start parent and start locus. Subject to theway of breaking the deadlock, two-parent MPPMX is not exactly
equivalent to PMX. More precisely, MPPMX is not an exact, but
an approximate, generalization of PMX in terms of the number ofparents.
3.4. Offspring legalization
In this paper, MPPMX starts legalization from the second substring even though the starting substring can be any of those available. As a result, it is not necessary for the second substring of the

proto-offspring to be legalized since there are no duplicate genes in
it at all. The remainder of the proto-offspring, on the other hand,needs to be legalized through the mapping list and order array.
The order array is an integer string used to indicate the sequenceof loci in a certain substring that needs to be checked for legality.
Here, the array is generated randomly in order to diversify thelegalization results. The process of legalization examines the offspring genes in the sequence indicated in the order array. If a geneappears only once in the proto-offspring, it is then legal and so willbypass the legalization process. Otherwise, the gene is illegal andneeds to be legalized. MPPMX will legalize it with an unused subsequent gene from the mapping list.
Fig. 7 gives an example of offspring legalization. According tothe order array, MPPMX ﬁrst checks the ﬁrst element of the third
substring for legality, namely gene ‘3’. Since gene ‘3’ appears only
once in the offspring, it is determined to be legal and thus bypasses
legalization. The next gene, ‘2’, is illegal in that it also appears inthe second substring. To legalize gene ‘2’, MPPMX searches thegenes subsequent to ‘2’ in the mapping list for an unused one. Gene
‘6’ would therefore be picked as the gene in place of ‘2’. By applying
the same procedures on the ﬁrst substring, as shown in Figs. 7d–f,
we can legalize the complete proto-offspring.

Fig. 7. Offspring legalization in MPPMX.

1883

C.-K. Ting et al. / Expert Systems with Applications 37 (2010) 1879–1886

1

1

Parent 1
Parent 2

0.8

Proportion

Proportion

0.8

0.6

0.4

0.2

0

0

20

40

60

80

0.4

0

100

0

20

40

60

Locus

Locus

(a) PMX(b) MPPMX (n=2)
1Parent 1
Parent 2
Parent 3

0.6

0.4

0.2

80

100

Parent 1
Parent 2
Parent 3
Parent 4
Parent 5
Parent 6
Parent 7
Parent 8
Parent 9
Parent 10

0.8

Proportion

0.8
Proportion

0.6

0.2

1

0

Parent 1
Parent 2

0.6

0.4

0.2

0

20

40

60

80

100

0

0

20

40

60

Locus

Locus

(c) MPPMX(n=3)(d) MPPMX(n=10)

80

100

Fig. 8. Inheritance proportions from each parent for one offspring reproduced by PMX and MPPMX using 2, 3, and 10 parents.

3.5. Complexity of MPPMX

4.1. Empirical analysis

In this paper, we conduct a worst-case complexity analysis of
MPPMX. With respect to complexity, the key steps of MPPMX are
mapping list determination and offspring legalization. In the former, the worst case of creating the list needs OðnlÞ steps for n parents with chromosome length l. In the latter, the worst case iswhen n substrings have equal length l=n, wherein all genes need
to be legalized except those in the second substring. Thus, thenumber of times that MPPMX needs to check the mapping list, inthe worst case, is

The inheritance proportion is deﬁned as the percentage of genesthat the offspring inherit from their parents. This number serves asa measure of a crossover’s level of exploitation. This study analyzes
the inheritance proportion of chromosomes with length l ¼ 100
and ﬁxed crossover points for equal-length substrings.
Fig. 8 shows that, in PMX, all of the genes of the second substring inherit from Parent 2. Only half of the genes of the ﬁrst substring inherit from Parent 1, while the other half is generated
through legalization process. This situation also occurs in two-parent MPPMX, but in the inheritance proportion, 30% of the ﬁrst substrings are lower than 50% of PMX. As explained in Section 3.4, thisdifference is caused by the deadlock in MPPMX, which decreases
the inheritance proportion. In addition, the inheritance proportion
decreases with the order of substrings since the succeeding substrings are legalized later and thus more likely to induce deadlock.

2

l l
l 2l
l ðn  1Þl nðn  1Þl; þ  þ  þ ¼
n n n nnn2n22which accounts for the complexity of Oðl Þ. To summarize the complexity in mapping list determination and offspring legalization for2
n < l, we have the worst-case complexity Oðl Þ in MPPMX.

4.2. Experimental results on the TSP
4. Performance evaluation
This work conducted a series of experiments to analyze theinheritance and evaluate the performance of MPPMX. First, we
empirically analyzed the inheritance proportion of genes in PMX
and MPPMX in Section 4.1. Second, the performance of MPPMX
is evaluated by experiments on the traveling salesman problem(TSP). The experimental results and discussion are presented in
Section 4.2.

This section examines the performance of MPPMX on ﬁve TSP
instances from TSPLIB (Reinelt, 1995): eil51, st70, pr76, lin105,
and d198. Table 1 lists the setting1 for the GA employed in our
experiments. The number of parents for MPPMX ranges from 2 to
10. Seven mutation rates ðr m Þ are tested: 0, 0.005, 0.01, 0.02, 0.03,
0.04, and 0.05. Each setting includes 30 independent runs.
1
For a more detailed description of these operators, see Bäck and Michalewicz(1997) and Eiben and Smith (2003).

1884

C.-K. Ting et al. / Expert Systems with Applications 37 (2010) 1879–1886

Table 1
Parameter setting for GA.
Parameter

Value

Representation
Population size
Population model
Parent selection
Crossover

Order
100
Generational
Roulette wheel selection
PMX
MPPMX ðn ¼ 2; . . . ; 10Þ
1.0
Swap0, 0.005, 0.01, 0.02, 0.03, 0.04, and 0.05
lþk5000 generations
30 runs

Crossover rate rc
Mutation
Mutation rate r mSurvivor selection
Termination
Number of runs

30000

80000
60000

29000

40000

Tour length

28000

20000
PMX2

4

6

8

10

27000

26000

25000

24000

rm = 0rm = 0.005
rm = 0.01
rm = 0.02
rm = 0.03
rm = 0.04
rm = 0.05

PMX

2

3

4
5
6
7
Number of parents (n)

8

9

10

Fig. 9. Mean and standard error of the best tour length for PMX and n-parent
MPPMX at different mutation rates on lin105.

Fig. 9 compares the mean best tour length obtained from PMX
and MPPMX with 2–10 parents. Due to the similarity of resultsfrom different test problems, we present here the results of thelin105 problem only. Here, the results of three representative
mutation rates are compared: MPPMX’s best ðrm ¼ 0:005Þ, PMX’sbest ðr m ¼ 0:02Þ, and the common setting ðr m ¼ 1=l  0:01Þ. The
miniature ﬁgure at the right top of Fig. 9 applies to all test mutation rates. The ﬁgure demonstrates that MPPMX with more than
two parents outperforms PMX and two-parent MPPMX. Roughly,
the performance of MPPMX improves along with the increase ofparents from the three representative mutation rates. This discrepancy between PMX and two-parent MPPMX reveals the inﬂuencesof deadlock in the mapping list determination of MPPMX.
Table 2 lists the mean and standard deviation of the best tour
lengths over 30 trials of PMX and MPPMX using different mutation
rates and numbers of parents. In terms of the respective best results for all test mutation rates, MPPMX (24444.9) enhances PMX(28409.2) by 13.95% in solution quality. In addition, the experimental results show that the suitable numbers of parents are
dependent on the adopted mutation rate. For mutation rates
rm ¼0–0.02, MPPMX using 3–10 parents can outperform PMX as
well as achieve the best performance with n ¼ 9 or 10. The
improvements of MPPMX over PMX range from 12.88% to38.63%, and all have statistical signiﬁcance, which is validated by
the one-tailed t-test with a conﬁdence level of 0.05. However, for
rm ¼ 0:04 or 0.05, MPPMX is inferior to PMX due to excessive
mutation. These phenomena occur in population sizes of 100 and
500 in our experiments.
Table 3 summarizes the best tour lengths for PMX and n-parent
MPPMX among all test mutation rates on the ﬁve TSP instanceswith population size of 100. The best numbers of parents for
MPPMX on each test TSP instance are shown in boldface. The
experimental results show that MPPMX can outperform PMX in
solution quality by 3.68% (eil51), 7.53% (st70), 5.82% (pr76),
13.95% (lin105), and 13.32% (d198). The signiﬁcance of the
improvement of MPPMX over PMX is further validated by the statistical one-tailed t-test. With a conﬁdence level 0.05, the p-values
in Table 4 indicate that MPPMX with 4–10 parents can lead to signiﬁcant improvement over PMX on all test TSP instances.
Fig. 10 depicts the convergence of PMX and MPPMX at
rm ¼ 0:01. Owning to the similarity of results in different test problems, only the results of the lin105 problem are presented here.
The ﬁgure shows that GAs using PMX converge faster than thoseusing MPPMX at the cost of solution quality. On the other hand,
the increase of parents in MPPMX slows the convergence but gives
better solution quality.

Table 2
Mean and standard deviation (in parenthesis) of the tour length over 30 trials of PMX and n-parent MPPMX on lin105. The boldface denotes signiﬁcant improvement of MPPMX
over PMX.
rm

PMX
MPPMX ðn ¼ 2Þ
MPPMX ðn ¼ 3Þ
MPPMX ðn ¼ 4Þ
MPPMX ðn ¼ 5Þ
MPPMX ðn ¼ 6Þ
MPPMX ðn ¼ 7Þ
MPPMX ðn ¼ 8Þ
MPPMX ðn ¼ 9Þ
MPPMX ðn ¼ 10Þ

0

0.05

0.01

0.02

0.03

0.04

0.05

70339.0(4918.5)
62663.0(4287.9)58222.9(2919.5)
54437.1(4561.1)
49943.8(3608.5)
47667.9(3034.5)45480.1(3207.1)
44761.6(2647.2)
44035.7(2902.8)43164.6(2655.6)28735.3(2592.6)29034.4(2454.5)28645.5(2956.8)27563.0(2374.4)
25958.1(1776.2)
26733.7(2434.6)
25584.5(1941.3)
25366.8(2572)
26540.7(2173.3)
24444.9(2013.7)28565.3(1846.1)
28935.1(2641.1)
27049.8(2545.3)
27276.8(2290.8)26427.1(2343.2)
25899.2(2536.7)
25404.7(2330.2)25680.7(2168.1)
24885.6(1923.8)25333.8(2546.0)28409.2(2527.5)28759.3(2652.8)27685.8(2499.0)25768.0(2267.6)
25995.8(1875.9)26247.1(1912.6)25045.3(2310.7)25176.9(2045.2)
24566.2(1561.9)24558.8(1765.1)

28989.6(2055.0)31685.1(2384.5)29429.3(2681.6)
28360.8(2453)
27913.7(3405.5)25111.6(2636.9)25507.5(2948.2)
25810.9(2923.0)25730.8(2225.1)
26953.8(4135.0)30243.9(2225.7)
40199.3(2887.3)
39213.7(3170.2)
41508.8(5226.8)40989.5(4795.5)35654.2(6101.7)
38338.2(5309.6)
37521(5885.7)
38755.2(5542.9)37574.3(4768.5)

33499.4(2405.7)49268.3(3090.8)52148.4(4337.3)
51193.6(5011.1)
49122(4729.6)43268.4(4495.6)
46421.7(4638.3)46825.8(5033.2)47253.6(4689.7)46225.3(4240.5)

1885

C.-K. Ting et al. / Expert Systems with Applications 37 (2010) 1879–1886

Table 3
Mean, standard deviation (in parenthesis), and the mutation rate (marked by an asterisk) corresponding to the best tour length over 30 trials of PMX and n-parent MPPMX. The
boldface denotes the best result with respect to the TSP instance.

PMX
MPPMX ðn ¼ 2Þ
MPPMX ðn ¼ 3Þ
MPPMX ðn ¼ 4Þ
MPPMX ðn ¼ 5Þ
MPPMX ðn ¼ 6Þ
MPPMX ðn ¼ 7Þ
MPPMX ðn ¼ 8Þ
MPPMX ðn ¼ 9Þ
MPPMX ðn ¼ 10Þ

eil51

st70

pr76

lin105

d198

533.52 (31.56)
0.04*
541.71 (30.74)
0.06*
527.18 (28.93)
0.05*
522.28 (28.93)
0.06*
513.86 (28.31)
0.04*
520.19 (32.03)
0.05*
517.77 (26.58)
0.06*
516.41 (28.27)
0.06*
519.09 (35.58)
0.05*
514.01 (30.48)
0.06*

1015.90 (68.79)
0.05*
1039.51 (72.28)
0.03*
1002.48 (73.47)
0.05*
973.89 (67.54)
0.04*
962.79 (66.38)
0.04*
959.57 (63.46)
0.05*
956.28 (81.60)
0.05*
951.51 (66.56)
0.05*
939.41 (63.71)
0.03*
947.07 (59.42)
0.04*

162172.2 (9898.4)
0.03*
163586.6 (10820.0)
0.03*
161547.9 (11214.7)
0.03*
157436.3 (11099.9)
0.04*
154115.7 (10660.5)
0.04*
156310.9 (11335.8)
0.04*155252.7 (10066.9)
0.04*155301.8 (10731.1)
0.04*
152737.9 (9697.3)
0.04*
153161.7 (11058.6)
0.04*

28409.2 (2527.5)
0.02*
28759.3 (2652.8)
0.02*27049.8 (2545.3)
0.01*
25768.0 (2267.6)
0.02*
25958.1 (1776.2)
0.005*
25111.6 (2636.9)
0.03*25045.3 (2310.7)
0.02*25176.9 (2045.2)
0.02*
24566.2 (1561.9)
0.02*24444.9 (2013.7)
0.005*

37275.8 (4472.8)
0.005*
37838.7 (4518.4)
0.006*
36049.1 (2803.7)
0.01*
34812.9 (3669.4)
0.01*
34220.0 (3371.5)
0.01*
34163.2 (3004.0)
0.01*
33398.7 (3253.1)
0.005*
33371.0 (3240.0)
0.01*
32309.6 (3459.1)
0.004*
33365.0 (3912.9)
0.004*

Table 4The p-values of t-test on the best tour length between n-parent MPPMX and PMX in
the TSP. The boldface denotes signiﬁcant improvement of MPPMX over PMX. The
negative p-values mean that MPPMX is inferior to PMX.
n

eil51

st70

pr76

lin105

d198

2
3
4
5
6
7
8
9
10

3.2E02
7.0E02
4.6E03
3.2E06
1.7E03
9.1E05
3.9E05
1.4E03
7.3E06

9.5E03
9.2E02
1.1E05
4.4E08
4.2E09
3.9E08
9.1E112.0E14
7.3E13

1.7E01
3.4E018.4E04
4.8E08
6.8E05
9.9E07
2.4E06
5.8E11
3.2E09

3.0E01
2.1E02
3.8E05
3.2E05
3.6E06
7.1E07
6.1E072.6E09
5.3E09

3.1E01
1.0E011.1E02
2.1E03
1.3E03
1.7E04
1.5E05
6.1E06
3.3E04

50000

PMX
MPPMX(n=2)
MPPMX(n=3)
MPPMX(n=5)
MPPMX(n=10)

45000

ents. For this, a novel approach to establish a global mapping list
for all parents is proposed. The resultant mapping list provides abasis for offspring legalization in MPPMX. The analysis shows that
2
MPPMX has the worst-case complexity of Oðl Þ.
A series of experiments were carried out to evaluate the performance of MPPMX. Experimental results on the TSP demonstrated
that, when comparing the best performance in tour length, MPPMX
can improve PMX by 3.68–13.95% on the ﬁve test TSP instances.
The signiﬁcance of such improvement is validated by a t-test. Additionally, the experimental results reveal that a suitable number ofparents for MPPMX is closely related to mutation rate.
In conclusion, MPPMX is capable of further improving the present performance of GAs using PMX on combinatorial optimization
problems. Nonetheless, experiments on more problems, such asscheduling problems, are necessary to verify the advantage andversatility of MPPMX. The reduction of time complexity in MPPMX
would be beneﬁcial to enhance it, and this could be studied in future works.

References

Tour length

40000

35000

30000

25000

20000
0.0

0.5

1.0

1.5

2.0

2.5

3.0

3.5

4.0

4.5

5.0

Generations (×10 3)
Fig. 10. Convergence of GAs using PMX and n-parent MPPMX at r m ¼ 0:01 on thelin105.

5. Conclusions
This paper presents MPPMX, a multi-parent extension of PMX.
A key point for extending PMX into a multi-parent version is todetermine the mapping relationship between more than two par-Bäck, T., & Michalewicz, Z. (1997). Test landscapes. In Handbook of evolutionary
computation. Institute of Physics Publishing and Oxford University Press. pp.
B2.7:14–B2.7:20.
Drechsler, R., Becker, B., & Göckel, N. (1997). A genetic algorithm for RKRO
minimization. Expert Systems with Applications, 12(1), 127–139.
Eiben, A. (2002). Multiparent recombination in evolutionary computing. In Advancesin evolutionary computing (pp. 175–192). Springer.
Eiben, A., Raué, P.-E., & Ruttkay, Z. (1994). Genetic algorithms with multi-parent
recombination. In Parallel problem solving from nature – PPSN III. LNCS (Vol. 866,
pp. 78–87). Springer.
Eiben, A., & Smith, J. (2003). Introduction to evolutionary computing. Natural
computing. Springer-Verlag.
Eiben, A., & van Kemenade, C. (1997). Diagonal crossover in genetic algorithms fornumerical optimization. Journal of Control and Cybernetics, 26(3), 447–465.
Eiben, A., van Kemenade, C., & Kok, J. (1995). Orgy in the computer: Multi-parent
reproduction in genetic algorithms. In Proceedings of the 3rd European conference
on artiﬁcial life (Vol. 929, pp. 934–945).
Ezziane, Z. (2006). Applications of artiﬁcial intelligence in bioinformatics: A review.
Expert Systems with Applications, 30(1), 2–10.
Goldberg, D., & Lingle, R. (1985). Alleles, loci, and the traveling salesman problem. In
Proceedings of the 1st international conference on genetic algorithms and theirapplications (pp. 154–159). Lawrence Erlbaum Associates, Publishers.
Gong, G., & Ruan, X. (2004). New multi-parent recombination genetic algorithm. In
Proceedings of the 5th world congress on intelligent control and automation (Vol. 3,
2099–2104).
Ho, W., & Ji, P. (2009). An integrated scheduling problem of PCB components on
sequential pick-and-place machines: Mathematical models and heuristic
solutions. Expert Systems with Applications, 36(3P2), 7002–7010.

1886

C.-K. Ting et al. / Expert Systems with Applications 37 (2010) 1879–1886

Holland, J. (1975). Adaptation in natural and artiﬁcial systems. University of Michigan
Press.
Kita, H., Ono, I., & Kobayashi, S. (1999). Multi-parental extension of the unimodal
normal distribution crossover for real-coded genetic algorithms. Proceedings ofthe congress on evolutionary computation (Vol. 2, pp. 1581–1588). IEEE Press.
Mühlenbein, H., Schomisch, M., & Born, J. (1991). The parallel genetic algorithm asfunction optimizer. In Proceedings of the 4th international conference on genetic
algorithms (pp. 271–278). Morgan Kaufmann.
Pan, J., & Huang, H. (2009). A hybrid genetic algorithm for no-wait job shop
schedulingproblems.
ExpertSystems
with
Applications,
36(3P2),
5800–5806.
Reinelt, G. (1995). TSPLIB. <http://www.iwr.uni-heidelberg.de/groups/comopt/
software/TSPLIB95/>.
Skliarova, I., & Ferrari, A. (2002). FPGA-based implementation of genetic algorithm
for the traveling salesman problem and its industrial application. Lecture notesin computer science (Vol. 2358, pp. 77–87). Springer.
Syswerda, G. (1991). Schedule optimization using genetic algorithms. In L. Davis(Ed.), Handbook of genetic algorithms (pp. 332–349). Van Nostrand Reinhold.

Ting, C.-K. (2005). Design and analysis of multi-parent genetic algorithms. Ph.D. thesis,
University of Paderborn, Germany.
Tseng, H., Wang, W., & Shih, H. (2007). Using memetic algorithms with guided local
search to solve assembly sequence planning. Expert Systems with Applications,33(2), 451–467.
Tsutsui, S., & Ghosh, A. (1998). A study on the effect of multi-parent recombinationin real coded genetic algorithms. In Proceedings of international conference on
evolutionary computation (pp. 828–833).
Tsutsui, S., & Jain, L. (1998). On the effect on multi-parent recombination in real
coded genetic algorithms. In Proceedings of the 2nd international conference onknowledge-based intelligent electronic systems (pp. 155–160).
Tsutsui, S., Yamamura, M., & Higuchi, T. (1999). Multi-parent recombination withsimplex crossover in real coded genetic algorithms. Proceedings of the genetic
and evolutionary computation conference (Vol. 1, pp. 657–664). Morgan
Kaufmann.
Voigt, H.-M., & Mühlenbein, H. (1995). Gene pool recombination and the utilizationof covariances for the breeder genetic algorithm. In Proceedings of the 2nd IEEE
international conference on evolutionary computation (pp. 172–177). IEEE Press.