Node-Based Genetic Algorithm for Communication Spanning Tree Problem SUMMARY Genetic Algori

IEICE TRANS. COMMUN., VOL.E89–B, NO.4 APRIL 2006
1091
PAPER
Special Section on Internet Technology VI
Node-Based Genetic Algorithm for Communication Spanning Tree Problem
Lin LIN?a) , Nonmember and Mitsuo GEN? , Member
SUMMARY Genetic Algorithm (GA) and other Evolutionary Algorithms (EAs) have been successfully applied to solve constrained minimum spanning tree (MST) problems of the communication network design and also have been used extensively in a wide variety of communication network design problems. Choosing an appropriate representation of candidate solutions to the problem is the essential issue for applying GAs to solve real world network design problems, since the encoding and the interaction of the encoding with the crossover and mutation operators have strongly in?uence on the success of GAs. In this paper, we investigate a new encoding crossover and mutation operators on the performance of GAs to design of minimum spanning tree problem. Based on the performance analysis of these encoding methods in GAs, we improve predecessor-based encoding, in which initialization depends on an underlying random spanning-tree algorithm. The proposed crossover and mutation operators o?er locality, heritability, and computational e?ciency. We compare with the approach to others that encode candidate spanning trees via the Pr?fer number-based encoding, edge set-based encoding, and demonstrate better results on larger instances for the communication spanning tree design problems. key words: minimum spanning tree (MST), communication network design, genetic algorithm (GA), node-based encoding
Fig. 1
Illustration of a network with spanning tree structure.
1.
Introduction
Communication Network Design has increased signi?cantly in the last decade due to the dramatic growth in the use of internet for business and personal use. As the society transforms itself to an information society the network becomes the primary source for information creation, storage, distribution and retrieval. A cost-e?ective structure for a large communication network is a multilevel hierarchical structure consisting of a backbone network (high level) and local access networks (low level) [1], [2]. The backbone network, which connects local access networks to each other is characterized by distributed tra?c requirements and is generally implemented using packet switching techniques. The Minimum Spanning Tree (MST) problem is one of the best-known network optimization problems used for designing backbone networks, which attempts to ?nd a minimum cost tree network that connects all the nodes in the communication network. Illustration of a network with spanning tree structure is shown in Fig. 1. The links or edges have associated costs that could be based on their distance, capacity, quality of line, etc. There might be other constraints imposed on the design such as the number of nodes
Manuscript received June 27, 2005. Manuscript revised October 3, 2005. ? The authors are with the Graduate School of Information, Production and Systems, Waseda University, Kitakyushu-shi, 8080135 Japan. a) E-mail: lin@ruri.waseda.jp DOI: 10.1093/ietcom/e89–b.4.1091
in a subtree, degree constraints on nodes, ?ow and capacity constraints on any edge or node, and type of services available on the edge or node [3]–[6]. The complexity of the MST problem increases as the number of nodes increases. When the network’s edge costs are ?xed and the search is unconstrained, many heuristics have been developed, prominent among them being Kruskal (1956) algorithm runs in O(m + n log n) plus time needed to sort m edge lengths, and Prim (1957) algorithm runs in O(m + n log n) time, identify MST’s in times that are polynomial in the number of nodes. However, the current techniques seem to have been pushed to the limit. For example, there is no guarantee of convergence to an optimal solution of the large-scale, reallife case, most of the algorithms generate good performance only for sparse networks, and many heuristics can only be implemented sequentially (i.e., not suitable for parallel operation). Recently, Genetic Algorithm (GA) and other Evolutionary Algorithms (EAs) have been successfully applied to solve constrained spanning tree problems of the reallife instances; and also have been used extensively in a wide variety of communication network design problems [2], [7], [8]. For example, Abuali et al. (1995) [9] developed a new encoding scheme for probabilistic MST problem. Zhou and Gen (1998) [10] gave an e?ective GA approach to the quadratic MST problem. Zhou and Gen (1998) [11], Fernades and Gouveia (1998) [12] investigated the leaf-constrained MST problem with GA approaches. Raidl and Drexe (2000) [13], Ahuja and Orlin (2001) [14] gave the EAs for the capacitated MST problem occurring in telecommunication applications, Zhou and Gen [15]–[17], Raidl (2000) [18], [19], Knowles and Corne (2000) [20], Chou et al. (2001) [21], Raidl and Julstrom (2003) [22] investi-
Copyright c 2006 The Institute of Electronics, Information and Communication Engineers

