A neural approach to topological optimization of communicationnetworks, with reliability constraints

摘要

Consider network topological optimization under a reliabilitynconstraint. The objective is to find the topological layout of links, atnminimal cost, under the constraint: all-terminal network reliability isnnot less than a given level of system reliability. The all-terminalnreliability is Pr{every pair of nodes in the network can communicatenwith each other}. This paper presents a new approach based on artificialnneural networks (ANN) for solving the problem. The problem is mappednonto an optimization ANN (OPTI-net) by constructing an energy functionnwhose minimization process drives the neural network into one of itsnstable states. This stable state corresponds to a solution for thennetwork design problem. The OPTI-net favors states that correspond to anselection of links with an overall reliability greater than or equal tona threshold value. Among these states it also favors the one which hasnthe lowest total cost. Hysteresis McCulloch-Pitts neuron model is usednin the solution, due to its performance and fast convergence.nConsidering the NP-hard complexity of the exact reliability calculation,ntogether with the iterative behavior of the neural networks, bounds fornthe all-terminal reliability are used. This paper introduces new uppernand lower bounds that are functions of the link selection and uses themnto represent the network reliability. The neural network is tested viancomputer simulation using three problem sets. The first two sets arenused to compare the results obtained by this method to those obtained bynprevious heuristics. The third test set contains five networks of largernsizes for which no results have been reported by previous methods. Thisnpaper rinds the optimal or near-optimal solutions for most of thenproblems in a relatively short time. The OPTI-net found many goodnsolutions for a 50-vertex 1225-arc network in 1/2 CPU hour. For eachnproblem instance, many solutions are found at each run of the simulator.nThe strengths of this neural network approach are very slowly increasingncomputation time with respect to network size, effective optimization,nand flexibility. The OPTI-net is very effective in identifying optimal,nor suboptimal, solutions even in search spaces up to ≈1016nfor a fully connected network with 50 vertexes. The OPTI-net is thenfirst approach to be applied on such large networks. The simulationnresults show that the neural approach is more efficient in designingnnetworks of large sizes compared to other heuristic techniques