List-Based Threshold Accepting Algorithm with Improved Neighbor Operator for 0–1 Knapsack Problem

Abstract

The list-based threshold accepting (LBTA) algorithm is a sophisticated local search method that utilizes a threshold list to streamline the parameter tuning process in the traditional threshold accepting (TA) algorithm. This paper proposes an enhanced local search version of the LBTA algorithm specifically tailored for solving the 0–1 knapsack problem (0–1 KP). To maintain a dynamic threshold list, a feasible threshold updating strategy is designed to accept adaptive modifications during the search process. In addition, the algorithm incorporates an improved bit-flip operator designed to generate a neighboring solution with a controlled level of disturbance, thereby fostering exploration within the solution space. Each trial solution produced by this operator undergoes a repair phase using a hybrid greedy repair operator that incorporates both density-based and value-based add operator to facilitate optimization. The LBTA algorithm’s performance was evaluated against several state-of-the-art metaheuristic approaches on a series of large-scale instances. The simulation results demonstrate that the LBTA algorithm outperforms or is competitive with other leading metaheuristics in the field.

1. Introduction

The list-based threshold accepting (LBTA) algorithm [1] falls under the category of threshold accepting (TA) algorithms [2]. In a manner analogous to simulated annealing (SA), LBTA accepts suboptimal solutions to prevent being trapped in local optima. Instead of setting to a fixed temperature, LBTA utilizes an adaptive threshold list that is updated iteratively based on the search space topology. This allows LBTA to achieve better results with fewer tuning parameters compared with SA and other local search methods. Owing to its flexibility, LBTA is effectively utilized in solving both combinatorial and continuous optimization problems, such as the vehicle routing problem (VRP) and its variants [3], the job shop scheduling problem (JSSP) [4], the zero-wait scheduling problem [5], and the traveling salesman problem (TSP) [6].

The 0–1 KP, which is recognized as a classic NP-hard problem in combinatorial optimization, has practical applications in various decision-making domains [7]. The problem involves a collection of n items, labeled from 1 to n; each item has a weight $w_i$ and a value $v_i$, as well as a maximum capacity c for the knapsack. The aim is to maximize the sum of the values of the items in the knapsack while making sure that the sum of the weights does not surpass the knapsack’s capacity, as follows (see Equation (1)):

$$\begin{array}{c}maxf\left(x\right)=\sum _{i=1}^n{v}_i{x}_i\\ s.t.\sum _{i=1}^n{w}_i{x}_i\le c\wedge x_i\in \left\{\begin{array}{c}0,1\end{array}\right\}\end{array}$$

(1)

where $x_i$ represents the number of items i included into the knapsack, and $f\left(x\right)$ is the target function.

Aiming to fill the gap in the literature, this paper introduces a binary LBTA designed for tackling the 0–1 KP. The proposed algorithm features a feasible threshold list that effectively narrows the search space, alongside a hybrid greedy repair operator that surpasses traditional density-based operator regarding optimization and convergence. Moreover, a bit-flip mutation operator is employed to generate trial solutions, which provides an elastic local search area and a sufficient perturbation to escape local minimum. Extensive experimental evaluations demonstrate the efficacy and competitiveness of the LBTA algorithm, with comparative results on two large 0–1 KP instances highlighting its advantages.

The remainder of this paper is structured as follows: Section 2 offers a brief introduction of the basic LBTA algorithm, the 0–1 KP, and algorithms for the 0–1 KP. Section 3 presents the proposed LBTA algorithm, while Section 4 analyzes its behavior. In Section 5, the performance of the LBTA algorithm is compared with other state-of-the-art metaheuristics. Finally, Section 6 summarizes the findings of this study and outlines potential avenues for future research.

2. Related Work

2.1. List-Based Threshold Algorithm

LBTA is a random search algorithm that explores the solution space by employing a neighborhood search strategy. It allows the acceptance of suboptimal candidate solutions based on a predefined threshold value. As an extension of the TA metaheuristic, LBTA maintains a unique list of threshold values that decrease over the process of the iteration. This enables the algorithm to balance diversification and intensification without the need for an additional intervention or parameter configuration. The procedure consists of two main components: the initialization and updating of the threshold value list and a local search process.

2.1.1. Initialize the List of Threshold Values

During the first stage, an initial list of threshold values is generated through a particular local search method. The procedure then begins with the following steps: (i) selecting a neighboring solution ${\mathbf{s}}^{\prime }$ from a present solution $\mathbf{s}$ by applying a local search move and (ii) calculating and normalizing the changing in the fitness function as follows:

$$T=|f\left({\mathbf{s}}^{\prime }\right)-f\left(\mathbf{s}\right)|/f\left(\mathbf{s}\right)$$

(2)

The newly generated threshold T is continually added to the list until it reaches its maximum length, which is controlled solely by the parameter L, representing the length of the list. In the initial phase, the local search procedure gathers information from the search space, while the normalization procedure helps to ensure a gradual decrease in the threshold values for the following iteration.

2.1.2. Iteration of the Algorithm

During the second stage, the iteration begins by generating a neighboring solution s’ from the initial randomized solution s using a local search move. This moving strategy may be the same one adopted in the initialization, or  a new method may be used. If the solution s’ is better than the original s, then s is updated with s’, or  a new threshold value T is generated using Equation (2). If T is less than the current largest threshold value $T_{max}$, s’ is accepted as the new solution, and T replaces $T_{max}$ and enters the list. Otherwise, s’ is abandoned, and the algorithm proceeds with the original solution s in the next iteration. This process is repeated until a stopping condition is satisfied.

2.1.3. Conservation of Threshold Strategy

