# Different Transfer Functions for Binary Particle Swarm Optimization with a New Encoding Scheme for Discounted {0-1} Knapsack Problem

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

---

## Abstract

The discounted {0-1} knapsack problem (DKP01) is a kind of knapsack problem with group structure and discount relationships among items. It is more challenging than the classical 0-1 knapsack problem. In this paper, we study binary particle swarm optimization (PSO) algorithms with different transfer functions and a new encoding scheme for DKP01. An effective binary vector with shorter length is used to represent a solution for new binary PSO algorithms. Eight transfer functions are used to design binary PSO algorithms for DKP01. A new repair operator is developed to handle isolation solution while improving its quality. Finally, we conducted extensive experiments on four groups of 40 instances using our proposed approaches. The experience results show that the proposed algorithms outperform the previous algorithms named FirEGA and SecEGA . Overall, the proposed algorithms with a new encoding scheme represent a potential approach for solving the DKP01.


---

## Body

## 1. Introduction

The discounted 0-1 knapsack problem (DKP01) is a new kind of knapsack problem proposed by Guldan [1]. This problem has an important role in the real-world business process. It is a part of many key problems such as investment decision-making, mission selection, and budget control. An exact algorithm based on dynamic programming for the DKP01 is first proposed in [1]. An approach combining dynamic programming with the core of the DKP01 to solve it is studied in [2]. Two algorithms based on genetic algorithm for DKP01 are named FirEGA and SecEGA in [3].Assume that there aren groups. Each group contains three items. Consider a given set of 3∗n items; each of them has an integer weight wi and an integer profit pi. The problem is to select a subset from the set of 3∗n items in n groups such that the overall profit is maximized without exceeding a given weight capacity C. We cannot choose more than 1 item in each group. It is an NP-Hard problem and hence it does not have a polynomial time algorithm unless P=NP. The problem may be mathematically modelled 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)subject tox3iw3i+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 knapsack: xj=0 indicates that the item jj=0,1,…,3n−1 is not in knapsack, while xj=1 indicates that the item j is in 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 equations (2) and (3), it is a feasible solution of DKP01.Recently, He et al. 2016 also had a detailed study of the algorithms of the DKP01 and proposed brand new deterministic algorithm and approximation algorithms. A new exact algorithm and two approximation algorithms with a greedy repair operator were proposed to solve DKP01 [4]. An algorithm based on PSO is named GBPSO using discrete particle swarm optimization [5]. An evolution algorithm combines with ring theory to solve DKP01 [6]. Multistrategy monarch butterfly optimization algorithm, Binary Moth Search algorithm [7], and hybrid teaching-learning-based optimization algorithm [8] are proposed for DKP01. Binary PSO is also developed to solve many optimization problems such as scheduling of appliances in smart homes [9], fault diagnosis of bearing [10], operation cost reduction in unit commitment problem [11], channel selection in the EEG signals and its application to speller systems [12], wireless sensor networks [13], transmission expansion planning considering n − 1 security criterion [14], a bare-bones multiobjective particle swarm optimization algorithm for environmental/economic dispatch [15], multiobjective particle swarm optimization for feature selection with fuzzy cost [16], multiobjective particle swarm optimization approach for cost-based feature selection in classification [17], and variable-size cooperative coevolutionary particle swarm optimization for feature selection on high-dimensional data [18].Many algorithms were proposed to solve DKP01, and each of them has its advantages and disadvantages. Further study on this problem is necessary. In this paper, we study binary particle swarm optimization (PSO) algorithms with different transfer function and a new encoding scheme for DKP01. An effective binary vector with2∗-dimensional length is used to represent an individual the proposed binary PSO strategies. Eight types of transfer functions are used to design binary PSO algorithms for DKP01. Finally, we conducted extensive experiments on four groups of 40 instances using our proposed approaches. The experience results demonstrate that the proposed algorithms outperform the genetic algorithm and original binary PSO in solving 40 DKP01 instances. The main contributions of this work can be listed as follows:(i)
Binary particle swarm optimization algorithms with difference binary transfer functions and new solution presentation are proposed to solve the discounted {0-1} knapsack problem.(ii)
A new encoding scheme has shorter binary vector (the length is 2n compared to 3n) and also automatically satisfies the constraint that chose the most one item in each group.(iii)
A new repair operator is developed to handle isolation solution while improving its quality.The rest of this paper is organized as follows: Section2 presents previous algorithms for KP01. Section 3 presents the binary particle swarm optimization 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 implements a population of particles. A population of particles is randomly created initially [19, 20]. The standard molecule swarm optimizer keeps up a swarm of molecule that speaks to the potential arrangements to issue on hand. Suppose that the search space is D-dimensional, and the position of the ith particle of the swarm can be described using 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 the ith particle is named as pi=pi1,…,pid,…,piD. In substance, the direction of each molecule is upgraded concurring to its claim flying experience as well as to that of the finest molecule within the swarm. The fundamental PSO calculation can be depicted as(5)vi,dk+1=w⋅vi,dk+c1⋅r1k⋅pi,dk−xi,dk+c2⋅r2k⋅pg,dk−xi,dk,(6)xi,dk+1=xi,dk+vi,dk+1,where vi,dk is the 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; r1 and r2 are two random values uniformly distributed in the range of [0, 1] [21].The pseudocode of the PSO is given in Algorithm1.Algorithm 1:PSO algorithm.
Input: Initial parametersOutput: optimal solution(1)
foreach particledo(2)
Initialize particle(3)
whilestop condition is not metdo(4)
foreach particledo(5)
Evaluate objective function(6)
ifthe objective function value ≤ pBestthen(7)
current value is replace bypBest(8)
Calculate thegBest (the global best value)(9)
foreach particledo(10)
Calculate particle velocity by equation (5)(11)
Update particle position by equation (6)


### 2.2. Binary Particle Swarm Optimization

The binary particle swarm optimization algorithm was introduced by Bansal and Deep to allow the PSO algorithm to operate in binary problem spaces [21–23]. It uses the concept of velocity as a probability that a bit (position) takes on one or zero. In the BPSO, equation (5) for updating the velocity remains unchanged, but equation (6) for updating the position is redefined by the rule using the two following equations:(7)xi,dk+1=0,if rand≥Svi,dk+1,1,if rand<Svi,dk+1,(8)xi,dk+1=notxi,dk,if rand≥Svi,dk+1,xi,dk,if rand<Svi,dk+1,where S (.) is the sigmoid function for transforming the velocity to the probability as the following expression:(9)S1vi,dk+1=11+e−2vi,dk+1,S2vi,dk+1=11+e−vi,dk+1,S3vi,dk+1=11+e1/2vi,dk+1,S4vi,dk+1=11+e1/3vi,dk+1,S5vi,dk+1=erfπ2vi,dk+1,S6vi,dk+1=tanhvi,dk+1,S7vi,dk+1=11+vi,dk+12,S8vi,dk+1=2πarctanπ2vi,dk+1.In this section, we propose 8 binary algorithms based on BSO named BPSO1 to BPSO8. The algorithm BPSOx uses transfer function Sx (where x is integer in [1, 8]), and BPSO1–BPSO4 use formula (7), while BPSO5–BPSO8 use formula (8) to calculate binary vector X.


## 2.1. Particle Swarm Optimization

The PSO implements a population of particles. A population of particles is randomly created initially [19, 20]. The standard molecule swarm optimizer keeps up a swarm of molecule that speaks to the potential arrangements to issue on hand. Suppose that the search space is D-dimensional, and the position of the ith particle of the swarm can be described using 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 the ith particle is named as pi=pi1,…,pid,…,piD. In substance, the direction of each molecule is upgraded concurring to its claim flying experience as well as to that of the finest molecule within the swarm. The fundamental PSO calculation can be depicted as(5)vi,dk+1=w⋅vi,dk+c1⋅r1k⋅pi,dk−xi,dk+c2⋅r2k⋅pg,dk−xi,dk,(6)xi,dk+1=xi,dk+vi,dk+1,where vi,dk is the 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; r1 and r2 are two random values uniformly distributed in the range of [0, 1] [21].The pseudocode of the PSO is given in Algorithm1.Algorithm 1:PSO algorithm.
Input: Initial parametersOutput: optimal solution(1)
foreach particledo(2)
Initialize particle(3)
whilestop condition is not metdo(4)
foreach particledo(5)
Evaluate objective function(6)
ifthe objective function value ≤ pBestthen(7)
current value is replace bypBest(8)
Calculate thegBest (the global best value)(9)
foreach particledo(10)
Calculate particle velocity by equation (5)(11)
Update particle position by equation (6)


## 2.2. Binary Particle Swarm Optimization

The binary particle swarm optimization algorithm was introduced by Bansal and Deep to allow the PSO algorithm to operate in binary problem spaces [21–23]. It uses the concept of velocity as a probability that a bit (position) takes on one or zero. In the BPSO, equation (5) for updating the velocity remains unchanged, but equation (6) for updating the position is redefined by the rule using the two following equations:(7)xi,dk+1=0,if rand≥Svi,dk+1,1,if rand<Svi,dk+1,(8)xi,dk+1=notxi,dk,if rand≥Svi,dk+1,xi,dk,if rand<Svi,dk+1,where S (.) is the sigmoid function for transforming the velocity to the probability as the following expression:(9)S1vi,dk+1=11+e−2vi,dk+1,S2vi,dk+1=11+e−vi,dk+1,S3vi,dk+1=11+e1/2vi,dk+1,S4vi,dk+1=11+e1/3vi,dk+1,S5vi,dk+1=erfπ2vi,dk+1,S6vi,dk+1=tanhvi,dk+1,S7vi,dk+1=11+vi,dk+12,S8vi,dk+1=2πarctanπ2vi,dk+1.In this section, we propose 8 binary algorithms based on BSO named BPSO1 to BPSO8. The algorithm BPSOx uses transfer function Sx (where x is integer in [1, 8]), and BPSO1–BPSO4 use formula (7), while BPSO5–BPSO8 use formula (8) to calculate binary vector X.


## 3. Proposed Binary Particle Swarm Optimization for DKP01

### 3.1. Solution Presentation

At present, there are two methods to encode a solution which are using a binary vector with length equal to the3∗n-dimensional problem [3, 7, 24, 25], and the other method is an integer vector with length equal to number of groups n to present a solution [8]. Each encoding scheme has its advantages and disadvantages. The binary scheme has an advantage when many metaheuristics have a good design to be directly applied to solution.In this paper, a new binary encode scheme with length2∗n is used to present the solution. The advantage of this encode scheme is shorter length and it automatically satisfies constraint 2. The new binary encoding scheme is presented in Table 1.Table 1
New binary encoding scheme.
No.Binary encoding schemeMeaning100No item of group is chosen201First item of group is chosen310Third item of group is chosen411Fourth item of group is chosen


### 3.2. Repair Function

