文献类型：期刊文章

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

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

出　　处：《系统仿真学报》

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

年　　份：2009

卷　　号：21

期　　号：18

起止页码：5735-5739

语　　种：中文

收录情况：BDHX、BDHX2008、CAS、CSCD、CSCD2011_2012、IC、INSPEC、JST、RCCSE、SCOPUS、ZGKJHX、核心刊

摘　　要：从一维细胞自动机模型入手,设计了一种求解二元离散优化问题的二元粒子群算法细胞自动机模型(BPSO-CA)。粒子从起始细胞出发,根据本身携带的信息并感知存储在细胞中的全局最优粒子位置的信息随机选择状态(0或1),从而实现复杂智能的"涌现"。然后将其用来求解多维0/1背包问题,同时引入贪心算法对不符合约束条件的非法个体进行修正。通过对Zuse Institute Berlin公布的测试集进行实验,表明该模型能在多项式时间内完成求解过程,且实验结果优于测试集记录的结果。

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

分 类 号：TP301.6]