Elite opposition-flower pollination algorithm for quadratic assignment problem

Abstract

The quadratic assignment problem (QAP) is one of the most studied combinatorial optimization problems with various practical applications. In This paper, we present an Elite Opposition-Flower Pollination Algorithm (EOFPA) for solving Quadratic Assignment Problems. The performance of the proposed algorithm is tested against a set of benchmarks of QAP from the public QAPLIB Library. we compare the algorithm against the best proposals from the related literatures and we determine that the proposed algorithm is superior to some other algorithms.

Keywords

Flower pollination algorithm meta-heuristics optimization quadratic assignment problem NP hard and combinatorial optimization

1 Introduction

The quadratic assignment problem (QAP) in location Theory is one of the models used for the multi-row layout problem with facilities of equal area and is known for its diverse applications. QAP was introduced by Koopmans and Beckman in 1957 [1] who were trying to model a facilities location problem. The objective of the problem is to assign a set of facilities to a set of locations in such a way to minimize the total assignment cost. The assignment cost for a pair of facilities is a function of the flow between the facilities and the distance between the locations of the facilities. It is possible to formulate some classic problems of combinatorial optimization, such as the traveling salesman, maximum clique and graph partitioning problems, as a QAP. The QAP belongs to the class of NP-complete problems and is considered as one of the most difficult combinatorial optimization problems. Exact solution strategies for the QAP have been unsuccessful for large problem (approximately N ≥ 25).

The mathematical formulation of the problem as follows [2]:

$\begin{matrix} QAP (Y, Z) = min f (x) \\ = \sum_{i = 1}^{n} \sum_{j = 1}^{n} \sum_{k = 1}^{n} \sum_{l = 1}^{n} a_{ik} b_{jl} x_{ij} x_{kl} \end{matrix}$ (1) $s . t X = (x_{ij}) \in Π_{n},$ where Y = (a_ik) _n×n corresponds to the flow matrix and X = (b_jl) _n×n corresponds to the distance matrix in a facility location application, Π_n denotes the set of all n × n permutation matrices, i.e.,

$\begin{matrix} Π_{n} & = & {(x_{ij})_{n \times n} : \sum_{i = 1}^{n} x_{ij} = 1, j = 1, \dots, n; \\ \sum_{j = 1}^{n} x_{ij} = 1, i = 1, \dots, n; x_{ij} \in {0, 1}, \\ i, j = 1, \dots, n} \end{matrix}$

x_ij = 1 means facility i being placed in location j

According to the computational complexity theory, there are no exact algorithms to solve NP-hard problems in polynomial time unless P = NP. Applications of the QAP in real life have been used to solve problems like: backboard Wiring [3], scheduling, process [4], design typewriter keyboard [5], hospital planning [6] other ergonomic designs, scheduling parallel production lines, forest parks [7], numerical analysis [8], turbine runner problem, very large scale integration (VLSI) etc. Other optimization combinatorial problems such as the traveling salesman problem, maximal clique, isomorphism and graph partitioning can be formulated as a QAP[9, 10].

Although small QAP instances can be solved with exact solution methods, the optimal solutions for large instances cannot be found due to the computational limitations. However, metaheuristic approaches are robust tools with their ability to produce high quality solutions for such conditions. Harmony Search [11], Simulated Annealing [7], Tabu Search [12, 13], Ant Colony Optimization [14], Genetic Algorithms [15 –17], Particle Swarm Optimization [18], Discrete firefly (DFA) [19], the Discrete Cat Swarm Optimization algorithms (DCA) [20] and teaching–learning-based optimization algorithms [21] are some of the well-known of these methods that have been successfully applied to the QAP. The metaheuristic approaches, with their well-known ability, can increase the solution quality for intractable problems. On the other hand, the exact solution methods do not provide much improvement in the size of optimally solvable problem instances since the complexity of intractable problem such as the Quadratic Assignment Problem.

The remainder of the paper is organized as follows: Section 2 briefly introduces the original flower pollination algorithm; this is followed in Section 3 by Elite Opposition- Flower Pollination algorithm for QAP; results analysis are described in Section 4. Finally, conclusions and future work are presented in Section 5.

2 The original flower pollination algorithm