In [1], to facilitate the ability to break free from local minima and enhance the chance of obtaining a better solution, this algorithm employs a strategy to save the threshold. This involves keeping the values in the list sufficiently high by periodically updating the list with the maximum normalized threshold values discovered within a predefined number of feasible moves. This delay factor helps to slow down the adaptation of list values and avoid premature convergence to suboptimal solutions.

2.1.4. Pseudocode of LBTA

The pseudocode of LBTA is shown in Algorithm 1. We assume that the problem solved here is a maximization optimization problem that is consistent with the 0–1 KP. The algorithm is composed of two parts: initialization and iteration. In the initialization phase, a preliminary list of threshold values is established through a specific local search method, where L represents the length of the list. In the iteration phase, the algorithm generates a new solution by performing a local search move and updates the current solution and threshold list based on an acceptance criterion. The iteration continues until the maximum number of iterations G is achieved.

Algorithm 1: List-based threshold accepting algorithm

2.2. 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.  

Algorithm 2: Greedy drop operator

Algorithm 3: Greedy add 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.

In terms of chemistry-based methods, a binary chemical reaction optimization (CRO) framework is commonly applied for the 0–1 KP [8,23]. In the field of physics-based algorithms, a series of improved harmony search (HS) algorithms have emerged. A CS algorithm with global HS (CSGHS) [24] combines the exploration of global HS and the exploitation of CS to address the 0–1 KP. Good performance is obtained by comparing CS, SFLA, and DE in terms of search accuracy and convergence speed. A simplified binary HS (SBHS) [25] utilizes the distinctions among harmonies to generate new solutions and dynamically modifies the harmony memory consideration rate with the size of the dimension. An improved HS (IHS) [26] employs a feasible parameter-tuning way to generate new solution vectors so as to improve the correctness and convergence. A global-best HS (GHS) [27] adjusts the pitch-adjustment step through a global best harmony and adds a social dimension so that the solution can use the global best and local best information at the same time. Self-adaptive HS (SAHS) [28] uses harmony memory to automatically adjust parameters. A low-discrepancy sequence is exploited to the traditional pseudo-random initialization of the harmony memory. A list-based SA (LBSA) replaces the traditional temperature-based descent method with a practical list to manage the convergence pattern [29]. In our algorithm, we included a bit-flip mutation operator that generates trial solutions, which has been shown to offer an effective search space. Additionally, the noising method (NM) is another variant of SA. NM with six variants of NMs for the 0–1 KP has been proposed to address the 0–1 KP. These variants include two noise strategies, two noise variations of objective solutions, and two decreasing strategies [30]. Both LBSA and NM algorithms incorporate a hybrid greedy optimization operator that combines a density-based operator and a value-based operator, which has been proved to enhance algorithm performance. Therefore, we have also adopted this hybrid operator in our algorithm as a replacement for the traditional single optimization operator to improve the effectiveness of the algorithm.

Furthermore, in recent years, many novel algorithms have emerged to handle these problems, such as the reptile search algorithm (RSA) [31], binary slime mould algorithm (BSMA) [32], binary Archimedes optimization algorithm (BAOA), binary tunicate swarm algorithm (BTSA) [33], binary Harris Hawks optimization (BHHO) [34], binary marine predators algorithm (BMPA) [35], and binary elephant herding optimization (BinEHO) [36]. These algorithms have demonstrated significant potential in addressing complicated optimization problems due to their ability to effectively explore large search spaces and locate near-optimal solutions. We also include these algorithms and make a comparison with them in Section 5 to show the competitiveness of our proposed algorithm.

3. LBTA Algorithm with Enhanced Local Search for 0–1 KP

In this study, we introduce a novel version of the LBTA algorithm to tackle the 0–1 KP. The main framework can be summarized as follows: Initially, we redefine the solution representation for the 0–1 KP. Subsequently, we devise a rule for generating the threshold list, which adapts based on the evolving search landscape, thus enabling a more efficient exploration of the solution space. Following this, a bit-flip mutation operator is utilized to generate a diverse set of candidate solutions. These candidates are then refined using a hybrid greedy optimization operator, which employs both value-based and density-based strategies to repair and optimize the quality of the solutions.

3.1. Solution Representation

The solution for the 0–1 KP is represented by an object $\mathbf{s}$ with three attributes: $\mathbf{s}.\mathbf{x}$, $\mathbf{s}.v$, and $\mathbf{s}.w$. The n-bit binary array $\mathbf{s}.\mathbf{x}$ is generated randomly from [0, 1], where $\mathbf{s}.x_i=1$ indicates that the corresponding item is included in the knapsack. $\mathbf{s}.v$ represents the overall value of items in the knapsack, while $\mathbf{s}.w$ represents the overall weight of the items in the knapsack.

3.2. The Initialization and Update of Threshold List

The threshold list is an essential part in the LBTA, which is responsible for providing a flexible search space. In the traditional LBTA, the list is generated through stochastic local search, and the threshold values are normalized and stored in the list. In our proposed approach, we adopt a simpler and more efficient method: randomly selecting item values and inserting them into the list until the list is full, without the need to calculate fitness values.

To achieve a thorough and delicate search with a uniformly descending threshold list, we modify the basic framework of LBTA by utilizing a Markov chain to perform a series of local search, similar to SA. During each inner iteration, the decision to accept a worse solution is based on the current maximum value in the threshold list $T_{max}$. If the worst solution is adopted, the difference between the current solution and the candidate solution is accumulated, and the number of acceptance times is recorded. After completing the local search, we replace $T_{max}$ with the average of cumulative differences. This approach provides a flexible threshold list that enables a border search space, occasional upward moves that promote escaping from local maximum points at the beginning, and a decreasing list of threshold values that lead to a thorough search and eventually reach the global maximum.

