A discrete artificial bee colony algorithm for quadratic assignment problem

Abstract

The quadratic assignment problem (QAP) is a well-known challenging combinational optimization problem that has received many researchers’ attention with varied real-world and industrial applications areas. Using the framework of basic artificial bee colony algorithm, frequently used crossover and mutation operators, and combined with an effective local search method, this paper proposes a simple but effective discrete artificial bee colony (DABC) algorithm for solving quadratic assignment problems (QAPs). Typical QAP benchmark instances are selected from QAPLIB in order to conduct the simulation experiment where common performance metrics are used to evaluate the algorithm. The paper also investigates the influence factors of the algorithm’s performance. The results show that the proposed algorithm is a quite effective and practical new approach for handling QAP problems.

Keywords

Discrete artificial bee colony algorithm combinatorial optimization Quadratic Assignment Problem

1. Introduction

Quadratic Assignment Problem is a typical combinational optimization problem [1]. The mathematical description of Quadratic Assignment Problem is [2]: presetting n facilities and n locations, define two n × n matrices $F = (f_{i j})$ and $D = (d_{i j})$ , where $f_{i j}$ represents the flow rates between facility i and j; $d_{i j}$ means the distance between location i and j. QAP’s goal is to find a permutation ϕ from collection of $N = {0, 1, \dots, n - 1}$ to minimize the objective function. $\begin{matrix} (1) & z = \sum_{i = 0}^{n - 1} \sum_{j = 0}^{n - 1} f_{i j} d_{ϕ (i) ϕ (j)} \end{matrix}$

QAP is well known because of its widespread application background. At the same time, it is recognized as one of intricate problems. At present, the QAP has been researched deeply. The research and design of heuristic algorithm for solving QAP become one research hot spot in the academia because QAP is an NP-hard problem [3]. Misevicius and Verene [12] presented a hybrid genetic-hierarchical algorithm for the solution of the quadratic assignment problem. The genetic algorithm is combined with the so-called hierarchical (self-similar) iterated tabu search algorithm, which serves as a powerful local optimizer (local improvement algorithm) of the offspring solutions produced by the crossover operator of the genetic algorithm. The results of the conducted computational experiments demonstrate the promising performance and competitiveness of the proposed algorithm. Ahuja et al. [1] proposed a solving QAP greedy genetic algorithm. In the design of the algorithm, the author integrated the multiple greedy strategy, such as using heuristic algorithm, to produce the initial population of random structure and design of a crossover operator based on greedy thought. In QAPLIB’s 103 test cases, greedy genetic algorithm has been found the best solution to problems of the known. Pardalos et al. [14] gave a suitable greedy randomized adaptive search procedure (GRASP) for QAP. The method had achieved a satisfactory solution on some QAPLIB test cases. Misevicius [10] put forward an improved simulated annealing algorithm to solve the problem of QAP effectively. The algorithm mixes with tabu search in order to improve the quality of the solution. The experimental results showed that the performance of the algorithm is better than the earlier version of the simulated annealing algorithm in QAPLIB test case. Misevicius [11] proposed a new version of the tabu search algorithm for QAP. One of the most important features of his tabu search implementation is an efficient use of mutations applied to the best solutions. He tested this approach on a number of instances from the library of the QAP instances–QAPLIB. The results obtained from the experiments show that the proposed algorithm belongs to the efficient heuristics for QAP. The researchers designed other heuristic algorithms specifically for solving QAP, such as ant colony algorithm [19], particle swarm optimization algorithm [22], flood algorithm [18], differential evolution algorithm [16] and bacterial foraging algorithm [15].

Artificial Bee Colony (ABC) is a simulation of the process of bees intelligent optimization algorithm and is put forward by Karaboga and Basturk [6]. In the ABC algorithm, there are three different types of bees such as employed bees, onlooker bees and scout bees. Different bee species have different work tasks. ABC algorithm considers a feasible solution to the problem as a food source, and give it a fitness. In the process of algorithm implementation, firstly, each employed bee produces a new food source and greedy strategy is used to choose between the old and the new food source. Secondly, each onlooker bee chooses a food source by way of roulette according to the information of the food source providing by the employed bees (i.e. fitness), uses the mechanism which is similar to the employed bees to try to improve the food source. Finally, if a food source in the consecutive iterations of “limit” did not improve, it corresponds to the employed bees changing to scout bees. Scout bees can produce a viable random solution according to the search space [20,21]. Repeat the process until the termination conditions are met.

