Artigo Nó Profundidade

Download as pdf or txt
Download as pdf or txt
You are on page 1of 10

Node-Depth Encoding for Evolutionary

Algorithms Applied to Network Design


A.C.B. Delbem, Andre de Carvalho, Claudio A. Policastro,
Adriano K.O. Pinto, Karen Honda, and Anderson C. Garcia
University of Sao Paulo - ICMC - USP, Sao Carlos - SP, Brazil
{acbd,andre,akogata,karen}@icmc.usp.br, claudio.policastro@terra.com.br,
anderson@grad.icmc.usp.br
Abstract. Network design involves several areas of engineering and science. Computer networks, electrical circuits, transportation problems,
and phylogenetic trees are some examples. In general, these problems
are NP-Hard. In order to deal with the complexity of these problems,
some alternative strategies have been proposed. Approaches using evolutionary algorithms have achieved relevant results. However, the graph
encoding is critical for the performance of such approaches in network design problems. Aiming to overcome this drawback, alternative representations of spanning trees have been developed. This article proposes an
encoding for generation of spanning forests by evolutionary algorithms.
The proposal is evaluated for degree-constrained minimum spanning tree
problem.

Introduction

Network design problems (NDPs) are present in several areas. The minimum
spanning tree problem (MSTP) is an example. In the real world, many NDPs
can be seen as extensions of the MSTP like, for example, telecommunication
network design, computer network restoration, transportation problems, and
determination of phylogenetic trees [1], [2], [3], [4], [5]. However, these extensions
are in general NP-Hard [6], [7]. In order to deal with such complexity, some
alternative strategies have been developed. Many of them utilize evolutionary
approaches, with relevant results [2], [4], [5], [7], [8], [9].
Nevertheless, evolutionary algorithms (EAs) using conventional encodings
produce many unconnected components or acyclic graphs when applied to large
systems. The production of such graphs may consume a large amount of computational time, which reduces the eciency of the EA approach. Depending on
the adopted encoding, the generated spanning trees may be very dierent from
their parents. Consequently, the convergence of EAs may be very slow.
To overcome this problem, an ecient representation should produce only
connected components and acyclic graphs. Moreover, child spanning trees should
resemble their parents. In this paper, we propose a representation with such
required encoding features1 .
1

References [10], [11] discuss more about representation characteristics for Evolutionary Algorithms.

K. Deb et al. (Eds.): GECCO 2004, LNCS 3102, pp. 678687, 2004.
c Springer-Verlag Berlin Heidelberg 2004


Node-Depth Encoding for Evolutionary Algorithms

679

The proposed approach generates spanning forests [12], while the available
ones focus on the production of spanning trees [10], [6], [7], [8]. Its purpose is a
more general representation, since several NDPs can be modelled as forests. The
proposal performance was evaluated for degree-constrained minimum spanning
tree problem.
The next section introduces the proposed representation. Sections 3 and 4
describe the correspondent operators. Section 5 presents experimental results
for the degree-constrained minimum spanning tree. Final considerations are presented in Section 6.

The Encoding

The proposed encoding is based on the concepts of chains and node depth in
a graph tree. The representation consists basically of linear lists containing the
tree nodes and their depths. The order the pairs (node,depth) are disposed
in the list is important and depends on the node position in an intermediate
representation, which utilizes a special kind of graph chain2 .
Next Section presents the intermediate representation. Section 2.2 introduces
the node-depth encoding proposed.
2.1

Intermediate Representation

The intermediate representation utilizes a special set of graph chains. This set
consists of the chains connecting a leaf to a root. This type of chain is called
main chain. Trees may be represented by main chains. Moreover, a forest can
be represented by the union of the main-chain encodings of its trees.
A tree has a number of main chains equal to its number of leaves l. The set of
all l main chains is a tree representation. For example, the representation of the
tree from Figure 1(a) is in Figure 1(b). Figure 1(c) shows the same set of chains
disposed in a dierent order. In this arrangement, nodes repeated in dierent
chains are side by side. Such chains are said to be properly grouped.
The node-depth encoding requires a tree to be represented by its main chains
properly grouped, which will be called intermediate representation.
2.2

The Node-Depth Representation