IEICE TRANS. COMMUN., VOL.E89–B, NO.4 APRIL 2006
1092
gated the di?erent encoding methods and gave the performance analyzes for the degree-constraint MST problem, respectively. Raidl and Julstrom (2003) [23], Julstrom (2003) [24] developed EAs for the bounded-diameter MST problem. Zhou and Gen (1999) [25], Gen et al. (2000) [26], Knowles and Corne (2000) [27], Lo and Chang (2000) [28], Neumann (2004) [29] investigated the multicriteria MST problem with GA approaches and other EAs. EAs were also applied to solve other communication network design problem such as two graph problem, one-max tree problem and communication spanning tree problem [30]–[33]. In EAs literature, whereas the several kinds of encoding methods were used to obtain MSTs, most of them can not e?ectuality encode or decode between chromosomes and legality spanning trees. Special di?culty arises from (1) a cardinality constraint implying that we choose exactly n?1 edges, and (2) implying any set of chosen edges containing no cycles. After recombining the chromosomes, o?spring of simple crossover and mutation should represent infeasible solutions. The repair strategies have to be considered, and their limitations weaken the encoding heritability. For this reason, in this paper, we propose a new node-based encoding method, PrimPred-based encoding that adopted Prim’s algorithm in chromosome generating procedure. This encoding method can represent various e?cient spanning tree by each chromosome. Considering the characteristic of PrimPred-based encoding method, we also propose Primbased crossover and LowestCost mutation. These methods provide a search capability that results in improved quality of solution and enhanced rate of convergence. In addition, for comparing the e?ectiveness of di?erent encoding methods, we just consider the canonical MST problem which is basic of all kinds of MST problems. The rest of the paper is organized as follows. In Sect. 2, we formulate the mathematic model of MST problem. The reviewing of the recent genetic representation is introduced in Sect. 3. The improved predecessor-based encoding and new proposed crossover and mutation operator are described in Sect. 4. In Sect. 5, we compare e?ectiveness with di?erent encoding methods. Finally, we give the conclusion follows in Sect. 6. 2. Mathematical Formulation
min z =
(i, j)∈E
wi j x i j xi j = n ? 1
(1) (2) (3) (4)
s. t.
(i, j)∈E
xi j ≤ |S | ? 1 for any set S
(i, j)∈AS
xi j ∈ {0, 1}, ?(i, j) ∈ E
In this formulation, the 0-1 variable xi j indicates whether we select edge (i, j) as part of the chosen spanning tree (note that the second set of constraints with |S | = 2 implies that each xi j ≤ 1). The constraint (2) is a cardinality constraint implying that we choose exactly n?1 edges, and the packing constraint (3) implies that the set of chosen edges contain no cycles (if the chosen solution contained a cycle, and S were the set of nodes on a chosen cycle, the solution would violate this constraint). 3. Recent Genetic Representations
How to encode a solution of the communication network problem into a chromosome is a key issue for GAs. For evaluating the e?ectiveness of the di?erent encoding approaches, there are several critical issues are summarized by Gen and Cheng (1997) [34], Raidl and Julstrom (2003) [35]. ? Space: Chromosomes should not require extravagant amounts of memory. ? Time: The time complexities of evaluating, recombining, and mutating chromosomes should be small. ? Feasibility: All chromosomes, particularly those generated by simple crossover (i.e., one-cut point crossover) and mutation, should represent feasible solutions. ? Uniqueness: The mapping from chromosomes to solutions (decoding) may belong to one of the following three cases: 1-to-1 mapping, n-to-1 mapping and 1-ton mapping. The 1-to-1 mapping is the best one among three cases and 1-to-n mapping is the most undesired one. ? Heritability: O?spring of simple crossover (i.e., onecut point crossover) should represent solutions that combine substructures of their parental solutions. ? Locality: A mutated chromosome should usually represent a solution similar to that of its parent. We need to consider these critical issues carefully when designing an appropriate encoding method so as to build an e?ective EA. How to encode a spanning tree T in a graph G is critical for developing an EA to network design problems, it is not easy to ?nd out a nature representation. We summarized the several kinds of classi?cation of encoding methods as follows: 1. Characteristic Vectors-based Encoding 2. Edge-based Encoding 3. Node-based Encoding
Many of the network topology design problems start with the MST, which attempts to ?nd a minimum cost tree that connects all the nodes of the network. The links or edges have associated costs that could be based on their distance, capacity, and quality of line. Let G = (V, E) be a connected weighted undirected graph with n = |V| nodes and m = |E| edges, and wi j ∈ W represent the weight or cost of each edge (i, j) ∈ E where the weight is restricted to be a nonnegative real number. Let AS denote the set of edges contained in the subgraph of G induced by the node set S (i.e., AS is the set of edges of E with both endpoints in S ). Consider the following integer programming formulation of the MST problem:

