Modeling and Solving the Knapsack Problem with a Multi-Objective Equilibrium Optimizer Algorithm Based on Weighted Congestion Distance

Abstract

The knapsack problem is a typical bi-objective combinatorial optimization issue, wherein maximizing the value of the packed items is achieved concurrently with minimizing the weight of the load. Due to the conflicting objectives of the knapsack problem and the typical discrete property of the items involved, swarm intelligence algorithms are commonly employed. The diversity of optimal combinations in the knapsack problem has become a focal point, which involves finding multiple packing solutions at the same value and weight. For this purpose, this paper proposes a Multi-Objective Equilibrium Optimizer Algorithm based on Weighted Congestion Distance (MOEO_WCD). The algorithm employs a non-dominated sorting method to find a set of Pareto front solutions rather than a single optimal solution, offering multiple decision-making options based on the varying needs of the decision-makers. Additionally, MOEO_WCD improves the balance pool generation mechanism and incorporates a weighted congestion incentive, emphasizing the diversity of packing combination solutions under the objectives of value and weight to explore more Pareto front solutions. Considering the discrete characteristics of the knapsack combination optimization problem, our algorithm also incorporates appropriate discrete constraint handling. This paper designs multiple sets of multi-objective knapsack combinatorial optimization problems based on the number of knapsacks, the number of items, and the weights and values of the items. This article compares five algorithms suitable for solving multi-objective problems: MODE, MO-PSO-MM, MO-Ring-PSO-SCD, NSGA-II, and DN-NSGAII. In order to evaluate the performance of the algorithm, this paper proposes a new solution set coverage index for evaluation. We also used the hypervolume indicator to evaluate the diversity of algorithms. The results show that our MOEO-WCD algorithm achieves optimal coverage of the reference composite Pareto front in the decision space of four knapsack problems. The experimental results indicate that our MOEO_WCD algorithm achieves the optimal coverage of the reference composite Pareto front in the decision space for four sets of knapsack problems. Although our MOEO_WCD algorithm covers less of the composite front in the objective space compared with the MODE algorithm for knapsack problem 1, its coverage of the integrated reference solutions in the decision space is greater than that of the MODE algorithm. The experiments demonstrate the superior performance of the MOEO_WCD algorithm on bi-objective knapsack combinatorial optimization problem instances, which provides an important solution to the search for diversity in multi-objective combinatorial optimization solutions.

1. Introduction

The classic bi-objective knapsack problem involves selecting a subset of items from a given set to place into a knapsack with the aim of maximizing value while minimizing weight [1]. The key challenge of the problem is how to select the optimal items from a limited set under the constraint of knapsack capacity to achieve those objectives. The knapsack problem has widespread applications in real life, such as in logistics transportation, warehouse management, and resource allocation [1].

Traditional methods for solving the knapsack problem primarily include dynamic programming and greedy algorithms, each of which has its own advantages and limitations. Dynamic programming is a commonly used method for solving the knapsack problem, but it can lead to excessive memory consumption for its space complexity, especially when dealing with large-scale problems [2]. Greedy algorithms, due to their strategy of selecting locally optimal solutions, cannot guarantee achieving the global optimum [3]. Traditional methods for solving such problems are relatively complex, requiring the introduction of more sophisticated algorithms or transformations of the problem.

At present, swarm intelligence algorithms have been applied to find the optimal knapsack solution [4]. They, with strong global search capabilities, can explore the solution space from multiple directions simultaneously, allowing them to adapt to changes in dynamic environments [5]. This characteristic is key to solving the dynamic search aspect of the knapsack problem. The algorithms can relatively easily adapt to the changes in the packaging process. For different types of knapsack problems, suitable swarm intelligence algorithms can be selected [4], or packing strategies can be optimized. Abdellah Rezoug et al. used a heuristic genetic algorithm (GA) to solve the multidimensional knapsack problem, employing an efficiency-based approach to perform a pre-analysis of the problem data in order to extract useful information. This prior knowledge was integrated into the genetic algorithm as a guide in two phases: the generation of the initial population and the evaluation of the offspring through the fitness function. This approach improved the efficiency and accuracy of the algorithm; however, the computational complexity of the genetic algorithm is high, requiring a significant amount of time when solving large-scale problems [6]. Young-Bin Shin et al. utilized an improved particle swarm optimization (PSO) algorithm to solve the two-dimensional knapsack problem, enhancing the convergence speed and solution quality by adjusting the particles’ velocity and position. However, they found the PSO algorithm tended to get trapped in local optima when handling high-dimensional and complex knapsack problems. And it was noted that the choice of parameters significantly affects the results [7]. Min Kong et al. proposed an ant colony optimization (ACO) algorithm to solve the knapsack problem. To prevent premature convergence, their algorithm ACO incorporated pheromone reinitialization and adopted different pheromone reinforcement strategies based on the convergence state of the algorithm. However, the algorithm requires a long computation time in the initial phase and performs poorly when handling dynamic knapsack problems [8]. Ravneil Nand et al. used the Firefly Algorithm (FA) to solve the multidimensional knapsack problem, improving solution stability and accuracy by leveraging the characteristics of firefly flashing behavior and genetic evolution. During the study, it was found that the FA algorithm incurs high computational time and memory consumption when handling large-scale knapsack problems [9].

As the research progressed, it gradually gained more attention to find more solutions to multi-objective knapsack problems. This paper proposed an improved Equilibrium Optimizer, MOEO_WCD, to explore the Pareto frontier with more solutions to the multi-objective knapsack combinatorial optimization problems.

