果蝇算法求解多维背包问题

A novel binary fruit flyoptimization algorithm for solving the multidimensional knapsack

problem

Ling Wang ⇑, Xiao-long Zheng, Sheng-yao Wang

Tsinghua National Laboratory for Information Science and Technology (TNList),Department of Automation, Tsinghua University, Beijing 100084, China

a r t i c l e i n f o a b s t r a c t

In this paper, a novel binary fruit flyoptimization algorithm (bFOA)is proposed to solve the multidimen-sional knapsack problem (MKP).In the bFOA, binary string is used to represent the solution of the MKP, and three main search processes are designed to perform evolutionary search, including smell-based search process, local vision-based search process and global vision-based search process. In particular, a group generating probability vector is designed for producing new solutions. To enhance the explora-tion ability, a global vision mechanism based on differential information among fruit fliesis proposed to update the probability vector. Meanwhile, two repair operators are employed to guarantee the feasibility of solutions. The influenceof the parameter setting is investigated based on the Taguchi method of design of experiment. Extensive numerical testing results based on benchmark instances are provided. And the comparisons to the existing algorithms demonstrate the effectiveness of the proposed bFOA in solving the MKP, especially for the large-scale problems.

Ó2013Elsevier B.V. All rights reserved.

Article history:

Received 7December 2012

Received in revised form 7April 2013Accepted 7April 2013

Available online 16April 2013Keywords:

Multidimensional knapsack problem Fruit flyoptimization algorithm Binary algorithm Smell-based search Vision-based search

1. Introduction

The multidimensional knapsack problem (MKP)is a generaliza-tion of the standard 0–1knapsack problem. The goal of the prob-lem is to finda subset of all items that yields maximum profitwithout exceeding the multidimensional resource capacities. The MKP is a typical discrete optimization problem with wide applica-tions. Many real problems can be formulated as the MKP, such as capital budgeting [1], resource allocating [2], cargo loading [3], cut-ting stock [4], knowledge and economics engineering [5], and pol-lution prevention and control [6]. The MKP has been shown to be strongly NP-hard [1].

In view of the pervasive nature of the MKP in knowledge-based system, there is abundant literature on the topic. Early solution algorithms are mainly exact methods, such as branch and bound algorithm (B&B)[3], dynamic programming (DP)[7], and the B&Band DP based hybridization method [8]. A recent breakthrough in developing effective methods for the MKP is the concept of core as described by Puchinger et al. [9]. Using the concept of core [10]can help to reduce the problem size significantly,which is use-ful in developing both the exact and approximate algorithms. Based on the concept of core, some effective algorithms have been developed for the knapsack problem (KP)[11,12], the MKP [9], the multiple-choice MKP [13], and the bi-objective MKP [14]. Besides, some heuristics have also been presented for the MKP [15–18]. Corresponding author. Tel.:+[1**********]5; fax:+[1**********]1.

E-mail address:[email protected](L.Wang).

0950-7051/$-see front matter Ó2013Elsevier B.V. All rights reserved. http://dx.doi.org/10.1016/j.knosys.2013.04.003

With the development of computational intelligence, some meta-heuristic methods have been proposed to solve the MKP. Relevant algorithms include simulated annealing [19], genetic algorithm [1], tabu search (TS)[20], linear programming with TS [21], ant colony optimization [22], max–minant system [23], and particle swarm optimization [6]. However, most of the above methods cannot solve large-scale problems effectively and efficiently.Very re-cently, Wang et al. [24]proposed a hybrid algorithm based on esti-mation of distribution algorithm (HEDA)and designed a new repair operator particularly for large-scale problems. Due to the significanceof the MKP in academic research and real applications, it is important to develop novel algorithms with satisfactory performances.

