# A New Moth-Flame Optimization Algorithm for Discounted {0-1} Knapsack Problem

Authors: Tung Khac Truong
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

The discounted {0–1} knapsack problem may be a kind of backpack issue with gathering structure and rebate connections among things. A moth-flame optimization algorithm has shown good searchability combined with an effective solution presentation designed for the discounted {0-1} knapsack problem. A new encoding scheme used a shorter length binary vector to help reduce the search domain and speed up the computing time. A greedy repair procedure is used to help the algorithm have fast convergence and reduce the gap between the best-found solution and the optimal solution. The experience results of 30 discounted {0-1} knapsack problem instances are used to evaluate the proposed algorithm. The results demonstrate that the proposed algorithm outperforms the two binary PSO algorithms and the genetic algorithm in solving 30 DKP01 instances. The Wilcoxon rank-sum test is used to support the proposed declarations.


---

## Body

## 1. Introduction

The knapsack problem is a well-known problem in combinatorial optimization. There are many variants of knapsack problems such as 0-1 knapsack problem, multidimensional knapsack problem, change-making problem, generalized assignment problem, bin-packing problem, and discounted {0-1} knapsack problem (DKP01). Among the knapsack variants, the discounted {0-1} knapsack problem is new. The DKP01 is first introduced by Guldan in [1]. This problem has an important role within the modern commerce real world. It could be a portion of numerous key issues such as venture decision-making, mission determination, and budget control. A correct calculation based on energetic programming for the DKP01 is, to begin with, proposed in [1]. An approach that combined dynamic programming with the center of the DKP01 to unravel it is considered in [2]. Two calculations based on approximate methods for DKP01 are named FirEGA and SecEGA in [3].DKP01 can be presented as follows:(1)maximizefX=∑i=0n−1x3ip3i+x3i+1p3i+1+x3i+2p3i+2,(2)subject tox3i+x3i+1+x3i+2≤1,i∈0,…,n−1,(3)x3iw3i+x3i+1w3i+1+x3i+2w3i+2≤C,(4)x3i,x3i+1,x3i+2∈0,1,∀i∈1,2,…,n−1,where x3i, x3i+1, and x3i+2 represent whether the items 3i,3i+1, and 3i+2 are put into the a knapsack; xj=0 indicates the item jj=0,1,…,3n−1 is not in knapsack, while xj=1 indicates the item j is in the knapsack. It is worth noting that a binary vector X=x0,x1,…,x3n−1∈0,13n is a potential solution of DKP01. Only if X meets both (2) and (3), it is a feasible solution of DKP01. n is the number of groups, each group has three items, and each item has its profit and weight. The item is collected for knapsack aims to maximized profit while the weight capacity does not excess C. Each group does not contain more than one item.Lately, they moreover had a point-by-point consideration of the calculations of the DKP01 and proposed greenhorn deterministic calculation and estimation calculations. A modern correct calculation and two guess calculations with an eager repair administrator were proposed to illuminate DKP01 [4]. A calculation based on PSO is named GBPSO utilizing discrete molecule swarm optimization [5]. An evolution algorithm combines with ring theory to solve DKP01 [6], binary moth search algorithm [7], and a teaching-learning-based optimization algorithm [8].Moth-flame optimization is first proposed in [9] and it is successfully used to solve many optimization problems such as a quantum-behaved simulated annealing algorithm-based moth-flame optimization method [10], an efficient task scheduling approach using moth-flame optimization algorithm for cyber-physical system applications in fog computing [11], a hybrid Harris hawks-moth-flame optimization algorithm including fractional-order chaos maps and evolutionary population dynamics [12], a differential moth-flame optimization algorithm for mobile sink trajectory [13], LVCI approach for optimal allocation of distributed generations and capacitor banks in distribution grids based on moth-flame optimization algorithm [14], real challenging constrained engineering optimization problems [15], parameters extraction of the three diode models for the multicrystalline solar cell [16], Alzheimer’s disease diagnosis [17], profit maximization with integration of wind farm [18], and MFO with rolling mechanism to forecast the electricity consumption of inner Mongolia [19].This research proposed a new moth-flame optimization (MFO) and a new encoding scheme for DKP01. A successful 0-1 vector with 2∗dimensional length is utilized for a solution combined with MFO. This advantageous solution present is first used by Truong [20]. The experience results on 30 discounted {0-1} knapsack problem (DKP01) instances are used to evaluate the proposed algorithm. The results demonstrate that the proposed algorithm outperforms the two binary PSO algorithms and genetic algorithm in solving 30 DKP01 instances:(i)
Moth-flame optimization algorithm has shown good searchability combined with an effective solution presentation designed to the discounted {0-1} knapsack problem.(ii)
A new encoding scheme used a shorter length binary vector to help reduce the search domain and speed up the computing time.(iii)
A greedy repair procedure is used to help the algorithm have fast convergence and reduce the gap between the best-found solution and the optimal solution.The rest of this paper is organized in the following order: Section2 presents related works. Section 3 proposes moth-flame optimization algorithm for DKP01. The simulated results of the proposed algorithms are presented in Section 4. We conclude this paper and suggest potential future work in Section 5.