LIN and GEN: NODE-BASED GENETIC ALGORITHM FOR COMMUNICATION SPANNING TREE PROBLEM
1093
Considering this classi?cation, the following subsections reviewed several recent encoding methods, how to represent a spanning tree. 3.1 Characteristic Vectors-Based Encoding Davis et al. (1993) [36], Piggott and Suraweera (1995) [37] have used binary-based encoding method to represent spanning trees in EAs. A binary-based encoding requires space proportional to m and the time complexities of binary-based encoding is O(m). The mapping from chromosomes to solutions (decoding) may be 1-to-1 mapping. In a complete graph, m = n(n ? 1)/2 and the size of the search space is 2n(n?1)/2 . However, only a tiny fraction of these chromosomes represent feasible solutions, since a complete graph G has only nn?2 distinct spanning trees. Repair strategies have been more successful, but they require additional computation and weaken the encoding heritability. Bean (1994) [38] described random keys-based encoding method for encoding ordering and scheduling problems. Schindler et al. [31] and Rothlauf et al. (2002) [33] further investigated network random keys in an evolution strategy framework. In this encoding, a chromosome is a string of real-valued weights, one for each edge. To decode a spanning tree, the edges are sorted by their weights, and Kruskal’s algorithm considers the edges are sorted order. Same as binary-based encoding, random keys-based encoding requires space proportional to m and the time complexities is O(m). Whereas all chromosomes represent feasible solutions, considering the uniqueness of the mapping from chromosomes to solutions may be n-to-1 mapping. In a complete graph with only nn?2 distinct spanning trees, consider random keys-based encoding, the size of the search space is (n(n ? 1)/2)! For this reason, most of di?erent chromosomes represent the same spanning tree (i.e., n is very large number with n-to-1 mapping from chromosomes to solutions) and it weaken the encoding heritability. 3.2 Edge-Based Encoding Edge-based encoding is an intuitive representation of a tree. A general Edge-based Encoding requires space proportional to n-1 and the time complexities is O(m). The mapping from chromosomes to solutions (decoding) may be 1-to-1 mapping. In a complete graph, m = n(n?1)/2 and the size of the search space is 2n(n?1)/2 . Edge-based encoding and binarybased encoding have very similar performance in theory. However, there are 2n(n?1)/2 possible values for a tree, and only a tiny fraction of these chromosomes represent feasible solutions, and weaken the encoding heritability. Recently, researchers investigated and developed edge-based representations in EAs for designing several MST-related problems. Considering the disadvantage of edge-based encoding, the heuristic method is adopted in chromosome generating procedure. These methods can insure feasibility; all of chromosomes can be represented feasible solutions. Knowles and Corne (2000) [27] proposed a method
which improves edge-based encoding. The basis of this encoding is a spanning-tree construction algorithm which is Randomized Primal Method (RPM), based on the Prim’s algorithm. Raidl and Julstrom (2003) [23] gave the method depend on an underlying random spanning-tree algorithm. Three choices for this algorithm, based on Prim’s algorithm, Kruskal’s algorithm and on random walks, respectively, are examined analytically and empirically. Raidl (2000) [19], Chou et al. (2001) [21], Raidl and Julstrom (2003) [23] and Julstrom (2003) [24] gave the other similar heuristic methods which insure feasibility of the chromosomes. All of these heuristic method based encoding requires space proportional to n ? 1 and the time complexities is O(n). The mapping from chromosomes to solutions (decoding) may be 1-to-1 mapping. In a complete graph, m = n(n?1)/2 and the size of the search space is nn?1 . These encoding methods offer e?ciency of time complexity, feasibility and uniqueness. However, o?spring of simple crossover and mutation should represent infeasible solutions. Several special genetic operator and repair strategies have been successful, but their limitations weaken the encoding heritability. 3.3 Node-Based Encoding Pr¨ fer Number-based Encoding: Cayley (1889) [39] proved u the following formula: the number of spanning trees in a complete graph of n nodes is equal to nn?2 . Pr¨ fer (1918) u [40] presented the simplest proof of Cayley’s formula by establishing a 1-to-1 correspondence between the set of spanning trees and a set of sequences of n ? 2 integers, with each integer between 1 and n inclusive. The sequence of n integers for encoding a tree is known as Pr¨ fer number. u Many researchers have encoded spanning trees as Pr¨ fer numbers in EAs for a variety of problems. These u include the degree-constrained MST problems, multicriteria MST problems, and lef-constrained MST problem, etc. However, researchers have pointed out that Pr¨ fer number u is a poor representation of spanning trees for evolutionary search, and their major disadvantages as follows: 1. It needs a complex encoding process and decoding process between chromosomes and solutions (computation cost); 2. It is di?cult to consist mostly of substructures of their parents’ phenotypes (poor heritability); 3. It contains no useful information such as degree, connection, etc, about a tree; 4. It also represents infeasible solutions, if the graph G is incomplete graph. Predecessor-based Encoding: A more compact representation of spanning trees is the predecessor or determinant encoding, in which an arbitrary node in G is designated the root, and a chromosome lists each other node’s predecessor in the path from the node to the root in the represented spanning tree: if pred(i) is j, then node j is adjacent to node i and nearer the root. Thus, a chromosome is string of length n ? 1 over 1, 2,. . . , n, and when such a chromosome decodes