Section 2 of this paper provides an overview of the current research on the knapsack problem. Section 3 details the framework of the MOEO_WCD algorithm proposed in this study, the multi-objective knapsack combinatorial optimization problems addressed, and the objective functions used in the algorithm. Section 4 presents the experimental results of applying the MOEO_WCD algorithm to the knapsack combinatorial optimization problem. Finally, Section 6 provides a comprehensive discussion of the results and implications of this study.

2. Related Work

The Pareto frontier is an important indicator for the study of the diversity of solutions of intelligent algorithms in multi-objective problems [10]. Imen Ben Mansour et al. evaluated the quality of solutions by measuring the size of the region dominated by the obtained Pareto front using the hypervolume difference indicator. The larger the hypervolume value, the better the quality of the obtained non-dominated set. Additionally, the Mann–Whitney non-parametric statistical test was employed to examine whether the differences between algorithms were statistically significant. Using these methods, the performance of different algorithms is compared with determine which algorithm performs better in solving specific problem instances [11]. Van Veldhuizen et al. evaluated the quality of solution sets by calculating the distance between the solution sets obtained by the algorithm and the known or theoretical Pareto front. Common metrics include GD (Generational Distance) and IGD (Inverted Generational Distance) [12]. Deb, Kalyanmoy et al. evaluated the diversity of solutions by assessing whether the distribution of the solution set in the objective space is uniform. Common metrics used for this evaluation include Spread, Spacing, and Entropy [13]. These methods provide different perspectives and criteria for evaluating multi-objective optimization algorithms, helping researchers objectively analyze and compare the performance of various algorithms in solving different problems.

Due to the powerful global search capability and adaptability to dynamic environments of multi-objective swarm intelligence algorithms, their application in solving multi-objective problems offers significant advantages [14]. The NSGA-II algorithm proposed by Kalyanmoy Deb et al. has demonstrated its effectiveness in multi-objective optimization problems, with a primary focus on efficiently finding a balanced Pareto front in a continuous solution space to simultaneously optimize multiple objective functions [13]. Xin-She Yang et al. found that the Firefly Algorithm (FA) has high search efficiency and solution diversity, making it suitable for solving nonlinear and multimodal optimization problems. However, it has higher computational time and memory consumption, and its performance can be unstable on noisy datasets, being susceptible to the influence of the initial population [15]. Christian Blum et al. found that the Ant Colony Optimization (ACO) algorithm performs exceptionally well in solving discrete combinatorial optimization problems, demonstrating strong robustness and adaptability. However, it has high computational complexity, slow convergence in the initial stages, and unstable performance when dealing with dynamic environments [16].

When using swarm intelligence algorithms to solve the knapsack problem, the algorithm needs to be appropriately modified according to the specific characteristics of the knapsack problem to find more and better solutions. In order to seek solution set diversity for the multi-objective knapsack problem, Mahrach et al. compared multi-objective algorithms and single-objective algorithms. The performance of the multi-objective algorithms was evaluated primarily based on the diversity and convergence of the Pareto front solutions. In addressing the knapsack problem and the traveling salesman problem, it was found that MOEAs focus on finding a set of Pareto front solutions rather than a single optimal solution. Furthermore, the introduction of diversity maintenance mechanisms effectively prevents the trap of local optima, enabling efficient search while maintaining solution set diversity [17]. However, the authors only focused on the basic 0/1 knapsack problem, lacking exploration of more complex knapsack problems. To enhance the effectiveness of solutions in the discrete space of the knapsack problem, Djaafar Zouache et al. proposed a new cooperative swarm intelligence algorithm (MOFPA). This algorithm combines the Firefly Algorithm (FA) and Particle Swarm Optimization (PSO), using dominance relations to manage the size of the external archive, ensuring the convergence and diversity of the Pareto optimal solution set. Additionally, a tanh transfer function was introduced to map the continuous search space of FA and PSO into a discrete search space. This discretization method ensures the adaptability and diversity of the algorithm in the discrete solution space of the knapsack problem. However, maintaining population diversity remains a challenge. If the population loses diversity too early, the algorithm may become trapped in local optima, preventing it from finding the global optimal solution [18]. To ensure the uniformity of the distribution of the solution set in the entire target space and the diversity of the algorithm, Deb et al. introduced the calculation method of crowding distance, drawing on the non-dominated sorting and crowding distance mechanisms of NSGA-II, to maintain the diversity of the solution set [19]. To maintain algorithm diversity, Herández Castellanos et al. proposed the NEDEA algorithm, which introduces a non-epsilon dominance mechanism. The algorithm exhibits better diversity and convergence when dealing with approximate solution sets and high-dimensional multi-objective optimization problems, improving the quality and applicability of the solution set [20]. To further improve the uniformity and extensiveness of the solution set distribution and ensure effective convergence of the solution set to the Pareto front, Zhanguo Li et al. proposed a MOEA method based on a clustering mechanism. This approach utilizes clustering techniques to calculate and maintain the distribution and diversity of the solution set. The fuzzy C-means clustering algorithm was used to cluster individuals, and LMOEA was applied to solve the classic multi-objective knapsack problem. Convergence and diversity metrics were used to evaluate the algorithm’s performance. Compared with the classic NSGA-II and MOEA/D, this algorithm achieved significant improvements in both convergence and population diversity. Although the algorithm enhanced population diversity through the clustering mechanism, maintaining diversity remains a challenge when the problem size is large, potentially leading to uneven solution distribution or local convergence issues [21].

As research on solving the knapsack problem using swarm intelligence algorithms deepens, researchers have found that when the solution space for the multi-objective knapsack combinatorial optimization problem is discrete, the search process in the discrete solution space is not as smooth as in the continuous solution space. Consequently, finding high-quality or near-optimal solutions may become more challenging. At the same time, the core challenge of multi-objective optimization lies in the conflict between objectives, where optimizing one objective can lead to a decline in the performance of other objectives. This trade-off between objectives makes it difficult to find a solution that optimizes all objectives simultaneously. In multi-objective optimization, it is not only necessary to find solutions close to the Pareto front but also to ensure that these solutions are well-distributed in the objective space, i.e., maintain diversity.

