求解多维0/1背包问题的二元粒子群算法  

Binary PSO Algorithm for Multiple 0/1 Knapsack Problem

作　　者：程美英[1] 熊伟清[1] 严彬[1] 叶青[1] 

机构地区：[1]宁波大学计算机科学与技术研究所,宁波315211

出　　处：《系统仿真学报》2009年第18期5735-5739,5743,共6页Journal of System Simulation

基　　金：国家自然科学基金(60472099);浙江省自然科学基金(Y106080);宁波市自然科学基金(2007A610051)

摘　　要：从一维细胞自动机模型入手,设计了一种求解二元离散优化问题的二元粒子群算法细胞自动机模型(BPSO-CA)。粒子从起始细胞出发,根据本身携带的信息并感知存储在细胞中的全局最优粒子位置的信息随机选择状态(0或1),从而实现复杂智能的"涌现"。然后将其用来求解多维0/1背包问题,同时引入贪心算法对不符合约束条件的非法个体进行修正。通过对Zuse Institute Berlin公布的测试集进行实验,表明该模型能在多项式时间内完成求解过程,且实验结果优于测试集记录的结果。Starting with the one dimension cellular automata model,a kind of binary PSO cellular automata model used to solve the binary discrete optimization problem was designed.In this model,the particle started from the first cell,randomly chose the state（0 or 1）according to its own information and the globe optimal information stored in the cell,then the complex intelligent emergences.The model was involved to solve the Multiple 0/1 Knapsack Problem,and the greedy algorithm was introduced to revise the illegal in...

关 键 词：二元粒子群算法(BPSO) 细胞自动机(CA) 贪心算法 多维0/1背包问题 NPC问题 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]