Order 974527: whale optimization algorithm

A directed and weighted flow network is defined as G= (V, E), where V indicates to the set of vertices and E points to set of edges. Thus, a flow capacity (Cuv) is represented by the weight at each edge which is non-negative C (u, v) ≥0; where u and v belong to V [6]. Moreover, the network has two main vertices: the source and the sink. The source is the beginning vertex and the sink is the objective vertex [6]. Assume a graph G(V, E) contains a vertex called X, and all edges connected with vertex X are called E (X), suppose that F= max{Cuv: (u,v) ϵ E}. So the main issue is to get the optimal solution for a specific directed graph wherever every edge has a capacity. According to these constraints, the aim is to find the maximum aggregate flow that directed to the sink [7]. This scenario is mathematically modeled by equation (1) [6].

Where Xuv represents the flow on the edge (u, v).

The whale optimization algorithm is one of meta- heuristic optimization algorithms. These algorithms are becoming even more popular and play important role in many various applications since they are based on simple notion as they imitate simple concepts and ideas from the nature [1]. In addition, they are considered simple to implement and can be used in many various problems. Many meta-heuristic optimization algorithms are emerged last decades [8]. The three main categorized classes: evolutionary, physics-based and swarm intelligence algorithms. Some studies utilized evolutionary meta-heuristic mechanisms which are inspired from the nature [2, 3], while other researchers used physics- based mechanisms that were imitated physical rules [4]. Whereas, others employed "swarm intelligence algorithms" were imitated the social intelligent attitude of swarms [5].

The whale optimization algorithm (WOA) simulates the behavior of humpback whales. The mechanism imitates the hunting behavior of this kind of whales in nature. The main phases of this behavior are exploration phase searching for the prey, encircling the prey phase and finally exploitation phase which indicates to bubble-net method and attacking the prey.

With the coming data deluge, there will be a growing interest from academia and industry for big data analysis tools. Big networks having billions of vertices and edges will soon need to be analyzed routinely, in the area of supercomputing. As a result, maximum flow solvers need to be made faster and be able to operate on massive networks. Traditional maximum flow algorithm usually run on a single node. To make them faster, parallel algorithms can be employed on a multiple nodes. Thus, this study presents a possible parallel solution to the max flow problem (MFP) using a Whale Optimization algorithm,it aims to solve the MFP by simultaneously clustering the search space to find the MF for each cluster (local MF) in order to find the overall solution (global MF) of the desired graph. The WOA is used to solve the MFP by supposing the graph is the search space that the whales looking to reach the prey. Here, the prey is the sink in the network (represented by the graph) and other whales are represented in other nodes in the graph.

The reset of this paper is organized as follows. Section II contains related work. Section III describes the whale optimization algorithm and how it works. Section IV outlines the suggested algorithm “MaxFlow-WO”. The experimental results are discussed in Section V. Finally, Section VI draws the conclusion and future work.

Many researchers noticed that the Maximum Flow problem (MFP) includes many issues to be studied in different manners [9, 10]. The first method was used in 1956 and called Ford and Fulkerson method [28], which helps to get the Maximum Flow (MF) from a source to a destination by using augmenting path algorithm. [11]. A study of Dinic (1970) and Cormen et al. (2009) found that the performance of the algorithm is O (mn) augmentation steps if each augmenting path in the shortest one; where n represents the number of nodes and m is number of arcs [6, 12]. A close results to Dinic’s algorithm where presented by Edmonds and Karp (1972) using new algorithm [12, 13]. The new algorithm conceded that the shortest path where the length of the arc equals one; such results were obtained using of Breadth First Search [14, 15]. As time goes on, more algorithms have been developed. A new algorithm was improved to compute the shortest augmenting path algorithm [15, 16].The study of Orlin (2013) on sparse network showed ameliorated polynomial time algorithm [17]. Moreover, the researcher presented how to find a solution for the max-flow problem in O(mn); where m = O(n), as well as, solving the max-flow in O(nm + m31/16 log2 n) time, where m= O(n1.06). An improvement of this algorithm is shown by King et al. (1994) who finds a solution for the Max Flow problem in O(nm 𝑙𝑜𝑔 m/(n log n) 𝑛) time.

In most graph problems, the genetic algorithm (GA) is rated as difficult algorithm to be applied in MFP, since the graph problems known with its various rare characteristics [18]. However, the genetic algorithm was applied in order to find the MF from the source to the sink in a weighted directed graph by [18]. In the previous study, every solution is executed by a flow matrix. There are two main features, in the fitness function - balancing nodes and the saturation rate of the flow. The first generation population is chosen randomly. After applying the GA, the resulted generation will be enhanced. After a particular number of iterations of applying genetic algorithm, the results will be optimal or near optimal.

Barham et al. [19] submitted chemical reaction optimization algorithm (CRO) for MFP in O(I E2) time, where I represents the number of iterations and E indicates to the number of edges in flow graph. The CRO is suggested by Lam and Li [21], which is a meta-heuristic algorithm that was designed for solving combinatorial optimization problems. The MaxFlow-CRO algorithm is offered to detect the best MF that can be transferred from the source to the target (sink) in a flow network with no constraints for the capacity and violation where the flow in every arc rests within the upper limit of the capacity.

