求解0/1背包问题的自适应元胞粒子群算法

摘要：

对0/1背包问题进行研究，提出一种自适应元胞粒子群算法。在算法设计过程中，重新定义粒子位置和速度的更新方程，引入自适应因子，为有效粒子的主动进化和无效粒子的主动退化提供依据，新的编码方式使得新产生的粒子能够以更大的概率和更快的速度成为有效粒子，将元胞及其邻居引入到算法中保持种群的多样性，利用元胞的演化规则进行局部优化，避免算法陷入局部极值。对多组不同规模的背包问题进行仿真实验，结果表明，该算法不仅可以有效求解0/1背包问题，而且能够以较快的速度搜索到精度较高的次优解甚至全局最优解，具有较好的稳定性。

关键词：粒子群优化、0/1背包问题、自适应因子、元胞自动机、组合约束优化、NP难题

分类号：TP301.6(计算技术、计算机技术)

资助基金：高等学校博士学科点专项科研联合基金资助项目20123120120005;上海市一流学科建设基金资助项目S1201YLXK;上海高校青年教师培养计划基金资助项目slg12010;上海市教育委员会科研创新基金资助项目14YZ090;上海市研究生创新基金资助项目JWCXSL1202;上海理工大学博士科研启动基金资助项目1D-10-303-002。

在线出版日期：2014-10-31（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：198-203