## 2. Related Works

### 2.1. Particle Swarm Optimization

The PSO conducts its search utilizing a swarm of particles; a swarm of particles is arbitrarily made initially [21, 22]. The standard atom swarm optimizer keeps up a swarm of atoms that talk to the potential courses of action for the issue at hand. Suppose that the look space is D-dimensional and the position of ith particle of the swarm can be portrayed utilizing a D-dimensional vector, xi = xi1,…,xid,…,xiD. The velocity of the particle xi is described by a D-dimensional vector vi = vi1,…,vid,…,viD. The last best position of ith particle is named pi = pi1,…,pid,…,piD. In substance, the heading of each atom is updated concurring to its claim flying encounter as well as to that of the finest atom inside the swarm. The basic PSO calculation can be portrayed as(5)vi,dk+1=w⋅vi,dk+c1⋅r1k⋅pi,dk−xi,dk+c2⋅r2k⋅pg,dk−xi,dk,xi,dk+1=xi,dk+vi,dk+1,where vi,dk is dth dimension velocity of particle i in cycle k; xi,dk is the dth dimension position of particle i in cycle k; pi,dk is the dth dimension position of personal best (pbest) of particle i in cycle k; pg,dk is the dth dimension position of global best particle (gbest) in cycle k; w is the inertia weight; c1 is the cognitive weight and c2 is a social weight; and r1 and r2 are two random values uniformly distributed in the range of [0, 1] [23].


### 2.2. Moth-Flame Optimization Algorithm

Mirjalili [9] proposed MFO in 2015 as a nature-inspired optimization algorithm that simulates the actions of individuals in a swarm of moths (search agents) that have unique night navigation methods. In the MFO algorithm, the candidate solutions are assumed to be search agents. In order to model how individuals move in a spiral, the m-by-d matrix namely M is used, where m stands for the number of search agents and d for the number of dimensions. It is assumed that, for each entity, there is an array for storing the value of the objective function as an m-by-one matrix, namely, OM.The flame, which is defined in an m-by-d matrix calledF, is also an important part of this algorithm. It is assumed that there is a way to store F’s fitness value as OF in an array. When using the MFO algorithm, F can be thought of as M’s best location in the search space. To mathematically model this action, each search agent’s location is modified as follows:(6)Mi=SMi,Fj,where Mi is the ith search agent and Fj is the jth best position found so far, and S indicates the logarithmic spiral function which is updated as follows:(7)SMi,Fj=Diecrcos2πr+Fj,where r is a random number in [−1, 1], c is a constant that defines the shape of the logarithmic spiral, and Di factor is the distance of the ith search agent for the jth flame, which is calculated as follows:(8)Di=Fj−Mi.M is required to use only one of the F to change its location in this algorithm, and an adaptive mechanism for the number of F is suggested as follows:(9)flame no.=roundN−tN−1T,where t is the current iteration number, N is the maximum number of flames, and T is the maximum iteration number.


## 2.1. Particle Swarm Optimization

The PSO conducts its search utilizing a swarm of particles; a swarm of particles is arbitrarily made initially [21, 22]. The standard atom swarm optimizer keeps up a swarm of atoms that talk to the potential courses of action for the issue at hand. Suppose that the look space is D-dimensional and the position of ith particle of the swarm can be portrayed utilizing a D-dimensional vector, xi = xi1,…,xid,…,xiD. The velocity of the particle xi is described by a D-dimensional vector vi = vi1,…,vid,…,viD. The last best position of ith particle is named pi = pi1,…,pid,…,piD. In substance, the heading of each atom is updated concurring to its claim flying encounter as well as to that of the finest atom inside the swarm. The basic PSO calculation can be portrayed as(5)vi,dk+1=w⋅vi,dk+c1⋅r1k⋅pi,dk−xi,dk+c2⋅r2k⋅pg,dk−xi,dk,xi,dk+1=xi,dk+vi,dk+1,where vi,dk is dth dimension velocity of particle i in cycle k; xi,dk is the dth dimension position of particle i in cycle k; pi,dk is the dth dimension position of personal best (pbest) of particle i in cycle k; pg,dk is the dth dimension position of global best particle (gbest) in cycle k; w is the inertia weight; c1 is the cognitive weight and c2 is a social weight; and r1 and r2 are two random values uniformly distributed in the range of [0, 1] [23].


