Hierarchic Genetic Algorithm for Designated Multi-nodes Routing

This paper proposed a hierarchic genetic algorithm used for solving the shortest path problem via designated multi-nodes routing of wireless networks. The hierarchy of solutions was plotted according to designated nodes, Variable-length chromosomes were employed in our genetic algorithm and the stochastic universal sampling was adopted as the selective operation. Crossover and mutation used the topological information from network to operate. A repair function was used to eliminate the unfeasible solution produced by genetic operations. The algorithm separated the solutions of feasible regions of objective function to reduce the size of populations and chromosome length, and each sub-population can run independently and simultaneously. Using this method can decompose complex routing issues into many sub-issues. By solving sub-issues the shortest path via designated multi-nodes can be obtained. The authors made simulation experiments on the algorithm by establishing a random network topology. The results indicated that the algorithm can effectively get the shortest path via designated multi-nodes , exhibits a much higher rate of convergence and is relatively less subject to network scale and the problem´s complexity than traditional methods.