论文摘要
组合优化问题在现实生活中有着广泛的应用,由于存在大量的NP-难问题,用传统方法求解非常困难,目前主要以启发式计算求解为主。粒子群算法是一种较新的群智能优化算法,其原理简单,性能优秀且易于实现,近年来逐步被运用来求解组合优化问题。多背包问题是一类典型的组合优化问题,目前常用的处理方法是采用二进制编码方式构建粒子模型,并用二进制的离散粒子群算法求解。这种粒子编码方式在问题规模较小的时候,求解效果不错,但随着规模的加大,尤其是背包数的增大,粒子的编码长度将成倍增加,严重影响到算法的求解效率。针对二进制编码方式存在的缺点,本文采用整数编码方式构建了粒子模型,在粒子更新方式上,本文放弃了传统的连续迭代取整的处理方法,采用了交换粒子群算法中粒子交换运动的思想,改进了粒子的运动模式,重新构建粒子更新公式,并通过加入运动系数参数,使算法有效地克服了易陷入局部极值的缺点。通过对多组多背包问题的求解对比,改进后的基于交换原理的粒子群算法,无论是在求解精度和算法耗时上,都远远优于二进制离散粒子群算法。粒子群算法对于普通车辆路径问题有着不错的求解效果,但在加入了时间窗约束的车辆路径问题上,已有文献算法的求解质量并不高。本文分析了其中粒子更新方式的不合理之处,采用改进的基于交换原理的离散粒子群算法和排序粒子群算法结合,构建粒子双层的进化方式。算法在8个任务点的通用算例的求解中,取得了很好的效果,求解精度达到了100%,远高于现有文献。