As a novel evolutionary optimization approach, fruit flyoptimi-zation algorithm (FOA)[25]is inspired by the knowledge from the foraging behavior of fruit flies.The FOA is easy to understand and implement. Some recent applications of the FOA can be found in literature, including financialdistress [25], power load forecasting [26], web auction logistics service [27]and PID controller tuning [28,29]. As the traditional FOA was proposed to solve the continu-ous optimization problem, it operates on the continuous variables. For the discrete optimization problems, such as the MKP, the FOA should be specially designed to operate on the discrete variables, such as encoding scheme and search operators. To the best of our knowledge, there is no research work about the FOA for solving discrete optimization problems. To solve the MKP effectively, we shall propose a binary fruit flyoptimization algorithm (bFOA)by considering the specificknowledge of the MKP, especially aiming

18L. at solving the large-scale problems. To be

represented as binary strings. The and the local vision-based search process of are also used in the bFOA to perform exploitation ferent from the traditional FOA, a global cess is designed for the bFOA to enhance the search. Meanwhile, in the global vision-based population is generated according to a group ity vector, which is updated based on the among fruit flies.In addition, two repair to guarantee the feasibility of solutions. The setting is investigated based on the Taguchi experiment, and suitable values are sive numerical testing results and comparisons demonstrate the effectiveness of the proposed The remainder of the paper is organized as the mathematical formulation of the MKP is the basic FOA is introduced. Then, the bFOA for sented in details in Section 4. In Section 5, the eter setting is investigated, and numerical testing results and comparisons are given. Finally, we end the paper with some con-clusions and future work in Section 6. 2. Multidimensional knapsack problem

Generally, the multidimensional knapsack problem can be for-mulated as follows [1]:

X n Maximize

c j d j

ð1Þj ¼1

subject to

X

n r i ; j d j 6s i ; i ¼1; 2; ... ; m ð2Þj ¼1

d j 2f 0; 1g ;

j ¼1; 2; ... ; n

ð3Þ

where n is the number of items, m is the number of knapsack con-straints with capacity s i (i =1, 2, ... , m ) at the i th dimension, c j de-notes the profitof item j , r i , j is the volume of item j at the i th

dimension, and d j is a binary decision variable. If item j is selected into the knapsack, then d j =1; otherwise, d j =0. Without loss of gen-erality, it is assumed that c j , r i , j and s i are non-negative integers with

r i , j 6s i and P

n j ¼1r i ; j >s i ; i ¼1; 2; ... ; m ; j ¼1; 2; ... ; n .

The objective of the MKP is to finda subset of all the items to be selected in the knapsack with a maximum profitwhile not exceed-ing the capacity of each dimension. 3. Fruit flyoptimization algorithm

Fruit flyoptimization algorithm (FOA)[25]is a new interactive evolutionary method inspired by the knowledge from foraging behavior of fruit flies.There are two main foraging processes:smell the food source by osphresis organ and flytowards the correspond-ing location; and use the sensitive vision to findfood and flyto-wards a better direction. The foraging process of a fruit flygroup can be illustrated in Fig. 1[26], and the procedure of the FOA is summarized as follows [26].

Step 1. Initialize parameters, including maximum number of gen-erations and population size.

Step 2. Initialize the fruit flygroup.

Step 3. Use osphresis for foraging:generate several fruit fliesran-domly around the fruit flygroup to construct a population:

Step 4. Evaluate the population to obtain the smell concentration

values (fitnessvalue) of each fruit fly.

Step 5. Use vision for the foraging:findthe best fruit flywith the

maximum smell concentration value, and then let the fruit flygroup flytowards the best one.

Step 6. End the algorithm if the maximum number of generations

is reached; otherwise, go back to Step 3. 4. bFOA for MKP

In this section, we present the design of the bFOA for the MKP. Different from the traditional FOA, firstwe adopt a discrete binary string in the bFOA to represent a solution; second we use a group generating probability vector to generate population; third we adopt 0–1flipoperation to exploit the neighborhood in the smell-based search process; fourth we design a global vision-based search mechanism to enhance the exploration ability. Besides, two repair operations are adopted in the bFOA to guarantee the feasi-bility of solutions for further improving the performances of the bFOA.

4.1. Encoding scheme and population generating with probability vector