Artificial bee colony algorithm has achieved great success in solving a single objective continuous optimization problems. In recent years, the study of discrete artificial bee colony algorithm has also aroused the attention of many scholars at home and abroad. In the existing literature, there are a number of examples that use artificial colony algorithm to solve the Lot-streaming Flow Shop Scheduling Problems [17], Permutation Flow Shop Scheduling Problem [9], Job-shop schedule problem [5] and Traveling Salesman Problem [7,13], amongst others. However, there is almost no literature using ABC algorithm to solve the problem of QAP. The research emphasis of this paper is the design and implementation of the discrete artificial colony algorithm which is suitable for QAP’s problem. Using the basic framework of artificial bee colony algorithm, applying common crossover operator and mutation operator and combining with effective local search strategy is the design of a simple and effective discrete artificial bee colony (DABC) algorithm. We choose the famous QAPLIB test instance to conduct a simulation experiment and compare the experimental results with the optimal results that have been reported. Finally, the paper discusses and analyzes the influence of local search strategy, mutation operator and different control parameters on the performance of the algorithm.

2. Discrete artificial bee colony algorithm of solving QAP

Solving the quadratic assignment problem which is put forward by this paper of the main process of discrete artificial bee colony (DABC) algorithm is shown in Fig. 1. As can be seen, DABC algorithm includes five main parts, initializing controls parameter, initializing colony (food source) and the phase of the employed bees, onlooker bees and scout bees.

2.1. Initializing control parameters

There are two control parameters in DABC algorithm, the colony’s size of $C S$ and abandoned condition limit. In DABC algorithm, the colony consists of equal number of employed bees and onlooker bees, each employed bee corresponds to a food source (i.e., a solution in the solution space). Therefore, the number of food sources $F N$ is half of the colony size, namely the $F N = \frac{C S}{2}$ . For each food source $S_{i}$ , the variable ${trial}_{i}$ record the process of the search that the food source are not improved continually. If the value of trial corresponding to a food source is greater than the predetermined limit, the food source abandons the employed bees corresponding to it and it is replaced by a new food source which is searched randomly by scout bees. The algorithm continuously repeats the phase of the employed bee, onlooker bee and scout bee. When the number of the evaluation FEs which is in the objective function (1) exceeded the allowed maximum maxFEs, the algorithm terminates. The two control parameters values are determined in advance before running DABC algorithm.

2.2. Coding scheme

Code maps the feasible solution to the problem into a “string” with a suitable algorithm. The choice of the ways of encoding will have great influence on the performance of the algorithm. In terms of QAP, a common way of coding is encoding the feasible solution into Permutations ϕ, a collection, $N = {0, 1, \dots, n - 1}$ ,which is composed of n numbers. Among them the first j number shows the location number of facility j. Such as $ϕ = {2, 4, 0, 5, 1, 3}$ , it indicates that the zeroth facility is placed in the second location and the first facility is placed in the fifth location. (Note: the serial number of facilities and locations are starting from 0). This encoding method is also used in this paper.

Fig. 1.

Main flowchart of DABC.

Fig. 2.

Employed bee phase.

2.3. Initializing colony

According to the encoding rule, the number of feasible solution is up to $n!$ , for n facilities and the n locations of the QAP. In the initialization phase, DABC algorithm produces $F N$ food sources (solutions) randomly according to the problem of search space. Then, calculate the random solution of objective function (1), and then find the optimal (minimum objective function) food source $gbest$ from current colony. At this point, the value of the objective function evaluation’s frequency $F E s$ is $F N$ , and the trial of each food source is initialized to 0.

2.4. Employed bees’ phase

The process of the Employed bees phase is shown in Fig. 2. For each food source $S_{i}$ , first determine the neighbors $K_{i}$ , defined as another food source selected by colony randomly. And then use the crossover operator to generate two individuals, $S_{i}$ and $K_{i}$ . In this paper, we choose the commonly used PMX crossover operator [4]. Then, select randomly individuals as a new food source, C of $S_{i}$ and calculating the objective function value. If C is better than $S_{i}$ (namely C objective function value is less than the objective function value of $S_{i}$ ), replace $S_{i}$ with C and change ${trial}_{i}$ to 0; on the other hand, the ${trial}_{i}$ ’s value add 1. If C is better than the $gbest$ , update the $gbest$ .