IEICE TRANS. COMMUN., VOL.E89–B, NO.4 APRIL 2006
1094
a spanning tree, its edges can be made explicit in time that is O(n log n). Applied to such chromosomes, positional crossover and mutation operators will generate infeasible solutions, requiring again penalization or repair. As shown in [22], Abuali et al. described a repair mechanism that applies to spanning trees on sparse, as well as complete graphs. However, these strategies require additional computation and weaken the encoding heritability, and these repairing process have to spend much computation cost. 4. Proposed GA Approach
Given a predecessor-based encoding string v, with length of n ? 1, where n represents number of nodes. Assume v(i) represents the allele of the ith ?xed position in chromosome v, where i starts from 2 to n. As discussed in Chou et al.’s research paper [21], predecessor-based encoding generates some chromosomes that are illegal (i.e., not a spanning tree). Combining the simple random initialization, most of the chromosomes will be illegal due to three reasons: missing node i, self-loop, or cycles. They gave the repair function for illegal chromosomes. However, the complex repair process will be used at each generation (computational cost), and after repairing, the o?spring of the crossover and mutation are di?cult to represent solutions that combine substructures of their parental solutions (worst heritability and locality). In this paper, we improved predecessor-based encoding, in which initialization depends on an underlying random spanning-tree algorithm. Considering the characteristic of predecessor-based encoding, we propose a new crossover and mutation operators. These operators o?er locality, heritability, and computational e?ciency. 4.1 PrimPred-Based Encoding and Population Initialization When a GA searches a space of spanning trees, its initial population consists of chromosomes that represent random trees. It is not as simple as it might seem to choose spanning trees of a graph so that all are equal likely. Prim’s algorithm greedily builds a minimum spanning tree from a start node by repeatedly appending the lowest cost edge that joins a new node to the growing tree. For applying Prim’s algorithm to the EAs, choosing each new edge at random rather than according to its cost [22]. The encoding procedure and decoding procedure are shown in Fig. 2 and Fig. 3, respectively. An example of generated chromosome and its decoded spanning tree is shown in Fig. 5, for the undirected network shown in Fig. 4. In general, there are two ways to generate the initial population, heuristic initialization and random initialization. Although the mean ?tness of the heuristic initialization is already high so that it may help the GAs to ?nd solutions faster. Unfortunately, in most large scale problems, for example, network communication designing, it may just explore a small part of the solution space and it is di?cult to
Fig. 2
Pseudocode of PrimPred-based encoding.
Fig. 3
Pseudocode of predecessor-based decoding.
Fig. 4
Pseudocode of predecessor-based decoding.
?nd global optimal solutions because of the lack of diversity in the population. Therefore, random initialization is e?ected in this paper so that the initial population is generated with the PrimPred-based encoding method.