## 2.2. Moth-Flame Optimization Algorithm

Mirjalili [9] proposed MFO in 2015 as a nature-inspired optimization algorithm that simulates the actions of individuals in a swarm of moths (search agents) that have unique night navigation methods. In the MFO algorithm, the candidate solutions are assumed to be search agents. In order to model how individuals move in a spiral, the m-by-d matrix namely M is used, where m stands for the number of search agents and d for the number of dimensions. It is assumed that, for each entity, there is an array for storing the value of the objective function as an m-by-one matrix, namely, OM.The flame, which is defined in an m-by-d matrix calledF, is also an important part of this algorithm. It is assumed that there is a way to store F’s fitness value as OF in an array. When using the MFO algorithm, F can be thought of as M’s best location in the search space. To mathematically model this action, each search agent’s location is modified as follows:(6)Mi=SMi,Fj,where Mi is the ith search agent and Fj is the jth best position found so far, and S indicates the logarithmic spiral function which is updated as follows:(7)SMi,Fj=Diecrcos2πr+Fj,where r is a random number in [−1, 1], c is a constant that defines the shape of the logarithmic spiral, and Di factor is the distance of the ith search agent for the jth flame, which is calculated as follows:(8)Di=Fj−Mi.M is required to use only one of the F to change its location in this algorithm, and an adaptive mechanism for the number of F is suggested as follows:(9)flame no.=roundN−tN−1T,where t is the current iteration number, N is the maximum number of flames, and T is the maximum iteration number.


## 3. The Proposed MFO for DKP01

### 3.1. Solution Presentation

Currently, there are two methods for presenting a solution: one uses a binary vector with a length equal to the dimensional of the problem which is 3∗n [3, 7, 24, 25], and the other uses an integer vector with a length equal to the number of groups n [8].The solution [20] is presented in this paper using a new binary encode scheme with a length of 2∗n. This encoding scheme has the benefit of being shorter in length and automatically satisfying constraint 2. In Table 1, a new binary encoding scheme is introduced. When compared with the previous solution presentation shown in Table 2, it has two disadvantages: it uses a longer vector to present a solution and there are four violate solutions in each scheme.Table 1
2∗n length binary encoding scheme.
No.2∗n length binary vectorMeaning100No item of the group is chosen201The first item of the group is chosen310The second item of the group is chosen411The third item of the group is chosenTable 2
3∗n length binary encoding scheme.
No.3∗n length binary vectorMeaning1000No item of the group is chosen2001The first item of the group is chosen3010The second item of the group is chosen4011Violate constraint (2)5100The third item of the group is chosen6101Violate constraint (2)7110Violate constraint (2)8111Violate constraint (2)


### 3.2. Repair Function

Constraint 2 is automatically satisfied by the current encoding scheme. A new repair based on the concept in [3] is proposed to manage restriction 3 and increase the consistency of the solution.The benefit of this repair technique is that it strikes a balance between CPU time consumption and the avoidance of local optima. The profit-to-weight ratios arepi/wi (i = 1, 2, …, n) so that they are not increasing. It means that(10)piwi≥pjwj,fori<j.This repair operator consists of two phases. The first phase (called repair phase) examines each variable in an increasing order ofpj/wj and drops an item from knapsack if feasibility is violated. The first phase (called optimization phase) examines each variable in an increasing order of pj/wj and add an item to knapsack as long as feasibility is not violated. The repair phase aims to obtain a feasible solution from an infeasible solution, whilst the optimization phase seeks to improve the fitness of a feasible solution. The details of this repair operator can be found in [20].The overall pseudocode of the MFO algorithms for DKP01 is given in Algorithm1.Algorithm 1: The overall pseudocode MFO algorithm for DKP01.
Input: initial parametersOutput: optimal solution(1)
Initialize search agents M(2)
t = 1;(3)
whilet≤Tdo(4)
Update flame no. by equation (9)(5)
Generate binaryX matrix by equation (11);(6)
Apply repair operator onX and assign its fitness to OM;(7)
ift = = 1 then(8)
F = sort (M1);(9)
OF = sort (OM1);(10)
else(11)
F = sort (Mt−1,Mt);(12)
OF = sort (OMt−1,OMt);(13)
fori = 1:mdo(14)
forj = 1:ddo(15)
CalculateD by equation (8);(16)
UpdateM (i, j) by equations (6) and (7);(17)
t = t + 1.