2.5. Onlooker bees’ phase

The process of the Employed bees phase is shown in Fig. 3. At this stage, the onlooker bee will select individuals to improve adapting the way of roulette according to the food source information provided by employed bee. The probability of the ith food source which is selected is ${prob}_{i}$ . The calculation process is as follows:

Use the formula (1) to calculate the objective function of ith food source $z_{i}$ ;

Find out the minimum value of all $z_{i}$ ;

Calculate $D_{i} = z_{i} - min$ , $i = 1, 2, \dots, F N$ ;

Calculate $sum = \sum_{i = 1}^{F N} D_{i}$ ;

If the sum is greater than zero, then $\begin{matrix} (2) & {prob}_{i} = 1 - (0.9 \times \frac{D_{i}}{sum} + 0.1) \end{matrix}$

If the sum is equal to 0, then $\begin{matrix} (3) & {prob}_{i} = \frac{1}{F N} \end{matrix}$

In a specific colony, the minimum min of all food source’s objective function is fixed. If the sum is greater than 0 (namely the objective functions of each food source are not equal), the formula (2) is used to calculate ${prob}_{i}$ . At this point, if the objective function of the food source is smaller (better), $D_{i}$ become smaller, then leads to the greater ${prob}_{i}$ . Thus, excellent food source will be selected in a larger probability. If the sum is zero (i.e., the objective functions of the food source are equal), the probability of each food source selected at this time is all $\frac{1}{F N}$ .

Fig. 3.

Onlooker bee phase.

The number of the onlooker bee in DABC algorithm is $F N$ . Each bee will select and try to improve a food source. In selection process, the greater food source will be selected more. When a food source was successfully selected, the onlooker bee mutates the food source and produce a new one. Mutation is varied and this paper uses common exchange variation, namely selected two positions randomly, and then exchange the values of these locations. The mutation operation is conducive to a wider search [8], which can improve the search performance of the algorithm. Experiments have proved the basic artificial bee colony algorithm possessing the ability of strong global search, and the ability of local search is relatively insufficient [21]. In order to make the DABC possessing better local search, this paper introduced a method, 2 – exchange, a local search algorithm [2]. As shown in Fig. 3, after 10% of the food source mutation, it will enter the local search phase. For a food source, 2 – exchange local search uses the method of swap to produce “neighbors”, and all “neighbors” form the “neighborhood” of the food sources. The algorithm uses a certain way to traverse a particular “neighborhood” of food source. If it finds an objective function of a “neighbor” which is smaller than itself, “neighbors” is used to replace the food source, otherwise nothing is done.

For n facilities and n locations of the QAP, the number of the “neighbors” of the food source ϕ is $C_{n}^{2} = n (n - 1) / 2$ . When 2 – exchange local search is performed, in order to determine to replace or not, the first “neighbors” objective function needs to be calculated to compare. Obviously, the time’s complexity of the algorithm is $O (n^{4})$ (the objective function (1) time’s complexity is $O (n^{2})$ ). In fact, in order to determine to replace or not, we only need to calculate the difference of the objective function between the old and the new food source. At this point time complexity of 2 – exchange is reduced to $O (n^{3})$ (Determining the difference between the old and the new food source of the objective function of the time complexity is $O (n)$ ). 2 – Exchange local search specific algorithm is given in Algorithm 1.

Algorithm 1

2- Exchange local search’s specific algorithm

2.6. Scout bees’ phase

Scout bees phase of the process is shown in Fig. 4. As mentioned earlier, when the trial value of certain food source is more than limit value, the food source will be discarded, and the corresponding employed bees will be converted to scout bees. First, find a maximum value from a swarm of bees in the trials of food source, and then determine whether the trial value is greater than the limit. If so, generated a new food source Sol randomly, then carry on the mutation and local search. Finally, evaluate the new result and use it to replace the original source of food. In the DABC algorithm, only one scout bee is allowed at each iteration.

Fig. 4.

Scout bee phase.

3. The experiment part

3.1. The experimental results and analysis

In order to test the performance of DABC algorithm, this paper chooses 75 simulation benchmark examples of QAPLIB [3]. The size of these benchmark examples ranges from $n = 12$ to $n = 150$ , and most of them belong to QAP problems that are difficult to optimize. We select gap and running time as performance index, which is defined respectively as follows:

Definition 1.
Performance gap [1] is used to measure the quality of the solution. For a specific problem, suppose algorithm finding the optimal value of ${OPT}_{a lg}$ , the known optimal value or the actual optimal value of the problem is ${OPT}_{best}$ , the gap is defined as: $\begin{matrix} (4) & gap = \frac{{OPT}_{a lg} - {OPT}_{best}}{{OPT}_{best}} \times 100 % \end{matrix}$ The smaller the index gap, then the solution is more precise and the algorithm is more effective.
Definition 2.
The running time of the algorithm is the time required for the last update $gbest$ . Set the last updated $gbest$ corresponding to the assessment’s times of objective is $F E s_{cut}$ and allow maximum times of the objective function evaluation as $max F E s$ . If the total time used at the termination of the algorithm is $T_{t}$ , the running time is defined as: $\begin{matrix} (5) & R T = \frac{T_{t}}{max F E s} \times F E s_{cut} \end{matrix}$

The control parameters of DABC algorithm are set to: $C S = 100$ , $lim i t = 100$ . When the evaluation’s times of target function reach to the maximum value $max F E s = 1000000$ , or the global best solution $gbest$ has not been improved more than $1 / 2 max F E s = 500000$ , the algorithm terminates. For each benchmark instance, the DABC algorithm runs 30 times independently. The computer configured for the experiment is Pentium (R) Dual-core CPU T4500 2.30 GHz 1.58 GHz, 1.99 GB of ram. Table 1 records the minimum value, average value, maximum value of the performance index gap (%) and the average running time (S). When you calculate gap, the actual optimal value of each benchmark instance or the latest best known value is available in the literature [3] and QAPLIB’s official website (www.opt.math.tu-graz.ac.at/qaplib/).

As can be seen from Table 1, in terms of the minimum value of gap, the DABC algorithm can solve 55 benchmark instances successfully (73% of the total). For the average, the percentage of successful solution to the benchmark instance is $30 / 75 = 40 %$ , but the maximum average gap is only 2.89% (chr20b). The above analysis shows that DABC algorithm not only has a wide range of applications, but also has high accuracy. From the running time, the DABC algorithm can find the optimal solution in a short period of time. However, due to the inherent complexity of QAP, as the scale of the problem increases, the time of the algorithm also presents a growing trend.

Table 1
Experimental results of DABC on selected benchmarks from QAPLIB

Benchmarks Performance indicator gap Runtime Benchmarks Performance indicator gap Runtime

Min Average Max Min Average Max

bur26a 0.00 0.00 0.00 0.41 chr20b 0.00 2.89 6.01 5.22

bur26b 0.00 0.00 0.00 0.48 chr20c 0.00 0.79 4.72 1.72

bur26c 0.00 0.00 0.00 1.38 chr22a 0.00 0.06 0.62 3.64

bur26d 0.00 0.00 0.00 2.57 chr22b 0.00 0.48 1.87 5.97

bur26e 0.00 0.00 0.00 1.71 chr25a 0.00 0.45 3.27 6.60

bur26f 0.00 0.00 0.00 0.39 esc32a 0.00 0.00 0.00 4.71

bur26g 0.00 0.00 0.00 0.60 esc32b 0.00 0.00 0.00 0.32

bur26h 0.00 0.00 0.00 0.54 esc32c 0.00 0.00 0.00 0.01

chrl2a 0.00 0.00 0.00 0.08 esc32d 0.00 0.00 0.00 0.06

chrl2b 0.00 0.00 0.00 0.01 esc32g 0.00 0.00 0.00 0.00

clirl2c 0.00 0.00 0.00 0.35 esc32h 0.00 0.00 0.00 0.13

chrl5a 0.00 0.00 0.00 0.53 esc64a 0.00 0.00 0.00 0.05

chrl5b 0.00 0.00 0.00 0.29 esc128 0.00 0.00 0.00 2.06

chrl5c 0.00 0.00 0.00 0.64 kra30a 0.00 0.10 1.34 4.24

chrl8a 0.00 0.00 0.00 0.97 kra30b 0.00 0.05 0.19 5.18

chrl8b 0.00 0.00 0.00 0.12 nug24 0.00 0.00 0.00 0.61

chr20a 0.00 0.85 1.82 3.77 nug25 0.00 0.00 0.00 1.45

nug30 0.00 0.03 0.07 5.73 tai20b 0.00 0.00 0.00 0.36

sko42 0.00 0.04 0.25 22.34 tai25a 0.00 0.48 1.15 3.66

sko49 0.00 0.10 0.25 41.61 tai25b 0.00 0.02 0.07 0.91

sko56 0.00 0.08 0.27 67.80 tai30a 0.40 0.68 1.03 8.83

sko64 0.00 0.08 0.28 98.09 tai30b 0.00 0.02 0.17 1.06

sko72 0.01 0.19 0.34 158.27 tai35a 0.69 1.02 1.33 15.95

sko81 0.02 0.14 0.25 232.17 tai35b 0.00 0.02 0.22 9.27

sko90 0.04 0.20 0.32 339.24 tai40a 0.70 1.16 1.50 21.13

skolOOa 0.07 0.18 0.27 456.64 tai40b 0.00 0.00 0.01 1.79

skolOOb 0.05 0.17 0.32 413.03 tai50a 0.74 1.55 1.93 33.20

skolOOc 0.03 0.15 0.24 387.71 tai50b 0.00 0.00 0.01 18.98

skolOOd 0.04 0.19 0.32 402.67 tai60a 1.30 1.64 1.81 44.44

skolOOe 0.02 0.13 0.39 584.19 tai60b 0.00 0.02 0.05 44.18

skolOOf 0.13 0.26 0.42 588.82 tai64c 0.00 0.00 0.00 0.51

ste36a 0.00 0.46 1.30 5.04 tai80a 0.78 1.22 1.55 193.07

ste36b 0.00 0.10 1.14 10.65 tai80b 0.00 0.02 0.05 243.67

ste36c 0.00 0.25 0.97 10.22 tail 00a 0.89 1.15 1.40 326.15

tailOOb 0.04 0.29 0.54 413.15 thol50 0.16 0.28 0.39 2010.56

tail 50b 0.12 0.36 0.48 2241.52 wil50 0.00 0.04 0.07 27.98

tho30 0.00 0.03 0.29 6.77 wilOO 0.06 0.11 0.16 586.43

tho40 0.00 0.10 0.40 20.41

3.2. Further analysis of the performance of the algorithm

Benchmarks	Performance indicator gap	Runtime	Benchmarks	Performance indicator gap	Runtime
bur26a	0.00	0.00	0.00	0.41	chr20b	0.00	2.89	6.01	5.22
bur26b	0.00	0.00	0.00	0.48	chr20c	0.00	0.79	4.72	1.72
bur26c	0.00	0.00	0.00	1.38	chr22a	0.00	0.06	0.62	3.64
bur26d	0.00	0.00	0.00	2.57	chr22b	0.00	0.48	1.87	5.97
bur26e	0.00	0.00	0.00	1.71	chr25a	0.00	0.45	3.27	6.60
bur26f	0.00	0.00	0.00	0.39	esc32a	0.00	0.00	0.00	4.71
bur26g	0.00	0.00	0.00	0.60	esc32b	0.00	0.00	0.00	0.32
bur26h	0.00	0.00	0.00	0.54	esc32c	0.00	0.00	0.00	0.01
chrl2a	0.00	0.00	0.00	0.08	esc32d	0.00	0.00	0.00	0.06
chrl2b	0.00	0.00	0.00	0.01	esc32g	0.00	0.00	0.00	0.00
clirl2c	0.00	0.00	0.00	0.35	esc32h	0.00	0.00	0.00	0.13
chrl5a	0.00	0.00	0.00	0.53	esc64a	0.00	0.00	0.00	0.05
chrl5b	0.00	0.00	0.00	0.29	esc128	0.00	0.00	0.00	2.06
chrl5c	0.00	0.00	0.00	0.64	kra30a	0.00	0.10	1.34	4.24
chrl8a	0.00	0.00	0.00	0.97	kra30b	0.00	0.05	0.19	5.18
chrl8b	0.00	0.00	0.00	0.12	nug24	0.00	0.00	0.00	0.61
chr20a	0.00	0.85	1.82	3.77	nug25	0.00	0.00	0.00	1.45
nug30	0.00	0.03	0.07	5.73	tai20b	0.00	0.00	0.00	0.36
sko42	0.00	0.04	0.25	22.34	tai25a	0.00	0.48	1.15	3.66
sko49	0.00	0.10	0.25	41.61	tai25b	0.00	0.02	0.07	0.91
sko56	0.00	0.08	0.27	67.80	tai30a	0.40	0.68	1.03	8.83
sko64	0.00	0.08	0.28	98.09	tai30b	0.00	0.02	0.17	1.06
sko72	0.01	0.19	0.34	158.27	tai35a	0.69	1.02	1.33	15.95
sko81	0.02	0.14	0.25	232.17	tai35b	0.00	0.02	0.22	9.27
sko90	0.04	0.20	0.32	339.24	tai40a	0.70	1.16	1.50	21.13
skolOOa	0.07	0.18	0.27	456.64	tai40b	0.00	0.00	0.01	1.79
skolOOb	0.05	0.17	0.32	413.03	tai50a	0.74	1.55	1.93	33.20
skolOOc	0.03	0.15	0.24	387.71	tai50b	0.00	0.00	0.01	18.98
skolOOd	0.04	0.19	0.32	402.67	tai60a	1.30	1.64	1.81	44.44
skolOOe	0.02	0.13	0.39	584.19	tai60b	0.00	0.02	0.05	44.18
skolOOf	0.13	0.26	0.42	588.82	tai64c	0.00	0.00	0.00	0.51
ste36a	0.00	0.46	1.30	5.04	tai80a	0.78	1.22	1.55	193.07
ste36b	0.00	0.10	1.14	10.65	tai80b	0.00	0.02	0.05	243.67
ste36c	0.00	0.25	0.97	10.22	tail 00a	0.89	1.15	1.40	326.15
tailOOb	0.04	0.29	0.54	413.15	thol50	0.16	0.28	0.39	2010.56
tail 50b	0.12	0.36	0.48	2241.52	wil50	0.00	0.04	0.07	27.98
tho30	0.00	0.03	0.29	6.77	wilOO	0.06	0.11	0.16	586.43
tho40	0.00	0.10	0.40	20.41

