✍ Scribed by Louis Anthony Cox; Lawrence Davis; Leonard L. Lu; David Orvosh; Xiaorong Sun; Dean Sirovica
No coin nor oath required. For personal study only.
Designing cost-effective telecommunications networks often involves solving several challenging, interdependent combinatorial optimization problems simultaneously. For example, it may be necessary to select a least-cost subset of locations (network nodes) to serve as hubs where traffic is to be aggregated and switched; optimally assign other nodes to these hubs, meaning that the traffic entering the network at these nodes will be routed to the assigned hubs while respecting capacity constraints on the links; and optimally choose the types of links to be used in interconnecting the nodes and hubs based on the capacities and costs associated with each link type. Each of these three combinatorial optimization problems must be solved while taking into account its impacts on the other two. This paper introduces a genetic algorithm (GA) approach that has proved effective in designing networks for carrying personal communications services (PCS) traffic. The key innovation is to represent information about hub locations and their interconnections as two parts of a chromosome, so that solutions to both aspects of the problem evolve in parallel toward a globally optimal solution. This approach allows realistic problems that take 4-10 hours to solve via a more conventional branch-and-bound heuristic to be solved in 30-35 seconds. Applied to a real network design problem provided as a test case by Cox California PCS, the heuristics successfully identified a design 10% less expensive than the best previously known design. Cox California PCS has adopted the heuristic results and plans to incorporate network optimization in its future network designs and requests for proposals.
📜 SIMILAR VOLUMES
For many optimum design problems, the objecti®e function is the result of a complex numerical code and may not be differentiable and explicit. The first aim is to propose a way of sol®ing such complexity on an example problem. A no®el and global strategy in®ol®ing artificial neural networks and a ge
Recently neural networks have been applied with some success to the study of quantitative structure activity relationships. One limitation of their use is that, while they are able to predict the biological activity of a new molecule from its physicochemical properties, it is difficult to get them t