From the intermediate representation, we obtain the proposed encoding as follows.


1. Eliminate the repeated nodes in dierent chains. This simplication is illustrated in Figures 2(a) and 2(b);
2. Store the remaining nodes with their depths in a linear list (which may be
an array T ). In this way, each element of the list should be a pair containing
a node and its depth (see Figure 2(c)).
2

An edge-sequence in which all the edges and nodes are distinct is called a chain.

680

A.C.B. Delbem et al.

10

12

13

11

14

1 3 4 5 14
128
1 3 4 11 12 13
134 5 6 7
1 3 9 10
1 3 4 5 15

15

(a) A graph with a


spanning tree indicated by thick edges

128
1 3 9 10
1 3 4 11 12 13
1 3 4 5 14
134 5 6 7
1 3 4 5 15

(b) The main chains of


the spanning tree

(c) The main chains


properly grouped

Fig. 1. A graph with a spanning tree and its main chains

The pairs must be disposed in the list in the same order they are in the
intermediate representation, considering the chains from top to bottom and, in
each chain, the nodes from left to right (see Figure 2(c)).

128
1 3 9 10
1 3 4 11 12 13
1 3 4 5 14
134 5 6 7
1 3 4 5 15

(a) Properly grouped main


chains of a spanning tree

128
3 9 10
4 11 12 13
5 14
6 7
15

(b) Representation by main


chains without repeated
nodes

0 1 2 1 2 3 2 3 4 5 3 4 4 5 4
1 2 8 3 9 10 4 11 12 13 5 14 6 7 15

depth
node

(c) Node-depth Representation


Fig. 2. Node-depth encoding from the intermediate representation

2.3

Forest Encoding

The proposed forest encoding is composed by the union of the encodings of all
trees of a forest. In this way, the forest data structure can be easily implemented

Node-Depth Encoding for Evolutionary Algorithms

681

using an array of pointers, where each pointer indicates the node-depth encoding
of a tree of the forest.

Operators

This Section presents two operators (called operator 1 and operator 2) to


generate new spanning forests using the node-depth encoding. Both operators
generate a spanning forest F  of a graph G when they are applied to another
spanning forest F of G.
The results produced by the application of both operators are similar. The
application of the operator 1 (or 2) to a forest is equivalent to transfer a subtree
from a tree Tf rom to another tree Tto of the forest. Applying operator 1, the root
of the pruned subtree will be also the root of this subtree in its new tree (Tto ).
On the other hand, the transferred subtree will have a new root (any node of
the subtree dierent from the original root) when applying operator 2.
In this way, the operator 1 can produce simple and small changes in the
forest. The operator 2 can generate larger and more complex alterations.
The operator 1 requires a set with two nodes previously determined: the
prune node p, which indicates the root of the subtree to be transferred; and the
adjacent node a, which is a node of a tree dierent from Tf rom and that is also
adjacent to p in G.
The operator 2 requires a set with three nodes: the prune node p, the adjacent
node a, and the new root node r of the subtree.
In the following, we explain both operators considering that the required set
of nodes were previously determined. We show how to eciently obtain these
sets of nodes in Section 4.
3.1

Operator 1

In the description of the operator 1, we consider that the nodes p and a were
previously chosen and that the node-depth representation were implemented
using arrays. Besides, we assume the indices of p (ip ) and a (ia ) in the arrays
Tf rom and Tto , respectively, are also known.
The operator 1 can be described by the following steps (see Figures 3(a),
3(b) and 3(c)):
1. Determine the range (ip -il ) of indices in Tf rom corresponding to the subtree
rooted at the node p. Since we know ip , we only need to nd il . The range
(ip -il ) corresponds to the consecutive nodes x in the array Tf rom such that
ix ip and dx dp (the dashed lines in Figure 3(a)), where dx is the depth
of the node x;
2. Copy the data in the range ip -il from Tf rom into a temporary array Ttmp
(containing the data of the subtree being transferred), see Figure 3(b). The
depth of each node x from the range ip -il is updated as follows: dx = dx
dp + da + 1;

682

A.C.B. Delbem et al.


