应用蚁群算法解决约束P-中位问题

论文摘要

约束p—中位问题(Capacitated p—median problem,CPMP)作为设备选址问题(Facility location problem,FLP)的一个特殊分支,有着广泛的应用背景,在选址理论和聚类理论中人们对其进行了深入地研究。已知CPMP是一类NP—hard组合优化问题,因此已有多种启发式算法用于求解该类问题。 蚁群算法(Ant colony algorithm,ACO)由于其良好的优化性能,已成为智能仿生算法领域中最具影响力的算法之一。它的主要优点是:利用蚁群间的信息交互,来逐步优化对问题状态的信息素表示,进而指导蚁群搜索问题的最优解。本论文旨在研究如何有效地将ACO用于求解CPMP,以及如何解决与算法执行相关的一系列重要问题,以获得最好的优化性能。本文的主要工作包括: 1.针对CPMP的特点,提出了一种新的求解该问题的启发式算法—中位学习算法(Median learning algorithm,MLA)。该算法借鉴了ACO的信息素学习机制,同时针对问题的结构设计了合理的对象分配方式,通过结合局部搜索策略,算法的全局和局部优化性能得到加强,最终生成问题的一个好的近似解。模拟计算表明,该算法具有良好的全局优化性能和计算效率。 2.设计了适应值曲面投影方法,结合曲面的陡峭性指标,研究了CPMP的适应值曲面的结构特征,进而深层次的刻画解空间的分布特征并据此将问题分类。分析了影响算法性能的主要因素:问题结构,初始中位选择策略,对象分配次序和方式,以及参数设置等。上述研究,为理解算法优化行为,提高优化性能提供了理论依据,进而指导算法设计。 3.在上述研究的基础上,提出了一种求解CPMP的蚁群算法(PMACO)。该算法针对问题特征,设计了新型的初始中位选择方法;利用ACO的学习和优化机制,蚁群逐步学习对象的分配次序和方式;当搜索陷于局部最优时,采用有效的信息素平滑策略以逃离局部最优,最终搜索到问题的最优解。仿真试验表明,PMACO是一种性能较优的求解CPMP的算法,其设计思想和策略是合理有效的。

论文目录

• 引言
• 第一章 理论背景
• 1.1 本文研究问题
• 1.1.1 组合优化问题
• 1.1.2 约束P-中位问题（CPMP）
• 1.1.3 CPMP的研究现状
• 1.2 蚁群算法（ACO）
• 1.2.1 仿生算法
• 1.2.2 蚁群算法的原理
• 1.2.3 蚁群算法的基本框架
• 1.2.4 蚁群算法的研究现状
• 1.3 总结
• 第二章 一种求解CPMP的启发式算法—中位学习算法（MLA）
• 2.1 MLA算法的设计思想
• 2.1.1 将CPMP表示为最短路径搜索问题
• 2.1.2 对问题状态的信息素表示
• 2.1.3 对象分配的次序和随机决策规则
• 2.1.4 信息素的更新规则
• 2.2 求解CPMP的MLA算法
• 2.2.1 中位选择策略
• 2.2.2 局部搜索策略
• 2.2.3 MLA伪代码描述
• 2.3 数值实验
• 2.4 总结
• 第三章 CPMP的难优化本质研究
• 3.1 适应值曲面的基本理论
• 3.1.1 适应值曲面的概念
• 3.1.2 适应值曲面的测度指标
• 3.2 适应值曲面投影方法
• 3.3 CPMP问题实例的适应值曲面
• 3.3.1 曲面的生成方法
• 3.3.2 曲面的测度指标
• 3.3.3 曲面的三维投影图
• 3.4 基于适应值曲面的CPMP难优化本质研究
• 3.4.1 问题分类
• 3.4.2 曲面的投影图分析
• 3.4.3 曲面测度指标分析
• 3.4.4 CPMP解空间的特点
• 3.5 算法的执行策略
• 3.5.1 CPMP的可行解的生成过程
• 3.5.2 初始中位选择策略
• 3.5.3 对象分配策略
• 3.5.4 参数设置方法
• 3.6 总结
• 第四章 求解CPMP的蚁群算法（PMACO）
• 4.1 PMACO算法的设计思想
• 4.2 PMACO算法
• 4.2.1 吸引力中位选择策略
• 4.2.2 对象的分配次序和方式
• 4.2.3 信息素更新和平滑策略
• 4.2.4 PMACO算法的伪代码描述
• 4.3 模拟计算
• 4.3.1 PMACO的全局优化能力
• 4.3.2 PMACO的执行策略的有效性
• 4.4 总结
• 第五章 总结与展望
• 参考文献
• 致谢
• 附录
• 承诺书