### 3.3. Binary Moth-Flame Optimization Algorithm

The MFO algorithm was designed for real domain. To solve DKP01, MFO is used to redesign a search in a binary domain. Equations (11)–(13) are used to convert real vectors to binary vectors:(11)Xi,j=0,if rand≥TFMi,j,1,if rand<TFMi,j,where TF (.) are the transforming functions of the probability as the following expressions:(12)TF1Mi,j=11+e−2Mi,j,(13)TF2Mi,j=11+e−Mi,j.In this section, we proposed 2 binary algorithms based on MFO named MFO1 and MFO2. MFO1 and MFO2 use transfer functionTF1 (equation (12)) and TF2 (equation (13)), respectively. They use formula (11) to compute binary vector X.


## 3.1. Solution Presentation

Currently, there are two methods for presenting a solution: one uses a binary vector with a length equal to the dimensional of the problem which is 3∗n [3, 7, 24, 25], and the other uses an integer vector with a length equal to the number of groups n [8].The solution [20] is presented in this paper using a new binary encode scheme with a length of 2∗n. This encoding scheme has the benefit of being shorter in length and automatically satisfying constraint 2. In Table 1, a new binary encoding scheme is introduced. When compared with the previous solution presentation shown in Table 2, it has two disadvantages: it uses a longer vector to present a solution and there are four violate solutions in each scheme.Table 1
2∗n length binary encoding scheme.
No.2∗n length binary vectorMeaning100No item of the group is chosen201The first item of the group is chosen310The second item of the group is chosen411The third item of the group is chosenTable 2
3∗n length binary encoding scheme.
No.3∗n length binary vectorMeaning1000No item of the group is chosen2001The first item of the group is chosen3010The second item of the group is chosen4011Violate constraint (2)5100The third item of the group is chosen6101Violate constraint (2)7110Violate constraint (2)8111Violate constraint (2)


## 3.2. Repair Function

Constraint 2 is automatically satisfied by the current encoding scheme. A new repair based on the concept in [3] is proposed to manage restriction 3 and increase the consistency of the solution.The benefit of this repair technique is that it strikes a balance between CPU time consumption and the avoidance of local optima. The profit-to-weight ratios arepi/wi (i = 1, 2, …, n) so that they are not increasing. It means that(10)piwi≥pjwj,fori<j.This repair operator consists of two phases. The first phase (called repair phase) examines each variable in an increasing order ofpj/wj and drops an item from knapsack if feasibility is violated. The first phase (called optimization phase) examines each variable in an increasing order of pj/wj and add an item to knapsack as long as feasibility is not violated. The repair phase aims to obtain a feasible solution from an infeasible solution, whilst the optimization phase seeks to improve the fitness of a feasible solution. The details of this repair operator can be found in [20].The overall pseudocode of the MFO algorithms for DKP01 is given in Algorithm1.Algorithm 1: The overall pseudocode MFO algorithm for DKP01.
Input: initial parametersOutput: optimal solution(1)
Initialize search agents M(2)
t = 1;(3)
whilet≤Tdo(4)
Update flame no. by equation (9)(5)
Generate binaryX matrix by equation (11);(6)
Apply repair operator onX and assign its fitness to OM;(7)
ift = = 1 then(8)
F = sort (M1);(9)
OF = sort (OM1);(10)
else(11)
F = sort (Mt−1,Mt);(12)
OF = sort (OMt−1,OMt);(13)
fori = 1:mdo(14)
forj = 1:ddo(15)
CalculateD by equation (8);(16)
UpdateM (i, j) by equations (6) and (7);(17)
t = t + 1.


## 3.3. Binary Moth-Flame Optimization Algorithm