LIN and GEN: NODE-BASED GENETIC ALGORITHM FOR COMMUNICATION SPANNING TREE PROBLEM
1095
Fig. 5
An example of the PrimPred-based encoding.
Fig. 6
Pseudocode of Prim-based crossover.
4.2 Genetic Operators Genetic operators mimic the process of heredity of genes to create new o?spring at each generation. Using the di?erent genetic operators has very large in?uence on GA performance [35]. Therefore it is important to examined di?erent genetic operators. Crossover Operator Crossover is the main genetic operator. It operates on two parents (chromosomes) at a time and generates o?spring by combining both chromosomes’ features. In network design problem, crossover plays the role of exchanging each partial route of two chosen parents in such a manner that the o?spring produced by the crossover represents. To provide good heritability, a crossover operator must build an o?spring spanning tree that consists mostly or entirely of edges found in the parents. In this paper, we also applying Prim’s algorithm described in the previous section to the graph G = (V, T 1 ∪ T 2 ), where T 1 and T 2 are the edge sets of the parental trees. Figure 6 gave the pseudocode of crossover process. Mutation Operator Mutation is a background operator which produces spontaneous random changes in various chromosomes. A simple way to achieve mutation would be to alter one or more genes. In GAs, mutation serves the crucial role of either replacing the genes lost from the population during the selection process so that they can be tried in a new context or providing the genes that were not present in the initial population. In this paper, it is relatively easy to produce some mutation operators for permutation representation. Several
Fig. 7
Pseudocode of LowestCost mutation.
mutation operators have been proposed for permutation representation, such as swap mutation, inversion mutation, and insertion mutation, and so on [34]. Swap mutation selects two positions at random. For considering represent a feasible solutions after mutated, improving the heritability of o?spring, we proposed a new mutation operator, ?rst removing a randomly chosen edge, determining the separated components, then reconnecting them by the lowest cost edge. Figure 7 gave the pseudocode of mutation process. Selection Operator The selection operator is intended to improve the average quality of the population by giving the high-quality chromosomes, i.e., a better chance to get copied into the next generation. The selection thereby focuses the exploration on promising regions in the solution space. In this paper, the

