GA Application with Hybrid Encoding for QoS Routing

The search of routes with multiple Quality of Service (QoS) constraints from sources to destinations connected by networks is a Non Polynomial (NP) problem, which can be approached using Genetic Algorithms (GAs). These are heuristic algorithms that simulate the natural evolution process to solve optimization problems. In this paper we elaborate on tree-based GAs which represent the set of paths from source to destination as a tree. While existing GA applications use m-ary or binary encoding representing single paths and classes of paths in chromosomes, respectively, we propose a GA application with hybrid encoding which uses both of them. This application uses binary encoding from the first iteration until good classes of paths are found and later encodes the best paths of these classes with m-ary encoding. Its objective is taking advantage of the fast convergence due to the per class-processing of binary chromosomes and the lower computational cost of the single path processing of m-ary chromosomes. Simulation results show the performance, in terms of convergence speed, of the proposed GA application with hybrid encoding.