TY  - JOUR
AU  - Yussof, Salman 
AU  - Razali, Rina Azlin 
AU  - See, Ong Hang 
PY  - 2011
TI  - An Investigation of Using Parallel Genetic Algorithm for Solving the Shortest Path Routing Problem
JF  - Journal of Computer Science
VL  - 7
IS  - 2
DO  - 10.3844/jcssp.2011.206.215
UR  - https://thescipub.com/abstract/jcssp.2011.206.215
AB  - Problem statement: Shortest path routing is the type of routing widely used in computer
network nowadays. Even though shortest path routing algorithms are well established, other alternative
methods 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 and
insensitive to variations in network topologies. However, it is also known that GA-based routing algorithm
is not fast enough for real-time computation. Approach: To improve the computation time of GA-based
routing algorithm, this study proposes a coarse-grained parallel GA routing algorithm for solving the
shortest path routing problem. The proposed algorithm is evaluated using simulation where the proposed
algorithm is executed on networks with various topologies and sizes. The parallel computation is performed
using an MPI cluster. Three different experiments were conducted to identify the best value for the
migration rate, the accuracy and execution time with respect to the number of computing nodes and speedup
achieved as compared to the serial version of the same algorithm. Results: The result of the simulation
shows that the best result is achieved for a migration rate around 0.1 and 0.2. The experiments also show
that with larger number of computing nodes, accuracy decreases linearly, but computation time decreases
exponentially, which justifies the use parallel implementation of GA to improve the speed of GA-based
routing algorithm. Finally, the experiments also show that the proposed algorithm is able to achieve a
speedup 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 be
improved by using a coarse-grained parallel GA implementation. Even though in this study the proposed
algorithm is executed using an MPI cluster, the algorithm is also applicable to other parallel architecture
such as multi-core CPU, multi-processor or GPGPU. A future work would be to evaluate the performance
of the proposed algorithm on these other parallel architectures.