For the bi-objective knapsack combinatorial optimization problem focusing on value and weight, this study proposes a multi-objective equilibrium optimizer algorithm based on weighted crowding distance (MOEO_WCD). The Bonferroni–Dunnand Holm’s tests for all functions showed that EO is significantly a better algorithm than PSO, GWO, GA, GSA, SSA, and CMA-ES, while its performance is statistically similar to SHADE and LSHADE-SPACMA [22]. Therefore, this paper is an improvement based on the equilibrium optimizer algorithm, utilizing non-dominated sorting to divide solutions into different Pareto fronts, aiming to find a Pareto optimal solution set that represents trade-offs between different objectives. Based on this, the algorithm adjusts its optimization characteristics by setting the crowding distance weights. Additionally, the algorithm improves the balanced pool random concentration generation mechanism and utilizes a weighted crowding distance mechanism to preserve the found solution set, optimizing the population diversity of the algorithm. At the same time, by applying discrete constraints to the population, the algorithm can adapt to solving multi-objective packing and combination optimization problems. In this study, nine sets of simulation experiments were conducted on the multi-objective packing and combination optimization problem. The results of each set of problems under the nine packing scenarios were integrated to form a composite Pareto front. The coverage of the composite Pareto front in the decision space was compared across different algorithms, including MODE, MO-PSO-MM, MO-PSO-Ring-SCD, NSGAII, and DN-NSGAII, along with the coverage of each algorithm’s Pareto front in the objective space [13,23,24,25]. The results show that the proposed algorithm demonstrates certain advantages in solving bi-objective packing and combination optimization problems, providing a new approach for solving such problems.

3. Multi-Objective Knapsack Combination Optimization Problem

The mathematical formulation of the multi-objective knapsack combinatorial optimization problem can be expressed as follows: Given N items and M knapsacks, each item i has two attributes, weight $v_i$ and value $w_i$. The total weight in knapsack m is ($W_m$), and the total value is ($V_m$). The objective is to select a set of items to place into multiple knapsacks without exceeding the weight limit of each knapsack, such that the total value $(V)$ of the M knapsacks is maximized and the total weight $(W)$ is minimized.

$${(W}_m)=\sum _{i=1}^{N_m}{w}_i,\hspace{1em}m=1,2,\cdots ,M.$$

(1)

The total weight $W_m$ of the $l_m$ items loaded into knapsack m, where $l_m\in$ [0, N].

$${(V}_m)=\sum _{i=1}^{N_m}{v}_i.$$

(2)

The total value $V_m$ of the $l_m$ items loaded into knapsack m.

$$(W)=\sum _{m=1}^M{(W}_m)=(W_1)+(W_2)+\cdots +(W_m).$$

(3)

The total weight $W$ of the items loaded into M knapsacks,

$$(V)=\sum _{m=1}^M{(V}_m)=(V_1)+{(V}_2)+\cdots +{(V}_m).$$

(4)

The total value $V$ of the items loaded into M knapsacks.

$$L=\sum _{m=1}^M{N}_m.$$

(5)

where L ≤ N.

3.1. Objective Functions

In this paper, the objective functions of the bi-objective combinatorial optimization problem are mathematically expressed, where $x$ represents the decision variable and $x_{im}$ denotes that item i is placed in knapsack m. Subject to the knapsack weight constraints, the objective is to maximize the packing value $f_V\left(x\right)$ and minimize the packing weight $f_W\left(x\right)$, where N is the number of items, ${weight}_i$ is the weight of item i, and ${value}_i$ is the value of item i.

Objective 1: Sum the weights of the items within each corresponding knapsack and compute the total weight of the packed items across all knapsacks.

$$\min f_W\left(x\right)=\sum _{m=1}^M\sum _{i=1}^{N_m}{|x}_{im}|w_i,$$

(6)

$$x_{im}=m,$$

(7)