3.3. Improved Neighbor Operator

Apart from the threshold list, another crucial part of LBTA is the local search strategy. An effective strategy should be powerful enough to help the algorithm to break away from the attraction of the current solution while also being gentle enough to avoid becoming a stochastic local search. In particular, for the 0–1 KP, changing only one item at a time would result in a weak perturbation, leading to slow convergence, while changing too many items would result in a blind search. To address these issues, a feasible bit-flip mutation operator is proposed. During each local search, we randomly select items to include or exclude from the backpack. Two parameters, namely, $FT$ and $DT$, are used to control the amount flipping and dropping times, respectively. Algorithm 4 outlines the process. Within the flipping number of $FT$, a random item index i is selected. If the current item has not been included yet, we flip $\mathbf{s}.x_i$ from 0 to 1. Alternatively, if the current dropping number is less than $DT$, we exclude the item by setting $\mathbf{s}.x_i$ from 1 to 0. The maximum flipping and dropping times are satisfied by iterating until the limits are reached.

Algorithm 4: A bit-flip mutation operator

3.4. Hybrid Greedy Repair and Optimized Operator

A traditional greedy repair operator only utilizes the profit density as the sole metric to determine the priority of item selection. One of the drawbacks of this approach is that it is challenging for high-value and high-weight items to be selected, which may lead to a local minimum. To solve this problem, we design a hybrid method that combines the greedy repair operator with an optimizing operator that considers both density and value. The hybrid approach involves two arrays, HD and HV, which keeps items organized in descending order based on the density of $v_i/w_i$ and the value of $v_i$, respectively. During the first stage, we use only HD to drop items with lower density first. In the optimizing process, an additional parameter p is introduced to determine which array is used to invoke the greedy drop and greedy add operator (see Algorithm 5). The reason for dropping items using only HD is to preserve as much beneficial information as possible. If we choose the hybrid arrays, items possessing a higher value tend to be removed more often, and these items would need to be re-added during the optimization process, which would be a waste of iterations.   

Algorithm 5: Hybrid greedy optimization operator

3.5. The Framework of the LBTA Algorithm for 0–1 KP

The framework of the LBTA algorithm is presented in Algorithm 6. Start with initializing the threshold list; a primary solution is generated randomly, repaired, and optimized using the hybrid greedy operator. In the inner iteration, a candidate solution ${\mathbf{s}}^{\prime }$ is generated using the bit-flip mutation operator. If ${\mathbf{s}}^{\prime }$ is better than $\mathbf{s}$, or if the deviation between ${\mathbf{s}}^{\prime }.v$ and $\mathbf{s}.v$ is less than $-T_{max}$, $\mathbf{s}$ is replaced with ${\mathbf{s}}^{\prime }$. After the number of local search iterations meets the Markov chain length, the current maximum threshold value is replaced with the average of the accumulation of deviation. The algorithm then starts a new local search until the global iteration limit is reached.   

Algorithm 6: The framework of LBTA

4. Behaviors Analysis

In this section, we present a series of experiments conducted to analyze the behavior of the LBTA algorithm. The experiments were performed on three sets of large 0–1 knapsack instances presented in [20]. These instances are classified by three types based on their features, as shown in

Table 1. Characteristics of three categories of large-scale 0–1 KP instances.

Correlation	Weight ${\mathit{w}}_{\mathit{i}}$	Value ${\mathit{v}}_{\mathit{i}}$	Capacity c
Uncorrelated	rand (10, 100)	rand (10, 100)	0.75 * sum of weights
Weakly correlated	rand (10, 100)	rand ($w_i-$ 10, $w_i$ + 10)	0.75 * sum of weights
Strongly correlated	rand (10, 100)	$w_i$ + 10	0.75 * sum of weights

. Each group consists of five instances of the 0–1 knapsack problem, along with the instance name; the number of items in each instance and the best solution for each instance are listed in Table 2. The optimal values are emphasized in bold. Instances KP01–KP05 represent uncorrelated cases, KP06–KP10 represent weakly correlated cases, and KP11–KP15 represent strongly correlated cases. The experiments were run on an Intel Core i7 CPU and an 8 GB RAM, using Java implementation, and each instance was run independently 50 times.

4.1. Parameters Settings

To validate the behavior of LBTA, we divided the parameters into two groups. The first group consisted of parameters for the basic LBTA framework, which included the number of generations G, the Markov chain length M, and the threshold list length L. The second group consisted of parameters for the local search, which included the probability p of the hybrid repair operator, the number of flipping times $FT$, and the number of dropping times $DT$. The total number of fitness evaluations was fixed at $G\ast M$ = 40,000.

In the preliminary experiments, we determined the parameter values in the initial LBTA framework. For the other parameters, we set $p=1$, $FT=1$, and $DT=1$ to ensure that these parameters did not cause interference. Specifically, we tried five values (50, 100, 200, 400, and 800) for G and ten values from 10 to 100 with 10 increments for L. We found that $G=800$, $M=50$, $L=10$, and $p=0.2$ were suitable for LBTA to achieve good performance.

4.2. Performance Tuning for the Feasible Bit-Flip Operator

To determine an appropriate combination for the number of bit flips, we conducted tests across a range of values for $FT$ and $DT$. We recorded the number of functions that achieved a 100% success rate for each iteration, as most of these combinations were able to produce optimal results for the majority of instances. However, when $FT=1$ and $DT=1$, none of the functions were able to achieve the optimal result with a 100% success rate. Therefore, we adjusted the values to set $FT$ from 10 to 80 with 10 increments and $DT$ from 0 to 5 with 1 increment.