The new encoding scheme automatically satisfies constraint 2. To handle constraint 3 and improve the quality of solution, a new repair based on the idea in [3] is proposed. The advantage of this repair procedure is the balance between CPU time cost and not getting stuck in local optima. The items are sorted according to the profit-to-weight ratio pi/wii=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 increasing order ofpj/wj and drops item from knapsack if feasibility is violated. The first phase (called optimization phase) examines each variable in increasing order of pj/wj and adds item to knapsack as long as feasibility is not violated. The aim of the repair phase is to obtain a feasible solution from an infeasible solution, while the optimization phase seeks to improve the fitness of a feasible solution. The pseudocode for the repair operator is given in Algorithm 2. The time complexity of repair operator is O (n).Algorithm 2:Repair operator.
Input: Solution x, value vector v, weight vector w, index vector id, and knapsack capacity C.Output: Solution x(1)
% Repair phase(2)
n ⟵ length (x)/2 fori = 1 : 3∗ndo(3)
k ⟵ floor ((id (i) − 1)/3);(4)
r ⟵ mod (id (i) − 1, 3);(5)
ifx2k+1=0∧x2k+1=1∧r=0∧fw+widi≤Cthen(6)
fv⟵fv+vidi(7)
fw⟵fw+widi(8)
else ifx2k+1=0∧x2k+1=1∧r=0∧fw+widi>Cthen(9)
x (2k + 1) ⟵ 0(10)
x (2k + 2) ⟵ 0(11)
ifx2k+1=1∧x2k+1=0∧r=1∧fw+widi≤Cthen(12)
fv⟵fv+vidi(13)
fw⟵fw+widi(14)
else ifx2k+1=1∧x2k+1=0∧r=1∧fw+widi>Cthen(15)
x (2k + 1) ⟵ 0(16)
x (2k + 2) ⟵ 0(17)
ifx2k+1=1∧x2k+1=1∧r=2∧fw+widi≤Cthen(18)
fv⟵fv+vidi(19)
fw⟵fw+widi(20)
else ifx2k+1=1∧x2k+1=1∧r=2∧fw+widi>Cthen(21)
x (2k + 1) ⟵ 0(22)
x (2k + 2) ⟵ 0(23)
% Optimization phase(24)
fori=1:3∗ndo(25)
k ⟵ floor ((id (i) − 1)/3);(26)
r ⟵ mod (id (i) − 1, 3);(27)
ifx2k+1=0∧x2k+1=0∧fw+widi≤Cthen(28)
fv⟵fv+vidi(29)
fw⟵fw+widi(30)
ifr=0then(31)
x (2k + 1) ⟵ 0; x (2k + 2) ⟵ 1(32)
ifr=1then(33)
x (2k + 1) ⟵ 1; x (2k + 2) ⟵ 0(34)
ifr=2then(35)
x (2k + 1) ⟵ 1; x (2k + 2) ⟵ 1(36)
returnxThe overall pseudocode of the BPSO algorithms for DKP01 is given in Algorithm3.Algorithm 3:Overall pseudocode of BPSO algorithms for DKP01.
Input: Initial parametersOutput: Optimal solution(1)
foreach particledo(2)
Initialize particle(3)
whilestop condition is not metdo(4)
foreach particledo(5)
Evalute objective function(6)
ifthe objective function value ≤ pBestthen(7)
current value is replace bypBest(8)
Caculate thegBest (the global best value)(9)
foreach particledo(10)
Calculate particle velocity by equation (5)(11)
CaculateS (.) using a transfer function(12)
Update particle position by equations (7) or (8)(13)
Apply repair operator for current particle position.


## 3.1. Solution Presentation

At present, there are two methods to encode a solution which are using a binary vector with length equal to the3∗n-dimensional problem [3, 7, 24, 25], and the other method is an integer vector with length equal to number of groups n to present a solution [8]. Each encoding scheme has its advantages and disadvantages. The binary scheme has an advantage when many metaheuristics have a good design to be directly applied to solution.In this paper, a new binary encode scheme with length2∗n is used to present the solution. The advantage of this encode scheme is shorter length and it automatically satisfies constraint 2. The new binary encoding scheme is presented in Table 1.Table 1
New binary encoding scheme.
No.Binary encoding schemeMeaning100No item of group is chosen201First item of group is chosen310Third item of group is chosen411Fourth item of group is chosen


## 3.2. Repair Function