In order to analyze the influence of different control parameter values on the performance of DABC algorithm, 8 typical examples in QAPLIB (bur26a, chr12a, esc32h, sko64, sko100a, tai40a, tai80a, wil50) were selected for the experiment. First, $C S$ and limit are initialized to 100, and then keep limit unchanged, $C S$ takes 50,100,150 and 200, sequentially, and the above eight benchmark examples are solved respectively. Record the average gap value of 30 independent runs and plot its change curve, as shown in Fig. 5. It can be seen from the figure that the effect of different colony sizes on the performance of the algorithm is very little, that is, the DABC algorithm is insensitive to the control parameters. The influence of controls parameter limit on algorithm performance is shown in Fig. 6. It can be seen that, except for the effect of different limit values on the algorithm performance on the two benchmark instances of tai40a and tai80a, the DABC algorithm is not sensitive to parameter limit in 6 other instances. In relative terms, limit = 100 is an optimal parameter.

To analyze local search and exchange variation effect on the properties of DABC algorithm, in $C S = 100$ and limit = 100 parameter configuration, we run DABC algorithm with local search and without local search respectively. The average gap value curve in different situations is drawn, as shown in Fig. 7. From the graph, we can find that the DABC algorithm with local search can greatly improve the quality of the solution at most of the selected benchmark instances, and fully show that local search of algorithm performance have a significant impact. The effect of exchange variation operation on the performance of the algorithm is shown in Fig. 8. As you can see, the exchange mutation operation has a certain effect on the performance of the DABC algorithm, especially for the tai40a, tai80a and sko64 which are difficult to optimize. The solution of the examples is significantly improved. In general, however, the improvement of the exchange mutation operations in algorithm significantly is less remarkable than the local search.

Fig. 5.

Effect of parameter CS on the performance of the algorithm.

Fig. 6.

Effect of parameter limit on the performance of the algorithm.

Fig. 7.

The effect of local search on the performance of the algorithm.

Fig. 8.

The effect of exchange variation on the performance of the algorithm.

4. Conclusion

Based on the basic framework of artificial bee colony algorithm, used common crossover and mutation operator, combined with effective 2 – exchange local search algorithm, we proposed an effective discrete artificial bee colony algorithm of solving QAP in this paper. Simulation experiments on 75 benchmark examples in QAPLIB illustrate the effectiveness and efficiency of this algorithm. The influencing factors of the performance of the algorithm are analyzed and discussed: 1) Local search can improve the performance of the algorithm greatly; 2) The new algorithm is insensitive to the control parameters. Therefore, the algorithm proposed in this paper has certain application prospect and future research direction mainly includes: 1) The new algorithm is used to solve practical problems; 2) The algorithm is extended to deal with multi-objective optimization problems, amongst others.

