Application of order-based genetic algorithms to network path searching and location estimation

Abstract

Given an incompletely connected network of nodes, populations of multiple redundant paths from each node to every other node are sought. Examples of such a scenario include telecommunications network routing, inventory control, and VLSI routing. The problem of location estimation for a network of nonstationary nodes is considered in detail as a framework for developing a solution. In particular, the problem of estimation of the actual physical positions of a system of mobile units is considered. The problem is solved by using order-based genetic algorithms, hybridized for the particular application of searching for multiple redundant subtours, increasing accuracy and robustness. With genetic algorithms performing the network routing, the modular approach used throughout is demonstrated by using four different schemes for location estimation. Implementation details are considered, with an emphasis toward eventual implementation on embedded controllers. The genetic algorithm operators are customized for the application by considering the subtour nature of the problem, as opposed to traditional applications of genetic algorithms which consider complete tours containing every node in the network. The customized genetic algorithm operators demonstrate greatly improved performance over traditional operators, both in terms of speed and robustness in the face of communication loss.