- For example, there are an intractably large number of ways to design the topology of a private data network for a large corporation. - These challenges present opportunities for collaboration between telecommunications engineers, researchers and developers in the computer science and artificial intelligence. - Much of this book focuses on these optimization techniques, and the work reported in the forthcoming chapters represents a good portion of what is currently going on in terms of applying these techniques to telecommunications-related problems. - The techniques employed include so-called ‘local search’ methods such as simulated annealing (Aarts and Korst, 1989) and tabu search (Glover, 1989. - For example, the provider of a distributed database service (such as video-on-demand, web-caching services, and so forth) must try to ensure good quality of service to each client. - A good, modern optimization technique can be used to distribute the load appropriately across the servers, however this solution becomes invalid as soon as there is a moderate change in the clients’ database access patterns. - The trick here is that the methods usually employ ‘off-line’ processing to learn about the problem they are addressing, so that, when a good, quick result is required, it is ready to deliver. - For example, an adaptive approach to optimal packet routing in the face of changing traffic patterns would involve some continual but minimal processing which continually updates the routing tables at each node based on current information about delays and traffic levels.. - In the remainder of this chapter, we will briefly introduce the optimization and adaptation techniques which we have mentioned. - Then, we will say a little about each of the three parts of this book. - There are a range of well-known methods in operations research, such as Dynamic Programming, Integer Programming, and so forth, which have traditionally been used to address various kinds of optimization problems. - What this means is discussed in the following.. - 1.3.1 Local Search. - For example, S could be a set of connection topologies for a network, and candidate solutions s, s′, s. - For example, if we were trying to find the most reliable network topology, then f(s) might calculate the probability of link failure between two particularly important nodes. - For example, if we mutate a network toplogy, the resulting mutant may include an extra link not present in the ‘parent’ topology, but otherwise be the same. - Now we can basically describe local search. - First, consider one of the simplest local search methods, called hillclimbing, which amounts to following the steps below:. - You can’t seriously expect a very reliable topology to emerge by, for example, adding a single extra link to a very unreliable topology. - In local search, we exploit this idea by continually searching in the neighbourhood of a current solution. - We will look at just two such methods here, which are those in most common use, and indeed, are those used later on in the book. - What happens in simulated annealing is that we sometimes accept a mutant even if it is worse than the current solution. - The overall effect is that the algorithm has a good chance of escaping from local optima, hence possibly finding better regions of the space later on. - All of this is encapsulated in the test function in step 3. - An example of the kind of test used is first to work out:. - Tabu Search. - There are many subtle aspects to tabu search. - It is not simply a matter of choosing the fittest neighbour of those tested. - For example, if the best neighbour of your current solution is one which can be reached by changing the other end of a link emerging from node k, but we have quite recently made such a move in an earlier iteration, then a different neighbour may be chosen instead. - Hence, any implementation of tabu search maintains some form of memory, which records certain attributes of the recently made moves. - What these attributes are depends much on the problem, and this is part of the art of applying tabu search. - For example, if we are trying to optimize a network topology, one kind of mutation operator would be to change the cabling associated with the link between nodes a and b. - Artful Local Search. - However, it is also clear that occasionally, perhaps often, we must accept the fact that we can only find improved current solutions by temporarily (we hope) moving to worse ones. - Unfortunately, however, it is almost never clear, given a particular problem, what is the best way to design and implement the approach. - There are many choices to make. - the first is to decide how to represent a candidate solution in the first place. - For example, a network topology can be represented as a list of links, where each link is a pair of nodes (a,b). - Decoding such a list into a network topology simply amounts to drawing a point-to- point link for each node-pair in the list. - Eac h position in the bit string will refer to a particular potential point-to-point link, So, a candidiate solution such as ‘10010…’ indicates that there is a point-to-point link between nodes 1 and 2, none between nodes 1 and 3, or 1 and 4, but there is one between nodes 1 and 5, and so forth.. - Generally, there are many ways of devising a method to represent solutions to a problem. - In the above example, removing a link from a topology involves two different kinds of operation in the two representations. - In the node-pair list case, we need to actually remove a pair from the list. - In the binary case, we change a 1 to a 0 in a particular position in the string.. - Devising good representations and operators is part of the art of effectively using local search to solve hard optimization problems. - For example, one problem with either of the two representations we have noted so far for network topology is that a typical randomly generated topology may well be unconnected. - It is not difficult to devise an alteration to the node- pair list representation, which ensures that every candidate solution s contains a spanning tree for the network, and is hence connected. - Better still, the problem we address will probably involve cost issues, and hence costs of particular links will play a major role in the fitness function. - It may therefore make good sense, depending on various other details of the problem in hand, to initialize each candidate solution with a minimal cost tree, and all that we need to represent are the links we add onto this tree.. - There are many, many more ways in which domain knowledge or existing heuristics can be employed to benefit a local search approach to an optimization problem. - Something about the problem might tell us, for example, what kinds of mutation have a better chance of leading to good neighbours. - There are two ways in which this potentially enhances the chances of finding good solutions. - However, at least a little time will be spent searching in the region of moderate or poor solutions, and should this lead to finding a particularly good mutant along the way, then the load-balancing of computational effort will be suitably revised.. - One of the difficulties of local search is that even advanced techniques such as simulated annealing and tabu search will still get stuck at local optima, the only ‘escape’ from which might be a rather drastic mutation. - That is, the algorithm may have tried all of the possible local moves, and so must start to try non-local moves if it has any chance of getting anywhere. - The real problem here is that there are so many potential non-local moves. - For example, if two parent solutions are each a vector of k elements, a recombination operator called uniform crossover (Syswerda, 1989) would build a child from these two parents by, for each element in turn, randomly taking its value from either point. - Select some of the population to be parents.. - There are many ways to perform each of these steps, but the essential points are as follows. - Step 2 usually employs a ‘survival of the fittest’ strategy. - The fitter a candidate solution is, the more chance it has of being a parent, and therefore the more chances there are that the algorithm will explore its neighbourhood. - There are several different selection techniques, most of which can be parameterised to alter the degree to which fitter parents are preferred (the selection pressure). - There are all sorts of standard recombination and mutation operators, but – as we hinted above – the real benefits come when some thought has been put into designing specific kinds of operator using domain knowledge. - A common approach is to simply discard the 20 least fit of the combined group, but there are a few other approaches;. - De Jong (1975), in which diversity plays a role in the decision about what candidate solutions to discard. - For example, we would. - certainly prefer to discard solution s in favour of a less fit solution t, if it happens to be the case that s already has a duplicate in the population, but t is ‘new’.. - There are many population based algorithms, and in fact they are usually called evolutionary algorithms (EAs).. - For example, to decide what the best ‘next hop’ is for a packet arriving at node a with destination d, we could perhaps run a simulation of the network given the current prevailing traffic patterns and estimate the likely arrival times at the destination for given possible next hops. - One example of such a black box is a routing table of the sort typically found in packet-switched networks. - The trouble with this, of course, is that it is fundamentally non-adaptive. - So, adaptive techniques in the context of telecommunications tends to involve black boxes, or models, which somehow learn and adapt ‘offline’ but can react very quickly and appropriately when asked for a decision. - In some of the chapters that involve adaptation, the techniques employed are those we have discussed already in section 1.3, but changed appropriately in the light of the need for fast decisions. - The real power of this method lies in the fact that we do not need to know how to distinguish one kind of pattern from another. - To build a classical rule-based expert system for distinguishing patterns, for example, we would obviously need to acquire rules, and build them into the system. - A classic application of the technique is in credit risk assessment. - one of the co-editors of this book), are highly complex, if indeed they can be expressed at all. - With things like p, r, s, and so forth, as inputs, the neural network gradually adjusts itself internally in such a way that it eventually produces the correct output (indication the likelihood of defaulting on the loan) for each of the examples it is trained with. - The problem inputs arrive as inputs to each of the first layer of nodes, the outputs from this layer feed into the second layer, and so on, although usually there are just three layers. - It is precisley these weights which are altered gradually in a principled fashion by the training process. - 1989), but there are many modern variants. - For example, ‘if traffic is heavy, use node a’, and ‘if traffic is very heavy, use node b’. - In a classical expert system approach, we would adopt pre-determined thresholds for these so-called ‘linguistic variables’, and decide, for example, that ‘traffic is heavy’ means that the utilization of the link in question is between 70% and 85%. - This might seem fine, but it is not difficult to see that 69.5% utilization might cause problems. - The extents depend upon the actual numerical values by way of the membership functions, which are often simple ‘triangular functions’. - For example, the extent to which traffic is heavy might be 0 between 0% and 35% utilization, it may then rise smoothly to 1 between 35% and 75%, and then drop smoothly to 0 again between 75%. - In particular, fuzzy logic provides ways in which to determine the degree to which different rules are applicable when the condition parts of the rules involve several linguistic variables. - The resulting system, in terms of the appropriateness of the decisions that eventually emerge, tends to be highly robust to variations in the membership functions, within reasonable bounds. - dynamics of the network, which includes, for example, the continual activity of users switching to different service providers occasionally based on new tariffs being advertised, will bear considerable resemblance to various models of competition which have been developed in theoretical biology, economics, and other areas. - For example, to maintain market share, new tariffs might need to be set hourly, and entirely automatically, on the basis of current activity in terms of new subscriptions, lapsed customers, and news of new tariffs set by rival providers. - The game theoretic approaches being developed by some of the contributors to this book will have an ever larger role to play in such scenarios, perhaps becoming the central engine in a variety of adaptive optimization techniques aimed at several service provision issues.. - Heuristic and adaptive techniques are applied to a variety of telecommunications related optimization problems in the remainder of this book. - This is, in fact, where most of the activity seems to be in terms of using modern heuristic techniques. - In contrast, routing and protocols, which are the subject of Part Two, involve optimization issues which are almost always dynamic (although two of the chapters in Part Two sidestep this point by providing novel uses for time-consuming optimization method – see below). - The bulk of this part of the book considers various ways to implement and adapt the ‘black box’ models discussed earlier. - Software development is a massive and growing problem in the telecommunications industry. - it is not a telecommunications problem per se, but good solutions to it will have a very beneficial impact on service providers. - One of the chapters in Part Three addresses an important aspect of this problem.. - The story that emerges is that heuristic and adaptive computation techniques have gained a foothold in the telecommunications arena, and will surely build on that rapidly. - The emerging technologies in telecommunications, not to mention increasing use of the Internet by the general public, serve only to expand the role that advanced heuristic and adaptive methods can play.
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt