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

李枝勇,马 良,张惠珍

(上海理工大学管理学院,上海200093)

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

李枝勇,马 良,张惠珍

(上海理工大学管理学院,上海200093)

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

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

1 概述

0/1背包问题是运筹学中的一个典型优化难题[1],已被应用于诸多领域,如预算控制、项目选择、装载问题、材料切割和投资问题等,并且还经常作为其他问题的子问题加以研究。

就计算复杂性而言,背包问题属于NP难题,随着问题规模的增大,求解时间随指数增长,在最坏的情况下,时间复杂度为O(2n)。因此,设计新的高效算法来求解背包问题具有重要的理论和实际意义[2-3]。从已有的研究成果来看,求解背包问题的方法主要有精确算法和启发式算法两大类。其中,精确算法包括分支界定法、动态规划法、递归法和回溯法等。……