In the bFOA, each individual is a solution of the MKP, which is represented by an n -bit binary string. That is, for an individual x j its i th bit x i , j (i =1, 2, ... , n ) is a binary decision variable, 0or 1. Meanwhile, we used an n -dimensional vector P (g)=[p 1(g),p 2(g),... , p n (g)],called group generating probability vector, to generate the fruit flypopulation. For an individual x j , p i (g ) indicates the probability of x i , j =1at the g th generation. To uniformly sample the search space, the probability vector is initialized as P (0)=[0.5,0.5, ... , 0.5].

In each generation, a new population with N individuals is gen-erated according to the probability vector. The procedure is shown in Fig. 2.

4.2. Smell-based search and local vision-based search

In the bFOA, S neighbors are randomly generated around each fruit flyx j (j =1, 2, ... , N ) using the following smell-based search process.

Step 1. Randomly select L bits from x j .

Step 2. Mutate the selected bits by replacing 0with 1or 1with 0.

L. Wang et al. /Knowledge-Based Systems 48(2013)17–2319

Considering a problem with 10items, an example is illustrated

in Fig. 3for the above process, where L =3, and the bold bits denote the selected ones.

Similar to the traditional FOA, each fruit flyin the bFOA also findsits best local neighbor using its sensitive vision. If the best neighbor is better, then it fliestowards that neighbor. That is, the individual will be replaced with the best neighbor. Otherwise, it re-mains unchanged.

4.3. Global vision-based search

The traditional FOA focuses much on the exploitation ability. To enhance the exploration ability, we introduce a global vision-based mechanism in the bFOA to update the group generating probability vector. To be specific,inspired by the mechanism of differential evolution algorithm [30], the differential information among the best individual Fg and two randomly selected individuals F 1, F 2are used to update p i (g ).

D i ¼x i ; Fg þ0:5Âðx i ; F 1Àx i ; F 2Þ

ð4Þp i ðg Þ¼1=½1þe Àb ÂðD i À0:5Þ

ð5Þ

where D i denotes the differential information, and b is a coefficient

indicating the vision sensitivity.

After the group generating probability vector is updated, a new population is produced accordingly. 4.4. Repair operator

Usually, the newly generated individuals may not satisfy the capacity constraints. To guarantee the feasibility of the individuals, a repair procedure is often needed. In this paper, the following two repair operators are employed.

n Maximize X

c j d j

ð6Þ

j ¼1

X n (

X

m )

subject to

x i r i ; j d j 6

X m x i s i

ð7Þj ¼1

i ¼1

i ¼1

d j 2f 0; 1g ;

j ¼1; 2; ... ; n

ð8Þ

20L. Wang et al. /Knowledge-Based Systems 48(2013)17–23

where x i is a positive real number as the surrogate multiplier (orweight).

When solving the LP relaxation of the original MKP, the values of the dual variables are the weights. That is, x i can be viewed as the shadow price of the i th constraint in the LP relaxation of the ori-ginal MKP. Thus, the pseudo-utility ratio of each variable can be cal-culated as follows:

,

u j ¼c j

m X i ¼1

x i r i ; j ; j ¼1; 2; ... ; n

ð9Þ

The core idea of this repair operator is to include or exclude each

variable based on u j . Before repairing, all the variables are sorted in a descent order according to the pseudo-utility ratios. Then, it performs repairing with two phases. The firstphase (denotedDROP) is used to guarantee the feasibility of the solution. To be specific,it examines each bit of the encoded string in an ascent order of u j and then changes the bit from 1to 0until the solution is feasible. The second phase (denotedADD) is to improve the performance of the solution. To be specific,it changes the bit from 0to 1in a descent order of u j as long as all the constraints are not violated. The pseu-do-code of RO1is illustrated in Fig. 4.

Repair operator 2(RO2).When using RO1, it needs to solve the LP relaxation problem. Since it is difficultto solve the LP prob-lem with large-scale, RO1can be applied to small or medium-scale instances. Recently, Wang et al. [24]proposed a new

