一种新的离散粒子群算法在指派问题中的应用

• 作者: 孙晓雅 林焰
• 来源期刊: 计算机应用研究
• 关键词: 指派问题 离散粒子群算法 交叉策略 局部搜索
• 年，卷（期）: 2009,（11）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 4091-4093,4097
• 页数: 4页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2009.11.027

摘要

指派问题在组合优化中属NP-Complete问题.提出了一种基于离散粒子群算法的求解方法.算法中每个粒子的位置代表了一种可行的指派方案,在迭代中通过交叉策略和局部搜索策略来更新粒子的位置,这既保证了粒子位置的可行性,又增加了粒子的多样性,避免陷入早熟收敛.通过实例仿真可以看出DPSO算法简洁,较以往算法具有更好的收敛性,能得到更优的解,能够求解匈牙利法不能求解的指派问题.对不同的问题,通过影响参数的调整,可以取得好的收敛效果.