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

Ziqian Wang, Xin Huang, Yan Zhang, Danju Lv (), Wei Li, Zhicheng Zhu and Jian’e Dong
Additional contact information
Ziqian Wang: College of Big Data and Intelligent Engineering, Southwest Forestry University, Kunming 650224, China
Xin Huang: Research Institute of Forestry Policy and Information Chinese Academy of Forestry, Beijing 100091, China
Yan Zhang: College of Mathematics and Physics, Southwest Forestry University, Kunming 650224, China
Danju Lv: College of Big Data and Intelligent Engineering, Southwest Forestry University, Kunming 650224, China
Wei Li: College of Big Data and Intelligent Engineering, Southwest Forestry University, Kunming 650224, China
Zhicheng Zhu: College of Big Data and Intelligent Engineering, Southwest Forestry University, Kunming 650224, China
Jian’e Dong: College of Big Data and Intelligent Engineering, Southwest Forestry University, Kunming 650224, China

Mathematics, 2024, vol. 12, issue 22, 1-19

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.

Keywords: MOEO_WCD; knapsack problem; multi-objective optimization; weighted crowding distance (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/22/3538/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/22/3538/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:22:p:3538-:d:1519448

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().