When an item is excluded from the knapsack, it still has the chance to be re-included. However, if $DT$ is the same value as $FT$, numerous items may be repeatedly included and excluded, leading to unnecessary iteration. Thus, we aim to fill up the knapsack as quickly as possible while also introducing local disturbance. This is why we set $DT$ to be much lower than $FT$.

The histograms in Figure 1 depict the simulation results for the different combinations of $FT$ and $DT$. From these histograms, we obtained the following results: (1) For $FT$, there is an insignificant difference between 15 functions. When $FT$ equals 40, 50, 70, and 80, 14 of 15 functions achieve a 100% success rate, while for $FT$ equal to 30 and 60, 13 of 15 functions obtain a 100% success rate. For the remaining values, 12 of 15 functions reach a 100% success rate. (2) For $DT$, there is a significant difference between six values. When $DT=1$, all $FT$ values were able to produce the best results. (3) In general, the value of $FT$ should not be too large to avoid random search. Based on the simulation results, we selected $FT=40$, $DT=1$ for the following simulations.

Table 2. Comparison of the LBTA algorithm on the first set of 15 instances.

			HGGA (2020)					NM (2021)					CMBO (2018)					LBTA
Instance	BKV		Best	Mean	Worst	SD		Best	Mean	Worst	SD		Best	Mean	Worst	SD		Best	Mean	Worst	SD
KP01	40,686		40,686	40,685.00	40,685	6.00 × ${10}^{-2}$		40,685	40,684.88	40,684	2.20 × ${10}^{-1}$		40,686	40,683.00	40,683	7.10 × ${10}^{-1}$		40,686	40,685.07	40,685	2.46 × ${10}^{-3}$
KP02	50,592		50,592	50,592.00	50,592	0.00		50,592	50,592.00	50,592	0.00		50,592	50,590.00	50,590	4.90 × ${10}^{-1}$		50,592	50,592.00	50,592	0.00
KP03	61,846		61,846	61,845.90	61,845	3.70 × ${10}^{-1}$		61,846	61,845.32	61,845	4.40 × ${10}^{-1}$		61,845	61,841.00	61,840	1.38		61,846	61,845.33	61,845	1.62 × ${10}^{-3}$
KP04	77,033		77,033	77,033.00	77,033	0.00		77,033	77,032.92	77,032	1.50 × ${10}^{-1}$		77,033	77,031.00	77,031	3.10 × ${10}^{-1}$		77,033	77,032.77	77,032	1.30 × ${10}^{-3}$
KP05	102,316		102,316	102,315.99	102,3165	2.00 × ${10}^{-2}$		102,316	102,316.00	102,316	0.00		102,316	102,314.00	102,313	1.11		102,316	102,315.53	102,314	1.96 × ${10}^{-3}$
KP06	35,069		35,069	35,069.00	35,069	0.00		35,069	35,069.00	35,069	0.00		35,069	35,067	35,064	1.47		35,069	35,069.00	35,069	0.00
KP07	43,786		43,786	43,786.00	43,786	0.00		43,786	43,785.96	43,785	8.00 × ${10}^{-2}$		43,786	43,784.00	43,781	1.34		43,786	43,786.00	43786	0.00
KP08	53,553		53,553	53,552.48	53,552	5.00 × ${10}^{-1}$		53,553	53,552.02	53,552	4.00 × ${10}^{-2}$		53,552	53,552.00	53,552	0.00		53,553	53,552.10	53,552	1.87 × ${10}^{-3}$
KP09	65,710		65,710	65,709.11	65,709	2.00 × ${10}^{-1}$		65,709	65,709.00	65,709	0.00		65,710	65,709.00	65,708	5.80 × ${10}^{-1}$		65,710	65,709.13	65,709	1.52 × ${10}^{-3}$
KP10	118,200		118,200	118,200.00	118,200	0.00		108,200	108,200.00	108,200	0.00		108,200	108,200.00	108,200	0.00		118,200	118,200.00	118,200	0.00
KP11	40,167		40,167	40,167.00	40,167	0.00		40,167	40,167.00	40,167	0.00		40,167	40,167.00	40,166	1.40 × ${10}^{-1}$		40,167	40,167.00	40,167	0.00
KP12	49,443		49,443	49,443.00	49,443	0.00		49,443	49,443.00	49,443	0.00		49,433	49,432.00	49,433	2.49		49,443	49,443.00	49,443	0.00
KP13	60,640		60,640	60,640.00	60,640	0.00		60,640	60,640.00	60,640	0.00		60,640	60,640.00	60,639	1.40 × ${10}^{-1}$		60,640	60,640.00	60,640	0.00
KP14	74,932		74,932	74,932.00	74,932	0.00		74,932	74,932.00	74,932	0.00		74,932	74,932.00	74,931	2.70 × ${10}^{-1}$		74,932	74,932.00	74932	0.00
KP15	99,683		99,683	99,683.00	99,683	0.00		99,683	99,683.00	99,683	0.00		99,683	99,682.00	99,672	2.23		99,683	99,683.00	99,683	0.00
order			15	12	14	10		13	9	12	10		13	1	2	2		15	11	13	11
rank			1					3					3					1

Table 2. Comparison of the LBTA algorithm on the first set of 15 instances.

			HGGA (2020)					NM (2021)					CMBO (2018)					LBTA
