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

Optimization Issues in TelecommunicationsThe complexity and size of modern telecommunications networks provide us with many challenges and opportunities. In this book, the challenges that we focus on are those which involve optimization. This simply refers to scenarios in which we are aiming to find something approaching the ‘best’ among many possible candidate solutions to a problem. For example, there are an intractably large number of ways to design the topology of a private data network for a large corporation....
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 P1 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)1Heuristic and AdaptiveComputation Techniques inTelecommunications:an IntroductionDavid Corne, Martin Oates and George Smith1.1 Optimization Issues in TelecommunicationsThe complexity and size of modern telecommunications networks provide us with manychallenges and opportunities. In this book, the challenges that we focus on are those whichinvolve optimization. This simply refers to scenarios in which we are aiming to findsomething approaching the ‘best’ among many possible candidate solutions to a problem.For example, there are an intractably large number of ways to design the topology of aprivate data network for a large corporation. How can we find a particularly good designamong all of these possibilities? Alternatively, we may be trying to find a good way toassign frequency channels to the many users of a mobile network. There are a host ofcomplex constraints involved here, but it still remains that the number of possible candidatesolutions which meet the main constraints is still too large for us to hope to examine eachof them in turn. So, again, we need some way of finding good solutions among all of thesepossibilities. These challenges present opportunities for collaboration between telecommunicationsengineers, researchers and developers in the computer science and artificial intelligenceTelecommunications Optimization: Heuristic and Adaptive Techniques, edited by D.W. Corne, M.J. Oates and G.D. Smith© 2000 John Wiley & Sons, Ltd2 Telecommunications Optimization: Heuristic and Adaptive Techniquescommunities. In particular, there is a suite of emerging software technologies specificallyaimed at optimization problems which are currently under-used in industry, but with greatpotential for profitable and effective solutions to many problems in telecommunications. Much of this book focuses on these optimization techniques, and the work reported inthe forthcoming chapters represents a good portion of what is currently going on in terms ofapplying these techniques to telecommunications-related problems. The techniquesemployed include so-called ‘local search’ methods such as simulated annealing (Aarts andKorst, 1989) and tabu search (Glover, 1989; 1989a), and ‘population-based’ searchtechniques such as genetic algorithms (Holland, 1975; Goldberg, 1989), evolutionstrategies (Schwefel, 1981; Bäck, 1996), evolutionary programming (Fogel, 1995) andgenetic programming (Koza, 1992). Section 1.3 gives a brief and basic introduction to suchtechniques, aimed at one type of reader: the telecommunications engineer, manager orresearcher who knows all too much about the issues, but does not yet know a way toaddress them. Later chapters discuss their use in relation to individual problems intelecommunications.1.2 Dynamic Problems and AdaptationA fundamental aspect of many optimization issues in telecommunications is the fact thatthey are dynamic. What may be the best solution now may not be the ideal solution in a fewhours, or even a few minutes, from now. For example, the provider of a distributeddatabase service (such as video-on-demand, web-caching services, and so forth) must try toensure good quality of service to each client. Part of doing this involves redirecting clients’database accesses to different servers at different times (invisibly to the client) to effectappropriate load-balancing among the servers. A good, modern optimization technique canbe used to distribute the load appropriately across the servers, however this solutionbecomes invalid as soon as there is a moderate change in the clients’ database accesspatterns. Another example is general packet routing in a large essentially point-to-pointnetwork. Traditionally, routing tables at each node are used to look up the best ‘next hop’for a packet based on its eventual destination. We can imagine an optimization techniqueapplying to this problem, which looks at the overall traffic pattern and determinesappropriate routing tables for each node, so that general congestion and delay may beminimized, i.e. in many cases the best ‘next hop’ might not be the next node on a shortestpath, since this link may be being heavily used already. But, this is clearly a routine whichneeds to be run over and over again as the pattern of traffic changes. Iterated runs of optimization techniques are one possible way to approach dynamicprob ...