An Effective Genetic Algorithm for QoS-Based Routing Optimization Problem

Routing of packets in networks requires that a path will be selected either dynamically while the packets are being forwarded, or statically (in advance) as in source routing from a source node to a destination. The genetic algorithms which has been applied to routing optimization problem is difficult because network is not a widely connectivity network. If we use traditional GA, it may generate some illegal routes during initialization, crossover and mutation. In order to remove these illegal solutions, some methods are used, for example establishing legitimate solution space and determining nodes connectivity before decoder. These methods increase algorithm complexity and computation time to some extent. In the paper an improved GA is brought out with a new encoding and decoding method. We describe how possible routes can be produced from prior knowledge, and then be selected based on fitness with respect to QoS. The decoding procedure is similar with Maze algorithm. Based on our experimental results, this approach adapts to network routing optimization problem, and it has obtained better convergence and stability.