$${|x}_{im}|=\left\{\begin{array}{c}1, x_{im}>0\\ 0, x_{im}=0.\end{array}\right.$$

(8)

Here, $x_{im}$ indicates that item i is placed in knapsack m, representing that item i is packed into knapsack m. When ${|x}_{im}|$ = 0, it indicates that item i is not included in the knapsack and its weight is not considered. When $x_{im}=$ 1, it indicates that item i is included in knapsack m, and its weight is added to the knapsack’s total weight.

Objective 2: Sum the values of the items within each knapsack and then aggregate the values across all knapsacks to calculate the total value of the packing scheme.

$$\max f_V\left(x\right)=\sum _{m=1}^M\sum _{i=1}^{N_m}{|x}_{im}| v_i.$$

(9)

3.2. Constraint Condition

The constraints in this paper require that the packing scheme must not exceed the capacity of each knapsack. The constraint is expressed by the formula,

$$\left(W_m\right)\le W_m.$$

(10)

In the formula, $W_m$ represents the maximum packing weight of knapsack m. $\left(W_m\right)$ represents the weight of the items in knapsack m.

3.3. Evaluation Metric

Due to the difficulty in obtaining the true Pareto front for multi-objective packing problems, this paper constructs a composite Pareto set ($composite PS$) to objectively and effectively evaluate the capability of the algorithm in finding solutions. This set integrates all solutions obtained from the swarm intelligence algorithms used in this study, with duplicate solutions removed. An evaluation metric, ${ps}_{cover}$ is proposed, which represents the ratio of the solutions found by the swarm intelligence algorithm ${ps}_{algorithm}$, to the composite Pareto set ($composite PS$), in order to measure the algorithm’s capability in identifying the Pareto front solutions.

$${ps}_{cover}={\displaystyle \frac{{ps}_{algorithm}}{composite PS}}\times 100\mathrm{\%}.$$

(11)

As shown in Figure 1, the black pentagram represents the $composite PS$, the blue circles indicate the Pareto front solutions found by algorithm 1, and the red circles denote the Pareto front solutions found by algorithm 2. The figure clearly illustrates the coverage of the composite Pareto front by algorithms 1 and 2.

4. Multi-Objective Knapsack Combination Optimization Based on MOEO-WCD Algorithm

4.1. Equilibrium Optimizer

The Equilibrium Optimizer (EO) is an optimization algorithm inspired by the physical phenomenon of controlled mass balance within a control volume. The algorithm principle is shown in Figure 2, which is primarily a physics-inspired heuristic algorithm based on the strong mixing dynamics of mass balance in a control volume. The mass balance equation reflects the physical processes of mass entering, leaving, and being generated within the control volume. The EO algorithm demonstrates fast and accurate optimization performance in single-objective continuous solution space problems. However, when faced with the demands of multi-objective optimization, the algorithm falls short of meeting those requirements. In Figure 3, the overall flowchart of the EO algorithm is shown.

4.2. MOEO-WCD Algorithm Process

Due to the fast and accurate optimization performance of the Equilibrium Optimizer (EO) algorithm in single-objective optimization problems, the algorithm is designed primarily for single-objective tasks. To address multi-objective problems while leveraging the advantages of EO, this paper proposes a multi-objective Equilibrium Optimizer algorithm based on weighted crowding distance (MOEO_WCD). In Figure 4, for the multi-objective knapsack combination optimization problem, we introduced a non-dominated sorting method to rank and classify the solution set based on the trade-offs between the objectives of knapsack weight and knapsack value. This allows for the identification and preservation of the Pareto front for the multi-objective optimization problem. We also introduced a random concentration generation strategy to enhance the diversity of the solutions obtained by the algorithm. Additionally, a weighted crowding distance was incorporated, allowing the adjustment of crowding distance weights in the decision space and objective space to meet the search requirements at different stages, thereby improving the adaptability of the algorithm.

At the same time, the algorithm design accommodates the discrete nature of the knapsack problem. MOEO_WCD ensures that the discrete population is not disrupted during the update process.

4.3. Random Concentration Knapsack Generation Mechanism in Equilibrium Pool

In solving the knapsack problem, this mechanism enhances the diversity of the obtained solutions, meaning that multiple decision solutions correspond to the same position on the Pareto front. In other words, it enables finding multiple distinct knapsack solutions that achieve the same packing objective result.

To balance exploration and exploitation capabilities and enhance diversity in both the decision space and objective space—meaning that multiple distinct knapsack solutions can be found for the same packing objective result—adaptive generation of individual vectors is employed. MOEO_WCD introduces a balanced pool random concentration generation mechanism. By using three different random concentration generation mechanisms, the EO-balanced pool particles are diversified, laying the foundation for solution diversity.

Strategy 1: Randomly select five neighbors from the entire population as the concentration.

$$C_{eq,pool}=\left\{C_{neighbour1,}{C}_{neighbour2,}{C}_{neighbour3,}{C_{neighbour4,}{C}_{neighbour5,}C}_{eqave}\right\}$$

(12)

where the concentration C_eqave is the average value of three neighboring solutions:

$$C_{eqave}={\displaystyle \frac{C_{neighbour1,}{C}_{neighbour2,}{C}_{neighbour3}{C}_{neighbour4,}{C}_{neighbour5}}{5}}.$$

(13)

Strategy 2: To enhance the exploration capability of the algorithm, select solutions that are farther apart in the decision space. This can increase population diversity and help avoid local optima. Based on the Manhattan distance between the current individual and the remaining solutions in the population, select a certain number of neighbors. Then, from the selected neighbors, randomly choose five concentrations, and select the neighbor with the maximum crowding distance in the decision space as the concentration:

$$C_{eq,pool}=\left\{C_{DMneighbour1,}{C}_{DMneighbour2,}{C}_{DMneighbour3,}{C_{DMneighbour3,}{C}_{DMneighbour4,}{C}_{DMneighbour5,}C}_{eqave}\right\}$$

(14)

where DMneighbour represents the Manhattan distance in the decision space, and the concentration C_eqave is the average value of four neighboring solutions:

$$C_{eqave}={\displaystyle \frac{C_{DMneighbour1,}{C}_{DMneighbour2,}{C}_{DMneighbour3,}{C}_{DMneighbour4,}{C}_{DMneighbour5}}{5}}.$$

(15)

Strategy 3: To enhance the global search capability of the algorithm and enable a broader search across different regions to find better solutions, select a certain number of neighbors based on the Manhattan distance between the current individual and the remaining solutions in the population within the objective space. Then, from the selected neighbors, randomly choose five concentrations, and select the concentrations with the maximum crowding distance in the objective space to enter the balanced pool. Under the corresponding strategy, the solutions are placed into the concentration pool for algorithm iteration.

$$C_{eq,pool}=\left\{C_{OMneighbour1,}{C}_{OMneighbour2,}{C}_{OMneighbour3,}{C}_{OMneighbour4,}{C}_{OMneighbour5,}{C}_{eqave}\right\}$$

(16)

where OMneighbour represents the Manhattan distance in the objective space, and C_eqave represents the concentration:

$$C_{eqave}={\displaystyle \frac{C_{OMneighbour1,}{C}_{OMneighbour2,}{C}_{OMneighbour3,}{C}_{OMneighbour4,}{C}_{OMneighbour5}}{5}}.$$

(17)

Calculate the distances in the decision space and objective space using Manhattan distance according to the formulas, and sort them in descending order.

$$Dist=\sum _{k=1}^n\left|\left|x_{1k}-x_{2k}\right|\right|.$$

(18)

4.4. Weighted Crowding Distance

In the process of solving the multi-objective knapsack combination optimization problem with the MOEO_WCD algorithm, due to the varying performance of multi-objective optimization at different stages, the algorithm is required to have strong search performance in the early stages and to focus on local search and solution development in the later stages. The weighted crowding distance mechanism is employed to meet the optimization needs at different stages of multi-objective optimization.

The first step in calculating the weighted crowding distance is to perform a dominance sorting of the population. Given a population of $N$ individuals, each individual is compared with others based on their objective values. If individual $i$ is not worse than individual $j$ on all objectives and is strictly better than $j$ on at least one objective, then individual $i$ dominates individual $j$. Establish a dominant relationship through a set of comparisons across all objectives.

$$\forall k\in \left\{1,2,\dots ,n_{obj}\right\}:\left\{\begin{array}{l}{dom}_k\left(i,j\right)=1, if f_k\left(i\right)\le f_k\left(j\right)\\ {dom}_k\left(i,j\right)=0, else. \end{array}\right.$$

(19)

where $f_k\left(i\right)$ represents the k-th objective value of individual $i$.

Based on this dominance relation, individuals are classified into different fronts. Individuals in the first front are not dominated by any other individuals; those in the second front are only dominated by individuals in the first front, and so on, until all individuals are assigned to a front.

The crowding distance of individual $i$ in the objective space can be expressed as:

$$D_{crowd,i}=\sum _{k=1}^{n_{obj}}{f}_k\left({neighbor}_1\left(i\right)\right)-f_k\left({neighbor}_2\left(i\right)\right)$$

(20)

where ${neighbor}_1\left(i\right)$ and ${neighbor}_2\left(i\right)$ represent the nearest neighbors of individual $i$ in the objective space.

Compute the crowding distance in the decision space to capture the diversity of solutions in the decision space. It measures the average distance of an individual to its $k$ nearest neighbors in the decision space. The crowding distance of individual $i$ in the decision space can be expressed as:

$$D_{crowd,i}^{decision}={\displaystyle \frac{1}{k}}\sum _{j=1}^{k}d\left(i,{neighbor}_j\left(i\right)\right)$$

(21)

where $d(i,j)$ represents the Euclidean distance between individual $i$ and individual $j$ in the decision space, and ${neighbor}_j\left(i\right)$ denotes the $j$-th nearest neighbor of individual $i$.

To leverage the advantages of crowding distance in both the objective space and the decision space, this paper introduces a weighted crowding distance. The weighted crowding distance is computed as a linear combination of the crowding distances in the objective space and the decision space:

$${WCD}_{crowd,i}^{decision}=\alpha ·D_{crowd,i}+\left(1-\alpha \right)·D_{crowd,i}^{decision}$$

(22)

where $\alpha$ is a weight parameter that balances the contributions of the crowding distances in the objective space and the decision space. In multi-objective evolutionary optimization algorithms, an effective method is needed to measure the crowding degree among individuals in order to achieve convergence to the Pareto optimal front while maintaining diversity of the solutions. By adjusting the parameter $\alpha$, the trade-off between the two can be flexibly controlled, thereby effectively managing the solution set. As $\alpha$ approaches 1, the importance of the crowding distance in the objective space increases; conversely, as $\alpha$ approaches 0, the importance of the crowding distance in the decision space increases. This method not only maintains the diversity of the solution set but also effectively guides the search process to converge to the Pareto optimal front.

4.5. Discretization of Solution Space

In the EO algorithm optimization process, individual updates convert discrete individuals into continuous ones. Since in the knapsack optimization problem, knapsack indices cannot be fractional, the updated population needs to be discretized.

$$x=round\left(x\right),$$

(23)

$$\left\{\begin{array}{c}x=ub,x>ub\\ x=lb,x<lb.\end{array}\right.$$

(24)

where $x$ represents the population individuals, $ub$ denotes the upper bound of the population, with its value depending on the number of knapsacks M, and $lb$ represents the lower bound of the population.

In Figure 5, rows represent the first decision scheme, i.e., a solution. Figure 5a shows the population updated to floating-point numbers after mutation operations. Figure 5b illustrates the population after constraint handling, where the green areas indicate the parts that require constraints and the decision variables after constraint processing.

The pseudocode of the MOEO_WCD in Algorithm 1 is as follows:

Algorithm 1. MOEO_WCD
Input: Population size $NP$; maximum number of iterations $Max\_iter$; individual value range of the population lb, ub
Output: Best individual $\overrightarrow{x}$; fitness of $\overrightarrow{x}$
1	Initialize the particle population ${\overrightarrow{x}}_i^D,i=\mathrm{0,1},\dots ,NP$, $iter=1,2,\dots ,Max\_iter$
2	Initializes the control parameters ${a_1=1,a}_2=1,GP=0.5$
3	While $iter<Max\_iter$
4	Calculate the contemporary weighted congestion distance weight $\beta$
	# Calculate the crowding distance weight
5	For $i=1:NP$
6	Calculate ${\overrightarrow{x}}_i$ fitness
7	Calculate ${\overrightarrow{x}}_i$ decision space distance
	# Calculate the distance in the decision space
8	Calculate ${\overrightarrow{x}}_i$ object space distance
	#Calculate the distance in the objective space
9	End for
10	Identify three particles based on a random concentration strategy
11	Calculate ${\overrightarrow{x}}_{ave}$ particles
12	Construct the equilibrium pool by Formula (14)
13	Calculate $t$
14	For $i=1:NP$
15	Randomly choose one candidate from the equilibrium pool
	# Random concentration selection strategy
16	Generate randomly vector $\overrightarrow{\lambda }$
17	Generate $\overrightarrow{F}$, $\overrightarrow{GCP}$, ${\overrightarrow{G}}_0$, $\overrightarrow{G}$
18	Update particle population
19	End(for)
20	$\overrightarrow{x}$ = round ($\overrightarrow{x}$)  # Discretization of solutions in the decision space
31	$iter=iter+1$
32	End while

5. Experiment

5.1. Experimental Setup

• Comparative algorithms: MODE, MO_PSO_MM, MO_Ring_PSO_SCD, NSGA-II, DN_NSGA-II, and MOEO_WCD;
• Number of runs: 50 independent runs;
• Population size NP: 400;
• Maximum number of evaluations (Max_FES): 10,000.

The performance of different algorithms is compared using the above evaluation metrics, where a higher metric value indicates better performance.

The population initialization in this paper uses knapsack numbers. The initialization matrix has columns representing item numbers and rows representing individuals, i.e., packing solutions. The initial population size is set to 400. For each algorithm, 50 independent experiments are conducted, with each experiment iterated 10,000 times. The upper bound for the population of individuals is set based on the number of knapsacks, with the lower bound being 0. If (i,j) = 0, it indicates that item j is not packed into any knapsack in packing scheme i; if (i,j) = m, it indicates that item j is packed into knapsack m in packing scheme i.

Population constraints: The initialized population is determined based on the number of knapsacks. If there are $M$ knapsacks, the initialized population is as follows:

$$x_{im}=randi\left(0,M\right)$$

(25)

Experimental Plan

To compare the performance of different algorithms under various experimental conditions, this paper considers nine types of knapsack problems. The experimental design is based on four dimensions: knapsack size, item weight and value, the number of knapsacks, and the number of items. In

Table 1. Experimental plan.

	Number of Knapsacks	Knapsack Capacity	Weight and Value of Items	Number of Items
Q1	3	15,20,25	weight: 5,3,7,2,6,4,9,8,1,10,2,3 value: 10,8,6,9,5,7,3,4,2,1,4,8	12
Q2	3	10,15,20	weight: 5,3,7,2,6,4,9,8,1,10,2,3 value: 10,8,6,9,5,7,3,4,2,1,4,8	12
Q3	3	15,20,25	weight: 3,3,1,2,2,4,9,8,1,10,2,3 value: 10,17,6,5,5,7,3,4,2,1,4,8	12
Q4	2	15,20	weight: 5,3,7,2,6,4,9,8,1,10,2,3 value: 10,8,6,9,5,7,3,4,2,1,4,8	12
Q5	1	25	weight: 5,3,7,2,6,4,9,8,1,10,2,3 value: 10,8,6,9,5,7,3,4,2,1,4,8	12
Q6	5	8,10,6,7,13	weight: 5,3,7,2,6,4,9,8,1,10,2,3 value: 10,8,6,9,5,7,3,4,2,1,4,8	12
Q7	3	15,20,25	weight: 5,3,7,2,6,4,9,8,1,10,2,3,4,7,3 value: 10,8,6,9,5,7,3,4,2,1,4,8,6,9,2	15
Q8	3	15,20,25	weight: 5,3,7,2,6,4,9,8 value: 10,8,6,9,5,7,3,4	8
Q9	3	15,20,25	weight: 8,3,4,9,17,11,8,10,7,6,5,3 value: 2,9,3,2,3,6,9,5,8,1,3,1	12

, Knapsack Problem 1 involves three knapsacks with capacities of 15, 20, and 25, respectively. The goal is to pack 12 items into the knapsacks with the values and weights of the items provided in the table.

5.2. Experimental Results

Table 2. The upper and lower limits for each algorithm to solve different problems.

Algorithm		Q1	Q2	Q3	Q4	Q5	Q6	Q7	Q8	Q9
MODE	weight	50,10	41,2	48,4	33,7	25,2	33,2	47,2	44,2	54,3
	value	66,21	63,9	72,23	59,19	51,9	59,9	76,9	52,9	41,9
MO_PSO_MM	weight	50,10	41,15	48,11	33,4	25,1	33,15	55,17	44,6	59,15
	value	66,21	63,38	72,30	59,13	51,2	59,38	80,40	52,5	46,20
MO_Ring_PSO_SCD	weight	51,15	38,15	48,11	31,10	24,2	27,26	48,13	44,6	52,33
	value	64,32	55,39	72,33	55,29	49,9	48,39	71,17	52,16	38,30
NSGAII	weight	50,26	41,12	38,11	31,6	24,3	32,27	49,34	44,11	47,30
	value	66,44	63,30	71,39	51,19	49,11	48,37	73,62	52,26	40,17
DN_NSGAII	weight	41,16	39,11	48,15	31,3	15,4	30,15	49,34	44,6	48,37
	value	63,24	52,24	72,53	46,11	32,13	40,25	73,62	52,16	39,30
MOEO_WCD	weight	50,3	43,3	48,6	27,2	25,1	25,1	55,12	44,15	51,12
	value	66,8	66,8	72,17	54,9	51,2	51,2	80,27	52,29	44,11

shows the upper and lower bounds of weight and value objectives for each algorithm when solving different packing optimization problems. For Problem 1, the upper bound for the weight objective using the MOEO_WCD algorithm is 50, and the lower bound is 3. The upper bound for the value objective is 66, and the lower bound is 8. As indicated by Table 2, the MOEO_WCD algorithm is able to find values closer to the boundaries in the nine sets of bi-objective packing combinatorial optimization problems, demonstrating its ability to effectively balance the conflicting objectives of value maximization and weight minimization.

Table 3. The average coverage of each algorithm on the reference solution set.

Algorithm	Q1	Q2	Q3	Q4	Q5	Q6	Q7	Q8	Q9
MODE	17.89% ±0.0739	46.26% ±0.0666	14.9% ±0.0141	26.98% ±0.0700	55.86% ±0.0755	56.69% ±0.0755	56.69% ±0.0460	12.2% ±0.0126	69.09% ±0.0543
MO_PSO_MM	33.83% ±0.0259	39.44% ±0.0674	39.6% ±0.0314	65.60% ±0.0320	59.49% ±0.0947	24.47% ±0.0947	24.47% ±0.0530	43.7% ±0.0337	13.19% ±0.0389
MO_Ring_PSO_SCD	1.11% ±0.0558	1.80% ±0.0769	1.54% ±0.0154	1.52% ±0.0529	22.88% ±0.0714	2.70% ±0.0714	2.7% ±0.0515	2.40% ±0.0127	2.23% ±0.0079
NSGAll	0.90% ±0.0035	1.39% ±0.0053	1.30% ±0.0033	1.17% ±0.0040	20.44% ±0.0568	2.24% ±0.0568	2.24% ±0.0075	3.13% ±0.0054	1.36% ±0.0061
DN_NSGAll	0.91% ±0.0026	1.29% ±0.0050	1.26% ±0.0031	1.24% ±0.0023	11.39% ±0.0393	1.99% ±0.0393	1.99% ±0.0059	3.11% ±0.0050	1.34% ±0.0055
MOEO_WCD	35.62% ±0.0027	10.07% ±0.0044	40.4% ±0.0025	12.24% ±0.0034	59.56% ±0.0328	11.91% ±0.0328	11.91% ±0.0053	43.7% ±0.0054	13.33% ±0.0529

shows the coverage of solutions calculated using Formula (11), which represents the proportion of solutions obtained by different algorithms relative to the overall set of solutions. It presents the average coverage and standard deviation of the solutions obtained by each algorithm across 50 independent experiments for the nine knapsack problems in comparison to the total reference set. From Table 3, it is evident that the results of MOEO_WCD and MODE significantly outperform those of MO_PSO_MM, MO_Ring_PSO_SCD, NSGA-II, and DN_NSGA-II. Specifically, for Problems 1, 3, 5, and 8, the MOEO_WCD algorithm demonstrates the highest coverage. When solving Knapsack Problems 2, 6, 7, and 9, the MODE algorithm achieves the highest coverage. However, the optimization results of the algorithm proposed in this paper rank second or third in terms of coverage for these problem sets. The results indicate that, except for Knapsack Problem 4, the coverage of solutions obtained by the MOEO_WCD algorithm, in terms of the composite Pareto front in the decision space, is higher than that of the other algorithms, with coverage comparable to that of the MODE algorithm. Therefore, the proposed MOEO_WCD algorithm demonstrates a certain advantage in the decision space when solving multi-objective packing optimization problems.

Table 4. HV indicator for each algorithm on the reference solution set.

HV	Repoint	MODE	MO_PSO_MM	MO_Ring_PSO_SCD	NSGAll	DN_NSGAII	MOEO_WCD
Q1	66,3	3481	3115	2737	2804	2999	3451
Q2	66,2	3329	3095	2743	2824	2654	3233
Q3	72,4	4630	4396	4239	4003	4086	4559
Q4	59,2	2737	2714	2285	2233	1951	2569
Q5	51,1	2137	2095	1795	1837	1901	2137
Q6	59,1	2770	2419	1485	1320	1782	2338
Q7	80,2	4778	4407	3559	3452	3423	4719
Q8	52,2	2031	1918	1768	1892	1816	2031
Q9	59,3	1892	1502	971	792	1034	1757
Friedman mean rank		1	2.78	5	5.11	4.89	2.22
Rank		1	3	5	6	4	2

lists the HV metrics of six algorithms on the objective function solved in this paper, and the last two lines show the Friedman test level. The reference points in this table were selected based on Table 2. It can be seen that the MOEO-WCD algorithm ranks second in the hypervolume (HV) metric. This indicates that the diversity of the algorithm solution set is good but still inferior to the MODE algorithm.

Table 5. Wilcoxon test results of HV indicator.

Algorithm	R+	R−	p Value	+	−
MOEO_WCD vs. MODE	0	28	0.018	0	7
MOEO_WCD vs. MO_PSO_MM	38	7	0.074	7	2
MOEO_WCD vs. MO_Ring_PSO_SCD	45	0	0.004	9	0
MOEO_WCD vs. NSGAII	45	0	0.004	9	0
MOEO_WCD vs. DN_NSGAII	45	0	0.004	9	0

conducted a Wilcoxon sign rank test, where “+” indicates that the MOEO-WCD algorithm performs better than the comparison algorithm on the HV indicator, and “−” indicates that the MOEO-WCD algorithm performs worse than the comparison algorithm on the HV indicator. It can be seen that our MOEO-WCD algorithm performs second only to the MODE algorithm.

Figure 6 shows the target frontier situation of all algorithms solving knapsack problem 1.

From Figure 7, it can be seen that the MODE algorithm has the largest overlap with the composite Pareto front in the objective space, while our MOEO_WCD algorithm is in the second place. However, in the decision space, Figure 8 plots the number of decision space solutions corresponding to the objective values obtained by the MODE and MOEO_WCD algorithms for Problem 1. It was found that the number of decision space solutions obtained by the MOEO_WCD algorithm is significantly higher than that of the MODE algorithm and the average number of solutions in the integrated composite Pareto set. Although the MODE algorithm exhibits a larger overlap with the reference composite Pareto front in the plotted objective space compared with the MOEO_WCD algorithm, Table 3 and Figure 8 indicate that the proposed MOEO_WCD algorithm has a higher coverage of the composite solutions in the decision space than the MODE algorithm. In the decision space, the number of solutions obtained by the MOEO_WCD algorithm is greater than that obtained by the MODE algorithm. Additionally, the MOEO_WCD algorithm yields more solutions corresponding to multiple objective values compared with the MODE algorithm. Therefore, it can be concluded that although the diversity of solutions in the objective space is not as high as that of the MODE algorithm, the MOEO_WCD algorithm performs better in terms of the number of solutions in the decision space. However, the MOEO_WCD algorithm proposed in this study exhibits greater diversity in decision space solutions compared with the MODE algorithm. The MOEO_WCD algorithm demonstrates a certain advantage in solving multi-objective packing combinatorial optimization problems, providing decision-makers with a larger number of packing decision options.

Table 6. Q1 Packaging solutions solved by various algorithms.

Algorithm	Option		Weight	Value	Count
MODE	Option 1	Bag1: 1,2,6,12 Bag2: 3,7,9 Bag3: 4,5,8,11	50	66	154
	Option 2	Bag3: 4	2	9
	Option 3	Bag1: 1,7 Bag2: 3,5 Bag3: 2,4,6,8,9,11,12	50	66
MO_PSO_MM	Option 1	Bag1: 2,4,10 Bag2: 7,8,12 Bag3: 1,3,5,6,9,11	60	67	355
	Option 2	Bag1: 1,11 Bag2: 4,9 Bag3: 6	14	32
	Option 3	Bag 1: 8,12 Bag2: 1,2,6,9 Bag3: 3,4,5,11	41	63
MO_Ring_PSO_SCD	Option 1	Bag2: 11 Bag3: 3,6	13	17	8
	Option 2	Bag1: 2,6 Bag2: 7,9 Bag3: 1,3,4,5,11	42	62
	Option 3	Bag1: 2,3,11 Bag2: 1,12 Bag3: 4,6,8,9	35	58
NSGAII	Option 1	Bag1: 5,12 Bag2: 1,4,11 Bag3: 2,3,6,8,9	41	63	11
	Option 2	Bag1: 3,6,11 Bag2: 4,8,12 Bag3: 1,2,5,9	41	63
	Option 3	Bag1: 2,9 Bag2: 1,4,11 Bag3: 8,12	35	58
DN_NSGAII	Option 1	Bag1: 2,3,4,12 Bag2: 1,5,6,11 Bag3: 9	33	59	11
	Option 2	Bag1: 5,6 Bag2: 4,7,8 Bag3: 1,2,3,11,12	49	64
	Option 3	Bag1: 6,8 Bag2: 2 Bag3: 4,11,12	22	40
MOEO_WCD	Option 1	Bag1: 1,2,4,6 Bag2: 3,8,11 Bag3: 5,7,12	49	64	399
	Option 2	Bag1: 1,2,3 Bag2: 3,8,11 Bag3: 5,7,12	50	66
	Option 3	Bag1: 11,12 Bag3: 9	6	14

presents only three packing schemes from the solutions to Knapsack Combinatorial Optimization Problem 1 obtained by each algorithm. The proposed MOEO_WCD algorithm found 399 solutions. In Option 1, items numbered 1, 2, 4, and 6 are packed into Knapsack 1, items numbered 3, 8, and 11 are packed into Knapsack 2, and items numbered 5, 7, and 12 are packed into Knapsack 3. The total packing weight is 49, and the total packing value is 64. The results show that the MOEO_WCD algorithm obtained the largest number of packing schemes, indicating that our algorithm has a certain advantage in solving bi-objective knapsack combinatorial optimization problems. It can meet the diverse needs of decision-makers by providing a greater number of solutions.

6. Conclusions

This paper proposes the MOEO_WCD algorithm, a weighted crowding distance-based equilibrium optimizer, for solving bi-objective packing and combinatorial optimization problems. The algorithm employs non-dominated sorting to solve the bi-objective problem, obtaining a set of Pareto front solutions. It also improves the balance pool generation mechanism and incorporates weighted crowding distance to enhance the diversity of the solution set in solving bi-objective packing and combinatorial optimization problems. Secondly, since multi-objective packing and combinatorial optimization problems are discrete, the algorithm was also adapted with discrete constraints to effectively address these problems. To validate the performance of the MOEO_WCD algorithm, simulation experiments were conducted on multi-objective packing optimization problems with multiple experimental setups. Due to the lack of standard evaluation metrics, a new evaluation metric was designed. According to this metric, the experimental results demonstrate that the MOEO_WCD algorithm shows competitive performance compared with five other multi-objective optimization algorithms. In addition, the HV indicator was also calculated, and the results showed that the MOEO-WCD algorithm was second only to the MODE algorithm in terms of diversity in the target space.

In summary, for discrete scenarios in multi-objective problems, further research and development of existing algorithms are needed to solve these complex optimization problems more effectively. This not only requires improvements in the adaptability of the algorithms but also a more comprehensive understanding of the problem space. In future research, we will attempt to improve the method using different discrete constraints, aiming to provide a new approach for solving combinatorial optimization problems. Additionally, we will discuss methods for improving the multi-objective performance of the MOEO_WCD algorithm. Ultimately, this research will provide more robust support for addressing multi-objective combinatorial optimization problems in practical engineering and applications.