# List-Based Threshold Accepting Algorithm with Improved Neighbor Operator for 0-1 Knapsack Problem
## 2 Related Work
### 0-1 Kp  
As a constrained optimization problem, dealing with the infeasible solution in the 0-1 KP requires an additional operator. Two the most commonly used methods in the literature are the penalty function and repair operation. The former involves designing a penalty function that assigns a lower fitness value to infeasible solutions, reducing their chance of being included in the next generation [8]. The repair operation is more widely used and typically involves a two-step greedy approach [9]. In step 1, when an infeasible solution is encountered, a greedy drop operator is applied to remove some items according to specific rules until the solution becomes feasible. In step 2, items are added back in until the solution becomes infeasible again. The most commonly used rule is based on profit density, which intuitively suggests that items with higher value and lower weight have a greater change in maximizing the total profits [10]. Algorithms 2 and 3 describe these steps respectively. In Algorithm 2, if the current solution is infeasible, the greedy drop operator checks every item in increasing order of \(v_{i}/w_{i}\) and changes \(x_{i}\) from 1 to 0 so that the lower density item can be removed at the very beginning. On the contrary, in Algorithm 3, the greedy add operator checks the items in descending order of \(v_{i}/w_{i}\) to include the higher profit density item in the first place. ```
Input: An infeasible solution \(\mathbf{x}\), the sorted items \(\mathbf{H}\) Output: A new feasible solution \(\mathbf{x}\)
1\(w=\sum_{i=1}^{n}w_{i}x_{i}\);
2 for\(i=n\) to 1 do
3 if\(x_{\mathbf{H}[i]}=1\) and \(w>c\)then
4\(x_{\mathbf{H}[i]}=0\);
5\(w=w-w_{\mathbf{H}[i]}\);
6
7 end if
8
9 end for
```  
**Algorithm 2**Greedy drop operator  
Early exact algorithms for the 0-1 KP, such as the dynamic programming approach [11], the branch and bound approach [12], and the enumeration approach [13], were designed for small-to-medium instances. As the size of instances increased, these methods failed to tackle the problem within an acceptable timeframe. Therefore, a wide range of metaheuristics have been put forward to tackle large-scale 0-1 KPs. Depending on the inspirational origins, these algorithms can be classified into four major categories: swarm-intelligence (SI)-based, bio-inspired, chemistry-based, and physics-based [14]. In the field of SI, traditional SI algorithms include the genetic algorithm (GA) [15], ant colony optimization (ACO) [16], and particle swarm optimization (PSO) [17]. Recently, a variety of novel SIs have proved to be very efficient in solving the 0-1 KP, such as the spider algorithm (BSSA), monkey algorithm (MA), whale optimization algorithm (WOA), cuckoo search (CS), chicken swarm optimization (CSO), wolf pack algorithm (WPA), and monarch butterfly optimization (MBO). Most of them design a binary version within the general algorithm framework, and use the aforementioned repair operator to fix the infeasible solution. For example, a binary MBO (BMBO) [18] uses real-valued vectors and binary vectors to define search space and solution space separately. In chaotic MBO (CMBO) [19], 12 one-dimensional chaotic maps are utilized to adjust the migration procedures, and a Gaussian mutation operator is imposed on the worst solution to prevent premature convergence. A generalized opposition-based learning (OBL) MBO (OMBO) [20] employs OBL to speed up the convergence. Gaussian perturbation is also included to escape from a local optimum. In the field of bio-inspired algorithms, a modified discrete shuffled frog leaping algorithm (MDSFLA) [21] includes a PSO-like technique and shuffled complex evolution to carry on local search. A binary version of differential evolution (BDE) [22] enriches the exploration and exploitation with four components: capability with the dual representation of solutions, an improved mapping method, enhanced mutation and one-point crossover, and a diversity mechanism.