Conflict of interest

None to report.

References

R.K.

Ahuja,

J.B.

Orlin and

Tiwari, A greedy genetic algorithm for the quadratic assignment problemComputers & Operations Research27(10) (2000), 917–934. doi:10.1016/S0305-0548(99)00067-2.

R.E.

Burkard, Quadratic Assignment Problems, Springer, New York, 2013.

R.E.

Burkard,

S.E.

Karisch and

Rendl, QAPLIB-a quadratic assignment problem libraryJournal of Global optimization10(4) (1997), 391–403. doi:10.1023/A:1008293323270.

Duan and

Xiang, A comparative study of different genetic operator combinations to solve TSP problemsReport of Science and Technology23(5) (2012), 27–31.

Hu,

Zhao and

Pengfei, Simulation and research of JSP based on artificial swarm algorithm, Mechanical Science and Technology7 (2009), 851–856.

Karaboga and

Basturk, A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm, Journal of Global Optimization39(3) (2007), 459–471. doi:10.1007/s10898-007-9149-x.

Karaboga and

Gorkemli, A combinatorial artificial bee colony algorithm for traveling salesman problem, in: 2011 International Symposium on Innovations in Intelligent Systems and Applications (INISTA), IEEE, 2011, pp. 50–53.

Ling, Intelligent Optimization Algorithm and Its Application, Tsinghua University Press, Beijing, 2001.

Y.F.

Liu and

S.Y.

Liu, A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problemApplied Soft Computing13(3) (2013), 1459–1463. doi:10.1016/j.asoc.2011.10.024.

10.

Misevicius, A modified simulated annealing algorithm for the quadratic assignment problemInformatica14(4) (2003), 497–514. doi:10.15388/Informatica.2003.037.

11.

Misevicius, A tabu search algorithm for the quadratic assignment problem., Comp. Opt. and Appl.30(1) (2005), 95–111. doi:10.1007/s10589-005-4562-x.

12.

Misevicius and

Verene, A hybrid genetic-hierarchical algorithm for the quadratic assignment problem, Entropy23(1) (2021), 108–108. doi:10.3390/e23010108.

13.

Pandiri and

Singh, A swarm intelligence approach for the colored traveling salesman problem, Applied Intelligence48(11) (2018), 4412–4428. doi:10.1007/s10489-018-1216-0.

14.

L.Y.

Pardalos and

M.G.C.

Resende, A greedy randomized adaptive search procedure for the quadratic assignment problemDiscrete Mathematics and Theoretical Computer Science16 (1994), 237–261.

15.

Parvandeh

et al., A modified single and multi-objective bacteria foraging optimisation for the solution of quadratic assignment problem, International Journal of Bio-Inspired Computation17(1) (2021). doi:10.1504/IJBIC.2021.113354.

16.

Shakir Hameed

et al., Improved Discrete Differential Evolution Algorithm in Solving Quadratic Assignment Problem for best Solutions, International Journal of Advanced Computer Science and Applications (IJACSA) (2018), 9.

17.

Tosun, Using artificial bee colony algorithm for permutation flow shop scheduling problem under makespan criterion, Int. J. of Mathematical Modelling and Numerical Optimisation5(3) (2014), 191–209. doi:10.1504/IJMMNO.2014.063267.

18.

Wei,

Ma and

Zhong, The large flood algorithm of secondary distribution problem is solvedLogistics and Management1 (2011), 12–15.

19.

Xia and

Yuren, Performance analysis of ACO on the quadratic assignment problem, Chinese Journal of Electronics27(1) (2018), 26–34. doi:10.1049/cje.2017.06.004.

20.

Xiang,

Chen,

Peng,

Lu,

Gao and

Zhong, The cluster algorithm optimizes the support vector machine and its application in the automatic classification of music, The Practice and Understanding of Mathematics43(23) (2013), 44–49.

21.

Xiang,

Peng,

Zhong,

Chen,

Lu and

Zhong, A particle swarm inspired multi-elitist artificial bee colony algorithm for real-parameter optimization, Computational Optimization and Applications57(2) (2014), 493–516. doi:10.1007/s10589-013-9591-2.

22.

Zhongand

Cai, A discrete particle swarm optimization algorithm for solving quadratic distribution problems is proposed, Automated Journal33(8) (2007), 871–874.