Instance	BKV		Best	Mean	Worst	SD		Best	Mean	Worst	SD		Best	Mean	Worst	SD		Best	Mean	Worst	SD
KP01	40,686		40,686	40,685.00	40,685	6.00 × ${10}^{-2}$		40,685	40,684.88	40,684	2.20 × ${10}^{-1}$		40,686	40,683.00	40,683	7.10 × ${10}^{-1}$		40,686	40,685.07	40,685	2.46 × ${10}^{-3}$
KP02	50,592		50,592	50,592.00	50,592	0.00		50,592	50,592.00	50,592	0.00		50,592	50,590.00	50,590	4.90 × ${10}^{-1}$		50,592	50,592.00	50,592	0.00
KP03	61,846		61,846	61,845.90	61,845	3.70 × ${10}^{-1}$		61,846	61,845.32	61,845	4.40 × ${10}^{-1}$		61,845	61,841.00	61,840	1.38		61,846	61,845.33	61,845	1.62 × ${10}^{-3}$
KP04	77,033		77,033	77,033.00	77,033	0.00		77,033	77,032.92	77,032	1.50 × ${10}^{-1}$		77,033	77,031.00	77,031	3.10 × ${10}^{-1}$		77,033	77,032.77	77,032	1.30 × ${10}^{-3}$
KP05	102,316		102,316	102,315.99	102,3165	2.00 × ${10}^{-2}$		102,316	102,316.00	102,316	0.00		102,316	102,314.00	102,313	1.11		102,316	102,315.53	102,314	1.96 × ${10}^{-3}$
KP06	35,069		35,069	35,069.00	35,069	0.00		35,069	35,069.00	35,069	0.00		35,069	35,067	35,064	1.47		35,069	35,069.00	35,069	0.00
KP07	43,786		43,786	43,786.00	43,786	0.00		43,786	43,785.96	43,785	8.00 × ${10}^{-2}$		43,786	43,784.00	43,781	1.34		43,786	43,786.00	43786	0.00
KP08	53,553		53,553	53,552.48	53,552	5.00 × ${10}^{-1}$		53,553	53,552.02	53,552	4.00 × ${10}^{-2}$		53,552	53,552.00	53,552	0.00		53,553	53,552.10	53,552	1.87 × ${10}^{-3}$
KP09	65,710		65,710	65,709.11	65,709	2.00 × ${10}^{-1}$		65,709	65,709.00	65,709	0.00		65,710	65,709.00	65,708	5.80 × ${10}^{-1}$		65,710	65,709.13	65,709	1.52 × ${10}^{-3}$
KP10	118,200		118,200	118,200.00	118,200	0.00		108,200	108,200.00	108,200	0.00		108,200	108,200.00	108,200	0.00		118,200	118,200.00	118,200	0.00
KP11	40,167		40,167	40,167.00	40,167	0.00		40,167	40,167.00	40,167	0.00		40,167	40,167.00	40,166	1.40 × ${10}^{-1}$		40,167	40,167.00	40,167	0.00
KP12	49,443		49,443	49,443.00	49,443	0.00		49,443	49,443.00	49,443	0.00		49,433	49,432.00	49,433	2.49		49,443	49,443.00	49,443	0.00
KP13	60,640		60,640	60,640.00	60,640	0.00		60,640	60,640.00	60,640	0.00		60,640	60,640.00	60,639	1.40 × ${10}^{-1}$		60,640	60,640.00	60,640	0.00
KP14	74,932		74,932	74,932.00	74,932	0.00		74,932	74,932.00	74,932	0.00		74,932	74,932.00	74,931	2.70 × ${10}^{-1}$		74,932	74,932.00	74932	0.00
KP15	99,683		99,683	99,683.00	99,683	0.00		99,683	99,683.00	99,683	0.00		99,683	99,682.00	99,672	2.23		99,683	99,683.00	99,683	0.00
order			15	12	14	10		13	9	12	10		13	1	2	2		15	11	13	11
rank			1					3					3					1

5. Competitiveness of the LBTA Algorithm

To access the competitive performance of the LBTA algorithm, we reviewed a broad range of references and selected two widely used benchmark sets from recent studies. The first set comprises three types of 0–1 KPs, as described in the previous section. The second set, more frequently used in recent references, was sourced from [25] and included instances with sizes ranging from 100 to 6400. The results were directly obtained from the original literature. In all experiments, the maximum number of generations was set to 40,000, and each instance was evaluated using 50 independent experiments. The performances of various algorithms were assessed using the best, worst, average, and standard deviation (SD) of the solution values. The optimal values are emphasized in bold.

5.1. Competitiveness of the LBTA Algorithm on the First Set of Instances

In this subsection, the performance of LBTA was evaluated against three state-of-the-art metaheuristics: CMBO algorithm [19], NMs [30], and HGGA [37]. The comparisons are presented in Table 2. The results show that HGGA and LBTA outperform NMs and CMBO. Regarding the best solution, the two algorithms yield comparable results. NMs failed to obtain the best solution for KP01 and KP09, while CMBO did not find the best solution for KP03 and KP08. Only HGGA and LBTA were successful in obtaining the best solution for every instance. Regarding the worst, mean solution, and SD, HGGA and LBTA also outperformed the other two algorithms.

5.2. Competitiveness of the LBTA Algorithm on the Second Set of Instances

First, we made a comparison on 25 small instances where the size varied between 8 and 24. Details of these 25 KPs were obtained from David Pisinger’s research [38]. To evaluate the effectiveness and accuracy of LBTA, it is assessed in relation to recent studies, including BEO [35], BinEHO [36], BMPA [39], BinRSA [31], BSMA [32], BHHO [34], BTSA [33], and BAOA [40]. In

Table 3. Comparison of LBTA on the second set of 18 large-scale instances.

