基于禁忌粒子群算法的多目标背包问题研究

摘要

多目标优化问题是工程与科学研究的重要类别，其中存在多个彼此冲突且有联系的优化方向，如何在有限的时间或资源代价下获得最优解是研究的核心问题。多目标优化问题寻求同时达到各个方向的最优解是困难的，通常经过各目标之间的权衡和折中，得到的问题最优解集合，或者是无穷大的Pareto集。目前提出的多目标优化问题解决方案基本采用进化智能优化手段。
　　 本文详细介绍了粒子群优化算法(PSO)和经典的局部优化禁忌算法(TS)，在这两种算法的基础上提出了禁忌-粒子群算法T-PSOA(Tabu-Particle Swarm Optimization Algorithm)。一方面，算法在粒子群进化过程后一阶段融入了禁忌算法的禁忌运算，它通过局部搜索方法改进第一阶段所取得解的质量。同时引入精英概率的概念，当禁忌运算产生新解好于原有解则代替它，否则根据精英概率的大小，随机选择粒子的一定数量的维度或分量复制新解的相应部分，以维持目标空间的多样性。另一方面，算法提出了惯性权重随种群多样性测度变化而自适应变化的策略，改进了原始粒子群算法的操作参数，提高算法对周围环境变化的适应性。种群多样性的测度可以由粒子群的多样性和集中度指标给出。
　　 最后以多目标0-1背包问题为例验证改进禁忌一粒子群算法较之原始算法在性能上的优势，并且通过实例对改进的粒子群算法中不同的参数做了研究。