Artigo Nó Profundidade
Artigo Nó Profundidade
Artigo Nó Profundidade
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
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
An edge-sequence in which all the edges and nodes are distinct is called a chain.
680
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
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
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
128
3 9 10
4 11 12 13
5 14
6 7
15
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
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
681
using an array of pointers, where each pointer indicates the node-depth encoding
of a tree of the forest.
Operators
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
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
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
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
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.
684
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
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
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
x
0
i0
of G, x is a column matrix: x =
j , where i0 is the index of the tree that
0
k0
results in
0 h
i0 i h
x = j0 jh .
k0 kh
685
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
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
687
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)