repair operator considering the specificknowledge of the MKP for solving the large-scale MKP. With this repair operator, it is not necessary to solve the LP relaxation problem in advance. This operator is described as follows.

First, it obtains a matrix Q =(q i , j =c j /r i , j ) m Ân , where q i , j is the value of a unit volume (calledvalue ratio) of the j th item in the i th constraint. Then, it uses an assistant matrix F to store the sorting rank of the item in a descent order of value ratio in all constraints. That is, f i , j represents the rank of the j th item in the i th constraint. Finally, we can design the corresponding DROP and ADD phases. In DROP phase, every constraint is checked by examining each bit and changing it from 1to 0in an ascending order of q i , j until the solution is feasible. In ADD phase, constraints are checked in an ascent order of the surplus capacity, and then it examines each bit and changes it from 0to 1in a descent order of q i , j as long as the constraint is not vio-lated. The pseudo-code of this operator is illustrated in Fig. 5. 4.5. Procedure of bFOA

With the above specificdesign, the flowchartof the bFOA is illustrated in Fig. 6. It can be seen that the procedure consists of three main processes in addition to the initialization process. In smell-based search process, local neighbors are exploited. In local vision-based search process, the fruit fliesare replaced by their best neighbors. In global vision-based search process,

differential

L. Wang et al. /Knowledge-Based Systems 48(2013)17–23

Table 1

Combinations of parameter values. Parameters

Factor level 1

N S L b

201120

2303330

3405540

45010750

21

Table 2

Orthogonal array and ARV value. Experiment number

Factors N

[***********]41516

[**************]4

S [**************]4

L [**************]1

b [**************]3

7637.187655.387651.407644.907654.607641.547648.767652.247652.087651.387643.247655.227649.847653.347655.507642.76ARV

information among the population is used to update the group generating probability vector for further generating new popula-tion to enhance exploration. Since exploitation and exploration are both considered in the algorithm, it expects to yield solutions with satisfactory quality.

In addition, we denote the algorithm as bFOA1when RO1is em-ployed and as bFOA2when RO2is employed. Although we employ the repair operators from [24], we apply a totally different algo-rithm (bFOA)to solve the MKP. And this is the firstwork about the FOA to solve the MKP. In addition, the numerical results in the next section will show that our bFOA is better than the algo-rithm in [24], especially for solving the large-scale problems.

5. Numerical testing results and comparisons