Flower Pollination Algorithm (FPA) was founded by Yang in the year 2012. The algorithm has been applied to resolve some engineering design problems and its variants are proposed by scholars constantly [22–24 , 30–35]. The FPA is inspired by the flow pollination process of flowering plants are the following rules [25]:

R1: Biotic and cross-pollination can be considered as a process of global pollination process, and pollen-carrying pollinators move in a way that obeys Le’vy flights.

R2: For local pollination, a biotic and self-pollination are used.

R3: Pollinators such as insects can develop flower constancy, which is equivalent to a reproduction probability that is proportional to the similarity of two flowers involved.

R4: The interaction or switching of local pollination and global pollination can be controlled by a switch probability p ∈ [0, 1], with a slight bias toward local pollination.

In order to formulate updating formulas, we have to convert the aforementioned rules into updating equations. For example, in the global pollination step, flower pollen gametes are carried by pollinators such as insects, and pollen can travel over a long distance because insects can often fly and move in a much longer range. Therefore, Rule 1 and flower constancy can be represented mathematically as: $x_{i}^{t + 1} = x_{i}^{t} + γ L (λ) (x_{i}^{t} - B)$ (2)

Where $x_{i}^{t}$ is the pollen i or solution vector x_i at iteration t, and B is the current best solution found among all solutions at the current generation/iteration. Here γ is a scaling factor to control the step size. In addition, L (λ) is the parameter that corresponds to the strength of the pollination, which essentially is also the step size. Since insects may move over a long distance with various distance steps, we can use a Le’vy flight to imitate this characteristic efficiently. That is, we draw L > 0 from a Levy distribution: $L \sim \frac{λ Γ (λ) sin (π λ / 2)}{π} \frac{1}{S^{1 + λ}}, (S > > S_{0} > 0)$ (3)

Here, Γ (λ) is the standard gamma function, and this distribution is valid for large steps s > 0.

Then, to model the local pollination, both Rule 2 and Rule 3 can be represented as $x_{i}^{t + 1} = x_{i}^{t} + U (x_{j}^{t} - x_{k}^{t})$ (4)

Where $x_{j}^{t}$ and $x_{k}^{t}$ are pollen from different flowers of the same plant species. This essentially imitates the flower constancy in a limited neighborhood. Mathematically, if $x_{j}^{t}$ and $x_{k}^{t}$ comes from the same species or selected from the same population, this equivalently becomes a local random walk if we draw U from a uniform distribution in [0,1]. Though Flower pollination activities can occur at all scales, both local and global, adjacent flower patches or flowers in the not-so-far-away neighborhood are more likely to be pollinated by local flower pollen than those faraway. In order to imitate this, we can effectively use the switch probability like in Rule 4 or the proximity probability p to switch between common global pollination to intensive local pollination. To begin with, we can use a naive value of p = 0.5 as an initially value. A preliminary parametric showed that p = 0.8 might work better for most applications [25]. The basic steps of FPA can be summarized as the pseudo-code shown in Fig. 1.

Fig.1

Pseudo code of the Flower pollination algorithm.

3 The proposed algorithm for solving QAP

Flower pollination algorithm (FPA) is a novel metaheuristic optimization algorithm with quick convergence, but its population diversity and convergence precision can be limited in some applications. In order to enhance the global searching and local searching abilities, we append three optimization strategies to basic flower pollination algorithm (FPA). There are global elite opposition-based learning strategy (GEOLS), local self-adaptive greedy strategy (LSGS) and chaotic switching probability strategy (CSPS).The improvement involves two major optimization strategies. Global elite opposition-based learning enhances the diversity of the population, and the local self-adaptive greedy strategy enhances its exploitation ability [26].

3.1 Global elite opposition-based learning strategy (GEOLS)

Elite Opposition-based Learning is a new technique in the field of intelligence computation. Its main ideology is: For a feasible solution, calculate and evaluate the opposite solution at the same time, and choose the better one as the individual of next generation. In this paper, individual with the best fitness value in the population is viewed as the elite individual Basic Flower Pollination Algorithm use Lévy flight in global search process. It is simulated by Lévy distribution.

Basic Flower Pollination Algorithm use Lévy flight in global search process. It is simulated by Lévy distribution. As we know that it is a stochastic process, the probability of getting a good solution is relatively low. For increasing the probability of obtained a better solution to the problem in global search process and expand the searching space, this strategy is applied to the proposed EOFPA. In essence, it is a greedy strategy.