3. Create an array Tto
containing the nodes of Tto and Ttmp (i.e., generate a
new tree connecting the pruned subtree to Tto ), see Figure 3(c);
4. Construct an array Tf rom comprising the nodes of Tf rom without the nodes
of Ttmp ;
5. Copy the forest data structure F to F  exchanging the pointers to the arrays

Tf rom and Tto for pointers to the arrays Tf rom and Tto
, respectively.

2
8
3

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

T_from

p
4

6
10

p
4

0
11

11
T_to

6
T_tmp

(a) Tto , Tf rom and their node-depth representations

(b) Ttmp and its


node-depth representation

2
8
3

1
9

T _from

0 1 2 2 3 3 3
3 1 2 7 8 9 10

10
p
11
T _to

1 2 2
4 5 6

0 1 2 2
11 4 5 6


(c) Tto
, Tf rom and their node-depth representations

Fig. 3. Example of application of the operator 1

Node-Depth Encoding for Evolutionary Algorithms

3.2

683

Operator 2

The operator 2 requires a set of three nodes: the prune node p, the new root
node r and the adjacent node a. The nodes p, r are in the tree Tf rom and a is
in Tto .
The dierences between operator 1 and operator 2 are in the steps 2 and 3
(see the operator-1 procedure, Section 3.1), i.e. only the formation of pruned
subtrees and their storing in temporary arrays are dierent.
In the sequel, we described the steps 2 and 3 for the operator 2. Figures 4(a),
4(b) and 4(c) provide an illustrative example of these steps.
The procedure of copy of the pruned subtree for the operator 2 can be divided
in two steps: The rst step is similar to the step 2 for the operator 1 and diers
from it in the exchanging of ip by ir . The array returned by this procedure is
called Ttmp1 .
The second step considers the nodes in the chain from r to p (i.e. r0 , r1 ,
r2 , . . . , rn , where r0 = r and rn = p) as roots of subtrees (see the highlighted
nodes in Figure 4(a)). The subtree rooted at r1 contains the subtree rooted at
r0 . The subtree rooted at r2 contains the subtree rooted at r1 , and so on (see
Figure 4(a)). The algorithm for the second step should copy the subtrees rooted
at ri (i = 1, . . . , n) without the subtree rooted at ri1 (see Figure 4(b)) and
store the resultant subtrees in a temporary array Ttmp2 (see Figure 4(c)).

from Tto and Ttmp . On the
The step 3 of the operator 1 creates an array Tto
other hand, the operator 2 utilizes both temporary arrays Ttmp1 and Ttmp2 to

.
construct Tto
3.3

Operators for One-Tree Forests

The proposed operators require a forest with at least two trees. However, it is
possible to utilize the same operators for forests with one tree. First, we add to
the original forest with one tree (denoted Tuniq ) an auxiliar tree Taux containing
only one node.
Second, the application of the operator 1 (2), given p and a (p, r, and a), is
divided into two steps. Initially, the operator 1 is utilized to transfer the pruned
subtree to the auxiliar tree (Tf rom = Taux ) using the node a equal to the unique
node in Taux . Afterward, we apply the operator 1 (or 2) to transfer the subtree
from Taux (Tf rom ) to the tree Tuniq (Tto ) using the original value of a.

Determination of the Nodes p, r, and a

As described in Section 3, the operators 1 and 2 require a set of predened nodes


and their positions in F . Next, we present a strategy to locate a given node in a
forest F . Subsection 4.2 describes an ecient procedure to nd adequate nodes
p, r, and a.

684

A.C.B. Delbem et al.

2
8

p
3

0 1 2 2 3 3 3 4 4 3

9
7

3 1 2 7 8 9 4 5 6 10

r
4

6
10

(a) Tto and its node-depth representation

r
4

9
7

1 2 2
4 5 6

8
6

r
4

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

10

3 4
1 2

10

2 3 3 3

7 8 9 10

(b) Subtrees rooted at the nodes in


the chain from r to p

(c) Node-depth Representation of the


pruned subtree

Fig. 4. Example of determination of Ttmp2 . The thick lines highlight the nodes in the
chain from r to p. The depth values shown in this Figure consider the depth of the
node a equal to zero

4.1

The Node Position in F

The determination of the position of a node in F can be eciently achieved using


