European Journal of Operational Research 199 (2009) 542–552
Contents lists available at ScienceDirect
European Journal of Operational Research journal homepage: www.elsevier.com/locate/ejor
Innovative Applications of O.R.
A cross entropy approach to design of reliable networks Fulya Altiparmak a,*, Berna Dengiz b a b
Department of Industrial Engineering, Gazi University, 06570, Ankara, Turkey Department of Industrial Engineering, Baskent University, 06530, Ankara, Turkey
a r t i c l e
i n f o
Article history: Received 12 December 2007 Accepted 18 November 2008 Available online 30 November 2008 Keywords: Communication networks Network design Network reliability Cross-entropy method Meta-heuristics Monte Carlo technique
a b s t r a c t One of the most important parameters determining the performance of communication networks is network reliability. The network reliability strongly depends on not only topological layout of the communication networks but also reliability and availability of the communication facilities. The selection of optimal network topology is an NP-hard problem so that computation time of enumeration-based methods grows exponentially with network size. This paper presents a new solution approach based on crossentropy method, called NCE, to design of communication networks. The design problem is to find a network topology with minimum cost such that all-terminal reliability is not less than a given level of reliability. To investigate the effectiveness of the proposed NCE, comparisons with other heuristic approaches given in the literature for the design problem are carried out in a three-stage experimental study. Computational results show that NCE is an effective heuristic approach to design of reliable networks. 2008 Elsevier B.V. All rights reserved.
1. Introduction The communication networks are the primary source for information creation, storage, distribution and retrieval. Their usage has increased significantly in recent years due to dramatic growth in the use of Internet for business and personal use. Therefore, the design of communication networks has attracted considerable attention from practitioners and academics. A cost-effective structure for a large communication network is a multilevel hierarchical structure consisting of a backbone network and local access networks (LAN). The LAN is the lower level of this hierarchy in which users in a defined proximity are connected with each other directly or via a communication center. In the higher level, the backbone network connects LANs to each other (Boorstyn and Frank, 1977). Usually, designing the large communication network is classified into two problems; the backbone network design and LAN design. This paper focuses on the design of backbone networks. One of the most important parameters which determine the performance of such systems is network reliability. The network reliability strongly depends on not only topological layout of the communication networks but also reliability and availability of the communication facilities. It is usually characterized by two-terminal reliability, k-terminal or all-terminal reliability.Two-terminal reliability is defined as the probability that two specified nodes, source and sink, can communicate with each other. k-terminal reliability is * Corresponding author. Tel.: +90 312 582 3856; fax: +90 312 230 8434. E-mail addresses:
[email protected] (F. Altiparmak),
[email protected] (B. Dengiz). 0377-2217/$ - see front matter 2008 Elsevier B.V. All rights reserved. doi:10.1016/j.ejor.2008.11.022
the probability that every pair of nodes in the set of k nodes can communicate with each other. All-terminal reliability is the probability that every pair of nodes in the network can communicate with each other. All-terminal reliability is also called global availability and it is a very good measure of communication network performance if all the network users are to be provided with the possibility of being connected with each other (Aggarwal et al., 1982). Therefore, it is the most widely used reliability measure in the design of communication networks. When all-terminal reliability is considered as one of the design criteria, the design problem is to choose a set of links for a given set of communication centers either to minimize cost given a minimum all-terminal reliability constraint or to maximize all-terminal reliability given a maximum cost constraint. This design problem is an NP-hard (Garey and Johnson, 1979). Complication of the problem increases with the NP-hardness of the calculation of all-terminal reliability. Therefore, the design of networks is very difficult even for small networks. Different solution algorithms have been proposed to find optimal/near optimal design of reliable networks in the literature. Jan et al. (1994) have developed an algorithm based on branch and bound algorithm (B&B) to find an optimal network design to minimize cost under all-terminal reliability constraint. Their study is the first attempt to solve the problem exactly. Koide et al. (2001) have also developed another B&B algorithm for the design of minimum cost network with different link reliabilities given all-terminal reliability constraint. This is an extension of the Jan et al.’s B&B algorithm in terms of different link reliabilities. Aggarwal et al. (1982) and Chopra et al. (1984) have proposed greedy heuristics for maximizing all-terminal network reliability under cost constraint. A two-step heuristic procedure
F. Altiparmak, B. Dengiz / European Journal of Operational Research 199 (2009) 542–552
has been developed by Ventetsanopoulos and Singh (1986) for the design of networks with minimum cost given all-terminal reliability requirement. Shao et al. (2005) have proposed a heuristic approach, called shrinking and searching algorithm (SSA), to maximize all-terminal reliability given cost constraint. Metaheuristics, which are global search techniques, have gained considerable attention and have experienced remarkable growth over the past decade. Among their benefits is their flexibility in application to complex optimization problems. Simulated annealing (SA), tabu search (TS) and genetic algorithms (GA) are some of the most popular metaheuristics. Although these techniques have been successfully applied to different problems in the area of communication networks (Chu et al., 2000; Zhou and Gen, 2003; Marseguerra et al., 2005; Menon and Amiri, 2006) and reliability optimization of series and parallel systems (Kulturel-Konak et al., 2003; Levitin, 2003; Zhao and Liu, 2004; Wattanapongsakorn and Levitan, 2004; Long et al., 2008), we only consider studies on the design of reliable communication networks. Atiqullah and Rao (1993) have proposed a heuristic approach based on SA to maximize network reliability under cost constraint. Kumar et al. (1995a) have developed a GA-based solution approach considering deterministic and probabilistic reliability measures such as diameter, average distance and network reliability. The same authors used this solution approach to expand existing computer networks (Kumar et al., 1995b). Dengiz et al. (1997a) have proposed a heuristic approach based on standard GA to minimize cost under all-terminal reliability constraint. Dengiz et al. (1997b) have also developed another GA-based solution approach with special encoding structure, crossover and mutation operators for the same problem. Deeter and Smith (1998) have presented a heuristic algorithm based on GA for generalized network design problems including maximization reliability and minimization network cost with alternative link reliabilities. Cheng (1998) has proposed a GAbased solution approach to minimize communication cost with fault tolerant to 1-link failure. A NN-based heuristic algorithm for minimizing cost under all-terminal reliability constraint has been developed by AboElfotoh and Al-Sumait (2001). Altiparmak et al. (2003) have proposed three heuristics based on hill-climbing, SA and GA for choosing node and link types of the fixed topology to maximize all-terminal reliability under cost constraint. Marquez and Rocco (2008) have presented a population-based heuristic approach called probabilistic solution discovery algorithm (SDA) to minimize cost under all-terminal reliability constraint. Recently, a new metaheuristic called cross-entropy (CE) method has been proposed by Rubinstein (1999) to solve combinatorial optimization problems. The CE method is in the class of population-based heuristics such as GA, evolutionary strategies, scatter search, etc. The main idea of CE is related to the design of an effective learning mechanism throughout the search. The CE transforms the deterministic optimization problem into a stochastic one and then uses rare event simulation techniques to solve the problem. It has been successfully applied to combinatorial optimization problems, such as buffer allocation problems (Alon et al., 2005), vehicle routing problems (Chepuri and Homem de Mello, 2005), maximal cut problems (Rubinstein, 2002; Laguna et al., 2009), reliable network design problem (Kroese et al., 2007), knapsack problem (Caserta et al., 2008) and lot-sizing problem (Caserta and Rico, 2009). This paper presents a new solution approach based on cross-entropy method, called NCE, to design of reliable communication networks. To obtain feasible solutions during the search process, a new network generation mechanism is embedded into NCE. As in the other metaheuristics, the performance of NCE depends on its parameters such as sample size, smoothness index, etc. Thus, the parameters of NCE are determined through experimental design. To investigate the effectiveness of NCE, we conduct a three-stage experimental study. In the first stage, NCE is compared with two
543
GAs proposed by Dengiz et al. (1997a,b) on the small-size networks with known optimal solution. The second stage investigates the effects of knowledge-based step and network generation mechanisms on the performance of NCE. Finally, the performance of NCE against two GA approaches on the moderate-size networks, which are not solved optimally, is evaluated. Computational results show that NCE is an effective heuristic approach to the design of reliable networks. The paper is organized as follows: mathematical model of the design problem and its assumptions are given in Section 2. While Section 3 gives information about CE method, the proposed algorithm based on CE for the problem is introduced in Section 4. Section 5 presents computational results. Finally, Section 6 summarizes the concluding remarks. 2. Problem statement A communication network can be modeled by a graph G = (V, E), where V and E are the set of nodes and links that corresponds to the computer sites and communication connections, respectively. It is assumed that location of each node is known and nodes are always operative, i.e. never fail. Each link is bi-directional and has two parameters c(e) and r(e), which are cost and reliability of link e, respectively. We also consider following assumptions: (1) links are either operative or failed, (2) they operate statistically independent to each other and (3) link reliabilities are equal to r, i.e. r(e) = r. It is important to note that the assumption of equal link reliabilities is made when no detailed information about link reliabilities is available (Colbourn, 1987). In this paper, all-terminal reliability is considered as a measure of network reliability. If all nodes in a network are connected with operative links, the network is assumed to be operative, otherwise failed. Thus, all-terminal reliability, R(x), is the probability that network is operative. The optimization problem is to find optimal network topology with minimum cost under all-terminal reliability constraint. Let e1, . . . , ejEj be the labels of all links in E and xi be a 0-1 variable on ei if ei is selected then xi = 1, otherwise xi = 0. The mathematical model of the problem (Koide et al., 2001) is
Minimize f ðxÞ ¼
X
cðei Þxi
ð1Þ
ei 2E
s:t: RðxÞ P Ro
ð2Þ
xi ¼ 0 or 1 8i 2 E
ð3Þ
where x is the network topology of {x1, x2, . . . , xi, . . . , xjEj}. It is also important to note that a network topology can be represented with the set of links, i.e. Ex = {eijxi = 1, i = 1, 2, . . . , jEj}. The set of all possible network topologies, i.e. solution space of the problem, is denoted by v. 3. Cross-entropy method The CE method has been developed by Rubinstein (1999) in the context of rare event simulations in where it is combined with the importance sampling technique. The main idea of CE is based on the design of effective learning mechanism during the search process. It translates a combinatorial optimization problem to an associated stochastic optimization problem which is characterized by a density function /. The stochastic optimization problem is solved by identifying the optimal importance sampling density /*, which minimizes the Kullback–Leibler distance in terms of the original density function /. This distance is called the cross-entropy between / and /*. The minimization of the cross-entropy provides the definition of optimal updating rules for the reference parameter of the density functions and the generation of improved feasible vectors. The method terminates when it converges to a solution in
544
F. Altiparmak, B. Dengiz / European Journal of Operational Research 199 (2009) 542–552
the feasible region (Rubinstein, 2004; de Boer et al., 2005; Caserta and Rico, 2009). This section briefly introduces the features of CE which are relevant to the network design problem. Let us consider a general 0-1 integer minimization problem
ðPÞ : z ¼ min f ðxÞ
ð4Þ
x2v
where v Bn represents the solution space of the problem. The CE method translates the original combinatorial optimization problem (P) to an associated stochastic optimization problem (SP) as follows:
ðSPÞ : l ¼ P u ðf ðXÞ 6 zÞ ¼
X
Iff ðxÞ6zg /ðx; uÞ
where I{f(x)6z} is the indicator function whose value is 1 if f(x) 6 z and 0 otherwise, /(x, u) is a family of density functions defined on v, which is parameterized with a vector u, and Pu is the probability that a random state X drawn from /(x, u) has an objective function value less than or equal to a given threshold value z. It should be noted that we use a family of Bernoulli density functions, given in (6), in the proposed NCE, since we want to generate a binary vector to identify the network topology for the reliable network design problem:
ð6Þ
i¼1
To estimate l = Pu(f(X) 6 z) for z = z*, Monte Carlo simulation can be implemented by drawing a random sample X1, X2, . . . , XN from / (x, u). Since the event Xk = x* is a rare event with probability 1/jvj, a large simulation effort is needed to obtain precise estimation of l. Thus, Importance Sampling (IS) can be used to estimate l. In this case, a random sample X1, X2, . . . , XN is taken from different density function /(x, p) and l is estimated as N X /ðX k ; uÞ ^l ¼ 1 Iff ðX k Þ6zg N k¼1 /ðX k ; pÞ
ð7Þ
where ^l is called the importance sampling (IS) or the likelihood ratio (LR) estimator. It is important to note that /(x, p) constitutes a change of measure and its parameter p should be chosen in such a way that cross-entropy between /(x, p) and /(x, u) is minimal. Thus, the parameter p, which is also called reference vector, is estimated by solving the problem in (8)
^ ¼ arg max p p
N 1 X Iff ðX k Þ6zg ln /ðX k ; pÞ N k¼1
ð8Þ
The solution of (8) can be obtained by solving the following system of equations: N @ X Iff ðX k Þ6zg ln /ðX k ; pÞ ¼ 0 @pi k¼1
ð9Þ
^ , which gives optimal updating rule, is Hence, the reference vector p
PN k¼1 I ff ðX k Þ6zg xki ^i ¼ P ; p N k¼1 Iff ðX k Þ6zg
i ¼ 1; 2; . . . ; n
4. The cross entropy-based algorithm for network design
ð5Þ
x2v
n Y /ðx; uÞ ¼ ðui Þxi ð1 ui Þ1xi
when either the global optimum, z*, is reached or the vector p converges to a vector in v (Rubinstein, 2004; Caserta and Rico, 2009). Based on these explanations, the CE method applied to solve any combinatorial optimization problem involves two main steps: (1) generate a random data sample using the specified probability density function, (2) update the probability density function parameters by Eq. (10). These steps are repeated until a stopping criterion is met.
ð10Þ
where Xk indicates a binary vector and xki is the ith component of the kth binary vector of the CE population. The rule (10) is iteratively used to generate a sequence of decreasing threshold values z0, z1, . . . converging either to the global optimum z* or to a value close to it. At each iteration t, the new value of zt is used to obtain a better vector pt+1. The new vector pt+1 is implemented to draw a new sample population, which will provide a better value of zt+1. The search process is terminated
In this section, a cross entropy-based algorithm to design of reliable communication networks, called NCE, is presented. The central idea of the algorithm is the design of an ‘‘intelligent” guessing mechanism. In order to apply the CE method for the design of reliable networks, rules of generating random network topologies and updating the parameters at each iteration have to be specified. In this context, the NCE is introduced in this section. 4.1. Generating random network topologies To generate random network topologies, i.e. X1, X2, . . . , XN, at iteration t, a reference vector pt consisting of jEj elements is used. pt,i in pt denotes existence probability of link i in a network topology. During the search process, {pt, t P 0} converges to a degenerate (i.e. binary) probability vector in the solution space, v, which is optimum or near optimum. A simple approach to generate random network topologies at iteration t of NCE is the directly application of the reference vector pt in which a decision related with the existence of link i in network topology is given by considering its existence probability, pt,i. Although the application of this approach is very easy, it has several drawbacks. First, this approach can generate unconnected networks especially in the earlier stages of the search process. This problem is handled with different ways in the literature such as correcting the topologies with a repair strategy, penalizing them using appropriate penalty function or discarding them. The second drawback is that connectivity control of each randomly generated topology causes an additional computational burden. The last drawback is that generated network topologies can not meet the reliability requirement although they are connected. Another network generation mechanism is proposed by Kroese et al. (2007) for the design problem of maximizing k-terminal reliability under cost constraint. After a small modification, it can be implemented into NCE to design of networks with minimum cost under all-terminal reliability constraint as follows: (1) randomly generate a permutation of links, p = (e1, e2, . . . , ejEj), (2) add links to network topology according to their order in the permutation p and existence probabilities in reference vector pt until meeting reliability requirement or considering all links in the permutation. As in the simple network generation mechanism, the application of this approach is also easy. However, it can generate infeasible networks, i.e. unconnected or failing to meet reliability requirement, during the search process. Based on these observations, we propose a new network generation approach for NCE in this paper. The proposed approach is devised to generate feasible networks which are connected and meeting all-terminal reliability requirement. It consists of two stages. Due to all-terminal reliability constraint, the generated network should be at least spanning tree to satisfy that all nodes communicate with each other. Therefore, in the first stage, a spanning tree is generated. In the second stage, new links are added to the topology considering two rules explained below until obtaining a reliable network. These stages are briefly explained in the remainder of this section.
545
F. Altiparmak, B. Dengiz / European Journal of Operational Research 199 (2009) 542–552
4.1.1. Generating spanning tree To generate a spanning tree, firstly, a link is randomly selected from E using probability distribution which is obtained according to the reference vector, pt. Then, at each of remaining jVj2 construction steps, a link, ei 2 EC(Ts), is added to the partial spanning tree where s 2 {2, . . . , jVj1} and EC(Ts) is the set of candidate links to be added to the partial spanning tree which is determined as follows:
EC ðT s Þ ¼ fei ¼ ðv ; v 0 Þ 2 E j v 2 VðT s1 Þ XOR
v0
2 VðT s1 Þg
ð11Þ
where V(Ts1) is the set of nodes in the partial spanning tree at the (s 1)th step. Hence, the link to be added to the partial spanning tree at the sth step is randomly chosen from EC(Ts) according to probability distribution given below:
p0t;i ¼ P
pt;i
ej 2EC ðT s Þ pt;j
;
8ei 2 EC ðT s Þ
ð12Þ
As seen in (12), the probability distribution for EC(Ts) is obtained by considering existence probabilities of the corresponding links in the reference vector pt. The algorithm for generating a spanning tree is given in Fig. 1. It is important to note that EC(Ts) is updated incrementally during the search process without re-computing it. Thus,
the updating process is carried out in O(jVj) operations. The overall complexity of the algorithm is O(jVj3). 4.1.2. Generating network topology It is obvious that a spanning tree does not meet reliability requirement if link reliabilities of a network are less than or equal to system reliability, i.e. r 6 Ro. Therefore, new links are added to topology considering the following two rules until obtaining a network that meets reliability requirement. As it is known in the literature, two-connectivity is one of the most important properties of highly reliable networks. Thus, the first rule ensures that all nodes have at least two-degree. This is done by determining the set of nodes with one-degree in the tree, Vnd1, and then upgrading the degree of each node in Vnd1. Let vrs be the randomly selected node from Vnd1 and EC the set of candidate links which are adjacent to vrs:
EC ¼ fei ¼ ðv ; v 0 Þ 2 EnEX k j v ¼ v rs XOR
v 0 ¼ v rs g
ð13Þ
In the process of upgrading the degree of vrs, after a probability distribution for EC is obtained as in (12), a link to be added to topology is randomly chosen from EC according to probability distribution.
Fig. 1. The algorithm for generating a spanning tree.
546
F. Altiparmak, B. Dengiz / European Journal of Operational Research 199 (2009) 542–552
The computational complexity of this process, i.e. upgrading degree of all nodes in Vnd1, is O(jVj2). The second rule ensures that upper bound of network reliability, RUB(Xk), meets minimum reliability requirement, i.e. RUB(Xk) P Ro. The reason of using the upper bound of network reliability is that its calculation is in polynomial (in jVj) time. Therefore, it increases the speed of search process. If RUB(Xk) < Ro, then the process of adding new links to the network topology continues until RUB(Xk) P Ro. In each step of this process, after a node, vrs, is randomly chosen from V and EC is determined as in (13), a link randomly chosen from EC according to probability distribution is added to the network topology. After that, the cost of the network topology is calculated by Eq. (1). The overall procedure to obtain a reliable network in NCE is given in Fig. 2.
We employ Jan’s (1993) approach to calculate the upper bound of all-terminal reliability of the network. This approach uses only cut sets separating individual nodes from a network, and its formulation is given in (14)
RUB ðX k Þ 6 1
" jVj X
qdi
i¼1
mi Y j¼1
ð1 qdj 1 Þ
i1 Y
# ð1 qdj Þ
ð14Þ
j¼mi þ1
where di is the degree of node i (i.e. number of links that are adjacent to the node i), q is the unreliability of links, i.e. q = 1 r, and mi = min(di, i 1), "i 2 V. The overall computational complexity of the procedure used to generate a reliable network topology is O(jVj3).
Fig. 2. The algorithm for generating a reliable network.
F. Altiparmak, B. Dengiz / European Journal of Operational Research 199 (2009) 542–552
4.2. Updating parameters As mentioned in Section 3, the CE method proceeds by constructing a sequence of reference vectors {pt, t P 0}, such that {pt, t P 0} converges to a degenerate probability vector (i.e. binary vector) in the solution space, v, which is optimal or near optimal. The sequence of reference vectors is obtained by a two-step procedure, including a sequence of costs {zt, t P 0} that tend to the optimal cost z = z* at the same time as pt tend to p*. Let q be the rarity parameter which is used to determine qth quantile of sample. Thus, at each iteration t, following two steps are repeated to estimate zt and pt: In the first step, after network topologies, X1, . . . , XN, are generated via the proposed network generation mechanism and these are ordered in ascending order with respect to their costs, an estimator ^zt of zt is obtained as f(X(dqNe)) which is ^ t of pt the q-th quantile of costs. In the second step, an estimator p is computed by Eq. (15):
PN k¼1 Iff ðX k Þ6^zt g xki ^t;i ¼ P ; p N k¼1 Iff ðX k Þ6^zt g
i ¼ 1; 2; . . . ; j E j
ð15Þ
^t;i is an estimator of the ith element of pt. where p To improve the performance of NCE, we implement two procedures called smoothed updating procedure and elitist strategy. The smoothed updating procedure given in (16) is applied to prevent the premature convergence of pt to a degenerate probability vector:
^ t1 ^ t ¼ ap ^ t þ ð1 aÞp p
ð16Þ
where a is called the smoothing parameter. As it is seen in (16), the original updating procedure, i.e. Eq. (15), is obtained if a is set to 1. If the smoothing parameter is set to a value between 0 and 1, the past is also taken in consideration when updating the reference vector. The elitist strategy, borrowed from GA, is also implemented to speed up the convergence of NCE to good solutions. As it is known, the elitist strategy in GA is applied to preserve good solutions found during the search process for using information gathered in them to direct the search to good regions of solution space. It is seen in the literature that this strategy has been successfully used in different applications of the CE method (Rubinstein, 2002; Chepuri and Homem de Mello, 2005). In our implementation, the dqNe worst solutions in the current iteration are replaced with the dqNe best solutions of the previous iteration. Meanwhile, it is worthy to point out that if the population in iteration t includes one or more good network topologies, i.e. their costs are smaller than cost (fbest) of the best topology found so far, b ðkÞ Þ, is obthen precise estimation of the all-terminal reliability, RðX tained for those networks using following procedure. Since network topologies in the population are ordered in ascending order according to their costs, all network topologies that f(X(k)) < fbest are put into a set B and the procedure for estimating all-terminal reliability starts with the first network topology in B, i.e. X(k) and b ðkÞ Þ P Ro , then the procedure terminates after the best k = 1. If RðX network topology found so far is updated. Otherwise, the network topology is repaired by adding a new link to it considering reference vector. If f(X(k)) < fbest for the repaired network, then reliability is estimated, otherwise another good network topology in B is considered to estimate its reliability. The procedure is repeated until finding a network topology that meets reliability requirement or examining all good network topologies in B with respect to reliability constraint. To estimate the network reliability, a Monte Carlo technique proposed by Yeh et al. (1994) is embedded into NCE. This Monte Carlo technique improves upon the classic method by reducing the variability of the estimate of network reliability, allowing for a more efficient estimator. The computational com-
547
plexity of Monte Carlo technique is O(nrjVj4) where nr is the number of replication (Yeh et al., 1994). In this paper, nr is taken as 3000 to estimate reliability for a network topology. 4.3. The steps of NCE The steps of NCE to the design of reliable networks are given in Fig. 3. Rubinstein (2002) has presented an approach to define the computational complexity of the algorithms based on CE for the maximal cut and partition problems. Based on this approach, we can define the computational complexity of NCE as in (17):
k ¼ sjVj ðNGjVj þ NZ jVj þ SN Þ
ð17Þ
where sjVj is the total number of iterations needed before the algorithm terminates. N is the sample size (or population size), GjVj = O(jVj3) is the cost of generating a reliable network through the proposed network generation mechanism, ZjVj = O(nrjVj4) is the cost of computing the objective function value of a reliable network (including the Monte Carlo estimation of the network), and SN = O(Nlog N) is the cost of sorting N networks according to objective function value. If we consider that sjVj is a function of the number of nodes jVj in the network, the computational complexity of NCE can be found as O(NnrjVj5). 4.4. Similarities and differences between NCE and other algorithms In this section, we briefly discuss similarities and differences between NCE and two GA approaches (Dengiz et al., 1997a,b), Kroese et al.’s (2007) CE and SDA (Marquez and Rocco, 2008) which are used in computational experiment. As mentioned in Section 1, while two GA approaches, called NGA and LS/NGA, and SDA have been developed to solve the problem considered in this paper, i.e. the design of networks with minimum cost under all-terminal reliability constraint, Kroese et al. (2007) have proposed a CE algorithm to maximize k-terminal reliability under cost constraint. The NGA uses a binary encoding, single point crossover, bit flip mutation and roulette wheel selection strategy. The LS/NGA implements the integer-based encoding to represent a network, special crossover and mutation operators and stochastic remainder sampling without replacement as selection mechanism. The NCE is similar to NGA and LS/NGA in terms of screening of candidate networks. All three algorithms make use of two-connectivity checking and Jan’s upper bound approach to obtain reliable networks and speed-up search process, respectively, and also Monte Carlo technique for only networks that improve the best solution found so far. Meanwhile, NCE differs from NGA and LS/NGA with respect to dealing with infeasible networks that fail to meet all-terminal reliability requirement. While NGA and LS/NGA use a special penalty function for those networks, NCE repairs them such that new links are added to those networks until meeting reliability requirement. As previously mentioned, Kroese et al.’s (2007) CE algorithm can be easily adopted to solve the problem considered in this paper. Nevertheless, Kroese et al.’s CE algorithm still differs from NCE in terms of two aspects: (1) network generation mechanism, (2) evaluating the networks. The network generation mechanism used in Kroese et al. CE algorithm can generate infeasible networks that are unconnected or not meeting reliability requirement. Thus, a mechanism for connectivity checking of networks and a penalty function for networks that fail to meet reliability requirement should be imposed into Kroese et al’s CE algorithm. With respect to evaluating the networks, Kroese et al.’s CE algorithm employs a Monte Carlo technique to estimate reliability of each candidate network in the population. As it is known, the Monte Carlo technique is time-consuming because of the intensive computations.
548
F. Altiparmak, B. Dengiz / European Journal of Operational Research 199 (2009) 542–552
Fig. 3. The algorithm of NCE.
Thus, evaluating each candidate network by Monte Carlo technique increases computational burden of the heuristic approach. However, NCE activates Monte Carlo technique for only networks that improve the best solution found so far to speed-up search process. Finally, in terms of search mechanism, SDA, which is a population-based algorithm, is similar to NCE. The SDA also implements a reference vector to generate networks and then updates the reference vector according to the S best solutions of the population in each iteration. But, main differences between NCE and SDA lay in the network generation mechanism and evaluating the networks. The SDA employs the simple network generation mechanism explained in Section 4.1. Since this mechanism can generate infeasible networks which are unconnected or failing to meet reliability
requirement, SDA also uses a connectivity checking algorithm and penalty function. As in the Kroese et al.’s CE algorithm, it employs a Monte Carlo technique to estimate reliability of each network. Thus, SDA has a similar drawback with Kroese et al.’s CE algorithm with respect to computational burden. 5. Experimental study This section presents numerical results of NCE. After determined the parameter set of NCE by experimental design, three sets of computational experiments are conducted. The first set compares NCE with NGA and LS/NGA in terms of effectiveness and efficiency on the small-size networks with known optimal solution. The second set investigates the effects of knowledge-based step
F. Altiparmak, B. Dengiz / European Journal of Operational Research 199 (2009) 542–552
549
, K X Hi Oi K Dav g ¼ 100 Oi i¼1
ð18Þ
and network generation mechanisms on the performance of NCE on the small-size networks. The third one evaluates the performance of NCE against two GA approaches on the moderate-size networks that are not solved optimally. To make a fair comparison, NCE, NGA and LS/NGA are coded in Borland Pascal and run on a Pentium IV, 2.8 GHz personal computer. 5.1. Parameter settings of NCE Since the performance of CE method depends on the values of control parameters, we have employed an experimental design approach to investigate the performance of NCE for a set of four parameters. These parameters are sample size multiplier (c), rarity parameter (q), smoothness index (a) and network size (i.e. number of nodes in the network, jVj). It is important to note that since we define the sample size in NCE as N = c jVj, only the multiplier, i.e. c, is considered as factor. Three levels are selected for each parameter: c = 5, 10 and 20, q = 0.05, 0.10 and 0.20, a = 0.50, 0.80 and 1, and jVj = 7, 8 and 10. Hence, the experimental design includes 34 design points. Ten observations for each design point are considered by solving 10 different problem instances for the corresponding problem size. Thus, the number of observations is 810 (=10 34). Each observation represents the percent deviation from optimal solution. The problem instances are taken from Dengiz et al.’s, 1997b test set. The statistical analysis is performed using ANOVA (analysis of variance) and Duncan’s multiple range tests. All parameters are significant at the level of 0.05 and the best results are found for c = 20, q = 0.20 and a = 0.50. 5.2. Computational results In this section, we present the results of the experimental study carried out into three-stage. 5.2.1. Comparison of NCE with NGA and LS/NGA for small-size networks To judge the effectiveness and efficiency of NCE, the results of NCE on small size networks are compared to NGA and LS/NGA. In the comparison, we consider test set given in Dengiz et al. (1997b). This set contains 79 problem instances with known optimal solution. These instances are generated considering fully-connected and non fully-connected networks. While jVj ranges from 6 to 11 for fully-connected networks, this value is between 14 and 20 for non-fully networks. The link costs of all networks are drawn from a uniform distribution between 1 and 100. For each fully-connected network in which jVj varies between 6 and 10, five problem instances are randomly generated. The following combinations of link reliability and reliability requirement are considered for each problem instance: (0.90, 0.90), (0.90, 0.95) and (0.95, 0.95). For each of the other networks which are fully-connected network with 11 nodes and three non fully-connected networks, one problem instance is randomly generated. The NCE, NGA and LS/NGA are run ten times with different random number seeds for each problem instance to gauge their natural variability. It should be noted that the parameters (i.e. population size, crossover and mutation rates) of NGA and LS/ NGA have been taken directly from Dengiz et al. (1997a,b). Since the optimal solutions are known for the problem instances, all algorithms are run until reaching the optimal solution or the predetermined number of solutions which are evaluated during the search process. While the number of evaluated solutions is set to jEj*1000 for the networks in which the number of nodes varies between 6 and 8, this is taken as jEj*2000 for the networks having nodes between 9 and 11. The solution quality is measured with the percentage relative increase in cost (D) with respect to optimal solution and Davg is computed as follows:
where Hi denotes the cost value generated by NGA, LS/NGA or NCE, Oi is the optimum cost, and K is the total number of replications, i.e. K equals to the number of replications for each instance times the total number of instances. In addition to Davg, Dstd (standard deviation of the relative percent increase in cost) and tavg (time to reach the best solution in each run averaged over K runs in seconds) are also computed. It is also important to note that since all heuristic approaches reached the optimal solutions at least one of ten runs for 79 problem instances, Dmin implying the response to the harder instances is not reported. Table 1 shows the results of NGA, LS/NGA and NCE. Davg gives information about average performance of the heuristic approaches. When Davg columns of NCE, LS/NGA and NCE are compared, it is seen that NCE exhibits better performance than other heuristics except to one problem on the average. As it is known, Dstd is an indicator the robustness of a heuristic approach. When the heuristic approaches are compared with respect to Dstd, it is seen that NCE performs better than NGA and LS/NGA. This result supports that NCE is more robust than NGA and LS/NGA to the initial seed. Lastly, the heuristic approaches are compared in terms of computational effort. As it is seen in Table 1, in average LS/NGA needs less computational time to reach optimum or near optimum than NGA and NCE. The reason is that NCE reaches many networks with minimum cost and spends time to determine whether they meet network reliability requirement by Monte Carlo technique during the search process. To obtain more robust information about NCE, a statistical analysis has been performed to test several hypotheses for significance. These hypotheses are related to the solution quality, robustness and computational burden. In the statistical analysis, Wilcoxon Signed Rank Test, which is a nonparametric version of paired-t test, is employed. Since it is expected that NCE will give better result than the other heuristic approaches according to corresponding performance measure, following three one-sided alternative hypotheses are defined: ð1Þ
HM H1 : lNCE Dav g lDav g < 0 ð2Þ
HM H1 : lNCE Dstd lDstd < 0 ð3Þ H1
NCE t av g
:l
HM t av g
l
ð19Þ