IEICE TRANS. COMMUN., VOL.E89–B, NO.4 APRIL 2006
1096 Table 1 Performance comparisons with di?erent GA approaches: Pr¨ fer Number-based encoding u (Zhou & Gen 97), edge-based 1 and edge-based 2 with di?erent mutation operators (Raidl and Julstrom 03) and proposed GA approach.
roulette wheel selection, i.e., a type of ?tness-proportional selection is adopted. 5. Experiments and Discussion
Mutation probability: p M =0.30, 0.50 or 0.70; Maximum generation: maxGen =1000; The experimental study was realized to investigate the effectiveness of the di?erent encoding method; the interaction of the encoding with the crossover operators and mutation operators; and the parameter settings a?ect its performance. Table 1 gives computational results for 4 di?erent encoding methods on 6 test problems by three kinds of parameter settings. We have summarized the advantages (and disadvantages) of our proposed method and other recent genetic representations in Table 2. For considering space, time, feasibility and uniqueness, It is better than (or same with) other algorithms. In our approach, the crossover and mutation operators are realized on the space of decoded spanning trees. Even though they can improve heritability and locality, yet, the crossover and mutation operators can not be implemented directly on chromosomes. When we compare with columns of the best cost of four encoding methods, it is possible to see that whereas the Pr¨ fer number-based approach is the fastest than others, it u is di?cult to consist mostly of substructures of their parents’ phenotypes (poor heritability), and the results is very far from the best one. The two kinds of mutation is used in edge-based encoding, the second one (depends on the cost) gives better performance than the ?rst one. For considering the computational cost (CPU time), because of the Lowest-
In this section, the proposed PrimPred-based GA is compared with Zhou and Gen (1997) [15], Raidl and Julstrom (2003) [22] for solving several large scale minimum spanning tree problems. All the simulations were performed with Java on Pentium 4 processor (2.6-GHz clock). For examining the e?ectiveness of di?erent encoding methods, we applied Zhou and Gen (1997)’s Pr¨ fer u Number-based encoding method and Raidl and Julstrom (2003)’s Edge-based encoding methord on 6 test problems [41]. We are combining the Pr¨ fer Number-based encodu ing with one-cut point crossover and swap mutation, and combining the Edge-based encoding using two kinds of mutation operators which included in [22], and for initializing the chromosomes based on the edge set, we combining the Raidl and Julstrom’s PrimRST (Prim Random Spanning Tree). Each algorithm was run 20 times using di?erent initial seeds for each test problems. And Prim’s algorithm has been used to obtain optimum solutions for the problems. The GA parameter is setting as follows: Population size: popS ize =10; Crossover probability: pC =0.30, 0.50 or 0.70;

LIN and GEN: NODE-BASED GENETIC ALGORITHM FOR COMMUNICATION SPANNING TREE PROBLEM
1097 Table 2 Summarizes the performance of genetic representations.
Cost mutation in proposed approach, spend the most CPU times to ?nd the edge with lowest cost, it is always longer than other algorithms. However, our algorithm developed in this study gives best cost than other algorithms. 6. Conclusion
In this paper, we investigated a new encoding crossover, and mutation operators on the performance of GAs to design of minimum spanning tree problem. Based on the performance analysis of these encoding methods in GAs, we improved predecessor-based encoding, in which initialization depends on an underlying random spanning-tree algorithm. Based on considering the characteristic of predecessor-based encoding, we proposed new crossover and mutation operators. Comparisons of the approach to others that encode candidate spanning trees via the Pr¨ fer number-based encoding, u edge set-based encoding, provides better results on larger instances. This study was realized to investigate the e?ects of the di?erent encoding method; the interaction of the encoding with the crossover operators and mutation operators; and the parameter settings a?ect its performance. In the future, we will investigate the a?ect of the different GA structure to solve constrained spanning tree problems of the large-scale, real-life instances; and also apply the e?ective GA approach to a wide variety of communication network design problems. Acknowledgments This work is partly supported by Waseda University Grant for Special Research Projects 2004 and the Ministry of Education, Science and Culture, the Japanese Government: Grant-in-Aid for Scienti?c Research (No.17510138).
References [1] R. Boorstyn and H. Frank, “Large-scale network topological optimization,” IEEE Trans. Commun., https://www.wendangku.net/doc/7a15165236.html,-25, no.1, pp.29–47, 1977.
[2] M. Gen, R. Cheng, and S.S. Oren, “Network design techniques using adapted genetic algorithms,” Advances in Engineering Software, vol.32, no.9, pp.731–744, 2001. [3] L. Gouveia and P. Martins, “The capacitated minimum spanning tree problem: Revisiting hop-indexed formulations,” Computers & Operations Research, vol.23, pp.2435–2452, 2005. [4] Y. Lee and M. Atiquzzaman, “Least cost heuristic for the delayconstrained capacitated minimum spanning tree problem,” Comput. Commun., vol.28, pp.1371–1379, 2005. [5] R. Montemanni and L.M. Gambardella, “A Benders decomposition approach for the robust spanning tree problem with interval data,” Euro. J. Oper. Res., vol.161, no.3, pp.771–779, 2005. [6] J. Crichigno and B. Baran, “Multiobjective multicast routing algorithm for tra?c engineering,” Proc. 13th Int. J. of Computer Communications and Networks, pp.301–306, 2004. [7] M. Gen, A. Kumar, and R. Kim, “Recent network design techniques using evolutionary algorithms,” Int. J. Production Economics, vol.98, no.2, pp.251–261, 2005. [8] L. Lin and M. Gen, “Bicriteria network design problem using interactive adaptive-weight GA and priority-based encoding method,” IEEE Trans. Evol. Comput., Jan. 2005 (in Reviewing). [9] F. Abuali, R. Wainwright, and D. Schoenefeld, “Determinant factorization: A new encoding scheme for spanning trees applied to the probabilistic minimum spanning tree problem,” Proc. 6th Int. Conf. Genetic Algorithms, pp.470–475, 1995. [10] G. Zhou and M. Gen, “An e?ective genetic algorithm approach to the quadratic minimum spanning tree problem,” Computers & Operations Research, vol.25, no.3, pp.229–247, 1998. [11] G. Zhou and M. Gen, “Leaf-constrained spanning tree problem with genetic algorithms approach,” Beijing Mathematics, vol.7, no.2, pp.50–62, 1998. [12] L.M. Fernandes and L. Gouveia, “Minimal spanning trees with a constraint on the number of leaves,” Euro. J. Oper. Res., vol.104, pp.250–261, 1998. [13] G. Raidl and C. Drexe, “A predecessor coding in an evolutionary algorithm for the capacitated minimum spanning tree problem,” Proc. GECCO, pp.309–316, 2000. [14] R. Ahuja and J. Orlin, “Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem,” Mathematical Programming, vol.91, pp.71–97, 2001. [15] G. Zhou and M. Gen, “Approach to degree-constrained minimum spanning tree problem using genetic algorithm,” Engineering Design and Automation, vol.3, no.2, pp.157–165, 1997. [16] G. Zhou and M. Gen, “A note on genetic algorithm approach to the degree-constrained spanning tree problems,” Networks, vol.30, pp.105–109, 1997.

