学位论文 > 优秀研究生学位论文题录展示

群智能算法及其应用研究

作　者: 寇晓丽
导　师: 刘三阳
学　校: 西安电子科技大学
专　业: 应用数学
关键词: 群智能算法蚁群优化算法微粒群算法大规模TSP问题连续空间函数优化约束优化问题无线传感器网络路由协议
分类号: TP18
类　型: 博士论文
年　份: 2009年
下　载: 1396次
引　用: 16次
阅　读: 论文下载

内容摘要

群智能算法是一种新型的仿生类进化算法,主要包括蚁群优化算法和粒子群算法.群智能算法具有较强的鲁棒性,采用分布式计算机制,并且易于实现,已在众多领域得到了广泛的应用.本文主要围绕蚁群优化算法和微粒群算法的理论及其应用,就如何求解大规模旅行商(Traveling Salesman Problem, TSP)问题、连续性优化问题、约束优化问题、无线传感器网络路由优化问题进行了研究.本文的主要工作概括如下:1.针对大规模TSP问题,提出了一种基于模块度分簇的改进蚁群算法.该算法首先借鉴网络中的分簇原理,基于模块度的分簇算法将TSP问题中的城市划分为若干个簇,降低了问题的维数,并提出模块度的概念来度量所得到的簇结构和实际TSP问题网络匹配的程度;其次,基于信息素扩散的改进蚁群算法求解簇间的连接顺序,即求解分簇得到的小规模TSP问题的最优解,在基于信息素扩散的改进蚁群算法中,从多方面模拟真实蚂蚁的行为,定义了新的信息素扩散挥发规则,增强了蚂蚁之间的合作,使其快速找到最优解,同时增加扰动因子避免其陷入局部最优解,并且分析了其全局收敛性,实例测试结果表明了算法的有效性;然后,构造了求解簇内最短路径的基于信息素扩散的改进蚁群算法;最后,将所有簇内和簇间的解按照一定的规则组成了原TSP问题的解.仿真实验结果表明该算法适合求解大规模TSP问题,与已有算法相比,解的质量和收敛速度均有了较明显的提高.2.针对蚁群算法在连续空间函数优化中应用的瓶颈,提出了一种蚁群混合算法求解连续空间问题,定义了新的蚁群信息素更新规则、蚁群在解空间的寻优方式和蚁群行进策略.为了克服蚁群算法搜索时间过长,易陷于局部最优等缺点,在搜索过程中嵌入了改进的Alopex算法,该算法具有快速搜索和摆脱局部最优解的能力,实验结果表明了蚁群混合算法的有效性.3.针对标准微粒群算法不能保证全局收敛性问题,提出了一种随机混合微粒群算法.在随机微粒群算法中,将惯性权重设置为零,减少了关键参数对算法性能的影响,提高了算法的通用性;在保证算法全局收敛性的同时,结合Alopex算法重新生成停止进化粒子的位置,有效地避免了算法因单一搜索机制引起地停滞现象.将该算法应用于复杂多维函数,取得了较好的效果,为解决较复杂的函数优化问题提供了一种可行的方法.4.针对约束优化问题,提出了一种基于协同进化的微粒群算法.该算法在标准微粒群算法的基础上,采用“保留最优,调节部分”的确定型选择策略,利用进化中个体之间的差异,提出协同算子公式,引导进化方向,使个体之间相互利用信息,更新微粒的位置进化方程;同时,提出基于不可行度的约束处理方法,根据不可行度和不可行度阀值提出新的竞争选择准则,并由此给出新的适应值函数引导群体加强对约束边界的搜索.基于典型的约束优化问题的实验结果表明:该算法可行有效,尤其对解决复杂问题表现出较优的性能.5.研究了蚁群算法在无线传感器网络路由协议中的应用.无线传感器网络路由协议的一个重要目标就是要合理高效地使用网络中各传感器节点的能量,延长网络寿命.文中提出了一种基于蚁群算法的无线传感器网络分簇路由协议.该方法首先利用网络自身拓扑结构,基于模块度的分簇算法得到一个稳定的簇结构,无需每轮循环都构造簇,从而节省了构造簇的开销;其次,根据每个簇内节点的剩余能量以及簇内节点的分布情况,给出了新的簇头选择函数;然后,提出基于蚁群算法的簇间多跳路由算法,该算法以如何均衡传输路径上消耗的能量和簇头节点的剩余能量为出发点,制定了新的蚂蚁转移概率和信息素更新规则,通过实验仿真,并与已有较好算法相比较,验证了算法的有效性.

全文目录

