A genetic algorithm for finding a path subject to two constraints

Multi-constrained routing (MCR) aims to find the feasible path in the network that satisfies multiple independent constraints, it is usually used for routing multimedia traffic with quality-of-service (QoS) guarantees. It is well known that MCR is NP-complete. Heuristic and approximate algorithms for MCR are not effective in dynamic network environment for real-time applications when the state information of the network is out of date. This paper presents a genetic algorithm to solve the MCR problem subject to transmission delay and transmission success ratio. Three key design problems are investigated for this new algorithm, i.e., how to encode the problem in genetic representation, how to avoid the illegal chromosomes in the process of population initialization and genetic operation, and how to design effective genetic operator. We propose the gene structure (GS) to deal with the first problem, and the gene structure algorithm (GSA) to generate the GS. Based on the GS, we provide the heuristic chromosome initialization and mutation operator to solve the last two problems. Computer simulations show that the proposed GA exhibits much faster computation speed so as to satisfy the real-time requirement, and much higher rate of convergence than other algorithms. The results are relatively independent of problem types (network scales and topologies). Furthermore, simulation results show that the proposed GA is effective and efficient in dynamic network environment.

This is the general structure of the proposed GA. The proposed GA is based on the GS. The GS is used to encode the routing path, and the GSA is presented to generate the GS. Based on the GS, the population initialization and genetic operation (i.e., mutation) generate paths without routing loops. There is no need to check and repair the illegal chromosomes. The mutation operator based on the GA is the unique genetic operator used in the evolution to search all potential solutions, which simplifies the genetic operation.Figure optionsDownload as PowerPoint slideHighlights
► This paper presents a genetic algorithm based on gene structure to solve the multi-constrained routing problem in dynamic environment.
► An algorithm to generate the gene structure of a network is proposed.
► Heuristic chromosome initialization and mutation operator are provided based on the gene structure.