ON ABILITY OF ORTHOGONAL GENETIC ALGORITHMS FOR
THE MIXED CHINESE POSTMAN PROBLEM
Hiroshi Masuyama
Information and knowledge Engineering, Tottori University, Koyama-cho Minami 4-101, Tottori, Japan
Tetsuo Ichimori
Information Systems, Osaka Institute of Technology, Kitayama 1-79-1, Hirakata, Japan
Toshihiko Sasama
Information and knowledge Engineering, Tottori University, Koyama-cho Minami 4-101, Tottori, Japan
Keywords: Orthogonal design, Genetic algorithm, Chin
ese postman problem, Postman’s route.
Abstract: The well known Chinese Postman Problem has many applications, and this problem has been proved to be
NP-hard in graphs where directed and non-directed edges are mixed. In this paper, in order to investigate the
salient feature of orthogonal design, we designed a genetic algorithm adopting an orthogonal crossover
seoperation to solve this (mixed Chinese Postman) problem and evaluate the salient ability. The results
indicate that for problems of small sizes, the orthogonal genetic algorithm can find near-optimal solutions
within a moderate number of generations. We confirmed that the orthogonal design shows better
performance, even for graph scales where simple genetic algorithms almost never find the solution.
However, only the introduction of orthogonal design is not yet effective for the Chinese Postman Problem
of practical size where a solution can be obtained in less than 104 generations. This paper concludes that the
optimal design scale of orthogonal array to this mixed Chinese Postman Problem does not conform to the
same scale as the multimedia multicast routing problem.
1 INTRODUCTION
The Chinese Postman Problem, as is well known, is
to find the shortest route in a graph that uses every
arc (directed or non-directed edge) and gets back to
where it started. For example in the non Eulerian
graph shown in Fig.1, since Postman’s route
traverses every arc at least once, the Postman must
passes doubly through an arc of weight 6. By
duplicating some arcs, the non Eulerian graph can
have at leaset one Postman’s route. In general, if a
given graph is a non Eulerian graph, it can be said
that the optimum solution of the Chinese Postman
Problem is a route where the total weight of
duplicated arcs is the minimum. When a given graph
is an Eulerian graph, the solution is uniquely
determined.
Though this problem has many applications,
in
cluding robot exploration and analyzing interactive
systems and web site usability (Thimbleby, 2003),
this problem has been proved to be NP-hard. The
multimedia multicast routing problem is also NP-
hard. Paper (Zhang and Leung, 1999) proposed an
orthogonal genetic algorithm for this latter problem,
and concluded on the basis of solving a benchmark
test problem, that for practical problem sizes the
orthogonal genetic algorithm can find near-optimal
solutions within a moderate number of generations.
Its salient feature is to incorporate an experimental
design method called orthogonal design into the
crossover operation. In order to further investigate
this salient feature of orthogonal design, which was
applied to the sampling of genes from the parents for
crossover, we will design a genetic algorithm
adopting an orthogonal crossover operation to solve
the mixed Chinese Postman Problem and evaluate
the salient ability.
For the problem which we treat is called the
C
hinese postman problem on mixed networks
(WCPP), heuristic solution procedures have been
proposed to solve approximately (Edmond and
Johnson, 1979)(Pearn and Liu, 1995)(Frederickson,
1979).
39
Masuyama H., Ichimori T. and Sasama T. (2006).
ON ABILITY OF ORTHOGONAL GENETIC ALGORITHMS FOR THE MIXED CHINESE POSTMAN PROBLEM.
In Proceedings of the First International Conference on Software and Data Technologies, pages 39-45
DOI: 10.5220/0001314600390045
Copyright
c
SciTePress
Figure 2: A basic process of genetic algorithm.
1. [Start] Generate random population of t
chromosomes (suitable solutions for the problem).
2. [Fitness] Evaluate the fitness f(x) of each
chromosome x in the population.
3. [New population] Create a new population by
repeating following steps until the new population
is complete.
1. [Selection] Select two parent chromosomes
from a population according to their fitness
(the better their fitness, the better their
chance of being selected).
2. [Crossover] Use crossover probability to
cross over the parents and form a new
offspring (children). If no crossover was
performed, the offspring would be an exact
copy of the parents.
3. [Mutation] Use mutation probability to
mutate new offspring at each locus (position
in the chromosome).
4. [Accepting] Place new offspring in a new
population.
4. [Replace] Use newly generated population to
continue the algorithm.
5. [Test] If the end condition is satisfied, stop, and
return the best solution in the current population.
6. [Loop] Go to step 2.
Figure 1: An example of route in Chinese postman
problem.
2 GENETIC ALGORITHM AND
ORTHOGONAL ARRAY
REPRESENTATION
A genetic algorithm (GA) is a heuristic approach
used to find approximate solutions to knotty
problems through application of the principles of
biological evolution. Genetic algorithms make the
best of biologically derived approaches such as
inheritance, mutation, natural selection, and
recombination (or crossover). Genetic algorithms are
a particular class of evolutionary algorithms where a
population of abstract representations (called
chromosomes) of candidate solutions (called
individuals) evolve into better solutions. That is,
information treated in GA can be classified into two
structures: phenotype and genotype. Phenotype
represents information in the biological world, and
genotype represents information in a population of
chromosomes. By encoding, the information in a
phenotype can be transferred into a genotype, and by
decoding the opposite occurs. We will chiefly
consider that in a genotype. Even though some
different encodings are possible, in general the
solutions are represented in binary strings of 0s and
1s.
In this mixed Chinese postman problem, we will
treat a given graph G whose every arc is a directed
edge or a non-directed edge. We will consider a
directed graph G’ where every non-directed edge in
the given graph is changed into two directed edges
with different directions each other. Then, we can
make our chromosome type as an integer string
whose element means the number of times that the
postman passes the arc. The length of a string is the
number of edges of G’. Therefore, in this mixed
Chinese postman problem, the solutions are
represented in strings of integer. The evolution starts
from a population of completely random individuals
and goes on in generations. In each generation, the
fitness of the whole population is evaluated, and
multiple individuals are stochastically selected from
the current population (by judging their fitness) and
modified (so called by mutation or recombination) to
form a new population, which becomes current in
the next iteration of the algorithm. The general
process of GA is known, and is shown in Fig.2.
Orthogonal array was developed to find the
smallest, yet most cost effective, and therefore best,
combination by which many and consumptive
ICSOFT 2006 - INTERNATIONAL CONFERENCE ON SOFTWARE AND DATA TECHNOLOGIES
40
combinations can be avoided (Fang and Wang,
1994). An orthogonal array is represented in
Table.1-1 by L
9
(3
4
), where 3, 4, and 9 mean the
number of kinds of entries, columns, and rows,
respectively. In general, we let L
m
(n
k
) denote an
orthogonal array for k factors, n levels, and m
combinations of level to be tested. Orthogonal arrays
can be systematically built. Label L comes
originally from a “Latin” square, which is defined as
a matrix where no two entries in a row (or a column)
have the same value. It has been proved that the
orthogonal design is optimal for use as an additive
model and a quadratic model, and that the selected
combinations are good representatives for all the
possible combinations (Wu, 1978). The problem of
building an orthogonal array is the same as the
problem of finding m nodes which are at the
maximum distance between any pair in the (k )-
dimensional hypercube. Table 1-2 shows 9 nodes
corresponding to 9 combinations (on an 8-
dimensional hypercube) in Table 1-1.
nlog
Table 1-1: A representation of orthogonal array L
9
(3
4
).
Table1-2: 9 nodes corresponding to 9 combinations on a
(k log n)-dimensional hypercube.
Combination Factor1 Factor2 Factor3 Factor4
1st 0 1 0 1 0 1 0 1
2nd 0 1 1 0 1 0 1 0
3rd 0 1 1 1 1 1 1 1
4th 1 0 0 1 1 0 1 1
5th 1 0 1 0 1 1 0 1
6th 1 0 1 1 0 1 1 0
7th 1 1 0 1 1 1 1 0
8th 1 1 1 0 0 1 1 1
9th 1 1 1 1 1 0 0 1
3 EXPERIMENTAL DESIGN
METHODS
In this section, we introduce the concept of
experimental design methods for our experiment
mentioned later.
3.1 Phenotype
Roads are modeled as a graph G = (V,E), where V is
a set of nodes and E is a set of arcs. By making
every non-directed arc express as two directed arcs,
change a given graph G into a directed graph G’. As
mentioned before, the optimum solution is a route
where the total weight of duplicated arcs is the
minimum. We number the edges in G’ from 1 to t.
We can then represent any route R of the graph G’
as an t-tuple (e
1
, e
2
, …, e
t
), where any element
(which means a gene) e
i
is defined as follows:
e
i
= The number of times that the postman passes
arc i
From the above definition, e
i
is a non negative
integer and can become 0 if e
i
is represented for one
of two directed edges changed from non-directed
edge in G. For example, assuming that edge with
weight 4 is r
4
, R in Fig.1(b) can be represented as
(e
r4
, e
r8
, e
r5
, e
r9
, e
r3
, e
r3
, e
r2
, e
r6
) =( 1, 1, 1, 1, 1, 0, 1,
2). Since R in Fig.1(b) is a Postman’s route, then this
phenotype ( 1, 1, 1, 1, 1, 0, 1, 2) is a solution.
3.2 Fitness
The Postman can return to the starting point if G is
an Eulerian graph. If G is a non Eulerian graph, in
order to return to the starting point the postman must
traverse some arcs more than once. In general, if G
is a non Eulerian graph, it can be said that the
optimum solution of the mixed Chinese Postman
Problem is a route where the total weight of
duplicated arcs is the minimum. When G is an
Eulerian graph, the solution is uniquely determined.
In order to set the fitness of the optimum solution
to maximum, we will prepare the following function
f of fitness.
⎩
⎨
⎧
=
otherwise ;0
route sPostman' hasG if arcs); gduplicatin of weight (total / 1
f
3.3 Orthogonal Crossover
In order to fit the mixed Chinese postman problem,
we interpret orthogonal array L
m
(n
k
) to be an
orthogonal array for k factors divided from n levels
(parent chromosomes), and m combinations of levels
(samplings at the time of crossover). Let orthogonal
Combination Factor1 Factor2 Factor3 Factor4
1st X X X X
2nd X Y Y Y
3rd X Z Z Z
4th Y X Y Z
5th Y Y Z X
6th Y Z X Y
7th Z X Z Y
8th Z Y X Z
9th Z Z Y X
ON ABILITY OF ORTHOGONAL GENETIC ALGORITHMS FOR THE MIXED CHINESE POSTMAN PROBLEM
41
array L
4
(2
3
) be shown in Table 2. Obeying the above
interpretation of L
4
(2
3
), 2 parent chromosomes are
divided into 3 factors each, and we obtain 4 new
chromosomes as shown in Fig.3 In the case of
L
9
(3
4
) , we obtain 9 new chromosomes from 4 parent
chromosomes as shown in Fig.4.
Table 2: Orthogonal array L
4
(2
3
).
Combination Factor1 Factor2 Factor3
1st X X X
2nd X Y Y
3rd Y X Y
4th Y Y X
Orthogonal crossover
X
) 11
213
201 ( )
(
) 21
211
201 ( )
(
) 21
213
110 ( )
(
)
11
211
110 ( )
(
3 2 1 4
3 2 1 3
3 2 1 2
3 2 1 1
= =
= =
= =
= =
x
y
y
O
y
x
y
O
y
y
x
O
x
x
x
O
, , ,
,
4 3 2 1
O O O O
Y
X
Children:
Parents:
( 110 211 11 )
( 201 213 21)
1
x
2
x
3
x
1
y
2
y
3
y
Y
Figure 3: Orthogonal crossover for L
4
(2
3
).
Figure 4: Orthogonal crossover for L
9
(3
4
).
3.4 Creation of the Initial
Population of Chromosomes
using an Orthogonal Array
In order to create the initial population of
chromosomes which resemble closely as possible as
they can, we will present a method to use an
orthogonal array in the creation of the initial
population of chromosomes.
A chromosome is an t-tuple whose the i-th
element is the number of times passing through the
i-th arc by the Postman’ route. Let divide a
chromosome into the number of factors. The range
of the random numbers is divided into the number of
levels of orthogonal array. In addition, for each one
of the same levels in orthogonal array select, let
randomly correspond to a random number in the
same range of the random numbers.
Let us take L
4
(2
3
) shown in table 3 and t=12 as
an example. Since a t-tuple is divided into 3 factors,
then we can represent 4 chromosomes based on
L
4
(2
3
) as follows:
X X X X X X X X X X X X
X X X X Y Y Y Y Y Y Y Y
Y Y Y Y X X X X Y Y Y Y
Y Y Y Y Y Y Y Y X X X X
Each X and Y are corresponded to a random
number in the ranges 0~6 and 7~12, respectively.
Then, we obtain the following initial population of
chromosomes (4 chromosomes) as an example.
1 3 5 3 5 4 2 4 5 5 4 6
5 6 4 2 7 9 8 9 10 7 9 11
8 10 9 7 2 5 1 4 11 8 9 10
7 11 8 9 10 7 8 12 2 5 1 3
11) 11 02 (11
1
X
x
x
x
x
4 3 2
21) 13 12 (20
4 1
Y
y
y
y
y
3 2
22) 11 01 (12
432 1
Z
z
z
z
z
) 11 13 01 12 ( ) (
) 22 11 12 12 ( ) (
21) 11 02 12 ( ) (
21) 11 01 20 ( ) (
11) 11 12 20 ( ) (
22) 13 02 20 ( ) (
) 22 11 01 11 ( ) (
) 21 13 12 11 ( ) (
) 11 11 02 11 ( ) (
43 2 1 9
43 2 1 8
43 2 1 7
43 2 1 6
43 2 1 5
43 2 1 4
4 3 2 1 3
43 2 1 2
43 2 1 1
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
x
y
z
z
O
z
x
y
z
O
y
z
x
z
O
y
x
z
y
O
x
z
y
y
O
z
y
x
y
O
z
z
z
x
O
y
y
y
x
O
x
x
x
x
O
Orthogonal crossover
Parents: X , Y , Z
Children: O
1
, O
2
, O
3
,
…
, O
9
4 EXPERIMENT
In this section, we will explain the experiments we
performed.
4.1 Graphs
We used random graphs shown in Table 4. We
applied the Genetic algorithm 30 times to each graph
and evaluated the mean values.
Table 4: Experimental graphs.
|V| |E| Total weight
5 7 44
4.2 Orthogonal Genetic Algorithm
(OGA)
We developed the following algorithm, as shown in
Fig.5, where an initial group starts from a population
of completely randomly generated individuals, and
ICSOFT 2006 - INTERNATIONAL CONFERENCE ON SOFTWARE AND DATA TECHNOLOGIES
42
the probabilities of crossover and mutation are 1.0
and 0.5, respectively.
Inputs: Graph G=(V,E), edge cost C(e) and node
degree deg(v)
Output: binary strings representing the Euler route
Step1) Initialization
Randomly create an initial generation of N
binary string P
0
= { X
1
, X
2
,…, X
N
}, X = {
x
1
, x
2
,…, x
k
}
and initialize the generation number gen
to 0.
* X is a chromosome, k = |V|
Step 2) Population Evolution
WHILE ( gen < MAX_GEN )
BEGIN
4.3 Simple Genetic Algorithm (SGA)
The simple genetic algorithm adopts a one-point
crossover in Step 2.1 instead of orthogonal
crossover.
4.4 Another Orthogonal Genetic
Algorithm using Orthogonal
Array in the Creation of the
Initial Population of
Chromosomes (OGA
2
)
This algorithm uses an orthogonal array also in Step
1 in Fig.5 instead of random number, and the
utilization method is shown in 3.4.
4.5 Results
Fig.6-1 shows the relationship between the number
of obtained Eulerian graphs and the number of
generations. On the other hand, Fig.7-1 shows the
relationship in the case where orthogonal array is
used in the creation of initial population of
chromosomes. Fig.6-2 shows the relationship
between the obtained minimum weight of the
Postman route and the number of generations.
Fig.7-2 shows the relationship in the case where
orthogonal array is used in the creation of initial
population of chromosomes. These results mean that
our orthogonal genetic algorithm shows better
performance, especially in L9(3
4
). SGA almost
never finds the solutions for Problem 3 where the
number of edges is 7.
For reader’s information, we show the
relationship between the number of generations and
the computation time required in 3 algorithms ( SGA,
OGA, and OGA
2
) in Tables 5 and 6.
In this mixed Chinese postman problem we
treated, in less than 10
4
generations we can obtain a
solution in graphs with nodes of less than 11.
However, we can’t obtain a solution in 2 or 3 days
for the larger sizes.
For reference we will show the data in the case of
non directed graphs G’’=(V’’, E’’), where |V’’|= 20,
|E’’|=30, total weight=178. The Chinese Postman
problem for non directed graphs belongs in Class P.
Figs.8-1 and 8-2 show the relationship between two
numbers of obtained Eulerian graphs and
generations, and the relationship between the
obtained minimum weight of the Postman route and
the number of generations, respectively.
Figure 5: A orthogonal genetic algorithm.
5 CONCLUSION
In order to investigate the salient feature of
orthogonal design, we designed a genetic algorithm
adopting an orthogonal crossover operation in the
mixed Chinese Postman Problem and evaluated the
salient ability. The orthogonal design shows better
performance, even for graph scales where simple
genetic algorithms almost never find the solution.
The experimental results show that, for problems of
non practical sizes, the orthogonal genetic algorithm
using the orthogonal array L
9
(3
4
) can find close-to-
optimal solutions within a moderate number of
generations. This optimal scale of orthogonal array
was confirmed for the multimedia multicast routing
problem of practical size (Zhang and Leung, 1999).
However, this orthogonal design is not yet effective
for the mixed Chinese Postman Problem of practical
sizes. For more effective computation, our one
possible extension of this research can be considered
as to incorporate the orthogonal array into the
DO N/2 times
BEGIN
Step 2.1) Orthogonal Crossover
Randomly select n parents strings from
P
gem
and perform orthogonal crossover
on them to generate m offspring o
1
,
o
2
,…, o
m
.
Step 2.2) Mutation
To perform mutation of offspring, flip
every bit in this string with a small
probability p.
Step 2.3) Select
Calculate the offspring fitness f, and
sort them by f, and choose n for the
next generation.
END
Step 3) Increment the generation number gem by 1.
END
ON ABILITY OF ORTHOGONAL GENETIC ALGORITHMS FOR THE MIXED CHINESE POSTMAN PROBLEM
43
0
10
20
30
40
50
60
70
80
90
100
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
Number of
g
enerations
Number of Eulerian graphs
SGA
OGA using L4
OGA using L9
Figure 6-1: Relationship between two numbers o
f
obtained Eulerian graphs and generations.
0
20
40
60
80
100
120
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
Number of
g
enerat ions
Obt ained minimum weight o
f
Euler route
SGA
OGA using L4
OGA using L9
Figure 6-2: Relationship between the obtained minimum
weight of the Postman route and the number of
generations.
0
10
20
30
40
50
60
70
80
90
100
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
Number of
g
enerat ions
Number of Eulerian graph
s
N
o
n
Us
in
g
L4
Us
in
g
L
9
Figure 7-1: Relationship between two numbers o
f
obtained Eulerian graphs and of generations in the case
where orthogonal array is used in the creation of initial
population of chromosomes.
0
10
20
30
40
50
60
70
80
90
100
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
Number of
g
enerations
Obtained minimum weight of
Euler rout e
N
o
n
Us
in
g
L4
Us
in
g
L
9
Figure 7-2: Relationship between the obtained minimum
weight of the Postman route and the number o
f
generations in the case where orthogonal array is used in
the creation of initial population of chromosomes.
SGA
OGA
using
L
4
(2
3
)
OGA
using
L
9
(3
4
)
generation
time
(sec)
time
(sec)
time
(sec)
1000 247.1 279.8 437
2000 252.5 286.4 447
3000 257.8 292.6 456.6
4000 263.3 298.4 465.8
5000 268.3 304.4 475
6000 273.8 310.3 484.4
7000 279.1 316.2 493.6
8000 284.5 322.1 502.9
9000 289.9 328.1 512.5
10000 295.3 333.9 521.7
Table 5: Computation time required at 1000~10000
generations.
Table 6: Computation time required at 1000~10000
generations.
OGA
using
L
9
(3
4
)
OGA
2
using
L
4
(2
3
)
OGA
2
using
L
9
(3
4
)
generation
time
(sec)
time
(sec)
time
(sec)
1000 437 428.3 433.4
2000 447 437.7 443.2
3000 456.6 447.3 452.7
4000 465.8 456.4 462.3
5000 475 465.7 471.6
6000 484.4 474.7 480.9
7000 493.6 483.9 490.3
8000 502.9 493.1 499.5
9000 512.5 502.2 508.6
10000 521.7 511.4 517.9
ICSOFT 2006 - INTERNATIONAL CONFERENCE ON SOFTWARE AND DATA TECHNOLOGIES
44
experimental design methods of setting an initial
group of populations. We performed this extension.
The experiment results show no innovative
improvement.
REFERENCES
Thimbleby, H., 2003. The directed Chinese postman
problem. In Software - Practice & Experience, Vol.33,
No.11, pp.1081-1096.
Zhang, Q. and Leung, Y., 1999. An orthogonal genetic
algorithm for multimedia multicast routing. In IEEE
Trans. on Evolutionary Computation, Vol.3, No.1,
pp.53-62, April.
Fang, K.T. and Wang, Y., 1994, Number-Theoretic
Methods in statistics. New York, Chapman & Hall.
Wu, Q., 1978. On the optimality of orthogonal
experimental design. In Acta Mathematicae Sinica,
Vol.1, No.4, pp.283-299.
Sasama, T., Masuyama, H. and Ichimori, T., 2002. On
Fault Tolerance of Hypercubes using Subcubes. In Int.
Journal of Reliability, Quality and Safety Engineering,
Vol.9, No.2, pp.151-161.
Leung, Y., Li, G. and Xu, Z., 1998. A Genetic Algorithm
for the Multiple Destination Routing Problem. In
IEEE Trans. on Evolutionary Computation, Vol.2,
No.4.
Zhang, Q. and Leung, Y., 1999. An Orthogonal Genetic
Algorithm for Multimedia Multicast Routing. In IEEE
Trans. on Evolutionary Computation, Vol.3, No.1.
Edmond, J. and Johnson, E., 1979. Matching, Euler tours,
and the Chinese postman. In Mathematical
Programming, No.5, pp.538-554.
Pearn, W. L., and Liu, C. M., 1995. Algorithms for the
Chinese postman problem on mixed networks. In
Computers & Operations Research, Vol.22, No.5,
pp.479-489, May.
Frederickson, G.N., 1979. Approximation algorithms for
some postman problems. In J. Assoc. Comput. Mach.
Vol.26, pp.538-554.
Figure 8-1: Relationship between two numbers of obtained
Eulerian graphs and generations.
Figure 8-2: Relationship between the obtained minimum
weight of the Postman route and the number of
generations.
ON ABILITY OF ORTHOGONAL GENETIC ALGORITHMS FOR THE MIXED CHINESE POSTMAN PROBLEM
45
