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

Telecommunications is a vital and growing area, important not only in its own right, but also for the service it provides to other areas of human endeavour. Moreover, there currently seems to be a demand for an ever-expanding set of telecommunication services of ever-increasing bandwidth. One particular technology that has the potential to provide the huge bandwidths necessary if such broadband services are to be widely adopted, is multiwavelength all-optical transport networks (Mukherjee, 1997)....
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 P6 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)6Node-Pair Encoding GeneticProgramming for Optical MeshNetwork Topology DesignMark C. Sinclair6.1 IntroductionTelecommunications is a vital and growing area, important not only in its own right, butalso for the service it provides to other areas of human endeavour. Moreover, therecurrently seems to be a demand for an ever-expanding set of telecommunication services ofever-increasing bandwidth. One particular technology that has the potential to provide thehuge bandwidths necessary if such broadband services are to be widely adopted, is multi-wavelength all-optical transport networks (Mukherjee, 1997). However, the development ofsuch networks presents scientists and engineers with a challenging range of difficult designand optimisation problems. One such problem is mesh network topology design. In the general case, this starts witha set of node locations and a traffic matrix, and determines which of the node pairs are to bedirectly connected by a link. The design is guided by an objective function, often cost-based, which allows the ‘fitness’ of candidate networks to be evaluated. In the more specificproblem of the topology design of multi-wavelength all-optical transport networks, thenodes would be optical cross-connects, the links optical fibres, and the traffic static.Suitable routing and dimensioning algorithms must be selected, with sufficient allowancefor restoration paths, to ensure that the network would at least survive the failure of anysingle component (node or link).Telecommunications Optimization: Heuristic and Adaptive Techniques, edited by D.W. Corne, M.J. Oates and G.D. Smith© 2000 John Wiley & Sons, Ltd100 Telecommunications Optimization: Heuristic and Adaptive Techniques In previous work, Sinclair (1995; 1997) has applied a simple bit-string GeneticAlgorithm (GA), a hybrid GA and, with Aiyarak and Saket (1997) three different GeneticProgramming (GP) approaches to this problem. In this chapter, a new GP approach,inspired by edge encoding (Luke and Spector, 1996), is described (a shorter version of thischapter was first published at GECCO’99 (Sinclair, 1999)). It was hoped that this wouldprovide better results than the best previous GP approach, and perhaps even provecompetitive with GAs. The eventual aim of the author’s current research into GP encodingschemes for mesh network topologies is to provide a more scalable approach than theinherently non-scalable encoding provided by bit-string GAs. The chapter is structured as follows. Section 6.2 presents some of the previous work onEvolutionary Computation (EC) for network topology design; section 6.3 provides a moredetailed description of the problem tackled, including the network cost model; and section6.4 summarises two previous solution attempts. In section 6.5 the node-pair encoding GPapproach is described; then in section 6.6 some experimental results are outlined; andfinally, section 6.7 records both conclusions and suggestions for further work.6.2 EC for Network Topology DesignOver the years, at least 30 papers have been published on EC approaches to networktopology design. Two of the earliest are by Michalewicz (1991) and Kumar et al. (1992).Michalewicz uses a two-dimensional binary adjacency matrix representation, and problem-specific versions of mutation and crossover, to evolve minimum spanning tree topologiesfor computer networks. Kumar et al. tackle three constrained computer network topologyproblems, aiming for maximum reliability, minimum network diameter or minimumaverage hop count. Their GA is bit-string, but uses problem-specific crossover, as well as arepair operator to correct for redundancy in their network representation. For optical network topology design, in addition to the papers by Sinclair, mentionedabove, there is the work of Paul et al. (1996) and Brittain et al. (1997). Both these groups ofauthors have addressed constrained minimum-cost Passive Optical Network (PON)topology design for local access. However, while problem-specific representations are usedby both, as well as problem-specific genetic operators by Paul et al., only Brittain et al.provide full details of their algorithm. This uses a two-part chromosome comprising a bit-string and a permutation, with each part manipulated with appropriate standard operators. Other recent work of interest includes Dengiz et al. (1997; Chapter 1, this volume) on ahybrid GA for maximum all-terminal network reliability, Ko et al. (1997a), who use athree-stage GA for computer network topology design, routing and capacity assignment;and Pierre and Legault (1998), who use a bit-string GA for computer mesh network design.6.3 Problem DescriptionGiven the locations of the n nodes (optical cross connects) and the static trafficrequirements, tij , between them, the problem is to determine which of the n(n–1)/2 possiblebi-directional links (optical fibres) should be used to construct the network. The number ofpossible topologies is thus 2 n ( n −1) / 2. To illustrate, Figure 6.1 shows a 15-node networkdesign problem, for which an example mesh topology design is given in Figure 6.2.Node-Pair Encoding Genetic Programming for Optical Mesh Network Topology Design 101Figure 6.1 Example network design problem. The cost model used to guide the design was developed by Sinclair (1995) formin ...