摘要  5-7
ABSTRACT  7-12
第一章绪论  12-31
  1.1 引言  12
  1.2 蚁群优化算法  12-24
    1.2.1 蚁群觅食的生物学行为  12-14
    1.2.2 蚁群优化算法的思想起源  14-16
    1.2.3 蚂蚁系统的模型  16-19
    1.2.4 改进的蚁群优化算法  19-21
    1.2.5 蚁群优化算法的研究现状  21-22
    1.2.6 蚁群优化算法的主要应用领域  22-24
  1.3 微粒群算法  24-29
    1.3.1 微粒群算法的思想起源  24-25
    1.3.2 微粒群算法的基本原理和模型  25-27
    1.3.3 微粒群算法的研究现状  27-28
    1.3.4 微粒群算法的主要应用领域  28-29
  1.4 本文的主要工作和内容安排  29-31
第二章求解大规模TSP 问题的蚁群算法  31-52
  2.1 引言  31-33
  2.2 基于模块度的分簇算法  33-37
  2.3 基于信息素扩散的改进蚁群算法  37-44
    2.3.1 簇间的连接顺序  37
    2.3.2 基于扩散原理的信息素更新规则  37-38
    2.3.3 扰动策略  38-39
    2.3.4 局部搜索策略  39-40
    2.3.5 DACA 算法流程  40
    2.3.6 全局收敛性分析  40-42
    2.3.7 仿真实验  42-44
  2.4 簇内边界城市的确定  44-45
  2.5 求解簇内最短路径的蚁群算法  45
  2.6 MCDACA 算法流程  45-46
  2.7 MCDACA 算法仿真实验与结果分析  46-51
  2.8 小结  51-52
第三章求解函数优化问题的群智能混合算法  52-73
  3.1 引言  52
  3.2 一种蚁群混合算法求解函数优化问题  52-60
    3.2.1 概述  52-54
    3.2.2 新的转移概率规则  54-55
    3.2.3 信息素全局更新规则  55
    3.2.4 蚁群在解空间中的初始分布  55
    3.2.5 嵌入改进的Alopex 算法的局部搜索  55-57
    3.2.6 AACO 算法步骤  57
    3.2.7 数值实验  57-59
    3.2.8 小结  59-60
  3.3 一种随机微粒群混合算法求解函数优化问题  60-73
    3.3.1 概述  60
    3.3.2 随机性算法的收敛准则  60-64
    3.3.3 标准微粒群算法的收敛性分析  64-65
    3.3.4 随机微粒群算法  65-67
    3.3.5 随机微粒群算法的收敛性分析  67-68
    3.3.6 随机混合微粒群算法  68-69
    3.3.7 数值实验  69-72
    3.3.8 小结  72-73
第四章用于约束优化问题的协同进化微粒群算法  73-93
  4.1 约束优化问题  73
  4.2 约束优化问题的求解方法  73-75
  4.3 协同进化算法  75-76
  4.4 基于协同进化的微粒群算法  76-78
    4.4.1 种群选择策略  76
    4.4.2 协同算子  76-78
    4.4.3 CPSO 算法流程  78
  4.5 基于不可行度的约束处理方法  78-81
  4.6 CIPSO 算法流程  81-82
  4.7 数值实验及结果分析  82-92
    4.7.1 实验参数设置  86
    4.7.2 实验结果分析  86-88
    4.7.3 算法性能分析  88-92
  4.8 小结  92-93
第五章蚁群算法在无线传感器网络路由中的应用  93-112
  5.1 引言  93-97
    5.1.1 无线传感器网络结构  93-94
    5.1.2 无线传感器节点结构  94
    5.1.3 无线传感器网络协议栈  94-95
    5.1.4 无线传感器网络的特征  95-96
    5.1.5 无线传感器网络的应用和研究进展  96-97
  5.2 无线传感器网络路由协议  97-99
    5.2.1 概述  97
    5.2.2 无线传感器网络路由算法  97-99
  5.3 基于蚁群算法的无线传感器网络分簇路由协议  99-111
    5.3.1 网络模型  100
    5.3.2 无线通信模型  100-101
    5.3.3 本文算法的基本思想  101-102
    5.3.4 簇的形成  102-103
    5.3.5 簇头的选择  103-104
    5.3.6 基于蚁群算法的簇间多跳路由  104-108
    5.3.7 实验仿真  108-111
  5.4 小结  111-112
结束语  112-113
致谢  113-114
参考文献  114-130
在读期间撰写的学术论文  130-132
在读期间参加的科研项目  132-133

群智能算法及其应用研究

内容摘要

全文目录

相似论文