文章基本信息

标题：A Parallel Genetic Algorithm for Maximum Flow Problem
本地全文：下载
作者：Ola M. Surakhi ; Mohammad Qatawneh ; Hussein A. al Ofeishat 等
期刊名称：International Journal of Advanced Computer Science and Applications(IJACSA)
印刷版ISSN：2158-107X
电子版ISSN：2156-5570
出版年度：2017
卷号：8
期号：6
DOI：10.14569/IJACSA.2017.080620
出版社：Science and Information Society (SAI)
摘要：The maximum flow problem is a type of network optimization problem in the flow graph theory. Many important applications used the maximum flow problem and thus it has been studied by many researchers using different methods. Ford Fulkerson algorithm is the most popular algorithm that used to solve the maximum flow problem, but its complexity is high. In this paper, a parallel Genetic algorithm is applied to find a maximum flow in a weighted directed graph, by finding the objective function value for each augmenting path from the source to the sink simultaneously in the parallel steps in every iteration. The algorithm is implemented using Message Passing Interface (MPI) library, and results are conducted from a real distributed system IMAN1 supercomputer and were compared with a sequential version of Genetic-Maxflow. The simulation results show this parallel algorithm speedup the running time by achieving up to 50% parallel efficiency.
关键词：Flow network; Ford Fulkerson algorithm; Genetic algorithm; Max Flow problem; MPI; multithread; supercomputer