Masadeh et al [20] presented grey wolf optimization (GWO) to solve the MFP in O(|N| + |E|2) time. GWO is suggested by Mirjalili [22], which is a meta- heuristics algorithm that is intended to resolve combinatorial optimization problems too. The “Maxflow-GWO” algorithm was proposed in order to find a solution for the MFP as similar to MaxFlow-CRO algorithm.

Surakhi et al [26] presented a parallel genetic algorithm (PGA) in order to solve MFP by calculating each augmenting path in the graph from the source to the sink in parallel stages during each iteration. PGA is implemented by using message passing interface (MPI) library. In addition; the study is implemented and conducted results from real distributed system IMAN1 supercomputer. Moreover; the study’ results present good improvement in terms of speedup efficiency; whereas PGA speedup the running time by achieving up to 50% parallel efficiency.

Khanafseh et al [27] presented a comparison study between the performances of "genetic algorithm (GA) and chemical reaction optimization (CRO) algorithm" in solving MFP compared with Ford-Fulkerson algorithm which is a popular algorithm for solving MFP. In addition to that, the main objective of the study is to determine which algorithm will give results approximately closer to Ford-Fulkerson with same accuracy. Thus, the results of both algorithms that presented in this study can solve MFP with accuracy approximately close to Ford-Fulkerson results, but better when employ GA in terms of time and accuracy.

In [28] solve the max flow problem using a Whale Optimization algorithm , by clustering the search space to find the max flow for each cluster in order to find the overall solution of the desired graph. The Whale Optimization algorithm is used to solve the MFP by supposing the graph is the search space that the whales looking to reach the prey. Here, the prey is the sink in the network (represented by the graph) and other whales are represented in other nodes in the graph. Their experimental results of the “MaxFlow-WO” algorithm that were tested on various datasets are good evidence that the technique can solve the MFP and reinforce its performance.

[1]: Kirkpatrick S, Gelatt CD, and Vecchi MP (1983). Optimization by simulated annealing. Science, 220(4598): 671-680.

[2]: HOLLAND, John H. Genetic algorithms. Scientific American, 1992, 267.1: 66-72.

[3]: SHAHEEN, Ameen; SLEIT, Azzam. Comparing between different approaches to solve the 0/1 Knapsack problem. Internatiosnal Journal of Computer Science and Network Security (IJCSNS), 2016, 16.7: 1.

[4]: ALATAS, Bilal. ACROA: artificial chemical reaction optimization algorithm for global optimization. Expert Systems with Applications, 2011, 38.10: 13170-13180.

[5]: DORIGO, Marco, et al. (ed.). Ant Colony Optimization and Swarm Intelligence: 6th International Conference, ANTS 2008, Brussels, Belgium, September 22-24, 2008, Proceedings. Springer, 2008.

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

[7]: Goldberg AV and Tarjan RE (1988). A new approach to the maximum-flow problem. Journal of the ACM (JACM), 35(4): 921-940.

[8]: Mirjalili, S., & Lewis, A. (2016). The whale optimization algorithm. Advances in Engineering Software, 95, 51-67.

[9]: Tarjan RE (1983). Data structures and network algorithms.Society for Industrial and Applied Mathematics, Philadelphia, USA.

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

[11]: Ford LR and Fulkerson DR (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3): 399-404.

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

[13]: Edmonds J and Karp RM (1972). Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (JACM), 19(2): 248-264.

[14]: Eppstein D (1998). Finding the k shortest paths. SIAM Journal on Computing, 28(2): 652-673.

[15]: Thomas H, CormenLeiserson CE, Rivest RL, and Stein C (2001). Introduction to algorithms.MIT press, Cambridge, USA.

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

[17]: 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.

[18]: 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

[19]: Barham, R., Sharieh, A., &Sliet, A. (2016). Chemical Reaction Optimization for Max Flow Problem. International Journal of Advanced Computer Science and Applications, 7(8): 189-196.

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

[21]: Lam AY and Li VO (2010). Chemical-reaction-inspired metaheuristic for optimization. IEEE Transactions on Evolutionary Computation, 14(3): 381-399.

[22]: Mirjalili S, Mirjalili SM, and Lewis A (2014). Grey wolf optimizer. Advances in Engineering Software, 69: 46-61.

[23]: Hof, P. R., & Van Der Gucht, E. (2007). Structure of the cerebral cortex of the humpback whale, Megapteranovaeangliae (Cetacea, Mysticeti, Balaenopteridae). The Anatomical Record, 290(1), 1-31.

[24]: Watkins, W. A., &Schevill, W. E. (1979). Aerial observation of feeding behavior in four baleen whales: Eubalaenaglacialis, Balaenoptera borealis, Megapteranovaeangliae, and Balaenopteraphysalus. Journal of Mammalogy, 60(1), 155-163.

[25]: Chintan, J., Garg, D. G., &Goel, S. G. (2010). An Approach to Efficient Network Flow Algorithm for Solving Maximum Flow Problem (Doctoral dissertation).

[26]: Surakhi, O. M., Qatawneh, M., & Hussein, A. (2017). A Parallel Genetic Algorithm for Maximum Flow Problem, International Journal of Advanced Computer Science and Applications.

[27]: Khanafseh, M. Y., Surakhi, O. M., Sharieh, A., &Sleit, A. (2017). A Comparison between Chemical Reaction Optimization and Genetic Algorithms for Max Flow Problem. INTERNATIONAL JOURNAL OF ADVANCED COMPUTER SCIENCE AND APPLICATIONS, 8(8), 8-15.