auxiliar matrices, here named x s, and a vector, here named . Each node x
of G possesses its correspondent matrix
. For the original spanning forest F0

x
0

i0
of G, x is a column matrix: x =
j , where i0 is the index of the tree that
0
k0

contains x (Ti0 ), j0 is the index corresponding to x in the array Ti0 and k0 is


the depth of x in its tree.
Suppose a forest Fh is being generated from Fg (g < h) and x is in the
subtree that will be transferred to a new tree generating Fh . Then, x will have a
new position in Fh dierent from its position in Fg . So, we insert a new column
in x with the indices correspondent to this new position. The altered matrix

Node-Depth Encoding for Evolutionary Algorithms

results in

0 h
i0 i h
x = j0 jh .
k0 kh

685

The position update is carried out for all nodes of the

transferred subtree (see Section 3).


The vector stores the forest g, from which the forest Fh was generated,
at the rank h of , i.e. (h) = g. The parent of g is (g), the parent of (g)
is ((g)), and so on. This constitutes a linked list with all precedessors of Fh .
Obviously, the last position change of x occured in one of predecessors of h.
In this way, we can look for the predecessors of h in the columns of x . We
start searching for (h). If this column is not found in x , we try the column
((h)), and so on. The process of looking for such columns in x can be achieved
eciently by running a binary search [13] on the list given by x (0, ) (the rst
row of x ).
Once identied a column with a predecessor of h, we only need to read the
position indices of x stored in the same column.
4.2

Choice of the Nodes p, r, and a

The proposed operators require a special set of nodes in order to generate a


spanning forest F  of G based on another spanning forest F of G.
For the operator 1, this set can be eciently obtained by the following strategy:
1. Pick up, randomly, an index of a tree in F and, for this tree, pick up, randomly, a node index that is not the tree root. Call p the correspondent node.
2. Pick up, randomly, a node adjacent to p (using the node adjacent list of G).
Call this node a. If a
/ T , determine its position in F using the vector
and matrix a ; otherwise pick up, randomly, another a or return to step 1.
The strategy for the determination of p and a for the operator 2 works as
follows:
1. Pick up randomly an index of a tree in F and, for this tree, pick up randomly
a node index that is not a root. Call p the correspondent node.
2. Determine the range of nodes in the subtree rooted at p as in the step 1
of operator 1.Choose randomly an index of the selected range. Call r the
correspondent node;
3. Pick up randomly a node adjacent to r (using the node adjacent list of G).
Call this node a. If a
/ T , determine its position in F using the vector
and matrix a ; else pick up randomly another a or return to step 1.

Tests

This Section presents an evaluation of the proposed procedure for the degreeconstrained minimum spanning tree problem [7]. The tests consider 11 complete
graphs with number of vertices from 15 to 1000. For each graph, the constraint
degree varies from 3 to 5. The edge weights were randomly obtained from the

686

A.C.B. Delbem et al.

interval ranging from 1 to the number of vertices. The proposed approached was
also compared with a Genetic Algorithm using the Prufer Encoding (GAPE) [6],
[4].
Table 5 shows the results, where best cost is the mean of the best individuals
in 20 trails and time is the mean running time corresponding to these individuals.
Tournament was used for selection in both methodologies to reduce the running
time.
The results suggest that the proposed procedure can deal with the degree
constrained minimum spanning tree. Besides this methodology seems adequate
to work with large graphs.
Table 1. Results from the proposed algorithm and GAPE applied to the degree constrained minimum spanning tree problem
Graph Vertices MST degree
3
1
15
4
5
2
20
3
4
5
3
25
3
4
5
4
30
3
4
5
3
5
50
4
5
6
100
3
4
5
7
200
3
4
5
8
300
3
4
5
9
400
3
4
5
10
500
3
4
5
11
1000
3
4
5

