{'fraction_non_alphanumeric': 0.026227983809211246, 'fraction_numerical': 0.00888852423148452, 'mean_word_length': 4.803968253968254, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A parallel water flow algorithm with local search for solving the quadratic assignment problem

In this paper, we adapt a nature-inspired optimization approach, the water flow algorithm, for solving the quadratic assignment problem. The algorithm imitates the hydrological cycle in meteorology and the erosion phenomenon in nature. In this algorithm, a systematic precipitation generating scheme is included to increase the spread of the raindrop positions on the ground to increase the solution exploration capability of the algorithm. Efficient local search methods are also used to enhance the solution exploitation capability of the algorithm. In addition, a parallel computing strategy is integrated into the algorithm to speed up the computation time. The performance of the algorithm is tested with the benchmark instances of the quadratic assignment problem taken from the QAPLIB. The computational results and comparisons show that our algorithm is able to obtain good quality or optimal solutions to the benchmark instances within reasonable computation time.

1. Introduction. The quadratic assignment problem (QAP) is one of the wellknown NP-hard combinatorial optimization problems [31] due to its important applications in practice, such as parallel and distributed computing [5], statistical data analysis [19], testing of electronic devices [13], plant layout design [30], data visualization [1], printed circuit board assembly process [12], and website structure improvement [32]. The problem is often described as follows: Given a set of facilities and a set of locations with the same size n, assign the facilities to the locations such that the total cost of assignment is minimized. The total cost w is calculated using the distance between locations and the flow between facilities. The QAP can then be expressed as the problem of finding a permutation π of n facilities as follows: where Π n denotes the set of possible permutations of N = {1, 2, ..., n}, while π[i] and π[j] denote the location of facilities i and j in the permutation π respectively.
Here, f ij is the flow between facilities i and j, and d π[i]π [j] is the distance between locations π[i] and π [j].
While there are some well-solved special cases of the QAP (see, for example, [10]), the QAP is generally difficult to solve [38], and so researchers have explored various possible solution methods. These solution methods can be broadly classified into two approaches: exact methods and heuristic methods. Exact methods aim to find the optimal solution to the QAP but they often run into computational difficulties with large QAP instances and are usually unable to solve instances of size n > 30 [8,9,17,4,15]. Heuristic methods on the other hand can be further divided into constructive heuristics and improvement heuristics. Constructive heuristics often construct a feasible solution for the QAP by assigning each facility to a location according to some principles. Such constructive methods for solving the QAP can be seen in [6,3,16]. However, they are only efficient for small and medium QAP instances and they may not produce good quality solutions for large QAP instances. Unlike constructive heuristics, improvement heuristics attempt to improve an existing solution through some iterative procedures. Some of the well-known algorithms belonging to this category are the metaheuristic algorithms, such as genetic algorithms [2,23], ant colony optimization algorithms [24,28,41], greedy randomized adaptive search procedure [22], memetic algorithm [25], iterated fast local search algorithm [29], simulated annealing algorithm [37], DNA algorithm [43] and bat algorithm [33]. A summary of the findings and drawbacks of several state-of-the-art metaheuristic algorithms for the QAP based on their reported computational results on the large number of benchmark instances from the QAPLIB is presented in Table  1 (since the bat algorithm was tested on some small instances, we did not report it in the table). Although the algorithms can obtain a relatively high proportion in the number of the best known solutions for the tested instances (e.g., a minimum proportion of 55% with iterated fast local search and a maximum proportion of 75% with ant system) and a small average percentage difference from the optimal or best known objective value (e.g., a minimum of 0.17% with greedy genetic algorithm and a maximum of 0.99% with simulated annealing), the best known solutions found are almost focused on small and medium instances. When the maximum percentage difference is taken into consideration, there are several instances (e.g., chrxxx and lipaxxx instances) in which the algorithms could not obtain good quality solutions possibly due to drawbacks of the algorithms described in Table 1. Moreover, there are limited algorithms, such as iterated fast local search and hybrid genetic algorithm that could solve large QAP instances of size n > 128. However, these two algorithms obtained poor quality solutions for the lipaxxx instances since the 2-opt local search used in the exploitation phase could place a limit on the solution intensification capability when solving the instances. Thus, it is desirable to develop an algorithm that can overcome the shortcomings of the state-of-the-art algorithms so as to solve the QAP effectively even for large instances.
Among the metaheuristic algorithms, nature-inspired algorithms have recently gained attention by many researchers. Besides popular algorithms such as the genetic algorithm introduced by Holland [18], ant colony optimization proposed by Dorigo [11], particle swarm optimization developed by Kennedy and Eberhart [20] and honey bee algorithm designed by Nakrani and Tovey [26], novel optimization approaches based on the natural phenomenon of water flow have also been introduced. One of the earliest applications of the water flow based optimization model was proposed in image processing [21]. The authors simulated the image processing problem by imitating the property of water always moving to lower regions and filling valleys. A threshold process was then used to extract the amount of filled water that represents the characters required to remove from a document image. Oh et al. [27] proposed splitting the input image into interest and desert regions, with rainfall only occurring within the interest regions. Based on this idea, some heuristic algorithms were developed to save computation time for solving the problem. Yang and Wang [44] developed a water flow-like algorithm for solving the bin packing problem. In their algorithm, solution agents were simulated as water flows that can traverse the terrain mapped from the objective function to find improved solutions. The algorithm includes four operations: splitting and moving, merging, evaporation, and precipitation. The numerical results showed that this algorithm outperforms some methods in solving the bin packing problem. Wu et al. [42] adapted the water flow-like algorithm for solving the cell formulation problem. The authors designed the efficient machine shifting and insertion-move strategies in the water flow splitting and moving operations for searching the best neighborhood solution. In addition, some improved operations were integrated into this algorithm, such as the velocity-based evaporation, the moist precipitation included, and the prior estimation of cell size. The computational results demonstrated the superiority of the adapted algorithm in both solution effectiveness and efficiency over other compared approaches. Shah-Hosseini [34] introduced an optimization algorithm based on the dynamics of river systems, as well as the reactions between water drops and the changes of environment in a flowing river, for solving the traveling salesman problem. The experiment results showed that the algorithm may find good solutions. The algorithm was also applied to other optimization problems, such as the multiple knapsack problem [35] and the n-queen puzzle [36]. However, the performance of this algorithm is still limited due to the large number of parameters needed by the algorithm, and the incomplete utilization of the properties of water flow. Tran and Ng [39] developed an algorithm based on the properties as well as behaviors of water flow, such as the simulation of raindrop distribution, the property of water flow always moving to lower positions, and especially the erosion process of water flow on the terrain, for the flexible flow shop scheduling with intermediate buffers. The experiment results demonstrate the efficiency of this algorithm for the scheduling problem, as well as the potential of this algorithm for solving other combinatorial optimization problems, including multi-objective optimization problems [40]. Such nature-inspired optimization approaches continued to be developed with the water cycle algorithm [14] and the water wave optimization [45]. Eskandar et al. [14] designed the algorithm based on the water cycle process and how rivers and streams flow to the sea, while Zheng [45] constructed the algorithm based on the shallow water wave theory and the phenomena of water waves, such as propagation, refraction and breaking. The water cycle algorithm was tested on several constrained benchmark optimization and engineering design problems, but its applicability for large-scale optimization problems has not been examined. The water wave optimization was applied successfully for solving the real-world high-speed train scheduling problem in China. Both algorithms demonstrated their competitive performance with state-of-the-art nature-inspired algorithms in the literature.
Following the successful applications of such nature-inspired algorithms for solving other optimization problems, we adapt in this paper the water flow algorithm (WFA) for solving the QAP. The properties and behaviors of water flow in nature are reinforced by many efficient processes to enhance solution diversification and intensification capabilities of the WFA. In particular, the algorithm uses a systematic drop of water (DOW ) generator scheme to distribute the positions of DOW s on the ground, where such distributed DOW s represent the permutations in the QAP. Also, this algorithm develops some efficient neighborhood structures to focus on strong exploitation of promising regions. A parallel computing strategy is applied in the distribution of DOW s and the exploitation of promising regions to improve the computation time of the algorithm. Benchmark problem instances drawn from the QAPLIB [7] are used to evaluate the performance of the algorithm. The computational results and comparisons show that the WFA is able to obtain good quality or optimal solutions to these instances and is a promising metaheuristic algorithm for solving the QAP instances.
The remaining content of this paper is organized as follows: In Section 2, the adapted WFA with parallel computing for solving the QAP is described in detail. In Section 3, computational results and comparisons of applying the WFA are shown. Next, the analysis of the results is discussed in Section 4. Finally, some conclusions and possible future work are presented in Section 5.
2. WFA with parallel computing for solving the QAP. WFA is a natureinspired algorithm, introduced by Tran and Ng [39] for solving certain types of combinatorial optimization problems such as the flexible flow shop scheduling problems with intermediate buffer, and then developed by the same authors [40] for the multi-objective scheduling optimization problem. This algorithm is inspired by the hydrological cycle in meteorology and the erosion phenomenon in nature. The properties and behaviors of water flow in nature are simulated to construct the main operators of the WFA, such as DOW s always moving to lower positions, spreading of DOW s onto many places on the ground, and DOW s eroding obstacles. The simulation of the natural phenomena in this algorithm aims to achieve a balance between its solution exploration and exploitation capabilities.
2.1. Description of standard WFA. We begin with a description of the relationship between the natural phenomena of water flow and the main phases of the WFA. The exploration phase of the WFA mimics the circulation of water (i.e., hydrological cycle) to generate a population of new positions (represented by longitude, latitude, and altitude) for DOW s after each cloud is generated (known as precipitation). The exploitation phase of the WFA imitates the erosion phenomenon to intensify the promising local optimal positions of DOW s and to overcome the obstacles to reach lower positions. The rate of intensity of erosion depends on the amount of precipitation, the falling force of precipitation and the soil hardness. In the WFA, the erosion capability is thus determined by a function of the number of DOW s at the eroding position and the altitude of that position [39].
The standard procedure of the WFA for solving an optimization problem can be described as follows. Firstly, a cloud (an iteration in the WFA) randomly generates a set of DOW s onto some positions on the ground (the solution space of the problem). Because of the gravity force of Earth (a local search algorithm), the DOW s flow down to their local optimal positions. Then, a set of promising positions to perform erosion process is obtained. If the erosion condition is satisfied, the erosion process is performed at these positions. The erosion process helps the DOW s overcome the local optimal positions to find better or global positions. The procedure is repeated by regenerating new positions for DOW s out of the eroded regions until the termination conditions are met. These conditions consist of the maximum number of clouds, the amount of limited time or non-improvement on the best position obtained after a certain number of clouds.
We next describe in detail the procedure for solving the QAP by the WFA with parallel computing. The main phases in the WFA include the exploration phase, the exploitation phase, and the improvement phase, as well as a systematic precipitation generating scheme. The solution representation and memory lists, which are the basic components of the WFA for solving the QAP, are first described below.

2.2.
Encoding scheme and memory lists. The WFA involves encoding a feasible solution of an optimization problem and its objective value into a DOW, which is a component of a cloud representing a pool of solutions. In particular, we consider the permutation π of n facilities in the QAP as the longitude and latitude in the position of DOW on the ground, while the total cost of flow between the facilities is encoded as the altitude. Given a permutation of n facilities π = (σ 1 , ..., σ n ) , we define: where ε is the largest integer less than or equal to ε. An illustrative example of a DOW and its positional vector components for the QAP with n = 8 facilities is shown in Figure 1.
With this encoding scheme, the neighborhood structure used in WFA for the QAP is mainly based on exchanging elements in a permutation. An example is the 2-opt neighborhood structure used in the traveling salesman problem as well as in the QAP [25]. Thus if π is the permutation obtained by exchanging positions of two facilities i and j in the permutation π, we can determine π by: In addition, we also consider the neighborhood structure of an extended 2-opt algorithm called the 2-opt mirror. In this 2-opt mirror algorithm, other than the usual 2-opt neighboring permutations, we also consider the reflected permutation and its corresponding 2-opt neighboring permutations. The reflected permutation π r of a permutation π can be determined as follows: The neighborhood structures are used for both exploration and exploitation phases.
To support the search for global optimal positions, we use three sets of memory lists, namely the best positions list (P 0 -list), the un-eroded positions list (UE-list), and the eroded positions list (E-list). Here, the P 0 -list is used to save the positions with the best-known objective value. The UE-list is used to record the local optimal positions which have not been eroded due to the erosion condition not being satisfied. The E-list is used to save the eroded local optimal positions. Hence, the E-list plays an important role in preventing the next clouds from regenerating DOW s to the eroded positions. This would in turn help to improve the computation time of the algorithm. Both the UE-list and the E-list are updated after performing the erosion process. The UE-list together with the P 0 -list is also updated each time a DOW finds a new local optimal position.
Let π Best c be the best optimal position found so far by the WFA at cloud c. Assume that we have found a local optimal position π * c+1 at cloud c + 1. Updating of the P 0 -list at the cloud can then be described as follows: Updating of the UE-list includes two phases in which the phase of removing the local optimal positions eroded and the phase of adding the ones just found are done in succession, while updating of the E-list is only to add the local optimal positions eroded. They are shown as follows: where Π 1 c and Π 2 c denote the set of local optimal positions eroded and the set of local optimal positions just found from initial positions generated at each iteration respectively.

Exploration phase.
Two schemes for generating the initial population of DOW positions in the exploration phase are proposed as follows: The first scheme is the random position generator scheme. In this scheme, a population Ω of positions of DOW s is generated randomly for each cloud and the number of such positions is the maximum population size allowed (MaxPop). Since the WFA mimics the property of water flow always moving from higher positions to lower positions due to Earth's gravity, a steepest ascent hill sliding algorithm is thus applied to search for local optimal positions from these initial positions. In particular, from an initial solution, the hill sliding algorithm searches for the best improved solution within the initial solution's neighbors in terms of objective value. Then, this process continues to be performed iteratively for the improved solution obtained until no other improved solution is found.
Due to the random nature of this scheme, the efficiency of WFA for solving the QAP may fluctuate in instances with large size. To resolve this drawback of the first scheme as well as to improve the solution exploration capability of WFA for QAP instances with large size, a second scheme is proposed. This scheme is a systematic DOW generator scheme that aims to distribute DOW s evenly into divided regions of the solution space. We first divide the solution space into n regions, where n is the instance size. Then at each cloud, the WFA generates n DOW s and each DOW is assigned to only one distinct region. This means that a cloud would consist of n different positions, which is achieved by fixing the first position of a facility in a permutation from 1 to n when generating the permutations of DOW. The rest of the positions in a permutation are assigned randomly. This can be represented with the following notation: A steepest ascent hill sliding algorithm is also used in the second scheme to search for local optimal positions from these initial positions.
At each cloud, the number of DOW s at the initial positions is updated as follows: where Q π c is the number of DOW s in the position π at cloud c, and π i c+1 denotes the position of ith DOW generated at cloud c + 1, while the set of initial positions generated or local optimal positions found through clouds 1 to c is denoted by Π 3 c . After the steepest ascent hill sliding algorithm is applied to find the local optimal position π * c+1 from the initial position π i c+1 , we also update the number of DOW s at the optimal position according to the following equation.
In general, the exploration phase in the WFA for the QAP results in a set of local optimal permutations. These permutations and the number of DOW s at the permutations are updated in the UE-list to be considered for performing the erosion process in the exploitation phase.
2.4. Exploitation phase. The exploitation phase involves applying the erosion process to overcome the local optimal positions found in the exploration phase. Before describing the erosion process, the erosion condition and limit are first described below.
2.4.1. Erosion condition and limit. The erosion process is triggered by the amount of precipitation. Thus if the number of DOW s at a local optimal permutation increases to the threshold MinEro, the erosion process is performed at this local optimal permutation. Next, we consider the limit L of the erosion process. For the QAP, the erosion limit is based on a main factor, which is the number of DOW s at the eroding local optimal permutation. In particular, the relationship between the erosion limit and this factor is a nonlinear function. However, to simplify the computations in the WFA, we have assumed the erosion limit to be a constant value MaxUIE, so that Procedure Erosion Process; Begin Do loop Choose un-eroded direction with the smallest ∆d h to erode; Do loop Apply the steepest ascent hill sliding algorithm for the erosion direction h chosen; Until (a new local optimal permutation is found or no improvement after MaxUIE steps) If (new local optimal permutation found is better than eroding local optimal permutation) Then Update it into UE-list to continue performing erosion process and update E-list; End if Until (erosion termination condition is satisfied) End. the relationship can be described as follows: If the erosion process cannot find any improved permutation after MaxUIE search steps, the erosion process stops and other permutations in the UE-list are considered for performing the next erosion process.

Erosion process.
The erosion process is the main operator in the exploitation phase of WFA for solving the QAP. Its task is to help the DOW s overcome local optimal permutations and obtain better local optimal or global optimal permutations. The operational mechanism of this operator is inspired by the erosion phenomenon caused by water flow in nature. In the QAP, the erosion process is built on a topological parameter ∆d h representing the geographical shape of the surface. It is defined as the difference of total cost between the local optimal position and its hth neighboring position: where π * and π * h denote the permutations of the local optimal position and its hth neighboring position respectively. In the case of the 2-opt mirror neighborhood, the number of directions is n(n − 1) + 1 .
The aim of computing ∆d h is to help the erosion process choose the most suitable direction to perform erosion. In particular, the smallest ∆d h is chosen to be the first erosion direction. If the erosion process for the erosion direction is not able to find a better permutation after MaxUIE steps, searching for that direction stops and we say that the direction is blocked. This is then followed by a backtracking procedure in which the search from the former local optimal permutation is restarted using another erosion direction with the next smallest ∆d h . If all the directions are blocked, we say that the local optimal permutation is fully blocked and we move it into the E-list so that it will not be considered for erosion process in the next clouds. On the other hand, if the erosion process is able to find a better permutation than the eroding local optimal permutation, that erosion direction is chosen to erode the local optimal permutation permanently. We then update the new local optimal permutation into the UE-list to continue with performing the erosion process.
The entire erosion process is summarized by Figure 2. 2.5. Improvement phase. The exploration and exploitation phases of the WFA for the QAP terminate when the maximum number of clouds (MaxCloud ) has been generated. To improve the solutions obtained by the WFA, we can apply the 3-opt algorithm at a final improvement phase. This 3-opt algorithm would still use the steepest ascent hill sliding method mentioned in the previous section. A 3-opt list is also used to save the solutions obtained by this improvement algorithm.
In summary, we have the following variants of WFA: 1.  Figure 3.
In general, the parallel computing strategy is very useful for such multiple-agentbased algorithm type. When applying the strategy for the WFA to solve the QAP, the efficiency of its computation time is significantly improved, especially for the large-size instances. On average, we can solve 4.3 times (with the usage of 8 cores) faster than the WFA without parallel computing.
3. Computational results. To test the performance of the adapted WFA, we have used the random 2-opt WFA for solving all the benchmark instances from the QAPLIB [7]. The systematic generator 2-opt WFA and the random 2-opt mirror WFA are used to solve the QAP benchmark instances when the random 2-opt WFA has not obtained their best known objective value.
3.1. Benchmark problem sets. The 134 benchmark instances drawn from the QAPLIB [7] are well-known benchmark problem sets in QAP with size ranging from 12 to 256. The best known upper bounds of these problem sets obtained from the literature were used to compare with the best results obtained by the WFA. In addition, we also compared these results with those obtained by greedy randomized adaptive search procedure (GRASP) of Li et al. [22], by ant system (ANT) of Maniezzo and Colorni [24], by greedy genetic algorithm (GGA) of Ahuja et al. [2], by hybrid genetic algorithm with partial local search (PGA) of Lim et al. [23], by iterated fast local search algorithm (IFLS) of Ramkumar et al. [29], by two-level modified simulated annealing based approach (MSA) of Singh and Sharma [37], and by population-based hybrid ant system (PHAS) of Ramkumar et al. [28], all of which are some of the most efficient metaheuristic algorithms for solving the QAP instances.

Platform and parameters.
The WFA with parallel computing strategy was implemented in Visual C++, and all the computational experiments were run on a desktop PC with an Intel Core i7-3770 processor (8 cores, 2.40 GHz per chip) and 24 GB of RAM.
The choice of parameters for WFA was determined by the design-of-experiment (DOE) method. In particular, we carried out several simulations that test the WFA on all types of QAP with various values for the controlled parameters, i.e., the exploration parameters MaxCloud and MaxPop, and the exploitation parameters MaxUIE and MinEro. The aim is to determine the best parameters of WFA for QAP that would achieve a balance between solution exploration and exploitation capabilities in finding the best solutions within reasonable computation time. Thus, smaller values may be used for the parameters for larger problem instances. The values that were used are as follows: MaxCloud = 2, 5, 10, 15, 20; MaxPop = 8, 16, 24; MaxUIE = 5, 10, 15, 20; and MinEro = 2, 3.
From the preliminary simulation results, the best parameter sets are shown in Table 2. These parameter sets are then used for the random 2-opt WFA and the random 2-opt mirror WFA. For the systematic generator 2-opt WFA, we have used the parameter sets (MaxCloud, MaxPop, MaxUIE, MinEro) = (50, n, 20, 2), (20, n, 10, 2), and (5, n, 5, 2) for instances with size at most 50, more than 50 but at most 100, and more than 100 respectively, in order to allow for a reasonable amount of the erosion process to occur.
With these parameter sets, 5 independent replicates were used for each instance and the best results obtained from these replicates were used to evaluate the performance of WFA, as well as to compare with other metaheuristic algorithms.

3.3.
Computational results. For comparison of objective values, we have used the following relative percentage difference in objective value: where Heuristic sol and Opt sol denote the best objective function value obtained by the WFA and the best known value in the literature respectively. For evaluation and comparison of the overall performance of algorithms, we use criteria such as the average relative percentage difference for all instances solved and the number of the best known solutions obtained in all instances solved. Thus, the algorithm with a smaller average relative percentage difference and a larger number of the best known solutions obtained would be considered a more effective optimization method.
The computational results and comparisons with other metaheuristic algorithms, such as GRASP, ANT, GGA, PGA, IFLS, MSA, and PHAS, are shown in Tables 3  to 7, while the improvement results obtained by the variants of WFA for the QAP benchmark instances that have not been solved optimally by the 2-opt WFA are displayed in Table 8. In Tables 3 to 7, the column with the best results of WFA shows the best solutions obtained by the random 2-opt WFA and the variants of WFA. Since the details of the computation time of applying PHAS to the QAP instances were not shown in [28], we did not include this information in Tables 3  to 7. In addition, the symbol "-" in the entries of these tables is used to indicate that the compared algorithms have not solved the respective benchmark instances. For Table 8, the entries displayed in italic font highlight the best results obtained by the respective variant of the WFA.     From Table 8, we can see that the systematic generator 2-opt WFA, the random 2-opt mirror WFA and the WFA-3-opt have obtained better results than the random 2-opt WFA for some of the benchmark instances when the random 2-opt WFA was unable to obtain the best known solution. In particular, these variants of WFA improved the solution quality for 25 instances.
From the best results obtained by WFA in Tables 3 to 7, it can be seen that out of the 134 instances from the QAPLIB [7], the best known solutions for 99 instances have been obtained by the WFA within reasonable computation time. The WFA is also able to obtain solutions with a relative percentage difference of less than 2% for all the remaining instances. The average relative percentage difference of WFA for all the 134 instances is found to be 0.20%.
When compared with other metaheuristic algorithms, namely GRASP, ANT, GGA, PGA, IFLS, MSA, and PHAS, it can be seen from Tables 3 to 7 that WFA outperforms GRASP, ANT, and MSA in all the instances, and also outperforms GGA, PGA, IFLS, and PHAS in many of the instances. When comparing the overall performance using the average relative percentage difference, as well as the number of the best known solutions obtained, the WFA dominates these metaheuristic algorithms as shown in Figure 4, especially when compared with GRASP, ANT, IFLS, and MSA. This shows that the WFA is able to obtain good results when compared to other efficient metaheuristic algorithms.
In addition, we present the comparison results, based on the average value of independent runs, between our algorithm and PGA in Table 9. The results show that the WFA can obtain better overall average solution quality than PGA, although our average computation time is larger than that of PGA. 4. Discussions. The computational results indicate that the WFA can obtain a large number of the best known solutions for the benchmark instances (99 out of 134 instances), a small average percentage difference (0.20% for all 134 instances), and a small maximum percentage difference (less than 2% for all 134 instances), as well as solve the largest instances (n = 256) from the QAPLIB [7]. The small maximum percentage difference also affirms the efficiency of the WFA for solving chrxxx and lipaxxx instances, in which the state-of-the-art metaheuristic algorithms (e.g., GRASP, ANT, GGA, PGA, IFLS, MSA, and PHAS) have difficulty finding good quality solutions as described in Table 1. The adapted algorithm is thus able to avoid the shortcomings of these metaheuristic algorithms. Using 2-opt mirror and 3-opt neighborhood structures also helps the WFA to exploit the solution space of the QAP more efficiently than the GGA, PGA, and IFLS. With the systematic DOW generator scheme, the WFA spreads its solutions widely onto the solution space that makes a better balance of the solution diversification and intensification capabilities than the GGA, PGA, and IFLS as well. In addition, this helps the WFA obtain a collection of diverse initial solutions in order to avoid the dependence on a constructive heuristic for an initial solution as in the case of GRASP. Moreover, the WFA is able to solve symmetric and non-symmetric QAP instances effectively since the exploration and exploitation phases are constructed without relying on the structure of the problem. Compared with ANT, since the WFA only performs erosion process on promising regions, the exploitation phase saves computation time to find a good quality solution. Also, unlike PHAS, this helps the WFA to avoid having to use the entire solution population. On the other hand, since the WFA does not use a solver to solve the QAP relaxation to construct an initial solution, it does not have to depend on the quality of the solution of the QAP relaxation as in the case of MSA. Thus, with a good balance of solution exploration and exploitation capabilities based on the systematic DOW generator scheme and the efficient local search schemes, the WFA is able to outperform the compared metaheuristic algorithms in the computational results.
However, as in any metaheuristic algorithm, the WFA has some controlled parameters (e.g., the exploration parameters MaxCloud and MaxPop, and the exploitation parameters MaxUIE and MinEro) that can affect the performance of the algorithm. If the values for the parameters are not chosen properly, the algorithm may spend more computation time to search for better solutions, or converge prematurely to a local optimal solution. To address this issue, an adaptive parameter tuning scheme could be integrated into the WFA in order to adjust the values of the parameters through each cloud or some clouds based on the information of the previous clouds. Then, the WFA may become more efficient for solving the QAP.

5.
Conclusions and future work. In this paper, a water flow algorithm with parallel computing is developed for solving the QAP. This algorithm includes the solution exploration and exploitation phases that mimic the water flow in hydrological cycle and erosion process in nature respectively. To solve the QAP by the adapted algorithm with enhanced solution diversification and intensification capabilities, a systematic DOW generator scheme to distribute the positions of DOW is applied, while neighborhood structures, such as the 2-opt mirror and 3-opt, are used to focus on strong searching of promising regions. In addition, a parallel computing strategy is applied to improve the efficiency of computation time for the WFA. The benchmark problem sets from the QAPLIB [7] are used to evaluate the performance of the WFA. The computational results show that the WFA is able to generate optimal solutions for many benchmark problems of QAP, and near-optimal solutions for the remaining problems. The algorithm is also compared with other metaheuristic algorithms from the literature. The results of the comparison show that the WFA compares favorably with other metaheuristic algorithms used to solve the QAP.
As discussed in the previous section, an area of future research is to improve the choice of the WFA parameters to solve the QAP more efficiently with the possibility of obtaining better quality solutions quickly through integrating an adaptive parameter tuning scheme. This scheme could involve adjusting the parameters of the WFA after some clouds without improvement in best solution obtained so as to increase the solution exploitation capability. One such adjustment is to decrease MinEro and increase MaxUIE appropriately. An alternative adjustment is to increase MaxPop and generate DOW s onto the regions in which they exploit weakly through the previous clouds. It is also possible to explore the incorporation of more elements or factors of the hydrological cycle into the WFA, such as evaporation and percolation. Another area of future research is to apply the WFA to solve other types of optimization problems that are similar to the QAP by adapting some of the components of the algorithm appropriately.