The MFO algorithm was designed for real domain. To solve DKP01, MFO is used to redesign a search in a binary domain. Equations (11)–(13) are used to convert real vectors to binary vectors:(11)Xi,j=0,if rand≥TFMi,j,1,if rand<TFMi,j,where TF (.) are the transforming functions of the probability as the following expressions:(12)TF1Mi,j=11+e−2Mi,j,(13)TF2Mi,j=11+e−Mi,j.In this section, we proposed 2 binary algorithms based on MFO named MFO1 and MFO2. MFO1 and MFO2 use transfer functionTF1 (equation (12)) and TF2 (equation (13)), respectively. They use formula (11) to compute binary vector X.


## 4. Simulation Results

In this paper, the experience results of MFO1 and MFO2 algorithms are compared to find out the best one to solve DKP01 among them. The proposed algorithms are used to compare the results of three algorithms took from [6] named as SecEGA and two PSO algorithms took from Truong [20]. The PSO1 and PSO2 algorithms are BSPO7 and BPSO8 taken from Truong [20], respectively. 30 DKP01 test instances include 10 weakly correlated instances (denoted as WDKP1–WDKP10), 10 inverse strongly correlated instances (denoted as IDKP1–IDKP10), and 10 strongly correlated instances (denoted as SDKP1–SDKP10) [3].All experiments of the proposed algorithms are running on a Laptop ASUS with an Intel (R) Core (TM) i5-8250u CPU-1.6 GHz and 8 GB DDR4 memory. The operating system is Microsoft Windows 10. The programming language is MATLAB, version R2016a.In MFO, the number of moths is set to 50, and the search domain is the interval [1, 10]. The parameters of SecEGA are shown in [6]. The population size of SecEGA is set to 50, and the iteration is set equal to the dimension of the DKP01. For a fair comparison, the parameters for two PSO algorithms are set as the number of particles equal to 50, C1 and C2 are set to 2, w is linearly decreased from 0.9 to 0.4, the maximum number of iterations is set equal to the dimension of DKP01, and the stopping criterion is satisfied when the maximum number of iterations is reached. For all algorithms, the max iteration is set equal to 2∗n. The Gap is calculated by(14)Gap=OPT−AverageOPT100%.In this section, the short terms Best, Average, Worst, and StdDev are best, average, worst, and standard deviation of 30 independent runs, respectively.Tables3–5 summarizes the comparison among PSO1, PSO2, MFO2, SecEGA, and MFO1 based on the 6 different performance criteria on 30 independent runs including Best, Average, Worst, StdDev, the Gap, and Average rank. The MFO1 is better than PSO1, PSO2, MFO2, and SecEGA in Best, Average, and Worst for the instances of SDKP, UDKP, and WDKP except for instances of IDKP. The algorithm MFO1 archived the best rank on Average results.Table 3
Comparison of PSO1, PSO2, SecEGA, MFO1, and MFO2 on IDKP1–IDKP10.
InstanceOPTAlgorithmBestAverageWorstStdDevGapRankIDKP170106PSO1694716898068252288.01.64PSO2695306911768376237.21.43SecEGA68 6636800067 369328.43.05MFO17010670106701060.00.01MFO27010670104700904.90.02IDKP2118268PSO1116710116212115370354.21.74PSO2117200116516115700337.31.53SecEGA114 434113385112 3077446.74.15MFO11182680.00.01MFO211826811825111823019.30.02IDKP3234804PSO1234290233653232350420.40.53PSO2234390232600232600389.60.44SecEGA220 096217982216 313835.87.25MFO12347702347482347407.70.01MFO223470023454423436092.30.12IDKP4282591PSO1280540279714277810578.11.04PSO2280770279858279110486.71.03SecEGA263 238260425258 922933.47.85MFO12825902825872825705.80.01MFO2282470282210281940132.10.12IDKP5335584PSO1333140331595329340748.81.24PSO2332710331896329280691.21.13SecEGA309 573306878304 881907.28.65MFO13355803355803355800.00.01MFO2335280335000334780107.20.22IDKP6452463PSO1450290449287447540681.70.74PSO2450880449350447890683.30.73414 090411367408 7881099.39.15MFO14524304524154523909.70.01MFO2451750451293450990198.30.32IDKP7489149PSO1483180481656478830944.51.53PSO24831704815784799101034.91.54SecEGA451 528444316442 1331280.39.25MFO14891504891324891209.70.01MFO2488520487889487030288.10.32IDKP8533841PSO15233005209395177201480.02.44PSO25262405218445191901540.02.23SecEGA490 494481831478 0352215.79.75MFO15338405338255338206.30.01MFO2533050532345531940284.30.32IDKP9528144PSO15156805119085072101937.03.14PSO25165505125755090901727.02.93SecEGA489 661477001471 8483656.29.75MFO15281405281365281207.20.01MFO2527140526734526370205.80.32IDKP10581244PSO15639605602145561002204.13.64PSO25666705620005595401950.23.33SecEGA535 541521604516 4454265.110.35MFO15812405812335812304.50.01MFO2580620579589578870365.00.32Table 4
Comparison of PSO1, PSO2, SecEGA, MFO1, and MFO2 on SDKP1–SDKP10.
InstanceOPTAlgorithmBestAverageWorstStdDevGapRankSDKP194459PSO1942199387493489184.333.94PSO2942059399993703130.534.13SecEGA89 7698883287463594.96.05MFO194286942749425812.634.51MFO294286942229412143.234.42SDKP2160805PSO1160280159531158810360.134.94PSO2160090159617159030307.435.03SecEGA153 821152059150753489.45.45MFO115998015989515980047.335.21MFO215984015966715939093.935.02SDKP3238248PSO1237340236389235320440.20.73PSO2237300236428235620371.40.71SecEGA224 997223580221918543.46.25MFO123653023640423631051.80.72MFO2236140235855235600128.80.44SDKP4340027PSO1337960337013335880585.019.31PSO2337860336811335890508.319.23SecEGA318 510315513313 747851.17.25MFO133698033686533680039.019.22MFO2336390335989335730172.918.94SDKP5463033PSO1459780458216456130728.536.53PSO2459420458086456840615.136.54SecEGA420 238416964413 9331291.710.05MFO146019046009646001045.537.11MFO2459240458554458240225.436.62SDKP6466097PSO1462350460874459340677.11.92PSO2462000460989459690602.61.91SecGA430 738427304425 5041031.18.35MFO146100046086246075064.31.93MFO2460060459245458780226.81.54SDKP7620446PSO16145106127466103601059.225.34PSO2614780612902610930928.125.33SecEGA561 224556083552 0071926.310.45MFO161590061575661563069.225.91MFO2613930613268612870281.125.42SDKP8670697PSO1663730661988659770984.424.04PSO2664250662529660340992.724.12SecEGA611 644606263603 7741446.99.65MFO166475066459066445076.024.51MFO2662910662053661640303.524.03SDKP9739121PSO17318307302837277701058.938.33PSO27323207306197285701060.138.32SecEGA674 885667900664 5801614.09.65MFO173163073150273136068.338.51MFO2728790728306727650315.537.94SDKP10765317PSO1756580755021753220806.229.92PSO27574307547987524701402.829.93SecEGA708 935695557691 9942956.19.15MFO1756190755966755650120.730.11MFO2753740753027752270336.629.64Table 5
Comparison of PSO1, PSO2, SecEGA, MFO1, and MFO2 on WDKP1–WDKP10.
InstanceOPTAlgorithmBestAverageWorstStdDevGapRankWDKP183098PSO1829988276482465140.518.14PSO2830028279782549125.718.13SecEGA800147902278096473.74.95MFO182962828948284822.518.21MFO282950828628279834.818.22WDKP2138215PSO1137880137278136770254.216.14PSO2137860137381136780247.216.23SecEGA133315132276131337415.64.35MFO113792013787313785022.016.61MFO213789013779513772040.716.52WDKP3256616PSO1256160255362254210422.38.84PSO2255990255386254670356.38.83SecEGA238331235721234025873.68.15MFO125597025589125582028.49.01MFO225566025546325526090.08.82WDKP4315657PSO1314790313860313010434.811.14PSO2314750314108313390399.311.23SecEGA293640290851288764950.17.95MFO131504031498031493028.011.51MFO2314630314400314190125.611.32WDKP5428490PSO1426910425683424470701.926.84PSO2426680425736424520501.126.93SecEGA3936173900143879921059.89.05MFO142771042766642762023.027.41MFO2427260426687426270214.527.12WDKP6466050PSO1463690462092460590641.32.14PSO2463350462284460930583.12.23SecGA4292084251124232691058.48.85MFO146488046481946476028.92.71MFO2463820463485463080203.22.42WDKP7547683PSO15447005427245388601154.911.04PSO2544730542765539860922.511.03SecEGA5015574961344938451230.99.45MFO154650054642554638029.811.71MFO2545300544705544110295.411.42WDKP8576959PSO15725305701875675301216.66.84PSO2571870570226568570825.36.83SecEGA5309715232035203502157.19.35MFO157559057546357536045.57.81MFO2574520573672572880299.17.52WDKP9650660PSO16439506412726382101501.321.44PSO26451406416586382301502.321.53SecEGA5983435867705838542315.59.85MFO164876064867264860035.922.81MFO2647040646510646030268.122.42WDKP10678967PSO16723806689236664201429.215.13PSO26718806688306657401553.115.14SecEGA6202306062156099643090.910.75MFO167745067738867733034.516.51MFO2676110675115674680284.216.22The results showed that MFO1 is the best one among the 5 algorithms. Table6 summarizes the average rank of the 5 algorithms on 30 instances. The result showed that MFO1 achieved the average best rank in all the three test instances on average mean rank. Figure 1 demonstrates the boxplot of the four algorithms on IDKP instances: IDKP2, IDKP4, IDKP6, and IDKP8. Figure 2 demonstrates the boxplot of the four algorithms on WDKP instances: WDKP2, WDKP4, WDKP6, and WDKP8. Figure 3 demonstrates the boxplot of the four algorithms on SDKP instances: SDKP2, SDKP4, SDKP6, and SDKP8. These box plot figures showed that MFO1 obtained the best result.Table 6
Average rank of PSO1, PSO2, SecEGA, MFO1, and MFO2 on 30 instances.
AlgorithmsMean rank of 10Mean rank of 10Mean rank of 10IDKP instancesSDKP instancesWDKP instancesPSO13.83.03.9PSO23.22.53.1SecEGA4.54.54.5MFO11.01.41.0MFO22.03.12.0Figure 1
Box plot of four algorithms on IDKP instances. (a) IDKP2. (b) IDKP4. (c) IDKP6. (d) IDKP8.
(a)(b)(c)(d)Figure 2
Box plot of four algorithms on WDKP instances. (a) WDKP2. (b) WDKP4. (c) WDKP6. (d) WDKP8.
(a)(b)(c)(d)Figure 3
Box plot of four algorithms on SDKP instances. (a) SDKP2. (b) SDKP4. (c) SDKP6. (d) SDKP8.
(a)(b)(c)(d)Figure4 demonstrates the convergence curves of the four algorithms on IDKP instances: IDKP2, IDKP4, IDKP6, and IDKP8. Figure 5 demonstrates the convergence curves of the four algorithms on WDKP instances: WDKP2, WDKP4, WDKP6, and WDKP8. Figure 6 demonstrates the convergence curves of the four algorithms on SDKP instances: SDKP2, SDKP4, SDKP6, and SDKP8. These convergence curves demonstrated that MFO1 has faster convergence than group algorithms PSO1, PSO2, and MFO2.Figure 4
Convergence curves of four algorithms on IDKP instances. (a) IDKP2. (b) IDKP4. (c) IDKP6. (d) IDKP8.
(a)(b)(c)(d)Figure 5
Convergence curves of four algorithms on WDKP instances. (a) WDKP2. (b) WDKP4. (c) WDKP6. (d) WDKP8.
(a)(b)(c)(d)Figure 6
Convergence curves of four algorithms on SDKP instances. (a) SDKP2. (b) SDKP4. (c) SDKP6. (d) SDKP8.
(a)(b)(c)(d)Therefore, the performance of MFO1 is better than that of the other algorithm for the DKP01 problem. From the above comparison, MFO1 showed far better result than those of PSO1, PSO2, MFO2, and SecEGA. The evidence supports that MFO1 is a potential method for solving DKP01.