Proposed Algorithm
GAPE
BestCost Time(s) Best Cost Time(s)
37.5
0.63
23.0
0.14
23.0
0.14
34.4
0.63
23.0
0.13
35.0
0.64
36.0
0.15
70.4
0.71
0.14
64.5
0.71
36.0
35.5
0.12
67.4
0.70
41.5
0.16
103.4
0.79
41.6
0.16
102.4
0.82
41.3
0.16
95.7
0.80
51.7
0.18
136.5
0.89
53.0
0.20
131.0
0.90
53.7
0.18
127.5
0.92
107.6
0.21
419.1
1.42
112.2
0.21
398.3
1.43
112.3
0.21
404.7
1.43
477.1
0.28
1937.1
3.74
495.5
0.28
1822.9
4.06
509.0
0.28
1816.8
4.08
3006.3
0.51
9868.9
15.72
2838.0
0.49
9628.3
17.24
2776.4
0.49
9702.2
17.55
9216.0
0.94
26712.2
36.96
9394.0
0.93
25838.5
41.07
9407.1
0.93
25650.5
41.79
21074.0
1.39
53089.5
69.10
20802.4
1.38
52114.0
73.80
20820.0
1.38
51834.2
77.72
37445.4
1.88
89886.2
113.16
37518.9
1.88
88421.2
123.67
37445.4
1.88
87649.3
127.12
247474.0
6.49
424783.2 525.71
245404.0
6.49
420479.1 571.83
247605.0
6.49
417868.4 583.01

Conclusions

EAs for network layout problems require special chromossome encoding. This
paper presented a forest representation, named node-depth encoding. Based on

Node-Depth Encoding for Evolutionary Algorithms

687

this representation, we have developed two new operators capable to manipulate


a forest generating a new one.
The proposed approach was evaluated for the degree-constrained minimum
spanning tree problem. The results suggest that the proposed technique can deal
with this problem and work with large graphs using relatively small running time.
In this way, this paper may encourage the development of new EA approaches
using the node-depth encoding for other NDPs.

References
1. Kershenbaum, A.: Telecommunications Network Design Algorithms. McGraw-Hill,
New York (1993)
2. Chou, H.H., Premkumar, G., Chu, C.H.: Genetic algorithms for communications
network design - an empirical study of the factors that inuence performance.
IEEE Transactions on Evolutionary Computation 5 (2001) 236249(3)
3. Harary, F., Gupta, G.: Dynamic graph models. Mathl. Comput. Modelling 25
(1997) 7987
4. Gen, M., Li, Y.Z., Ida, K.: Solving multiobjective transportatin problem by spanning tree-based genetic algorithm. IEICE Transactions on Fundamental of Electronics Communications and Computer Sciences E82A (1999) 28022810
5. Reijmers, T.H., Wehrens, R., Daeyaert, F.D., Lewi, P.J., Buydens, L.M.C.: Using genetic algorithm for the construction of phylogenetic trees: Application to
g-protein coupled receptor sequences. Biosystems 49 (1999) 3143
6. Gen, M., Cheng, R.: Genetic Algorithms and Engineering Design. Ashikaga Institute of Technology, Ashikaga, Japan (1997)
7. Knowles, J., Corne, D.: A new evolutionary approach to the degree-constrained
minimum spanning tree problem. IEEE Transaction on Evolutionary Computation
4 (2000) 125134(2)
8. Carvalho, P.M.S., Ferreira, L.A.F.M., Barruncho, L.M.F.: On spanning tree recombination in evolutionary large-scale network problems - application to electrical
distribution planning. IEEE Transactions on Evolutionary Computation 5 (2001)
623630(6)
9. Delbem, A.C.B., de Carvalho, A., Bretas, N.G.: Optimal energy restoration in radial distribution systems using a genetic approach and graph chain representation.
Electric Power Systems Researchs 67/3 (2003) 197205
10. Palmer, C., Kershenbaum, A.: An approach to a problem in network design using
genetic algorithms. Networks 26 (1995) 101107
11. Droste, S., Wiesmann, D.: On representation and genetic operators in evolutionary algorithms. Technical Report CI41/98, Fachbereich Informatik, Universit
at
Dortmund, 44221 Dortmund (1998)
12. Delbem, A.C.B., de Carvalho, A.: A forest encoding for evolutionary algorithms
applied to design problems. Genetic Algorithm and Evolutionary Computation
Conference 20003, Lecture Notes in Computer Science 2723 (2003) 634635
13. Goodaire, E.G., Parmenter, M.M.: Discrete Mathematics with Graph Theory.
Prentice Hall, Upper Saddle River, USA (1998)

You might also like