Grey wolf optimization applied to the maximum flow problem

Masadeh, et al.

International Journal of Advanced and Applied Sciences

Int. j. adv. appl. sci.

EISSN: 2313-3724

Print ISSN: 2313-626X

Volume 4, Issue 7 (July 2017), Pages: 95-100

Title: Grey wolf optimization applied to the maximum flow problem

Author(s): Raja Masadeh ^1,*, Ahmad Sharieh ², Azzam Sliet ²

Affiliation(s):

¹Software Engineering Department, The World Islamic Science and Education University, Amman, Jordan
²Computer Science Department, The University of Jordan, Amman, Jordan

https://doi.org/10.21833/ijaas.2017.07.014

Full Text - PDF XML

Abstract:

The problem of getting the maximum flow from source to destination in networks is investigated in this paper. A proposed algorithm is presented in order to solve Maximum Flow problem by using Grey Wolf Optimization (GWO). The GWO is a recently established meta-heuristics for optimization, inspired by grey wolves (Canis Lupus). In addition; in this current research, K-means clustering algorithm is used to group each 12 vertices with each other at one cluster according to GWO constraint. This work is implemented and tested various datasets between 50 vertices and 1000 vertices. The simulation results show rapprochement between experimental and theoretical results.

This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).

Keywords: Grey wolf optimization, Maximum flow problem, Meta-heuristic, Optimization

Article History: Received 21 March 2017, Received in revised form 5 June 2017, Accepted 10 June 2017

Digital Object Identifier:

https://doi.org/10.21833/ijaas.2017.07.014

Citation:

Masadeh R, Sharieh A, and Sliet A (2017). Grey wolf optimization applied to the maximum flow problem. International Journal of Advanced and Applied Sciences, 4(7): 95-100

http://www.science-gate.com/IJAAS/V4I7/Masadeh.html

References:

Ahuja RK, Magnanti TL, Orlin JB (1989). Network flows. In: Nemhauser GL, Rinnooy Kan AHG, and Todd MJ (Eds.), Optimization handbooks in Operations Research and Management Science, 1: 211-369, Amsterdam, Netherlands.

Alkalha Z, Al-Zu'bi Z, Al-Dmour H, Alshurideh M, and Masa'deh R (2012). Investigating the effects of human resource policies on organizational performance: An empirical study on commercial banks operating in Jordan. European Journal of Economics, Finance and Administrative Sciences, 51(1): 44-64.

Altamony H, Masa'deh R, Alshurideh M, and Obeidat B (2012). Information systems for competitive advantage: Implementation of an organisational strategic management process. In the 18th IBIMA Conference on Innovation and Sustainable Economic Competitive Advantage: From Regional Development to World Economic, Istanbul, Turkey.

Barham R, Sharieh A, and Sliet A (2016). Chemical reaction optimization for max flow problem. International Journal of Advanced Computer Science and Applications, 7(8): 189-196. https://doi.org/10.14569/IJACSA.2016.070826

Chintan J, Garg DG, and Goel SG (2010). An approach to efficient network flow algorithm for solving maximum flow problem. .Ph.D. Dissertation, Thapar University, Patiala, India.

Cormen TH, Leiserson CE, Rivest RL and Stein C (2009). Introduction to algorithms. MIT Press, Cambridge, USA.

Dinic EA (1970). Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Math Doklady, 11: 1277-1280.

Edmonds J and Karp RM (1972). Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (JACM), 19(2): 248-264. https://doi.org/10.1145/321694.321699

Eppstein D (1998). Finding the k shortest paths. SIAM Journal on Computing, 28(2): 652-673. https://doi.org/10.1137/S0097539795290477

Fong S, Deb S, Yang XS, and Zhuang Y (2014). Towards enhancement of performance of K-means clustering using nature-inspired optimization algorithms. The Scientific World Journal, 2014: Article ID 564829, 16 pages. https://doi.org/10.1155/2014/564829

Ford LR and Fulkerson DR (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3): 399-404. https://doi.org/10.4153/CJM-1956-045-5

Goldberg AV and Tarjan RE (1988). A new approach to the maximum-flow problem. Journal of the ACM (JACM), 35(4): 921-940. https://doi.org/10.1145/48014.61051

King V, Rao S, and Tarjan R (1994). A faster deterministic maximum flow algorithm. Journal of Algorithms, 17: 447-474. https://doi.org/10.1006/jagm.1994.1044

Kirkpatrick S, Gelatt CD, and Vecchi MP (1983). Optimization by simulated annealing. Science, 220(4598): 671-680. https://doi.org/10.1126/science.220.4598.671 PMid:17813860

Lam AY and Li VO (2010). Chemical-reaction-inspired metaheuristic for optimization. IEEE Transactions on Evolutionary Computation, 14(3): 381-399. https://doi.org/10.1109/TEVC.2009.2033580

Masa'deh R, Tayeh M, Al-Jarrah IM, and Tarhini A (2015). Accounting vs. market-based measures of firm performance related to information technology investments. International Review of Social Sciences and Humanities, 9 (1): 129-145.

McHugh JA (1990), Algorithmic graph theory. Prentice-Hall, Upper Saddle River, USA.

Mirjalili S, Mirjalili SM, and Lewis A (2014). Grey wolf optimizer. Advances in Engineering Software, 69: 46-61. https://doi.org/10.1016/j.advengsoft.2013.12.007

Munakata T and Hashier DJ (1993). A genetic algorithm applied to the maximum flow problem. In the 5th International Conference on Genetic Algorithms, Urbana-Champaign, Urbana, USA: 488-493. Available online at: http://grail.cba.csuohio.edu/~munakata/publs/pdf/ICGA93.pdf

Orlin JB (2013). Max flows in O (nm) time, or better. In the 45th annual ACM symposium on Theory of Computing, ACM, Palo Alto, USA: 765-774. https://doi.org/10.1145/ 2488608.2488705 https://doi.org/10.1145/2488608.2488705

Shannak R, Masa'deh R, Obeidat B, and Almajali D (2010). Information technology investments: A literature review. In the 14th IBIMA Conference on Global Business Transformation Through Innovation and Knowledge Management: An Academic Perspective, Istanbul-Turkey: 1356-1368. PMid:21286360 PMCid:PMC2987204

Tarjan RE (1983). Data structures and network algorithms. Society for Industrial and Applied Mathematics, Philadelphia, USA. https://doi.org/10.1137/1.9781611970265

Thomas H, Cormen Leiserson CE, Rivest RL, and Stein C (2001). Introduction to algorithms. MIT press, Cambridge, USA.