Problem						BEO (2020)			BinEHO (2020)			BMPA (2021)			BinRSA (2023)			BSMA (2021)			BHHO (2019)			BTSA (2020)			BAOA (2021)			LBTA
No.		Instance		BKV		Mean	Gap (%)		Mean	Gap (%)		Mean	Gap (%)		Mean	Gap (%)		Mean	Gap (%)		Mean	Gap (%)		Mean	Gap (%)		Mean	Gap (%)		Mean	Gap (%)
P1		KP_8a		3,924,400		3,924,400.00	0.00		3,924,400.00	0.00		3,924,400.00	0.00		3,924,400.00	0.00		3,924,400.00	0.00		3,924,400.00	0.00		3,924,400.00	0.00		3,924,400.00	0.00		3,924,400.00	0.00
P2		KP_8b		3,813,669		3,813,669.00	0.00		3,813,669.00	0.00		3,813,669.00	0.00		3,813,669.00	0.00		3,813,669.00	0.00		3,813,669.00	0.00		3,801,149.00	3.28 × ${10}^{-1}$		3,810,772.00	7.60 × ${10}^{-2}$		3,813,669.00	0.00
P3		KP_8c		3,347,452		3,347,452.00	0.00		3,347,452.00	0.00		3,347,452.00	0.00		3,347,452.00	0.00		3,347,452.00	0.00		3,347,452.00	0.00		3,347,452.00	0.00		3,347,452.00	0.00		3,347,452.00	0.00
P4		KP_8d		4,187,707		4,187,707.00	0.00		4,187,707.00	0.00		4,187,707.00	0.00		4,187,707.00	0.00		4,187,707.00	0.00		4,187,707.00	0.00		4,187,707.00	0.00		4,187,707.00	0.00		4,187,707.00	0.00
P5		KP_8e		4,955,555		4,955,555.00	0.00		4,955,555.00	0.00		4,955,555.00	0.00		4,955,555.00	0.00		4,955,555.00	0.00		4,955,555.00	0.00		4,955,555.00	0.00		4,955,555.00	0.00		4,955,555.00	0.00
P6		KP_12a		5,688,887		5,688,887.00	0.00		5,688,757.34	2.28 × ${10}^{-3}$		5,688,887.00	0.00		5,688,757.34	2.28 × ${10}^{-3}$		5,688,887.00	0.00		5,688,887.00	0.00		5,682,416.00	1.14 × ${10}^{-1}$		5,688,887.00	0.00		5,688,887.00	0.00
P7		KP_12b		6,498,597		6,498,597.00	0.00		6,498,597.00	0.00		6,498,597.00	0.00		6,498,597.00	0.00		6,498,597.00	0.00		6,496,784.00	2.79 × ${10}^{-2}$		6,498,597.00	0.00		6,498,597.00	0.00		6,498,597.00	0.00
P8		KP_12c		5,170,626		5,170,626.00	0.00		5,170,626.00	0.00		5,170,626.00	0.00		5,170,626.00	0.00		5,170,626.00	0.00		5,170,626.00	0.00		5,170,626.00	0.00		5,170,626.00	0.00		5,170,626.00	0.00
P9		KP_12d		6,992,404		6,992,404.00	0.00		6,992,404.00	0.00		6,992,404.00	0.00		6,992,404.00	0.00		6,941,564.00	7.27 × ${10}^{-1}$		6,941,564.00	7.27 × ${10}^{-1}$		6,941,564.00	7.27 × ${10}^{-1}$		6,939,908.00	7.51 × ${10}^{-1}$		6,992,404.00	0.00
P10		KP_12e		5,337,472		5,337,472.00	0.00		5,337,472.00	0.00		5,337,472.00	0.00		5,337,472.00	0.00		5,337,472.00	0.00		5,337,472.00	0.00		5,337,472.00	0.00		5,337,472.00	0.00		5,337,472.00	0.00
P11		KP_16a		7,850,983		7,850,983.00	0.00		7,850,224.60	9.66 × ${10}^{-3}$		7,850,983.00	0.00		7,850,983.00	0.00		7,850,983.00	0.00		7,850,983.00	0.00		7,831,459.00	2.49 × ${10}^{-1}$		7,850,983.00	0.00		7,850,983.00	0.00
P12		KP_16b		9,352,998		9,352,998.00	0.00		9,352,998.00	0.00		9,352,998.00	0.00		9,352,998.00	0.00		9,352,998.00	0.00		9,352,998.00	0.00		9,332,841.00	2.16 × ${10}^{-1}$		9,352,998.00	0.00		9,352,998.00	0.00
P13		KP_16c		9,151,147		9,151,147.00	0.00		9,151,147.00	0.00		9,151,147.00	0.00		9,151,147.00	0.00		9,151,147.00	0.00		9,140,752.50	1.14 × ${10}^{-1}$		9,151,147.00	0.00		9,145,012.50	6.70 × ${10}^{-2}$		9,151,147.00	0.00
P14		KP_16d		9,348,889		9,348,889.00	0.00		9,345,961.48	3.13 × ${10}^{-2}$		9,348,889.00	0.00		9,348,889.00	0.00		9,348,889.00	0.00		9,348,889.00	0.00		9,348,889.00	0.00		9,348,889.00	0.00		9,348,889.00	0.00
P15		KP_16e		7,769,117		7,769,117.00	0.00		7,766,509.36	3.36 × ${10}^{-2}$		7,769,117.00	0.00		7,769,117.00	0.00		7,769,117.00	0.00		7,769,117.00	0.00		7,762,520.00	8.49 × ${10}^{-2}$		7,769,117.00	0.00		7,769,117.00	0.00
P16		KP_20a		10,727,049		10,727,049.00	0.00		10,727,049.00	0.00		10,727,049.00	0.00		10,727,049.00	0.00		10,727,049.00	0.00		10,727,049.00	0.00		10,727,049.00	0.00		10,716,101.00	1.02 × ${10}^{-1}$		10,727,049.00	0.00
P17		KP_20b		9,818,261		9,818,261.00	0.00		9,818,261.00	0.00		9,818,261.00	0.00		9,818,261.00	0.00		9,818,261.00	0.00		9,818,261.00	0.00		9,814,002.00	4.34 × ${10}^{-2}$		9,818,261.00	0.00		9,818,261.00	0.00
P18		KP_20c		10,714,023		10,714,023.00	0.00		10,713,587.70	4.06 × ${10}^{-3}$		10,714,023.00	0.00		10,713,993.98	2.71 × ${10}^{-4}$		10,714,023.00	0.00		10,713,149.00	8.16 × ${10}^{-3}$		10,714,023.00	0.00		10,714,023.00	0.00		10,714,023.00	0.00
P19		KP_20d		8,929,156		8,929,156.00	0.00		8,929,156.00	0.00		8,929,156.00	0.00		8,928,880.80	3.08 × ${10}^{-3}$		8,929,156.00	0.00		8,924,769.30	4.91 × ${10}^{-2}$		8,929,156.00	0.00		8,927,679.40	1.65 × ${10}^{-2}$		8,929,156.00	0.00
P20		KP_20e		9,357,969		9,357,969.00	0.00		9,357,751.44	2.32 × ${10}^{-3}$		9,357,969.00	0.00		9,357,953.46	1.66 × ${10}^{-4}$		9,357,969.00	0.00		9,357,969.00	0.00		9,357,969.00	0.00		9,357,969.00	0.00		9,357,969.00	0.00
P21		KP_24a		13,549,094		13,549,094.00	0.00		13,546,986.14	1.56 × ${10}^{-2}$		13,549,094.00	0.00		13,549,094.00	0.00		13,549,094.00	0.00		13,546,249.00	2.10 × ${10}^{-2}$		13,549,094.00	0.00		13,547,058.00	1.50 × ${10}^{-2}$		13,549,094.00	0.00
P22		KP_24b		12,233,713		12,233,713.00	0.00		12,233,713.00	0.00		12,233,713.00	0.00		12,233,713.00	0.00		12,233,713.00	0.00		12,233,713.00	0.00		12,233,713.00	0.00		12,233,713.00	0.00		12,233,713.00	0.00
P23		KP_24c		12,448,780		12,448,780.00	0.00		12,448,780.00	0.00		12,448,780.00	0.00		12,448,780.00	0.00		12,448,780.00	0.00		12,448,780.00	0.00		12,448,780.00	0.00		12,448,780.00	0.00		12,448,780.00	0.00
P24		KP_24d		11,815,315		11,814,367.00	8.02 × ${10}^{-3}$		11,810,682.68	3.92 × ${10}^{-2}$		11,811,630.20	3.12 × ${10}^{-2}$		11,814,367.48	8.02 × ${10}^{-3}$		11,815,315.00	0.00		11,814,208.00	9.37 × ${10}^{-3}$		11,814,108.00	1.02 × ${10}^{-2}$		11,814,072.00	1.05 × ${10}^{-2}$		11,815,315.00	0.00
P25		KP_24e		13,940,099		13,940,099.00	0.00		13,940,099.00	0.00		13,940,099.00	0.00		13,940,099.00	0.00		13,940,099.00	0.00		13,933,743.00	4.56 × ${10}^{-2}$		13,940,099.00	0.00		13,938,971.00	8.09 × ${10}^{-3}$		13,940,099.00	0.00
order						24			17			24			20			24			17			17			17			25
rank						2			9			4			5			3			7			8			6			1