For explaining the definition of elite opposition-based solution, an example should be exhibited. If we suppose that the elite individual of the population is X_e = (x_e,1x_e,2, …, x_e,D) For the individual x_i (x_i,1x_i2, …, x_iD), the elite opposition-based solution of X_i can be defined $x_{i}^{'} = (x_{i, 1}^{'}, x_{i, 2}^{'}, \dots, x_{i, D}^{'})$ . And it can be obtained by following equation:

$\begin{matrix} x_{i, j}^{'} & = & k • ({da}_{j} + {db}_{j}) - x_{e, j}; \\ i & = & 1, 2, \dots, n; j = 1, 2, \dots, D \end{matrix}$ (5) where n is the population size, D is the dimension of X, k ∈ U (0, 1), (da_j, db_j) is the dynamic bound of jth decision variable. da_j, db_j can be obtained by following equation: ${da}_{j} = \min (x_{i, j}), {db}_{j} = \max (x_{i, j})$ (6)

As we know that the shrink of searching space may cause algorithm stuck in local minimal. Thus, in this proposed algorithm, we will update da_j and db_j every 50 generations. Dynamic bound is good at restoring searching experience. but it can make $x_{i, j}^{'}$ jump out of (da_j, db_j), if that happened, equation below should be used to reset $x_{i, j}^{'}$ $x_{i, j}^{'} = rand ({da}_{j}, {db}_{j}); {ifx}_{i, j}^{'} ≺ {da}_{j} {ordb}_{j} ≻ x_{i, j}^{'}$ (7)

In global searching process, this strategy expands the searching space of algorithm and it can strengthen the diversity of the population, thus the proposed global searching ability can be enhanced by this optimization strategy.

3.2 Local self-adaptive greedy strategy (LSGS)

Standard Flower Pollination Algorithm use DE to conduct local search. And it is known to us that the searching ability of standard DE is not good enough to solve high-dimensional optimization problems. For improving the local search, this local self-adaptive greedy strategy is added to the proposed algorithm. In local searching process, if X = (x_i,1x_i,2, …, x_i,D) is the ith individual in the population, we can find a greedy solution x^′ in the neighbor of it by following equation: $x_{i, j}^{'} = x_{i, j} + φ_{i, j} C_{i, j} x_{i, j}$ (8) where $\begin{matrix} C_{i, j} & = & C_{min} + exp [- C {(\frac{iter}{{Max}_{i} ter})}^{d}] \\ (C_{max} - C_{min}) \end{matrix}$ and $x_{i, j}^{'}$ is the jth decision variable of greedy solution, φ_i, j is a random number in (–1,1). iter is the number of current iteration, Max Generation is the maximum iteration. c_min, c_max, c and d are related parameters. By using this strategy, the adjustment of greedy solution is bigger at the beginning of the iterations. It helps to expand the searching space, enhance the ability of jump out of the local minima. And the adjustment of greedy solution is smaller in the end, which helps to enhance the local search and speed up finding the best solution.

3.3 Chaotic switching probability strategy (CSPS)

In FPA, local search and global search is controlled by a switch probability p ∈ [0, 1], and it is a constant value. We suppose that a reasonable algorithm should do more global search at the beginning of searching process and global search should be less in the end. Thus, we apply chaotic Switching Probability Strategy (CSPS) to adjust the proportion of two kinds of search. Switch probability p can alter according to the following equation: $Y_{n} = μ Y_{n} (1 - Y_{n}), Y_{n} \in [0, 1]$ (9)

Clearly, Y_n ∈ [0, 1] under the conditions that the initial Y₀ ∈ [0, 1], where n is the iteration number and μ = 4 . The selected chaotic map for all problems is the logistic map, according to the above equation. The basic steps of EOFPA can be summarized as the pseudo-code shown in Fig. 3.

Fig.2

Pseudo code of the EOFPA.

Fig.3

The convergence curves for instance 1.

3.4 Some preparation work for using the EOFPA to solve QAP

For unconstrained problem, its global best solution is the one who has the minimum objective function value. In the meantime, it is hard to measure and determine the global best solution of constrained problem, for it is difficult to find a balance between the constraints and the objective function value.

3.4.1 Handling constraints

One of the well-known techniques of handling constraints is penalty function, which transforms constrained problem into unconstrained one, consisting of a sum of the objective and the constraints weighted by penalties. By using penalty function methods, the objectives are inclined to guide the search toward the feasible solutions. Here, we create a new penalty function to tradeoff the constraints and the objective function value. This method adopts the information of all solutions. The new fitness function can be defined as: $min F (x) = f (x) + λ \sum_{n = 1}^{K} \max (0, g_{n})$ where f (x) is the objective function for assignment problem, λ is the penalty coefficient and it is set to 10¹¹ in this paper, K is the number of constraints and g_n the constraints of the problem. The obtained optimal solution is a real number, and we transform it into a nearest integer.

4 Experimental results and analysis

4.1 Experimental setup

All the experiments were performed on a Windows 7 Ultimate 64-bit operating system; processor Intel Core to Duo CPU 2.20 GHZ; 4 GB of RAM and code was implemented in MATLAB.

4.2 Comparison results

In a facility layout problem in which there are n facilities to be assigned to n given location. The QAP formulation requires an equal number of facilities and locations. If there are fewer than n, say m < n, facilities to be assigned to n locations, then to use the QAP formulation, n-m dummy facilities should be created and a zero flow between each of these and all others must be assigned (including the other dummy facilities). If there are fewer locations than facilities, then the problem is infeasible [27]. In this section, some instances from Quadratic Assignment Problem Library (QAPLIB) and two artificial instances are designed to test the performance ofEOFPA.

4.2.1 Instances from QAPLIB

Numerous examples have been done to verify the weight of the planned algorithm. The standard flower pollination algorithm (FPA) [25], particle swarm optimization (PSO) [18, 28], Discrete firefly (DFA) [19] and the Discrete Cat Swarm Optimization algorithms (DCA) [20] are tested on some instances (benchmarks) of QAP taken from the publicly available electronic library QAPLIB of QAP problems [29]. Most of the instances included in QAPLIB have already been solved in the literature and their optimality results can be used to compare algorithms. The numerical value in the name of an instance represents the number of provided cities.

The values of parameters of the proposed algorithm are selected, based on some preliminary trials. The initial parameters of standard flower pollination algorithm are set at n = 50, p = 0.8 and the number of iterations is set to t = 1000.

As can be seen in Tables 1, 2, the EOFPA has demonstrated an overwhelming advantage over the other algorithms on solving Quadratic Assignment Problems with large scales. The best solutions found by the EOFPA are all better than those obtained by the other algorithms. Furthermore, the best solutions found by the EOFPA are even better than the best solutions obtained by DFA. The EOFPA has better performance than the DFA on solving the nine problems.

Table 1
Summarize the experiments results between EOFPA, FPA, particle swarm optimization algorithm, discrete cat algorithm and discrete firefly algorithm

Instance Optimal sol. EOFPA DFA [19] DCA [20] FPA PSO

Chr12a 9552 9552 9552 9552 9552 9552

Chr15a 9896 9896 – 9896 9230 9896

Esc16h 996 996 996 996 996 996

Nug17 1732 1732 – 1732 1652 1732

nug18 1930 1930 1946 1930 1940 1949

had20 6922 6922 6922 6922 6811 6922

Chr20a 2192 2192 3824 2192 3745 3945

Nug21 2438 2438 – 2438 2501 2438

Chr22a 6156 6156 – 6156 5231 6156

Nug24 3488 3488 – 3488 3488 3488

Chr25a 3796 3796 3796 3796 3796 3796

tai25b 34435646 34435646 372821202 344355646 33213734 32123445

Bur26a 5426670 5426670 5432634 – 5435431 5568559

Nug27 5234 5234 – – 5234 5234

Esc32g 6 6 6 6 8 8

Ste36a 9526 9526 – – 9526 9526

Lipa40a 31538 31538 – – 28568 30214

Lipa50a 62093 62093 – 62093 49521 60854

Instance	Optimal sol.	EOFPA	DFA [19]	DCA [20]	FPA	PSO
Chr12a	9552	9552	9552	9552	9552	9552
Chr15a	9896	9896	–	9896	9230	9896
Esc16h	996	996	996	996	996	996
Nug17	1732	1732	–	1732	1652	1732
nug18	1930	1930	1946	1930	1940	1949
had20	6922	6922	6922	6922	6811	6922
Chr20a	2192	2192	3824	2192	3745	3945
Nug21	2438	2438	–	2438	2501	2438
Chr22a	6156	6156	–	6156	5231	6156
Nug24	3488	3488	–	3488	3488	3488
Chr25a	3796	3796	3796	3796	3796	3796
tai25b	34435646	34435646	372821202	344355646	33213734	32123445
Bur26a	5426670	5426670	5432634	–	5435431	5568559
Nug27	5234	5234	–	–	5234	5234
Esc32g	6	6	6	6	8	8
Ste36a	9526	9526	–	–	9526	9526
Lipa40a	31538	31538	–	–	28568	30214
Lipa50a	62093	62093	–	62093	49521	60854

‘–’ means the instance not tested with the algorithm.

Table 2

The experiments results between the proposed method and discrete firefly algorithm [19]

Instance	EOFPA	DFA
Chr12a	Mean	9552	9552
	Best	9552	9552
	SD	0	0
Esc16h	Mean	996	996
	Best	996	996
	SD	0	0
Nug18	Mean	1930	1995
	Best	1930	1946
	SD	0	46.7166
Had20	Mean	6922	6922
	Best	6922	6922
	SD	0	0
Chr20a	Mean	2192	3982
	Best	2192	3824
	SD	0	84.5327
Chr25a	Mean	3796	9077.8
	Best	3796	8716
	SD	0	174.1786
Tai25b	Mean	34435646	375488560
	Best	34435646	372821202
	SD	0	1208102.9
Bur26a	Mean	5426670	5433182.4
	Best	5426670	5432634
	SD	0	567.1596
Esc32g	Mean	6	6
	Best	6	6
	SD	0	0

4.2.2 Artificial instances

In this section, two artificial instances are tested in this subsection. The details of the instances are given in Table 3. x and y are represented the x-coordinate and y-coordinate of each locations respectively. And the flow between the facilities are listed in the form of array. The details of the instances are given as follows:

Table 3
The details of the two artificial instances

Instances

1 $\begin{matrix} flow = [ & 0 & 30 & 18 & 34 & 31 & 25 & 22 & 20 \\ 30 & 0 & 31 & 25 & 27 & 39 & 34 & 26 \\ 18 & 31 & 0 & 34 & 26 & 22 & 38 & 28 \\ 34 & 25 & 34 & 0 & 36 & 30 & 46 & 37 \\ 31 & 27 & 26 & 36 & 0 & 26 & 22 & 32 \\ 25 & 39 & 22 & 30 & 26 & 0 & 20 & 30 \\ 22 & 34 & 38 & 46 & 22 & 20 & 0 & 42 \\ 20 & 26 & 28 & 37 & 32 & 30 & 42 & 0]; \end{matrix}$

x = [93480926613968637287169248485333808308779128212229477590];

y = [63604912704595984556987404249185283132181091773163980263];

2 $\begin{matrix} flow = [ & 0 & 6 & 6 & 3 & 5 & 5 & 5 \\ 6 & 0 & 6 & 4 & - 10 & 3 & 6 \\ 6 & 6 & 0 & 4 & 5 & 8 & 6 \\ 3 & 4 & 4 & 0 & 4 & 4 & 100 \\ 5 & - 10 & 5 & 4 & 0 & 3 & 4 \\ 5 & 3 & 8 & 4 & 3 & 0 & 4 \\ 5 & 6 & 6 & 100 & 4 & 4 & 0]; \end{matrix}$

x = [6780623454365346393583588790833826784967];

y = [9819438930958717485865686227336341737];

Instances
1	$\begin{matrix} flow = [ & 0 & 30 & 18 & 34 & 31 & 25 & 22 & 20 \\ 30 & 0 & 31 & 25 & 27 & 39 & 34 & 26 \\ 18 & 31 & 0 & 34 & 26 & 22 & 38 & 28 \\ 34 & 25 & 34 & 0 & 36 & 30 & 46 & 37 \\ 31 & 27 & 26 & 36 & 0 & 26 & 22 & 32 \\ 25 & 39 & 22 & 30 & 26 & 0 & 20 & 30 \\ 22 & 34 & 38 & 46 & 22 & 20 & 0 & 42 \\ 20 & 26 & 28 & 37 & 32 & 30 & 42 & 0]; \end{matrix}$
	x = [93480926613968637287169248485333808308779128212229477590];
	y = [63604912704595984556987404249185283132181091773163980263];
2	$\begin{matrix} flow = [ & 0 & 6 & 6 & 3 & 5 & 5 & 5 \\ 6 & 0 & 6 & 4 & - 10 & 3 & 6 \\ 6 & 6 & 0 & 4 & 5 & 8 & 6 \\ 3 & 4 & 4 & 0 & 4 & 4 & 100 \\ 5 & - 10 & 5 & 4 & 0 & 3 & 4 \\ 5 & 3 & 8 & 4 & 3 & 0 & 4 \\ 5 & 6 & 6 & 100 & 4 & 4 & 0]; \end{matrix}$
	x = [6780623454365346393583588790833826784967];
	y = [9819438930958717485865686227336341737];

To evaluate the performance of EOFPA, it is compared with ACO [14], FA [19], GA [15], PSO [18, 28], FPA [25]. The maximum generation of all algorithms is set as 1000, the population size are set to 100. The parameters setting of the mentioned algorithms are given in Table 4. The setting values of algorithm control parameters of the mentioned algorithms are given below.

Table 4

Values of parameters of each of the rival algorithms

ACO		GA		FPA&EOFPA
Parameter	Value	Parameter	Value	Parameter	Value
evaporation rate	0.1	crossover rate	0.4	switch probability	0.8
		mutate rate	0.8
PSO		FA
Parameter	Value	Parameter	Value
C ₁	1.5	mutation coefficient	0.2
C ₂	2.0	attraction coefficient	2
weight factor	0.7298	light absorption coefficient	1

Each algorithm is applied 20 times individually with random initial solution. The comparison of test results is shown in Table 5, the Best, Worst, Mean and Std represent optimal fitness values, worst fitness value, mean fitness value and standard deviation respectively. It is apparent that the best value of FA, GA and FPA reach the same result as EOFPA, which means the four algorithm can get the same optimal value both in instance one and instance two. While, the worst value, standard deviation and mean values of FPA and EOFPA are much better than other algorithms. Especially in instance two, EOFPA is superior to other five algorithm. Figures 4 and 6 show convergence curves of the six algorithms in solving the two artificial instances. It is easy to find that the curve of EOFPA is much smoother than other algorithms and its convergence speed is faster. It is clear to see the superiority in EOFPA compared with ACO, FA, GA and PSO in terms of ANOVA tests as shown in Figs. 5 and 7. The boxplot for EOFPA have smaller value and less height than those of ACO, FA, GA and PSO and achieves the better results to EOFPA in instance two.

Table 5

The experiments results of six algorithms for two artificial instances

		ACO	FA	GA	PSO	FPA	EOFPA
Instance 1	Best	35251.52	31868.61	31868.61	32249.52	31868.61	31868.61
	Worst	46434.13	37786.43	37739.73	49219.83	32452.78	33396.26
	Mean	41455.09	33388.58	32931.46	39683.59	31981.65	32089.24
	SD	2691.01	1992.34	1356.20	5517.06	160.13	416.80
Instance 2	Best	3796.82	3498.06	3498.06	3518.37	3498.06	3498.06
	Worst	4875.46	3824.30	4714.98	6120.05	3568.84	3557.61
	Mean	4317.27	3579.80	3790.17	4403.70	3517.84	3514.34
	SD	325.47	93.32	258.97	886.86	17.53	15.59

Fig.4

Anova test for instance 1.

Fig.5

The convergence curves for instance 2.

Fig.6

Anova test for instance 2.

Fig.7

Artificial QAP instances 1 for EOFPA.

4.2.3 Graphical results comparison

In this subsection, the two artificial instances are selected to carry out the graphical comparison between EOFPA and other algorithms. The maximum generation is set to 20 to demonstrate the superiority of EOFPA. The graphical results of EOFPA for the two instances are presented in Figs. 7 and 10. Circles represent the given locations and the concentrated yellow labels indicate the facilities are wellassigned.

Fig.8

Artificial QAP instances 1 for FPA.

Fig.9

Artificial QAP instances 1 for FA.

Fig.10

Artificial QAP instances 2 for EOFPA.

As shown in Table 5, the numerical value of FPA is very close to EOFPA and both the two algorithms are perform better than other algorithms. A further comparison to demonstrate the differences of efficient ability between FPA and EOFPA are shown in Figs. 9 and 12. In contrast to Figs. 8 and 11, the yellow labels are not concentrated in Figs. 9 and 11. In order to carrying out another comparison for instance one, FA is selected cause the algorithm performs well in the speed of convergence and stability, which can be concluded from Figs. 4 and 6. The comparison is illustrated with Figs. 8 and 10 and only one facility is not located in a better location shown in Fig. 10. Figures 11 and 13 are drawn for the comparison for instance two between PSO and EOFPA, witch directly show the superiority of EOFPA in QAP.

Fig.11

Artificial QAP instances 2 for FPA.

Fig.12

Artificial QAP instances 2 for PSO.

5 Conclusion and future work

The Quadratic Assignment Problem (QAP) is a well-known NP-hard combinatorial optimization problem that has received a lot of attention from the research community since it has many practical applications, such as allocation of facilities, backboard Wiring, scheduling, process communication, design typewriter keyboard, etc. In this paper, we present an Elite Opposition-Flower Pollination Algorithm for solving the Quadratic assignment Problem. In the computational results, firstly, we evaluate the performance of our algorithm on widely known instances from the literature. In these experiments, we compare our algorithm against the best proposals from the related literature and we determine that our algorithm exhibits mostly better performance than other algorithms, which is one of the best method for solving the QAP and find the latest best solutions of many benchmark QAPs in QAPLIB. Secondly, two artificial instances, in which the number of facility is fewer than location, are tested using the QAP formulation. The results illustrate that EOFPA performs better than ACO, FA, GA and PSO. Meanwhile, it is powerful in convergence speed and is equipped with strong robustness compared with other algorithms. The graphical results give a further comparison to demonstrate the superiority of EOFPA in efficient ability.

For future work, the EOFPA will be extended to more QAP instances with different types and sizes and more algorithms can be applied to be conducted. For the constrained engineering optimization problems, it is often challenging to obtain high equality solution. The EOFPA should be used to solve these optimization problems to validate its superiority. In order to test the performance of EOFPA comprehensively, the existed NP-hard problems in literature, such as traveling salesman problem and graph coloring problem, should be solved in the future. Also, new adaptive mechanism can be adopted to the original FPA to enhance its search ability in the future research.

Footnotes

Acknowledgments

This work was supported by the National Science Foundation of China under Grants Nos. 61463007, 61563008.

References

Koopmans

T.C.

and Beckmann

, Assignment problems and the location of economic activities, Econometrica 25(1) (1957), 53–76.

Cela

, The quadratic assignment problem: Theory and algorithms, Vol. 1. Springer Science & Business Media, 2013.

Steinberg

, The backboard wiring problem: A placement algorithm, Siam Review 3(1) (1961), 37–50.

Geoffrion

A.M.

and Graves

G.W.

, Scheduling parallel production lines with changeover costs: Practical application of a quadratic assignment/LP approach, Operations Research 24(4) (1976), 595–610.

Pollatschek

M.A.

, Gershoni

and Radday

Y.T.

, Optimization of the typewriter keyboard by simulation, Angewandte Informatik 17 (1976), 438–439.

Elshafei

A.N.

, Hospital layout as a quadratic assignment problem, Operational Research Quarterly (1970-1977) 28(1) (1977), 167–179.

Wilhelm

M.R.

and Ward

T.L.

, Solving q uadratic assignment problems by ‘simulated annealing’, Iie Transactions 19(1) (1987), 107–119.

Brusco

M.J.

and Stahl

, Using quadratic assignment methods to generate initial permutations for least-squares unidimensional scaling of symmetric proximity matrices, Journal of Classification 17(2) (2000), 197–223.

Loiola

E.M.

, et al., A survey for the quadratic assignment problem, European Journal of Operational Research 176(2) (2007), 657–690.

10.

Drezner

, The quadratic assignment problem, Location Science, Springer International Publishing, 2015, pp. 345–363.

11.

Amudha

, Improving the solution quality of quadratic assignment problems using harmony improvised, 3(8) (2012), 1–8.

12.

Skorin-Kapov

, Tabu search applied to the quadratic assignment problem, Informs Journal on Computing 2(1) (1990), 33–45.

13.

Taillard

, Robust tabu search for the quadratic assignment problem, Parallel Comput, vol. 17, 1991, pp. 443–455.

14.

Montero

A.R.

and López

A.S.

, Ant Colony Optimization for Solving the Quadratic Assignment Problem, Fourteenth Mexican International Conference on Artificial Intelligence (2015), pp. 182–187. IEEE.

15.

Azarbonyad

and Babazadeh

, A Genetic Algorithm for solving Quadratic Assignment Problem (QAP), Computer Science (2014).

16.

Ahuja

R.K.

, Orlin

J.B.

and Tiwari

, A greedy genetic algorithm for the quadratic assignment problem[J], Computers & Operations Research 27(10) (1995), 917–934.

17.

Ahmed

Z.H.

, A multi-parent genetic algorithm for the quadratic assignment problem, Opsearch (2015), 1–19.

18.

Mamaghani

A.S.

and Meybodi

M.R.

, Solving the Quadratic Assignment Problem with the modified hybrid PSO algorithm, International Conference on Application of Information and Communication Technologies IEEE, 2012, pp. 1–6.

19.

Durkota, Implementation of a discrete firefly algorithm for the QAP problem within the sage framework, Master’s thesis, Czech Technical University, Prague, 2009.

20.

Riffi

M. Essaid

and Bouzidi

, Discrete cat swarm optimization for solving the quadratic assignment problem, International Journal of Soft Computing and Software Engineering [JSCSE] 4(6) (2014), 85–92.

21.

Dokeroglu

, Hybrid teaching–learning-based optimization algorithms for the Quadratic Assignment Problem, Computers & Industrial Engineering 85(C) (2015), 86–101.

22.

Yang

X.S.

, Karamanoglu

and He

, Flower pollination algorithm: A novel approach for multiobjective optimization[J], Engineering Optimization 46(9) (2014), 1222–1237.

23.

Reddy

P.D.P.

, Reddy

V.C.V.

and Manohar

T.G.

, Application of flower pollination algorithm for optimal placement and sizing of distributed generation in Distribution systems, Journal of Electrical Systems & Information Technology 3(1) (2016), 14–22.

24.

Abdel-Raouf

, Abdel-Baset

and El-henawy

, An Improved Flower Pollination Algorithm with Chaos, I.J. Education and Management Engineering, vol. 2, 2014, pp. 1–8.

25.

Yang

X.-S.

, Flower pollination algorithm for global optimization, Unconventional computation and natural computation, Springer, Berlin, Heidelberg, 2012, pp. 240–249.

26.

Zhou

, Wang

and Luo

, Elite opposition-based flower pollination algorithm, Neurocomputing 188 (2016), 194–310.

27.

Heragu

, Facilities Design, PWS Publishing company, Boston, 1997.

28.

Kennedy

, Eberhart

R.C.

, Particle swarm optimization, in: Proc of the IEEE International Conference on Neural Networks, IEEE Service Center, Piscataway, NJ, 1995, pp. 1942–1948.

29.

Burkard

R.E.

, Karisch

S.E.

and Rendl

, QAPLIB–a quadratic assignment problem library, Journal of Global Optimization 10(4) (1997), 391–403. Accessed: 5 June 2016.

30.

Raouf

, El-henawy

and Abdel-Baset

, A novel hybrid flower pollination algorithm with chaotic harmony search for solving Sudoku puzzles, International Journal of Modern Education and Computer Science 3 (2014), 38–44.

31.

Abdel-Baset

and Hezam

, An improved flower pollination algorithm based on simulated annealing for solving engineering optimization problems, Asian Journal of Mathematics and Computer Research 3(3) (2015), 194–170.

32.

Abdel-Baset

and Hezam

, A hybrid flower pollination algorithm for solving ill-conditioned set of equations, International Journal of Bio-Inspired Computation 8(4) (2016), 215–220.

33.

Abdel-Baset

and Hezam

I.M.

, An improved flower pollination algorithm for ratios optimization problems, Applied Mathematics & Information Sciences Letters An International Journal 3(2) (2015), 83–91.

34.

Abdel-Baset

and Hezam

I.M.

, An effective hybrid flower pollination and genetic algorithm for constrained optimization problems, Advanced Engineering Technology and Application An International Journal 4 (2015), 27–27.

35.

Abdel-Baset

and Hezam

, A hybrid flower pollination algorithm for engineering optimization problems, International Journal of Computer Applications 140(12) (2016).