Tối ưu hóa viễn thông và thích nghi Kỹ thuật Heuristic P2

Evolutionary Methods for the Design of Reliable NetworksAlice E. Smith and Berna Dengiz Introduction to the Design ProblemThe problem of how to design a network so that certain constraints are met and one or more objectives are optimized is relevant in many real world applications in telecommunications (Abuali et al., 1994a; Jan et al., 1993; Koh and Lee, 1995; Walters and Smith, 1995), computer networking (Chopra et al., 1984; Pierre et al., 1995), water systems (Savic and Walters, 1995) and oil and gas lines (Goldberg, 1989). This chapter focuses on design of minimum cost reliable communications networks when a set...
Nội dung trích xuất từ tài liệu:
Tối ưu hóa viễn thông và thích nghi Kỹ thuật Heuristic P2 Telecommunications Optimization: Heuristic and Adaptive Techniques. Edited by David W. Corne, Martin J. Oates, George D. Smith Copyright © 2000 John Wiley & Sons Ltd ISBNs: 0-471-98855-3 (Hardback); 0-470-84163X (Electronic)2Evolutionary Methods for theDesign of Reliable NetworksAlice E. Smith and Berna Dengiz2.1 Introduction to the Design ProblemThe problem of how to design a network so that certain constraints are met and one or moreobjectives are optimized is relevant in many real world applications in telecommunications(Abuali et al., 1994a; Jan et al., 1993; Koh and Lee, 1995; Walters and Smith, 1995),computer networking (Chopra et al., 1984; Pierre et al., 1995), water systems (Savic andWalters, 1995) and oil and gas lines (Goldberg, 1989). This chapter focuses on design ofminimum cost reliable communications networks when a set of nodes and their topologyare given, along with a set of possible bi-directional arcs to connect them. A variety ofapproaches are cited, and the previous work of the authors using genetic algorithms isdiscussed in detail. It must be noted that the design problem solved by these methods issignificantly simplified. A large number of components and considerations are not treatedhere. Instead, the approaches focus on the costs and reliabilities of the network links.2.1.1 CostsCosts can include material costs of the cabling, installation costs such as trenching orboring, land or right of way costs, and connection or terminal costs inherent with thecabling. Many of these are ‘unit costs’, i.e. they depend on the length of the arc. However,there can be fixed costs per arc and these are easily accommodated in the methodsdiscussed. In many papers, a unit cost is not specifically mentioned; instead each arc isassigned a weight which is used as the complete cost of the arc (Aggarwal et al., 1982;Atiqullah and Rao, 1993; Kumar et al., 1995).Telecommunications Optimization: Heuristic and Adaptive Techniques, edited by D.W. Corne, M.J. Oates and G.D. Smith© 2000 John Wiley & Sons, Ltd18 Telecommunications Optimization: Heuristic and Adaptive Techniques2.1.2 ReliabilityAssociated with each type of connection is a reliability (with an implicit mission time), orequivalently, a stationary availability. This reliability has a range from 0 (never operational)to 1 (perfectly reliable). It is assumed (with good justification) that reliability comes at acost. Therefore, a more reliable connection type implies a greater unit cost. The trade-offbetween cost and reliability is not linear. An increase in reliability causes a greater thanequivalent increase in cost; often a quadratic relationship is assumed. Other simplifyingassumptions commonly made are that nodes are perfectly reliable and do not fail, and thatarcs have two possible states – good or failed. Arcs fail independently and repair is notconsidered. There are two main reliability measures used in network design, namely all-terminal(also called uniform or overall network reliability) and source-sink (also called twoterminal reliability). Sections 2.4 and 2.5 in this chapter consider only all-terminalreliability, while section 2.6 includes a source-sink reliability problem. All-terminalnetwork reliability is concerned with the ability of each and every network node to be ableto communicate with all other network nodes through some (non-specified) path. Thisimplies that the network forms at least a minimum spanning tree. Source-sink reliability isconcerned with the ability of the source node (pre-specified) to communicate with the sinknode (also pre-specified) through some (non-specified) path. The problem of calculating or estimating the reliability of a network is an active area ofresearch related to the network design problem. There are four main approaches – exactcalculation through analytic methods, estimation through variations of Monte Carlosimulation, upper or lower bounds on reliability, and easily calculated, but crude, surrogatesfor reliability. The issue of calculating or estimating the reliability of the network is soimportant for optimal network design, section 2.3 covers it in detail.2.1.3 Design Objectives and ConstraintsThe most common objective is to design a network by selecting a subset of the possiblearcs so that network reliability is maximized, and a maximum cost constraint is met.However, in many situations, it makes more sense to minimize network cost subject to aminimum network reliability constraint. There may be side constraints, such as minimumnode degree (a node’s degree is simply the numb ...