IEICE TRANS. COMMUN., VOL.E89–B, NO.4 APRIL 2006
1098
[17] G. Zhou and M. Gen, “Approach to degree-constrained minimum spanning tree problem using genetic algorithm,” in Genetic algorithms & Engineering Design, M. Gen and R. Chen, John Wiley, New York, 2000. [18] G. Raidl, “A weighted coding in a genetic algorithm for the degree-constrained minimum spanning tree problem,” Proc. SAC(1), pp.440–445, 2000. [19] G. Raidl, “An e?cient evolutionary algorithm for the degreeconstrained minimum spanning tree problem,” Proc. Congress on Evol. Comput., vol.1, pp.104–111, 2000. [20] J. Knowles and D. Corne, “A new evolutionary approach to the degree-constrained minimum spanning tree problem,” IEEE Trans. Evol. Comput., vol.4, no.2, pp.125–134, 2000. [21] H. Chou, G. Premkumar, and C. Chu, “Genetic algorithms for communications network design—An empirical study of the factors that in?uence performance,” IEEE Trans. Evol. Comput., vol.5, no.3, pp.236–249, 2001. [22] G.R. Raidl and B.A. Julstrom, “Edge sets: An e?ective evolutionary coding of spanning trees,” IEEE Trans. Evol. Comput., vol.7, no.3, pp.225–239, June 2003. [23] G. Raidl and B. Julstrom, “Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem,” Proc. SAC, pp.747–752, 2003. [24] B. Julstrom, “A permutation-coded evolutionary algorithm for the bounded-diameter minimum spanning tree problem,” Proc. GECCO, pp.2–7, 2003. [25] G. Zhou and M. Gen, “Genetic algorithm approach on multi-criteria minimum spanning tree problem,” Euro. J. Oper. Res., vol.114, no.1, pp.141–152, 1999. [26] M. Gen, G. Zhou, and M. Takayama, “Matrix-based genetic algorithm approach on bicriteria minimum spanning tree problem with interval coe?cients,” J. of Japan Society for Fuzzy Theory and Systems, vol.10, no.6, pp.643–656, 2000. [27] J. Knowles and D. Corne, “A new evolutionary approach to the degree-constrained minimum spanning tree problem,” IEEE Trans. Evol. Comput., vol.4, no.2, pp.125–134, 2000. [28] C. Lo and W. Chang, “A multiobjective hybrid genetic algorithm for the capacitated multipoint network design problem,” IEEE Trans. Syst. Man Cybern., vol.30, no.3, pp.461–470, 2000. [29] F. Neumann, “Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem,” Proc. 8th Inter. Conf. of Parallel Problem Solving from Nature, pp.80–89, 2004. [30] B. Julstrom and G. Raidl, “Weight-biased edge-crossover in evolutionary algorithms for two graph problems,” Proc. 16th ACM Symposium on Applied Computing, pp.321–326, Las Vegas, NV, 2001. [31] B. Schindler, F. Rothlauf, and H. Pesch, “Evolution strategies, network random keys, and the one-max tree problem,” Proc. Applic. of Evol. Computing on EvoWorkshops, pp.143–152, 2002. [32] F. Rothlauf, D. Goldberg, and A. Heinz, “Network random keys a tree network representation scheme for genetic and evolutionary algorithms,” Evol. Comput. Spring, vol.10, no.1, pp.75–97, 2002. [33] F. Rothlauf, J. Gerstacker, and A. Heinzl, “On the optimal communication spanning tree problem,” Working Paper 10/2003, Univ. of Mannheim, 2003. [34] M. Gen and R. Cheng, Genetic Algorithms and Engineering Design, John Wiley & Sons, New York, 1997. [35] M. Gen and R. Cheng, Genetic Algorithms and Engineering Optimization, John Wiley & Sons, New York, 2000. [36] L. Davis, D. Orvosh, A. Cox, and Y. Qiu, “A genetic algorithm for survivable network design,” Proc. 5th Int. Conf. Genetic Algorithms, pp.408–415, 1993. [37] P. Piggott and F. Suraweera, “Encoding graphs for genetic algorithms: An investigation using the minimum spanning tree problem,” Progress in Evol. Comput., ed. X. Yao, vol.956, LNAI, pp.305–314, Springer, New York, 1995. [38] J.C. Bean, “Genetic algorithms and random keys for sequencing and
optimization,” ORSA J. Comput., vol.6, no.2, pp.154–160, 1994. [39] A. Cayley, “A theorem on tree,” Quart. J. Math., vol.23, pp.376–378, 1889. ¨ [40] H. Pr¨ fer, “Neuer bewis eines Satzes uber Permutationnen,” Arch. u Math. Phys., vol.27, pp.742–744, 1918. [41] OR-Library. [Online]: https://www.wendangku.net/doc/7a15165236.html,/depts/ma/research/ jeb/info.html
Lin Lin was born in Shenyang, China, on Nov. 23, 1977. He graduated computer science program from Shenyang Yingcai College, China in 1999, was a research student at the Ashikaga Institute of Technology, Japan in 2001–2003, graduated M.S. degree from Waseda University in 2005, and is presently a Ph.D student at the Graduate School of Information, Production and Systems, Waseda University. His research interests include Genetic Algorithms, Multiobjective Optimization, Neural Networks, and the applications of Evolutionary Techniques to Network Design and Large-scale Optimization.
Mitsuo Gen received the Ph.D. degree from the Kogakuin University, Japan in 1974. He was Lecturer in 1974–1980, Assoc. Professor in 1980–1987, Professor in 1987–2003 at Ashikaga Institute of Technology, Japan. He is currently a Professor of Graduate School of Information, Production & Systems, Waseda University from 2003.4. He was Visiting Assoc. Prof. at University of Nebraska Lincoln, USA in 1981–1982; Visiting Prof. at University of California at Berkeley, USA in 1999.8–2000.3. His research interests include Genetic Algorithms, Neural Network, Fuzzy Logic, and the applications of evolutionary techniques to Network Design, Scheduling, System Reliability Design, etc. He has authored Genetic Algorithms & Engineering Design, John Wiley & Sons, New York (1997), Genetic Algorithms & Engineering Optimization, John Wiley & Sons, New York (2000) with Dr. Runwei Cheng, and is an Area Editor Journal of Computers & Industrial Engineering.