约束满足问题与调度问题中离散粒子群算法研究

论文摘要

约束满足问题与调度问题在实际生产生活有大量的应用，它们的求解技术是人们研究的重点。本文主要针对离散粒子群算法求解约束满足问题和调度问题作了研究。主要工作包括：提出了取整粒子群算法组合局部搜索求解约束满足问题；改进了Schoofs的离散粒子群算法，指出该算法的位置更新实际上是一个启发式选择公式，之后我们扩展了该公式，并且组合模拟退火算法用于求解约束满足问题；提出了一个基于值序选择的离散粒子群算法；提出把静态变量序作为静态权重提高离散粒子群算法的效率；提出了离散粒子群算法组合环割集算法求解稀疏约束满足问题；提出了基于AllDifferent约束的置换离散粒子群算法，并且组合模拟退火算法后用于求解单机调度和Open-shop问题；最后我们提出了一个通用的离散粒子群算法，并且成功求解了分布式系统中的任务分配问题。对我们的这些算法，用公开的测试数据集进行测试，实验表明，我们提出的这些算法运行结果良好。

论文目录

• 提要
• 第一章 绪论
• 1.1 计算智能
• 1.2 人工生命
• 1.3 进化计算
• 1.4 群智能
• 1.5 约束满足问题
• 1.6 调度问题
• 1.7 本文工作
• 第二章 粒子群算法
• 2.1 概述
• 2.2 粒子群算法
• 2.3 粒子群算法的参数选择
• 2.4 离散粒子群算法
• 2.4.1 取整粒子群算法
• 2.4.2 二元离散粒子群算法
• 2.4.3 模糊离散粒子群算法
• 2.4.4 基于交换的离散粒子群算法
• 2.4.5 基于AllDiffereni的离散粒子群算法
• 2.5 小结
• 第三章 离散粒子群求解约束满足问题
• 3.1 约束满足问题和随机约束满足问题
• 3.1.1 约束满足问题的求解方法
• 3.1.2 约束满足问题的例子
• 3.1.3 随机约束满足问题
• 3.2 取整粒子群算法
• 3.2.1 约束优化问题和约束满足问题
• 3.2.2 粒子群算法求解
• 3.2.3 算法描述
• 3.2.4 实验结果
• 3.3 离散粒子群改进算法
• 3.3.1 算法改进
• 3.3.2 组合模拟退火算法
• 3.3.3 消除重复和禁忌列表
• 3.3.4 算法描述
• 3.3.5 实验结果
• 3.4 基于值序的选择
• 3.4.1 算法改进
• 3.4.2 实验结果
• 3.5 静态权重离散粒子群算法
• 3.5.1 算法改进
• 3.5.2 算法描述
• 3.5.3 实验结果
• 3.6 基于环割集的离散粒子群算法
• 3.6.1 环割集和回溯无关
• 3.6.2 环割集粒子群算法
• 3.6.3 实验结果
• 3.7 小结
• 第四章 离散粒子群算法求解调度问题
• 4.1 基于ALLDIFFERENT约束的置换离散粒子群算法
• 4.1.1 结合模拟退火及算法描述
• 4.1.2 求解单机调度和Open-shop问题
• 4.2 离散粒子群算法及求解任务分配问题
• 4.2.1 离散粒子群算法
• 4.2.2 任务分配问题
• 4.2.3 实验结果
• 4.3 小结
• 第五章 结论与未来工作
• 5.1 结论
• 5.2 未来工作
• 参考文献
• 读博士期间完成的论文和参加的项目
• 致谢
• 摘要
• ABSTRACT