, the average results and gap values of each algorithms are provided. The proposed method demonstrates superior or equal performance compared with other algorithms across all 25 problems, as indicated by the gap results. Notably, LBSA outperforms all competing algorithms, achieving the best solution in 100% of the instances. While algorithms such as BMPA, BSMA, and BEO also obtain the best solution in 100% of the 24 instances, their performance falls slightly short of LBSA on specific problems—BMPA and BEO on the P24 instance and BSMA on the P9 instance. Additionally, although BinRSA achieves the best average in 20 instances, and BinEHO, BHHO, BTSA, and BAOA secure the best results in 17 out of 25 instances, none match the consistent and optimal performance of LBSA across all test cases.

Furthermore, the LBTA algorithm was evaluated on large-scale instances from David Pisinger’s optimization codes [41]. The datasets used in this study fall into three different categories: datasets 1–6 are high dimensional uncorrelated, datasets 7–12 are high dimensional weakly correlated, and datasets 13–18 are high dimensional strongly correlated. In

Table 4. Comparison of LBTA on the second set of 25 instances.

			IGA-SA (2019)			BinRSA (2023)			BSMA (2021)			BTSA (2020)			BAOA (2021)			BHHO (2019)			LBTA
Instance	BKV		Mean	Gap (%)		Mean	Gap (%)		Mean	Gap (%)		Mean	Gap (%)		Mean	Gap (%)		Mean	Gap (%)		Mean	Gap (%)
KP1_100	9147		8575.00	6.25		9147.00	0.00		9147.00	0.00		9147.00	0.00		9147.00	0.00		9147.00	0.00		9147.00	0.00
KP1_200	11,238		8576.00	23.69		11,238.00	0.00		11,238.00	0.00		11,238.00	0.00		11,238.00	0.00		11,238.00	0.00		11,238.00	0.00
KP1_500	28,857		12,072.00	58.17		28,857.00	0.00		28,857.00	0.00		28,849.00	0.03		28,852.00	0.02		28,850.00	0.02		28,857.00	0.00
KP1_1000	54,503		14,563.00	73.28		54,503.00	0.00		54,503.00	0.00		53,301.00	2.21		53,574.00	1.70		53,396.00	2.03		54,503.00	0.00
KP1_2000	110,625		27,645.00	75.01		110,587.55	0.03		110,625.00	0.00		95,619.00	13.56		110,625.00	0.00		110,625.00	0.00		110,615.40	0.01
KP1_5000	276,457		49,306.00	82.17		276453.6	0.00		274,569.00	0.68		272,923.00	1.28		274,385.00	0.75		273,961.00	0.90		276,438.47	0.01
KP2_100	1514		1217.00	19.62		1514.00	0.00		1514.00	0.00		1514.00	0.00		1514.00	0.00		1514.00	0.00		1514.00	0.00
KP2_200	1634		1347.00	17.56		1634.00	0.00		1634.00	0.00		1634.00	0.00		1634.00	0.00		1634.00	0.00		1634.00	0.00
KP2_500	4566		3038.00	33.46		4557.5	0.19		4565.30	0.02		4537.20	0.63		4549.40	0.36		4518.70	1.04		4565.30	0.02
KP2_1000	9052		5435.00	39.96		9051.05	0.01		9052.00	0.00		8346.80	7.79		9052.00	0.00		8835.60	2.39		9052.00	0.00
KP2_2000	18,051		10,938.00	39.41		18,046.75	0.02		17,557.00	2.74		14,902.00	17.45		15,885.00	12.00		15,729.00	12.86		18,050.20	0.00
KP2_5000	44,356		27,387.00	38.26		44,353.15	0.01		44,312.00	0.10		42,972.00	3.12		44,206.00	0.34		43,276.00	2.43		44,352.83	0.01
KP3_100	2397		1481.00	38.21		2397.00	0.00		2397.00	0.00		2395.20	0.08		2396.50	0.02		2396.40	0.03		2397.00	0.00
KP3_200	2697		1495.00	44.57		2697.00	0.00		2697.00	0.00		2692.10	0.18		2695.10	0.07		2694.70	0.09		2697.00	0.00
KP3_500	7117		3412.00	52.06		7117.00	0.00		7117.00	0.00		6999.50	1.65		7117.00	0.00		7117.00	0.00		7117.00	0.00
KP3_1000	14,390		5589.00	61.16		14,390.00	0.00		14,390.00	0.00		14,191.00	1.38		14,279.00	0.77		14,225.00	1.15		14,390.00	0.00
KP3_2000	28,919		10,818.00	62.59		28,919.00	0.00		28,919.00	0.00		28,919.00	0.00		28,597.00	1.11		28,657.00	0.91		28,919.00	0.00
KP3_5000	72,505		27,304.00	62.34		72,505.00	0.00		72,075.00	0.59		71,018.00	2.05		71,579.00	1.28		71,826.00	0.94		72,487.83	0.02
order			0			14			13			5			7			6			14
rank			7			3			2			6			4			5			1