### 4.1. Wilcoxon Rank Sum Test

With the observable measures, I am ready to prove beyond a shadow of a doubt that the outcomes are not the product of chance. The nonparametric Wilcoxon statistical test is used and the calculatedp values are reported as metrics of significance as well. Any p values <0.05 evidence the statistical significant superiority of the results when comparing MFO1 with MFO2, PSO1, and PSO2. After all, the statistical results for 30 instances are provided in Table 7.Table 7
p values of the Wilcoxon rank-sum test over 30 runs.
InstanceMFO2PSO1PSO2IDKP10.0814041.21E − 121.21E − 12IDKP21.14E − 051.21E − 121.21E − 12IDKP31.86E − 111.87E − 111.87E − 11IDKP46.34E − 126.42E − 126.42E − 12IDKP51.2E − 121.21E − 121.21E − 12IDKP61.23E − 111.24E − 111.24E − 11IDKP72.25E − 112.25E − 112.25E − 11IDKP81.45E − 111.45E − 111.45E − 11IDKP97.77E − 127.8E − 127.8E − 12IDKP108.84E − 128.87E − 128.87E − 12SDKP14.45E − 072.11E − 112.11E − 11SDKP25.56E − 114.32E − 060.000351SDKP32.89E − 110.4821580.578909SDKP42.76E − 110.0305750.109566SDKP52.93E − 112.94E − 112.94E − 11SDKP62.95E − 110.1643450.26713SDKP72.96E − 112.97E − 112.97E − 11SDKP82.96E − 112.96E − 112.96E − 11SDKP92.97E − 113.91E − 080.000431SDKP102.99E − 111.02E − 063.36E − 05WDKP12.68E − 050.0007740.000401WDKP22.19E − 101.87E − 108.09E − 11WDKP32.21E − 112.41E − 076.25E − 10WDKP42.71E − 112.74E − 112.73E − 11WDKP52.86E − 112.87E − 112.87E − 11WDKP62.87E − 112.86E − 112.88E − 11WDKP72.85E − 112.85E − 112.85E − 11WDKP82.9E − 112.92E − 112.92E − 11WDKP92.83E − 112.84E − 112.83E − 11WDKP102.92E − 112.93E − 112.93E − 11p>0.05 is indicated in bold.