The new encoding scheme automatically satisfies constraint 2. To handle constraint 3 and improve the quality of solution, a new repair based on the idea in [3] is proposed. The advantage of this repair procedure is the balance between CPU time cost and not getting stuck in local optima. The items are sorted according to the profit-to-weight ratio pi/wii=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 increasing order ofpj/wj and drops item from knapsack if feasibility is violated. The first phase (called optimization phase) examines each variable in increasing order of pj/wj and adds item to knapsack as long as feasibility is not violated. The aim of the repair phase is to obtain a feasible solution from an infeasible solution, while the optimization phase seeks to improve the fitness of a feasible solution. The pseudocode for the repair operator is given in Algorithm 2. The time complexity of repair operator is O (n).Algorithm 2:Repair operator.
Input: Solution x, value vector v, weight vector w, index vector id, and knapsack capacity C.Output: Solution x(1)
% Repair phase(2)
n ⟵ length (x)/2 fori = 1 : 3∗ndo(3)
k ⟵ floor ((id (i) − 1)/3);(4)
r ⟵ mod (id (i) − 1, 3);(5)
ifx2k+1=0∧x2k+1=1∧r=0∧fw+widi≤Cthen(6)
fv⟵fv+vidi(7)
fw⟵fw+widi(8)
else ifx2k+1=0∧x2k+1=1∧r=0∧fw+widi>Cthen(9)
x (2k + 1) ⟵ 0(10)
x (2k + 2) ⟵ 0(11)
ifx2k+1=1∧x2k+1=0∧r=1∧fw+widi≤Cthen(12)
fv⟵fv+vidi(13)
fw⟵fw+widi(14)
else ifx2k+1=1∧x2k+1=0∧r=1∧fw+widi>Cthen(15)
x (2k + 1) ⟵ 0(16)
x (2k + 2) ⟵ 0(17)
ifx2k+1=1∧x2k+1=1∧r=2∧fw+widi≤Cthen(18)
fv⟵fv+vidi(19)
fw⟵fw+widi(20)
else ifx2k+1=1∧x2k+1=1∧r=2∧fw+widi>Cthen(21)
x (2k + 1) ⟵ 0(22)
x (2k + 2) ⟵ 0(23)
% Optimization phase(24)
fori=1:3∗ndo(25)
k ⟵ floor ((id (i) − 1)/3);(26)
r ⟵ mod (id (i) − 1, 3);(27)
ifx2k+1=0∧x2k+1=0∧fw+widi≤Cthen(28)
fv⟵fv+vidi(29)
fw⟵fw+widi(30)
ifr=0then(31)
x (2k + 1) ⟵ 0; x (2k + 2) ⟵ 1(32)
ifr=1then(33)
x (2k + 1) ⟵ 1; x (2k + 2) ⟵ 0(34)
ifr=2then(35)
x (2k + 1) ⟵ 1; x (2k + 2) ⟵ 1(36)
returnxThe overall pseudocode of the BPSO algorithms for DKP01 is given in Algorithm3.Algorithm 3:Overall pseudocode of BPSO algorithms for DKP01.
Input: Initial parametersOutput: Optimal solution(1)
foreach particledo(2)
Initialize particle(3)
whilestop condition is not metdo(4)
foreach particledo(5)
Evalute objective function(6)
ifthe objective function value ≤ pBestthen(7)
current value is replace bypBest(8)
Caculate thegBest (the global best value)(9)
foreach particledo(10)
Calculate particle velocity by equation (5)(11)
CaculateS (.) using a transfer function(12)
Update particle position by equations (7) or (8)(13)
Apply repair operator for current particle position.


## 4. Simulation Results