, a comparison of the performance of the LBTA algorithm with that of IGA-SA [42], BinRSA [31], BSMA [32], BTSA [33], BAOA [40], and BHHO [34] is presented. The results, as shown in Table 4, demonstrate that LBSA performs similarly as or better than other algorithms in 14 out of 18 problems according to the mean results, matching or exceeding the number of optimal solutions obtained by the other algorithms. While the BinRSA algorithm achieves the same number of optimal solutions, our proposed LBTA ranks first overall when all algorithms are considered, with BinRSA ranking third behind BSMA. The results clearly show that LBTA performs only slightly worse than BinRSA in the KP1_5000, KP2_5000, and KP3_5000 instances, and its performance in the KP1_2000 instance is marginally worse than those of BSMA, BAOA, and BHHO. However, LBTA outperforms all algorithms in the median items for the KP2_500 instance and matches the best value achieved by other algorithms in 13 other instances.

In conclusion, the LBTA algorithm demonstrated strong performance across multiple large-scale instances, particularly on high-dimensional weakly correlated and strongly correlated datasets, showcasing its robust competitiveness. Although it performed slightly less effectively than certain algorithms on a few specific instances, it ranked first overall, proving the effectiveness and robustness of the LBTA algorithm in solving 0–1 KPs.

6. Conclusions

This paper presents an enhanced local search algorithm, LBTA, tailored to effectively address the 0–1 knapsack problem (KP). The LBTA algorithm employs several key mechanisms to improve the performance in both solution quality and computational efficiency. By incorporating a feasible threshold list, this algorithm is able to regulate convergence speed, ensuring that the search process balances between intensification and diversification. The integration of a bit-flip mutation operator further strengthens the exploration capabilities, enabling a more comprehensive search for the solution space and reducing the likelihood of premature convergence. Moreover, the algorithm incorporates a hybrid repair operator that merges value-based and density-based greedy strategies. This hybrid operator enhances the quality of candidate solutions by guiding the search towards more optimal areas of the solution space. Through this combination of strategies, LBTA demonstrates its capability to provide high-quality solutions for the 0–1 knapsack problem while maintaining simplicity in its implementation.

The LBTA algorithm’s performance has been systematically tested on two large instances of the 0–1 KP, and its results have been compared with those of several cutting-edge metaheuristics found in the existing literature. The outcomes of these simulations reveal that LBTA is not only straightforward to implement but also exhibits remarkable efficiency in solving the 0–1 knapsack problem. A limitation observed in the initial testing instances indicates that the performance of LBTA is slightly less stable compared with those of other algorithms, which may be attributed to the random flip mutation operator used during the neighborhood search. While this operation introduces search diversity, it may also lead to a degree of blind searching. Consequently, in our next steps, we plan to integrate all operators with a status feedback mechanism. This approach will allow for the adaptive selection of operators, each serving distinct purposes, based on the current evolutionary status, thereby facilitating a more balanced and effective search. Additionally, we aim to expand the LBTA algorithm to address more complicated and practical real-world optimization problems, further enhancing its applicability and effectiveness in various domains.