## 4.1. Wilcoxon Rank Sum Test

With the observable measures, I am ready to prove beyond a shadow of a doubt that the outcomes are not the product of chance. The nonparametric Wilcoxon statistical test is used and the calculatedp values are reported as metrics of significance as well. Any p values <0.05 evidence the statistical significant superiority of the results when comparing MFO1 with MFO2, PSO1, and PSO2. After all, the statistical results for 30 instances are provided in Table 7.Table 7
p values of the Wilcoxon rank-sum test over 30 runs.
InstanceMFO2PSO1PSO2IDKP10.0814041.21E − 121.21E − 12IDKP21.14E − 051.21E − 121.21E − 12IDKP31.86E − 111.87E − 111.87E − 11IDKP46.34E − 126.42E − 126.42E − 12IDKP51.2E − 121.21E − 121.21E − 12IDKP61.23E − 111.24E − 111.24E − 11IDKP72.25E − 112.25E − 112.25E − 11IDKP81.45E − 111.45E − 111.45E − 11IDKP97.77E − 127.8E − 127.8E − 12IDKP108.84E − 128.87E − 128.87E − 12SDKP14.45E − 072.11E − 112.11E − 11SDKP25.56E − 114.32E − 060.000351SDKP32.89E − 110.4821580.578909SDKP42.76E − 110.0305750.109566SDKP52.93E − 112.94E − 112.94E − 11SDKP62.95E − 110.1643450.26713SDKP72.96E − 112.97E − 112.97E − 11SDKP82.96E − 112.96E − 112.96E − 11SDKP92.97E − 113.91E − 080.000431SDKP102.99E − 111.02E − 063.36E − 05WDKP12.68E − 050.0007740.000401WDKP22.19E − 101.87E − 108.09E − 11WDKP32.21E − 112.41E − 076.25E − 10WDKP42.71E − 112.74E − 112.73E − 11WDKP52.86E − 112.87E − 112.87E − 11WDKP62.87E − 112.86E − 112.88E − 11WDKP72.85E − 112.85E − 112.85E − 11WDKP82.9E − 112.92E − 112.92E − 11WDKP92.83E − 112.84E − 112.83E − 11WDKP102.92E − 112.93E − 112.93E − 11p>0.05 is indicated in bold.


## 5. Conclusion

A moth-flame optimization algorithm that showed good searchability is combined with an effective solution presentation designed to the discounted {0-1} knapsack problem. A new encoding scheme used a shorter length binary vector to help reduce the search domain and speed up the computing time. A greedy repair procedure is used to help the algorithm have fast convergence and reduce the gap between the best-found solution and th eoptimal solution. The simulation results of 30 DKP01 instances showed that the proposed algorithms are better than the two particle swarm optimization algorithms and one genetic algorithm. In the future, some variants of the moth-flame optimization algorithm are considered for study for the discounted {0-1} knapsack problem.



---

*Source: 5092480-2021-11-01.xml*