To test the performance of the bFOA, two sets of well-known benchmark instances are used. Test set 1consists of eight small-scale problems (availableform ORLIB) with m =2–30and n =15–105. Test set 2consists of 11medium-scale and large-scale problems (availablefrom http://hces.bus.olemiss.edu/tools.html) with m =15–100and n =100–2500.We code the algorithm in C++and run it on a PC of Intel ÒCore2(TM)Q9550, 2.83GHz.

5.1. Parameter setting

The proposed bFOA contains four key parameters:population size (N ), the number of generated neighbors (S ) and the number of the bits selected to flip(L ) in the smell-based search process, and the global vision sensitivity (b ). To investigate the influenceof these parameters on the bFOA1, we apply the Taguchi method of design of experiment (DOE)[32]with instance Mk_gk06(m =50and n =200). Different combinations of the values are listed in Table 1.

With each combination of values, the bFOA1is run 50times independently (setthe maximum evaluation times as 100,000). The average response variable (ARV)value is the average of total profitobtained by the bFOA1. Considering four factor levels for each parameter, we list the orthogonal array L 16(44) and the ob-tained ARV values in Table 2. Using the statistical analysis tool Minitab, we can analyze the significancerank of each parameter

Table 3

Response value. Level 1234Delta Rank

N 7647.217649.287650.487650.363.272

S 7648.427650.417649.727648.781.993

L 7641.187655.187652.277648.7214.001

b 7648.637650.187650.037648.501.674

22L. Wang et al. /Knowledge-Based Systems 48(2013)17–23

and obtain the trend of each factor level, as shown in Table 3and Fig. 7, respectively.

From Table 3and Fig. 7, it can be seen that L is the most signif-icant parameter. A small value of L is helpful for local exploitation. But a too small value may be helpless for repair process. As for N , with a fixedtotal evaluation times, a small size may lead to poor exploration so as to cause premature convergence, while a large size implies a small number of evolution generations which may cause insufficientsearch. As for S and b , it can be seen from Fig. 7that they have little influenceon the algorithm, where med-ium values are preferable.

According to the DOE test based investigation, the suitable val-ues of these parameters are set as N =40, S =3, L =3and b =30, which will be used for the following testing. 5.2. Comparison of bFOA1with HEDA1

Very recently, an algorithm named HEDA was proposed in [24]with better performances than other existing approaches. There-fore, we compare the bFOA1with the HEDA1(HEDAwith RO1).

Same as [24], we set the maximum number of evaluations as 100,000and run the algorithm 20times independently.

The comparative results with eight small-scale instances of test set 1are listed in Table 4, where the column SR denotes the success ratio of hitting the best known value and AVG denotes the average value of the 20runs. The comparative results with eight medium-scale instances of test set 2are listed in Table 5, where Min.Dev and Ave.Dev represent the minimum and average percentage devi-ations from the best-known values, respectively, and Var. Dev de-notes the variance of the deviation.

For the small-scale instances, it can be seen from Table 4that both the bFOA1and the HEDA1can optimally solve the instances consistently. For the medium-scale instances, it can be seen from Table 5that the bFOA1is superior to the HEDA1in terms of Min.D-ev, Ave.Dev and Var.Dev. It implies that the bFOA1is able to obtain better solutions than the HEDA1in a more consistent way. 5.3. Comparison of bFOA2with HEDA2

In [24], RO2was incorporated in the HEDA as the HEDA2for solving the large-scale instances. Similarly, we incorporate RO2in the bFOA as the bFOA2. Then, we compare the bFOA2with the HEDA2using all the instances of test set 2. The comparative results are listed in Table 6.

From Table 6, it is clear that the bFOA2dominates the HEDA2for all the instances. So, our bFOA2is more powerful than the HEDA2to solve the MKP, including the large-scale instance with 2500items.

In addition, comparing the results of the bFOA1in Table 5with those of the bFOA2in Table 6, it can be seen that RO1is superior to RO2for the algorithm to obtain better solutions. But, RO1is diffi-cult to be applied for the large-scale problems. Thus, the bFOA1is recommended for the small and medium-scale problems, while the bFOA2is recommended for the large-scale problems.

Table 4

Comparisons of bFOA1with HEDA1on small scale MKP. Problem

n Âm

Best known

bFOA1AVG

Sent01Sent02Weing7Weing8Knap15Knap20Knap39Knap28

60Â3060Â30105Â2105Â215Â1020Â1039Â528Â10

77728722

1,095,445624,[1**********]10,61812,400

77728722

1,095,445624,[1**********]10,61812,400

SR [***********]100100

HEDA1AVG 77728722

1,095,445624,[1**********]10,61812,400

SR [***********]100100

Table 5

Comparisons of bFOA1with HEDA1on medium scale MKP. Problem

n Âm

Best known

bFOA1Min.Dev

Mk_gk01Mk_gk02Mk_gk03Mk_gk04Mk_gk05Mk_gk06Mk_gk07Mk_gk08

100Â25100Â50150Â25150Â50200Â25200Â50500Â25500Â50

[***********]57767219,21518,801

0.23900

0.07080.05200.05290.11730.05200.0851

Ave.Dev 0.30530.19830.15840.19430.11980.20460.08220.1402

Var.Dev 0.03320.23060.09460.35670.07870.12140.04720.1267

HEDA1Min.Dev 0.26550.07580.12390.08670.13230.29980.52040.6117

Ave.Dev 0.31730.19830.20180.33480.27720.44380.72030.7680

Var.Dev 0.07830.11940.09980.29160.21500.23390.82401.1028

Note:The bold values denote better results.

Table 6

Comparisons of bFOA2with HEDA2. Problem

n Âm

Best known

bFOA2Min.Dev

Mk_gk01Mk_gk02Mk_gk03Mk_gk04Mk_gk05Mk_gk06Mk_gk07Mk_gk08Mk_gk09Mk_gk10Mk_gk11

100Â25100Â50150Â25150Â50200Â25200Â50500Â25500Â501500Â251500Â502500Â100

[***********]57767219,21518,80158,08557,29295,231

0.55760.65690.79650.86751.00570.84721.43121.28722.17441.74371.5037

Ave.Dev 0.75540.85180.91501.02791.19300.98021.51941.36592.28161.79051.5738

Var.Dev 0.33050.33170.41260.48040.59050.42440.57840.35510.92670.41480.5780

HEDA2Min.Dev 0.61070.75800.93811.09301.24391.12101.70181.65952.45852.01771.7043

Ave.Dev 0.93600.97901.15311.26731.49601.44361.84601.72602.54612.11701.7348

Var.Dev 0.65550.40390.78280.70690.74831.15730.98730.28800.68130.78070.2184

Note:The bold values denote better results.

L. Wang et al. /Knowledge-Based Systems 48(2013)17–2323

6. Conclusions

This was the firstreported work of using fruit flyoptimization to solve the multidimensional knapsack problem. We designed a binary fruit flyoptimization algorithm with three main search pro-cesses, including the smell-based search, local vision-based search and global vision-based search. In particular, a group generating probability vector was designed to generate population and a mechanism for the global vision-based search was provided to up-date the probability vector for well exploration. Besides, two repair operators were employed to guarantee the feasibility of solutions. The influenceof parameter setting was investigated and suitable values were suggested. Numerical testing results and comparisons demonstrated the effectiveness of the proposed bFOA. To further improve the performance of the bFOA for solving the MKP, it is worthy of applying the concept of core in designing the algorithm. Besides, our future work includes the design of the FOA-based ap-proaches for solving other combinatorial optimization problems like shop scheduling, and it is also important to study the FOA for solving the multi-objective optimization problems. Acknowledgments

The authors thank the Editor-in-Chief Prof. Hamido Fujita and the anonymous reviewers for their constructive comments to im-prove the paper. This research is partially supported by the Na-tional Key Basic Research and Development Program of China (No.2013CB329503), the National Science Foundation of China (No.61174189), and the National Science and Technology Major Project of China (No.2011ZX02504-008). References

[1]P.C. Chu, J.E. Beasley, A genetic algorithm for the multidimensional knapsack

problem, Journal of Heuristics 4(1998)63–86.

[2]B. Gavish, H. Pirkul, Allocation of databases and processors in a distributed

computing system, Management of Distributed Data Processing (1982)215–231.

[3]W. Shih, A branch and bound method for the multi-constraint zero–one

knapsack problem, Journal of the Operational Research Society 30(1979)369–378.

[4]P.C. Gilmore, R.E. Gomory, The theory and computation of knapsack functions,

Operations Research 14(1966)1045–1075.

[5]S. Martello, P. Toth, Knapsack Problems:Algorithms and Computer

Implementations, Wiley, New York, 1990.

[6]J.C. Bansal, K. Deep, A modifiedbinary particle swarm optimization for

knapsack problems, Applied Mathematics and Computation 218(2012)11042–11061.

[7]P. Toth, Dynamic programing algorithms for the zero–oneknapsack problem,

Computing 25(1980)29–45.

[8]G. Plateau, M. Elkihel, A hybrid method for the 0–1knapsack problem,

Methods of Operations Research 49(1985)277–293.

[9]J. Puchinger, G.R. Raidl, U. Pferschy, The core concept for the multidimensional

knapsack problem, Lecture Notes on Computer Science 3906(2006)195–208. [10]E. Balas, E. Zemel, An algorithm for large zero–oneknapsack problems,

Operations Research 28(1980)1130–1154.

[11]S. Martello, P. Toth, A new algorithm for the 0–1knapsack problem,

Management Science 34(1988)633–644.

[12]D. Pisinger, An expanding-core algorithm for the exact 0–1knapsack problem,

European Journal of Operational Research 87(1995)175–187.

[13]M.R. Razzazi, T. Ghasemi, An exact algorithm for the multiple-choice

multidimensional knapsack based on the core, Communications in Computer and Information Science 6(2009)275–282.

[14]G. Mavrotas, J.R. Figueira, A. Antoniadis, Using the idea of expanded core for

the exact solution of bi-objective multi-dimensional knapsack problems, Journal of Global Optimization 49(2011)589–606.

[15]R. Loulou, E. Michaelides, New greedy-like heuristics for the multidimensional

0–1knapsack problem, Operational Research 27(1979)1101–1114.

[16]Y. Toyoda, A simplifiedalgorithm for obtaining approximate solutions to zero–

one programming problems, Management Science 21(1975)1417–1427. [17]J.E. Beasley, Multidimensional knapsack problems, in:C.A. Floudas, P.M.

Pardalos (Eds.),Encyclopedia of Optimization, 2nd ed., Springer-Verlag, US, 2009, pp. 2402–2406.

[18]F.D. Croce, A. Grosso, Improved core problem based heuristics for the 0/1

multi-dimensional knapsack problem, Computers &Operations Research 39(2012)27–31.

[19]A. Drexl, A simulated annealing approach to the multi-constraint zero–one

knapsack problem, Computing 40(1988)1–8.

[20]F. Dammeyer, S. Voss, Application of tabu search strategies for solving multi-constraint zero–oneknapsack problems, Working paper, 1991.

[21]M. Vasquez, Y. Vimont, Improved results on the 0–1multidimensional

knapsack problem, European Journal of Operational Research 165(2005)70–81.

[22]M. Kong, P. Tian, Y.C. Kao, A new ant colony optimization algorithm for the

multidimensional knapsack problem, Computers &Operations Research 35(2008)2672–2683.

[23]L. Ke, Z. Feng, Z. Ren, X. Wei, An ant colony optimization approach for the

multidimensional knapsack problem, Journal of Heuristics 16(2010)65–83. [24]L. Wang, S. Wang, Y. Xu, An effective hybrid EDA-based algorithm for solving

multidimensional knapsack problem, Expert Systems with Applications 39(2012)5593–5599.

[25]W.T. Pan, A new fruit flyoptimization algorithm:taking the financialdistress

model as an example, Knowledge-Based Systems 26(2012)69–74.

[26]H. Li, S. Guo, C. Li, J. Sun, A hybrid annual power load forecasting model based

on generalized regression neural network with fruit flyoptimization algorithm, Knowledge-Based Systems 37(2013)378–387.

[27]S.M. Lin, Analysis of service satisfaction in web auction logistics service using a

combination of fruit flyoptimization algorithm and general regression neural network, Neural Computing &Applications (2011),http://dx.doi.org/10.1007/s00521-011-0769-1.

[28]J. Han, P. Wang, X. Yang, Tuning of PID controller based on fruit fly

optimization algorithm, International Conference on Mechatronics and Automation (ICMA)(2012)409–413.

[29]C. Li, S. Xu, W. Li, L. Hu, A novel modifiedflyoptimization algorithm for

designing the self-tuning proportional integral derivative controller, Journal of Convergence Information Technology 7(2012)69–77.

[30]R. Storn, K. Price, Differential evolution-a simple and efficientheuristic for

global optimization over continuous spaces, Journal of Global Optimization 11(1997)341–359.

[31]H. Pirkul, A heuristic solution procedure for the multiconstraint zero–one

knapsack problem, Naval Research Logistics 34(1987)161–172.

[32]D.C. Montgomery, Design and Analysis of Experiments, John Wiley &Sons,

Arizona, 2005.