In this paper, the experience results of eight BPSO algorithms are compared to find out the best one among them to solve DKP01. The best proposed BPSO is used to compare the results of two algorithms taken from [6] named FirEGA and SecEGA. 40 DKP01 test instances are 10 uncorrelated instances (denoted as UDKP1–UDKP10), 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 performed on a Dell Vostro 5471 VTI5207W laptop with an Intel (R) Core (TM) i5-8250u CPU-1.6 GHz and 8 GB DDR3 memory. The operating system is Microsoft Windows 10. All the algorithms are implemented using MATLAB R2018a.The parameters of FirEGA and SecEGA are shown in [6]. The population sizes of FirEGA and SecEGA are set to 50, and the iteration is set to be equal to the dimension of the DKP01. For a fair comparison, the parameters for BPSO algorithms are set as follows: the number of particles is 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 to be equal to the dimension of the DKP01, and the stopping criterion is satisfied when the maximum number of iterations is reached. For all algorithms, the numbers of objective function evaluations are similar.Tables2–5 summarize the comparison among 8 BPSO algorithms based on the five different performance factors, that is, the best results (BEST), the average results (AVE), the worst results (Worst), the standard deviation (Std. dev), and the gap between the AVE and OPT, where OPT is the optimal value of the instance. The results are averaged over 30 independent runs, and the best results are highlighted in bold font. The formula of computing the gap is as follows:(11)Gap=OPT−AVEOPT×100%.Table 2
Comparison of 8 BPSO algorithms on IDKP1–IDKP10.
BPSO1BPSO2BPSO3BPSO4BPSO5BPSO6BPSO7BPSO8IDKP1Best6798265735661306521569940699446990569950AVE66360.465219.164523.164206.469650.569689.369652.869761.0Worst6572464686639116358369345690696934869521Std. dev450.89285.19468.09367.69127.49184.26151.25109.15Gap5.346.977.968.420.650.590.650.49IDKP2Best111220109980107920106690117840117700117960118000AVE109885.7108308.3106567.0105800.3117157.7117265.3117237.7117418.0Worst108670107420105580104920116530116690116880117040Std. dev526.83583.77527.62375.53317.69220.23250.72228.83Gap7.098.429.8910.540.940.850.870.72IDKP3Best223100220370217660217270234550234600234510234540AVE221673.7219018.7216489.0215686.7234234.0234193.3234192.3234253.7Worst220330218260215340214360233870233740233820233800Std. dev655.53522.10621.85588.95170.00194.82196.90192.52Gap5.596.727.808.140.240.260.260.23IDKP4Best262250261600256030254560281630281460281860281560AVE260578.7257426.7254213.0253443.3280915.7280937.0280926.7280953.3Worst259350255980253070251990280230280210280310280220Std. dev680.611036.33669.28545.32370.76298.83381.13328.28Gap7.798.9010.0410.310.590.590.590.58IDKP5Best306710304080300290299740334080334460334370334330AVE305651.3302176.0298676.3297292.7333196.0333540.0333450.7333380.7Worst304530300500297810296300331670332140331700332480Std. dev627.16837.40572.50822.63558.47545.39595.10479.64Gap8.929.9611.0011.410.710.610.640.66IDKP6Best424860420840414340414270451530451120451180451390AVE422738.0418002.7412954.3410614.0450461.3450450.0450227.7450455.0Worst420920416490411800409440449550449230449230448980Std. dev1094.931134.30671.58922.85476.18491.61468.12563.12Gap6.577.628.739.250.440.440.490.44IDKP7Best445470440660437100434590485500485610485970485920AVE443578.0438952.7434153.7432156.0484351.7484123.3484322.3484205.7Worst441760437450432760430820482930482580482450482400Std. dev973.401031.281060.95965.40741.76739.59938.96879.02Gap9.3210.2611.2411.650.981.030.991.01IDKP8Best476350469590465180462400528810528720528910528450AVE473369.7467065.0462243.3460488.7526964.3526535.3526150.3526356.7Worst470860465310459400459070524250524640523860524150Std. dev1361.111059.541294.50853.731377.911070.181437.351268.72Gap11.3312.5113.4113.741.291.371.441.40IDKP9Best467480460890456610452870521210521390520960522140AVE463983.7458418.0453862.3451666.0516689.3517894.3518507.0518834.7Worst460970456540451430450200513400514390514080515480Std. dev1575.601013.391205.04700.421976.731723.291353.101726.89Gap12.1513.2014.0614.482.171.941.821.76IDKP10Best512140505660503250500520571780572400572250572260AVE509844.0503661.7498110.3495816.3568518.7569094.3568045.0569364.7Worst506800501750495910493320564150564620563900566140Std. dev1072.29996.781548.611635.381711.131681.261724.571446.41Gap12.2813.3514.3014.702.192.092.272.04Table 3
Comparison of 8 BPSO algorithms on SDKP1–SDKP10.
BPSO1BPSO2BPSO3BPSO4BPSO5BPSO6BPSO7BPSO8SDKP1Best9104690103900678955894300944219441494363AVE90484.489446.688655.588449.994089.394112.794174.494181.6Worst8996488772878358784793687938079392093897Std. dev240.44312.35513.73422.86152.07128.84103.15113.74Gap4.215.316.146.360.390.370.300.29SDKP2Best152080149910148440148320160470160490160430160570AVE150627.7148857.0147307.0146598.3160058.0160033.3160127.0160136.0Worst149590148000146410145830159730159380159480159780Std. dev591.17505.77535.13595.93190.92237.35214.82182.33Gap6.337.438.398.830.460.480.420.42SDKP3Best225340222940220310218570237580237350237430237370AVE223456.7221130.0218620.0217727.3236629.7236821.0236829.3236778.3Worst222120219740217530217020235770236390236110235960Std. dev617.52777.22567.24435.05359.95265.44352.00314.48Gap6.217.188.248.610.680.600.600.62SDKP4Best317610313630310850310020338360338480338520338240AVE315521.0311837.3308411.3306979.7337381.0337525.0337545.0337433.0Worst314020310180306940305490336270336540336440336210Std. dev938.08789.991010.631074.09501.50524.94540.16495.98Gap7.218.299.309.720.780.740.730.76SDKP5Best438720431560427340425190459900459890460190459970AVE435066.7429523.7424714.0422803.3458421.7458479.3458505.0458292.0Worst432570427170422560421120456570456980457430457130Std. dev1412.531057.971127.73833.64724.35669.22548.81802.76Gap6.047.248.288.691.000.980.981.02SDKP6Best428070424110417840415960463040462310463070462650AVE424916.3420600.0415690.3413662.3461229.3461288.0461370.0461310.7Worst423230418080414020412230459870459390459610459880Std. dev1121.731370.311020.89994.05759.15708.60789.20680.64Gap8.849.7610.8111.251.041.031.011.03SDKP7Best580940574630567460562990615640615810615100614830AVE578574.3571778.7564752.3561783.7613474.3613542.7613242.0613182.7Worst576180569410563080560270611790611970611180610700Std. dev1210.371118.881034.42708.71955.251000.74953.90984.83Gap6.757.848.989.451.121.111.161.17SDKP8Best619660613680605780602220665540665340665070665230AVE616572.0609950.0603096.3600201.3663894.7663703.3663633.7663681.7Worst614660607940601290598950662710661970661310661500Std. dev1288.631507.531244.25876.08772.79865.64806.70925.22Gap8.079.0610.0810.511.011.041.051.05SDKP9Best679360672620664590661320733260732790732800732910AVE676278.0668958.7661978.0659159.0731433.3731057.0731107.0730950.3Worst671400667010659530657170730050729290728590728990Std. dev1620.021566.351313.951201.62645.22869.96892.301024.07Gap8.509.4910.4410.821.041.091.081.11SDKP10Best691200681980677280672420758000757900758090758110AVE687130.3679407.7672908.3669316.7756100.0756291.0756452.3756337.3Worst684090676750669860667010754400754250754150753730Std. dev1737.151527.541694.791452.26837.73993.511023.711038.86Gap10.2211.2312.0712.541.201.181.161.17Table 4
Comparison of 8 BPSO algorithms on WDKP1–WDKP10.
BPSO1BPSO2BPSO3BPSO4BPSO5BPSO6BPSO7BPSO8WDKP1Best8061979846794867855683086830838308383090AVE80013.779208.478425.378067.982977.383001.482995.083014.1Worst7914378770779527750582783828768286682649Std. dev344.73308.46352.70246.3581.1659.4761.9382.14Gap3.714.685.626.050.150.120.120.10WDKP2Best129590127850126590126010138020138040138060138110AVE128602.7126549.3124836.0124143.0137769.7137740.0137814.3137830.0Worst127680125580123800123260137390137420137430137270Std. dev534.56561.11643.57620.55154.53128.04171.26161.59Gap6.958.449.6810.180.320.340.290.28WDKP3Best243760240740239080237110256120256320256330256360AVE242457.7239491.0236892.0235980.0255743.0255603.0255831.3255778.7Worst241370238570235560235110254750254910254930254850Std. dev661.12581.07749.34481.79330.32377.36351.57325.67Gap5.526.677.698.040.340.390.310.33WDKP4Best296760293210289800288090315040315120315020315040AVE294886.7291169.0287984.7286589.7314392.0314444.7314413.3314340.7Worst293860289950286820285510313470313900313160313360Std. dev660.30638.33728.30541.86360.52318.05423.15471.89Gap6.587.768.779.210.400.380.390.42WDKP5Best402060397880393220392120427390427280427420427390AVE400608.7395759.3391217.7389422.0426337.3426314.7426490.7426349.7Worst398530394270389620387990425140424980425170424950Std. dev909.19915.60995.13928.49570.29569.34507.68640.64Gap6.517.648.709.120.500.510.470.50WDKP6Best432220427900421630419290464810464440464430464040AVE429596.3424036.7419191.3417385.0463214.7463253.3463201.7463228.3Worst428160421740417910416010461760461920462000461980Std. dev1087.141200.48892.42762.16666.55627.89555.16487.82Gap7.829.0110.0510.440.610.600.610.61WDKP7Best506860503130495310494200545820545570545570545270AVE505569.3499531.0493412.7491195.3544327.0544235.3544057.0544006.7Worst503840496860491740489660543130542560542170542140Std. dev786.271319.85847.951281.14620.46884.96783.31779.24Gap7.698.799.9110.310.610.630.660.67WDKP8Best521960515930509890508840574630574580573780574290AVE519367.7513180.0507473.7505650.3572645.7572659.0572513.7572652.7Worst515830510670505790503570571260570240570270571520Std. dev1441.061205.031069.101391.39797.36771.39705.13693.20Gap9.9811.0512.0412.360.750.750.770.75WDKP9Best584160577510571210568630646730647010646690646910AVE580843.3574534.3568415.0566222.3645331.7645445.0645101.0645133.0Worst576840572340566130564130643900643790642660642980Std. dev1659.971273.191136.321116.77811.74901.38900.69923.83Gap10.7311.7012.6412.980.820.800.850.85WDKP10Best592210585730580200578010675100675790675310675460AVE589632.0582542.0576737.3574541.0672859.7673530.0673296.3673135.3Worst586780580160574670572440669350671700671090670990Std. dev1281.471245.801511.331320.041249.331078.37959.271171.04Gap13.1514.2015.0515.380.900.800.830.86Table 5
Comparison of 8 BPSO algorithms on UDKP1–UDKP10.
AlgorithmBPSO1BPSO2BPSO3BPSO4BPSO5BPSO6BPSO7BPSO8UDKP1Best7907077244751137448285728857408572885740AVE77771.075977.274212.673635.385526.185555.085532.285590.0Worst7645474811729287282485193852828502685347Std. dev618.95667.48534.68487.81135.12130.18184.05102.30Gap9.2911.3913.4414.120.250.220.240.17UDKP2Best145300143840138350136930163560163500163630163560AVE143420.3139566.3136063.0134346.3162678.3162878.7163002.0163061.7Worst141530137850134630132520161520161760162360162260Std. dev1032.821243.82741.111018.84466.99399.78304.90314.45Gap12.4114.7716.9117.950.650.530.450.42UDKP3Best236780231160227280224910268270267810268450268430AVE233404.0228742.0224682.7222441.0266421.0266729.3266814.3267008.7Worst231530226860222570220600264740265150264980265560Std. dev1247.531053.301101.781077.08864.86715.80805.32681.78Gap13.3615.0916.6017.431.100.990.960.89UDKP4Best301870295140290750288990345340345110345980346120AVE299048.3292933.7287865.0285816.7343429.7343510.3343958.3343789.0Worst296850290590285580284460341160341330341970341800Std. dev1338.881104.721178.901126.14999.47848.451036.98924.93Gap13.9715.7317.1817.771.201.181.051.10UDKP5Best377980370780363930362700436440437610437610437870AVE374958.3367368.0361415.3358738.3434067.0434640.7435638.0435053.0Worst372200363700358340354560430540431110432930431500Std. dev1687.231465.291430.941788.701415.511410.721362.971572.94Gap15.2917.0118.3518.961.941.811.581.71UDKP6Best460830452640441270439260528730529110528940530600AVE455015.3446125.3438852.3435647.0525352.3525774.0525666.0527004.7Worst451680443210435620432550521500522460519710523880Std. dev2176.801998.821368.331766.471682.211691.982340.591877.81Gap15.2016.8618.2118.812.092.012.031.78UDKP7Best545040537910525410521590624860624300626480627350AVE542066.3531413.7522129.3518659.0620906.0620467.7622543.3621875.3Worst539210527820518860515290616570615210618950617290Std. dev1425.632665.991579.611717.161898.052135.622122.032120.14Gap14.7516.4317.8918.432.352.422.092.20UDKP8Best551650540430532270533240638060638320641500637900AVE546316.3536630.3528103.7524527.7633762.3635553.7635667.3634388.3Worst543810532280524740521420630280630450630150629600Std. dev1938.411996.291807.582466.312124.681784.872357.172121.45Gap15.9817.4718.7819.332.532.252.242.43UDKP9Best594880582140570220565930702810705110704700704350AVE588958.7577306.7566914.3561907.7699517.7699452.3700655.0699156.3Worst584970574490561620558820692160693090694810693320Std. dev2264.911811.951962.561931.902335.852628.182570.033132.54Gap18.0319.6521.1021.802.652.662.492.70UDKP10Best633620619750604900598780763810760920762640767550AVE627361.3612962.3598703.3593618.7756328.3757261.7757706.3756768.3Worst620570608500594060589560751310752420749190749330Std. dev3489.472565.512702.422415.983078.532348.743148.563865.48Gap19.5121.3623.1923.842.972.852.792.91The results show that BPSO7 and BPSO8 have better performance compared to the other six algorithms. Table6 summarizes the average ranks of eight BPSO algorithms on 40 instances. The results showed that BPSO8 achieved the average best rank in all three factors, that is, average best rank (rank based on Best), average mean rank (rank based on AVE), and average worst rank (rank based on Worst). Tables 7–10 summarize the comparison among the FirEGA, SecEGA, and BPSO8 based on the five different performance criteria on 30 independent runs: BEST, AVE, Worst, Std. dev, and Gap. BPSO8 is better than FirEGA and SecEGA in Best, AVE, and Worst for the instances of SDKP, UDKP, and WDKP except for instances of IDKP. The results show that BPSO8 has better performance than FirEGA and SecEGA algorithms. Table 11 summarizes the average ranks of eight BPSO8, FirEGA, and SecEGA algorithms on 40 instances. The results showed that BPSO8 achieved the average best rank in all three factors, that is, average best rank (rank based on Best), the average mean rank (rank based on AVE), and average worst rank (rank based on Worst).Table 6
Average ranks of 8 BPSO algorithms on 40 instances.
IndexAlgorithmAverage best rankAverage mean rankAverage worst rank1BPSO15.05.14.82BPSO26.15.95.33BPSO36.96.75.84BPSO48.07.26.35BPSO52.73.13.46BPSO62.52.63.67BPSO72.53.43.48BPSO82.22.03.5Table 7
Comparison of BPSO8, SecEGA, and FirEGA on IDKP1–IDKP10.
IndexInstanceOPTAlgorithmBestAverageWorstStd. devGap1IDKP170106FirEGA70106700997009070.01SecEGA6866368000673693283.00BPSO86995069761695211090.492IDKP2118268FirEGA118169117869117625102.590.34SecEGA1144341133851123077446.674.13BPSO8118000117418.0117040228.830.723IDKP3234804FirEGA234497233997233666175.420.34SecEGA220096217982216313835.837.16BPSO8234540234253.7233800192.520.234IDKP4282591FirEGA282148280695278881827.630.67SecEGA263238260425258922933.47.84BPSO8281560280953.3280220328.280.585IDKP5335584FirEGA3350043334843296211173.90.63SecEGA309573306878304881907.198.55BPSO8334330333380.7332480479.640.666IDKP6452463FirEGA4516804498634467041161.520.58SecEGA4140904113674087881099.319.08BPSO8451390450455.0448980563.120.447IDKP7489149FirEGA4880094855924763852294.280.73SecEGA4515284443164421331280.319.17BPSO8485920484205.7482400879.021.018IDKP8533841FirEGA5330355299845141962308.110.72SecEGA4904944818314780352215.669.74BPSO8528450526356.75241501268.721.409IDKP9528144FirEGA5264105239825116512216.130.79SecEGA4896614770014718483656.229.68BPSO8522140518834.75154801726.891.7610IDKP10581244FirEGA5789035767725689031905.180.77SecEGA5355415216045164454265.0710.26BPSO8572260569364.75661401446.412.04Table 8
Comparison of BPSO8, SecEGA, and FirEGA on SDKP1–SDKP10
IndexInstanceOPTAlgorithmBestAverageWorstStd. devGap1SDKP194459FirEGA93235931719307042.151.36SecEGA897698883287463594.915.96BPSO89436394181.693897113.740.292SDKP2160805FirEGA15915915900415885961.541.12SecEGA153821152059150753489.395.44BPSO8160570160136.0159780182.330.423SDKP3238248FirEGA23545423524123504379.861.26SecEGA224997223580221918543.386.16BPSO8237370236778.3235960314.480.624SDKP4340027FirEGA336353335963335709122.411.20SecEGA318510315513313747851.147.21BPSO8338240337433.0336210495.980.765SDKP5463033FirEGA4529004475874442551974.993.34SecEGA4202384169644139331291.659.95BPSO8459970458292.0457130802.761.026SDKP6466097FirEGA459254458893458584162.941.55SecEGA4307384273044255041031.128.32BPSO8462650461310.7459880680.641.037SDKP7620446FirEGA5993615922795796733949.034.54SecEGA5612245560835520071926.2610.37BPSO8614830613182.7610700984.831.178SDKP8670697FirEGA661276660104659367426.061.58SecEGA6116446062636037741446.949.61BPSO8665230663681.7661500925.221.059SDKP9739121FirEGA729135727544727064343.671.57SecEGA6748856679006645801614.049.64BPSO8732910730950.37289901024.071.1110SDKP10765317FirEGA756205753394750757985.461.56SecEGA7089356955576919942956.089.12BPSO8758110756337.37537301038.861.17Table 9
Comparison of BPSO8, SecEGA, and FirEGA on WDKP1–WDKP10.
IndexInstanceOPTAlgorithmBestAverageWorstStd. devGap1WDKP183098FirEGA82803826938259252.040.49SecEGA800147902278096473.674.91BPSO88309083014.18264982.140.102WDKP2138215FirEGA13770413758413735663.230.46SecEGA133315132276131337415.624.30BPSO8138110137830.0137270161.590.283WDKP3256616FirEGA254120253657253307173.011.15SecEGA238331235721234025873.588.14BPSO8256360255778.7254850325.670.334WDKP4315657FirEGA313966312849311998484.760.89SecEGA293640290851288764950.067.86BPSO8315040314340.7313360471.890.425WDKP5428490FirEGA426311424548423058798.530.92SecEGA3936173900143879921059.838.98BPSO8427390426349.7424950640.640.506WDKP6466050FirEGA4631854616724577181107.570.94SecEGA4292084251124232691058.378.78BPSO8464040463228.3461980487.820.617WDKP7547683FirEGA5440195419495381261224.681.05SecEGA5015574961344938451230.949.41BPSO8545270544006.7542140779.240.678WDKP8576959FirEGA5734275715595632531495.360.94SecEGA5309715232035203502157.099.32BPSO8574290572652.7571520693.200.759WDKP9650660FirEGA6474776448206300862056.060.90SecEGA5983435867705838542315.59.82BPSO8646910645133.0642980923.830.8510WDKP10678947FirEGA6754526730086682391441.960.88SecEGA6202306062156099643090.8610.72BPSO8675460673135.36709901171.040.86Table 10
Comparison of BPSO8, SecEGA, and FirEGA on UDKP1–UDKP10.
IndexInstanceOPTAlgorithmBestAverageWorstStd. devGap1UDKP185740FirEGA805937910377935690.017.74SecEGA782877680775156798.9510.42BPSO88574085590.085347102.300.172UDKP2163744FirEGA1550391516621498751044.957.38SecEGA148043145548143833883.4311.11BPSO8163560163061.7162260314.450.423UDKP3269393FirEGA2466982408862379801491.9710.58SecEGA2288232254922224861353.5816.30BPSO8268430267008.7265560681.780.894UDKP4347599FirEGA3216053173193144861426.858.71SecEGA3057962999782976061435.4613.70BPSO8346120343789.0341800924.931.105UDKP5442644FirEGA4054093996203953671692.239.72SecEGA3761473708083675741611.7116.23BPSO8437870435053.04315001572.941.716UDKP6536578FirEGA4865564787264740152233.6110.78SecEGA4474384424994388091765.2817.53BPSO8530600527004.75238801877.811.787UDKP7635860FirEGA5681195609485569382441.811.78SecEGA5297535214015184071813.0418.00BPSO8627350621875.36172902120.142.208UDKP8650206FirEGA5901375852865806842078.879.99SecEGA5506455466785438361449.3615.92BPSO8637900634388.36296002121.452.439UDKP9718532FirEGA6551726496366450122023.649.59SecEGA6135816022156058352003.7516.19BPSO8704350699156.36933203132.542.7010UDKP10779460FirEGA7122707065757015452013.439.35SecEGA6654596589086556451723.815.47BPSO8767550756768.37493303865.482.91Table 11
Average ranks of BPSO8, SecEGA, and FirEGA on 40 instances.
IndexAlgorithmAverage best rankAverage mean rankAverage worst rank1FirEGA1.81.31.42SecGA2.92.12.13BPSO81.30.90.9For the stability, the Std. dev and Gap value from Tables2–10 demonstrate the stability of the proposed algorithms. Figure 1 demonstrates the box plot of eight instances. The results showed that the group of algorithms BPSO5–BPSO8 is better than group of algorithms BPSO1–BPSO4. Figure 2 demonstrates the convergence curves of eight instances. The results showed that the group of algorithms BPSO5–BPSO8 has faster convergence than the group of algorithms BPSO1–BPSO4.Figure 1
Box plot of 8 instances: (a) IDKP3, (b) IDKP9, (c) UDKP3, (d) UDKP9, (e) WDKP3, (f) WDKP9, (g) SDKP3, and (h) SDKP9.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 2
Convergence curve of (a) IDKP1, (b) IDKP10, (c) UDKP1, (d) UDKP10, (e) WDKP1, (f) WDKP10, (g) SDKP1, and (h) SDKP10.
(a)(b)(c)(d)(e)(f)(g)(h)Therefore, the performance of BPSO8 is excellent compared to that of BPSOs for the DKP01 problem. From the above comparison, it is not difficult to see that, for the DKP01 problem, the BPSOS has the best performance, followed by BPSO8, and they are far better than FirEGA and SecEGA. This shows that the designed method of binary swarm optimization with a new binary encoding scheme is not only feasible but also effective.


## 5. Conclusion

In this paper, eight new algorithms have been proposed based on the binary particle swarm optimization with a new repair operator to solve discounted 0-1 knapsack problem efficiently. An effective binary encoding scheme is proposed to present the solution to the problem. The new encoding scheme has two advantages, that is, helping reduce the computing effort when using shorter binary vector and also automatically satisfy the constraint that chose the most one item in each group. The simulation results on forty DKP01 instances showed that the proposed algorithms are better than the two algorithms based on genetic algorithm.In the future, I will study the effect of transfer function combined with PSO algorithm for other optimization problems. Many other optimization algorithms are also considered to solve DKP01.



---

*Source: 2864607-2021-04-24.xml*