A Modified Binary Particle Swarm Optimization for Knapsack Problems
A Modified Binary Particle Swarm Optimization for Knapsack Problems
复制标题
DOI：
10.1016/j.amc.2012.05.001
复制
发表时间：
2012-07-15
影响因子：
4
通讯作者：
Deep, Kusum
中科院分区：
文献类型：
--
作者：
Bansal, Jagdish Chand;Deep, Kusum
背包问题 (KP) 是运筹学中的经典 NP 难题，具有许多工程应用。文献中提供了几种传统的以及基于群体的搜索算法来解决这些问题。本文提出了一种新的改进二元粒子群优化（MBPSO）算法来解决KP，特别是0-1背包问题（KP）和多维背包问题（MKP）。与基本的二元粒子群优化（BPSO）相比，该改进算法引入了一种新的概率函数，该函数保持了粒子群的多样性，使其在求解 KP 时更具探索性、有效性和高效性。 MBPSO 通过基准问题的计算实验进行测试，并将结果与 BPSO 和 BPSO 的相对较新的修改版本（即基因型-表型修改二元粒子群优化 (GPMBPSO)）进行比较。为了验证我们的想法并证明所提出的 KP 算法的效率，用 KP 和 MKP 的各种数据实例进行了实验，并将结果与 BPSO 和 GPMBPSO 的结果进行了比较。 (C) 2012 Elsevier Inc. 保留所有权利。
The Knapsack Problems (KPs) are classical NP-hard problems in Operations Research having a number of engineering applications. Several traditional as well as population based search algorithms are available in literature for the solution of these problems. In this paper, a new Modified Binary Particle Swarm Optimization (MBPSO) algorithm is proposed for solving KPs, particularly 0-1 Knapsack Problem (KP) and Multidimensional Knapsack Problem (MKP). Compared to the basic Binary Particle Swarm Optimization (BPSO), this improved algorithm introduces a new probability function which maintains the diversity in the swarm and makes it more explorative, effective and efficient in solving KPs. MBPSO is tested through computational experiments over benchmark problems and the results are compared with those of BPSO and a relatively recent modified version of BPSO namely Genotype-Phenotype Modified Binary Particle Swarm Optimization (GPMBPSO). To validate our idea and demonstrate the efficiency of the proposed algorithm for KPs, experiments are carried out with various data instances of KP and MKP and the results are compared with those of BPSO and GPMBPSO. (C) 2012 Elsevier Inc. All rights reserved.