| 求解多维0/1背包问题的二元粒子群算法 |
| |
| 引用本文： | 程美英,熊伟清,严彬,叶青.求解多维0/1背包问题的二元粒子群算法[J].系统仿真学报,2009,21(18). |
| |
| 作者姓名： | 程美英 熊伟清 严彬 叶青 |
| |
| 作者单位： | 宁波大学计算机科学与技术研究所,宁波,315211 |
| |
| 基金项目： | 国家自然科学基金，浙江省自然科学基金(Y106080):宁波市自然科学基金 |
| |
| 摘 要： | 从一维细胞自动机模型入手,设计了一种求解二元离散优化问题的二元粒子群算法细胞自动机模型(BPSO-CA).粒子从起始细胞出发,根据本身携带的信息并感知存储在细胞中的全局最优粒子位置的信息随机选择状态(0或1),从而实现复杂智能的"涌现".然后将其用来求解多维0/1背包问题,同时引入贪心算法对不符合约束条件的非怯个体进行修正.通过对Zuse Institute Berlin公布的测试集进行实验,表明该模型能在多项式时间内完成求解过程,且实验结果优于测试集记录的结果.
|
| 关 键 词： | 二元粒子群算法(BPSO) 细胞自动机(CA) 贪心算法 多维0/1背包问题 NPC问题 |
Binary PSO Algorithm for Multiple 0/1 Knapsack Problem |
| |
| Abstract: | |
| |
| Keywords: | binary PSO (BPSO) cellular automata (CA) greedy algorithm (GA) Multiple 0/1 Knapsack Problem (MKP) NPC problem |
| 本文献已被 万方数据 等数据库收录！ |
|
