An Investigation of Using Parallel Genetic Algorithm for Solving the Shortest Path Routing Problem | Science Publications

Journal of Computer Science

On H. See¹  Rina A. Razali¹  Salman Yussof¹ 

关键词: Parallel genetic algorithm;    coarse-grained;    shortest-path routing;    message passing interface;    parallel architecture;    routing algorithm;    Genetic algorithm (GA);    parallel computer;    Message Passing Interface (MPI);    smaller networks;    computer network;   

DOI  :  10.3844/jcssp.2011.206.215

学科分类：计算机科学（综合）

来源: Science Publications

【 摘 要 】

Problem statement: Shortest path routing is the type of routing widely used in computernetwork nowadays. Even though shortest path routing algorithms are well established, other alternativemethods may have their own advantages. One such alternative is to use a GA-based routing algorithm.According to previous researches, GA-based routing algorithm has been found to be more scalable andinsensitive to variations in network topologies. However, it is also known that GA-based routing algorithmis not fast enough for real-time computation. Approach: To improve the computation time of GA-basedrouting algorithm, this study proposes a coarse-grained parallel GA routing algorithm for solving theshortest path routing problem. The proposed algorithm is evaluated using simulation where the proposedalgorithm is executed on networks with various topologies and sizes. The parallel computation is performedusing an MPI cluster. Three different experiments were conducted to identify the best value for themigration rate, the accuracy and execution time with respect to the number of computing nodes and speedupachieved as compared to the serial version of the same algorithm. Results: The result of the simulationshows that the best result is achieved for a migration rate around 0.1 and 0.2. The experiments also showthat with larger number of computing nodes, accuracy decreases linearly, but computation time decreasesexponentially, which justifies the use parallel implementation of GA to improve the speed of GA-basedrouting algorithm. Finally, the experiments also show that the proposed algorithm is able to achieve aspeedup of up to 818.11% on the MPI cluster used to run the simulation. Conclusion/Recommendations:We have successfully shown that the performance of GA-based shortest path routing algorithm can beimproved by using a coarse-grained parallel GA implementation. Even though in this study the proposedalgorithm is executed using an MPI cluster, the algorithm is also applicable to other parallel architecturesuch as multi-core CPU, multi-processor or GPGPU. A future work would be to evaluate the performanceof the proposed algorithm on these other parallel architectures.

【 授权许可】

Unknown