胞蚂蚁优化算法及其若干工程应用

VIP免费
3.0 陈辉 2024-11-19 7 4 4.1MB 171 页 15积分
侵权投诉
I
目 录
第一章 绪论.............................................................................................................1
§1.1 组合优化问题...........................................................................................2
§1.1.1 组合优化........................................................................................2
§1.1.2 计算复杂性基本概念....................................................................2
§1.2 TSP 概述 ...................................................................................................3
§1.3 本文研究的内容安排...............................................................................4
第二章 基本蚂蚁算法模型.....................................................................................5
§2.1 蚂蚁算法研究历史和现状......................................................................5
§2.2 基本蚂蚁算法原理及模型......................................................................7
§2.2.1 基本蚂蚁算法原理.......................................................................7
§2.2.2 基本蚂蚁算法的生物学模型.......................................................8
§2.2.3 基本蚂蚁算法的系统学模型.......................................................9
§2.2.4 基本蚂蚁算法的数学模型.........................................................11
§2.3 基本蚂蚁算法的理论分析....................................................................13
§2.3.1 时间复杂度分析..........................................................................13
§2.3.2 空间复杂度分析..........................................................................14
§2.3.3 收敛性分析..................................................................................15
§2.3.4 基本蚂蚁算法的缺陷.................................................................16
第三章 元胞蚂蚁算法模型及收敛性证明...........................................................17
§3.1 元胞自动机定义、构成及其特征.........................................................17
§3.1.1 元胞自动机定义..........................................................................17
§3.1.2 元胞自动机的构成......................................................................18
§3.1.3 元胞自动机的一般特征..............................................................22
§3.2 元胞自动机的分类.................................................................................23
§3.2.1 元胞自动机分类..........................................................................23
§3.2.2 常用的元胞自动机......................................................................27
§3.3 对不同规则元胞自动机的计算机模拟.................................................31
§3.3.1 一维元胞自动机计算机模拟......................................................31
§3.3.2 二维元胞自动机计算机模拟......................................................36
§3.4 求解 TSP 问题的元胞蚂蚁算法模型 ....................................................38
§3.4.1 算法模型......................................................................................38
§3.4.2 算法流程图..................................................................................42
II
§3.5 元胞蚂蚁算法的复杂度分析.................................................................45
§3.5.1 时间复杂度分析..........................................................................45
§3.5.2 空间复杂度分析..........................................................................45
§3.6 元胞蚂蚁算法的收敛性证明.................................................................46
§3.6.1 收敛条件......................................................................................46
§3.6.2 符号及公式..................................................................................47
§3.6.3 收敛性证明..................................................................................48
§3.7 本章小结.................................................................................................57
第四章 基于元胞蚂蚁算法的非线性规划...........................................................58
§4.1 非线性规划.............................................................................................58
§4.2 元胞蚂蚁算法求解非线性规划问题.....................................................58
§4.2.1 求解非线性规划的元胞蚂蚁算法模型......................................58
§4.2.2 算法的实现..................................................................................61
§4.2.3 实验结果及分析..........................................................................65
§4.3 算法参数的选择....................................................................................69
§4.3.1 信息素挥发度的选择.................................................................69
§4.3.2 蚂蚁个数的选择.........................................................................70
§4.3.3 总信息量的选择.........................................................................71
§4.3.4 迭代次数的选择.........................................................................72
§4.4 本章小结.................................................................................................72
第五章 PCB 布线问题的求解 .............................................................................. 74
§5.1 PCB 及相关概念 .................................................................................... 74
§5.1.1 PCB 的概念 ................................................................................. 74
§5.1.2 电子电路 CAD 技术与自动布线 .............................................. 75
§5.2 PCB 布线问题 ........................................................................................ 78
§5.2.1 布线的基本要求及思路.............................................................78
§5.2.2 通孔最小化算法.........................................................................79
§5.3 线网顺序安排.........................................................................................83
§5.3.1 布线顺序对布通率的影响.........................................................83
§5.3.2 布线顺序处理方法.....................................................................85
§5.3.3 与其他方法的比较.....................................................................86
§5.4 布线中的避障方法设计........................................................................89
§5.4.1 避障的线长计算.........................................................................89
III
§5.4.2 布线中障碍物的规避.................................................................92
§5.5 基于 UVM 布线思路的蚂蚁算法求解 ................................................ 96
§5.5.1 main 程序段描述 .........................................................................97
§5.5.2 Algorithm1 描述.......................................................................... 97
§5.5.3 Algorithm2 描述.......................................................................... 99
§5.5.4 避障程序段与 Algorithm3 ........................................................101
§5.6 基于 CVM 布线思路的元胞蚂蚁算法求解 ...................................... 102
§5.6.1 算法模型....................................................................................102
§5.6.2 算法主要步骤............................................................................103
§5.7 基于 UVM 布线思路的元胞蚂蚁算法求解 ....................................... 105
§5.7.1 算法模型....................................................................................105
§5.7.2 算法具体步骤............................................................................107
§5.8 三种布线算法的结果比较..................................................................110
§5.8.1 一布线实例及各算法的布线结果...........................................110
§5.8.2 各算法的布线结果分析............................................................120
§5.9 本章小结...............................................................................................120
第六章 燃料电池发动机冷启动控制问题求解.................................................123
§6.1 燃料电池发动机及温度控制问题......................................................123
§6.1.1 燃料电池发动机........................................................................123
§6.1.2 燃料电池发动机的温度控制问题............................................124
§6.1.3 智能控制的基本概念................................................................124
§6.2 燃料电池发动机的系统及模型描述..................................................125
§6.2.1 PEMFC 燃料电池发动机的系统描述 ..................................... 125
§6.2.2 PEMFC 燃料电池发动机的模型描述 ..................................... 127
§6.3 基于蚂蚁算法的燃料电池发动机的智能控制..................................130
§6.3.1 一些定义....................................................................................130
§6.3.2 燃料电池发动机智能控制问题................................................130
§6.3.3 基于蚂蚁算法的燃料电池发动机智能控制的步骤................130
§6.3.4 基于蚂蚁算法的燃料电池发动机智能控制仿真....................133
§6.4 基于元胞蚂蚁算法的燃料电池发动机智能控制..............................139
§6.5 本章小结..............................................................................................143
第七章 量子蚂蚁算法模型及收敛性分析.........................................................144
§7.1 量子计算概述.......................................................................................144
IV
§7.1.1 量子计算的研究现状................................................................145
§7.1.2 量子算法（QA）.....................................................................146
§7.2 求解 TSP 的量子蚂蚁算法模型 .........................................................147
§7.2.1 算法模型....................................................................................147
§7.2.2 算法实现步骤............................................................................150
§7.2.3 算法程序流程............................................................................152
7.3 量子蚂蚁算法收敛性分析....................................................................154
7.4 本章小结................................................................................................156
第八章 总结与展望.............................................................................................159
参考文献...............................................................................................................161
在读期间公开发表的论文和承担科研项目及取得成果...................................169
一．发表的论文...........................................................................................169
二．参与的科研项目...................................................................................169
三．参与编写的著作...................................................................................170
致谢.......................................................................................................................171
第一章 绪论
1
第一章 绪 论
随着计算机科学的飞速发展，针对离散变量的优化问题逐渐被重视，从而形
成了有别于数学规划的另一类重要模型，即组合优化（Combinatorial Optimization）。
越来越多的人开始研究组合优化问题，提出许多新的方法和思路，使得组合优化
问题内容更加丰富。组合优化问题的求解一直是近年来研究的热点领域之一。
组合优化就是离散优化，它是通过数学方法寻找离散时间的最优编排、分组、
次序、或筛选等。组合优化问题【1】【2】通常可描述为：令
},...,,{ 21 n
sss
为所有状
态构成的解空间，
}{ i
sC
为状态
i
s
对应的目标函数值，要求寻求最优解
，使得
i
s
，
)(min)( i
sCsC
。对组合优化问题的研究，特别是求解复杂组合优化
问题方法的探索已成为众多学科关注的焦点，这不仅在于其内在的复杂性有着重
要的理论价值，也在于它们在现实生活中的很多方面有着广泛的应用。
例如：旅行商人如何安排所经过城市的顺序，物流系统中如何引导车辆寻路，
物流配送中如何确定需求点和中心仓库的位置等等。复杂性理论指出，在这些应
用下隐藏的组合优化问题通常都不是多项式复杂度的。实践经验也表明，现实世
界中这些问题的实例规模使得在可接受的时间内不可能完成精确的求解。因此人
们在努力研究如何寻求问题的较优解，即在可以接受的时间内寻找具有可以接受
的质量的解。其中，通过模拟生物界的复杂系统——蚁群而进行组合优化问题求
解是目前国际上的研究热点之一，称为蚁群优化（Ant Colony Optimization，简称
ACO）,一般也称为蚁群算法。
蚁群算法是由意大利学者 M.Dorigo 等人
【3】
在20 世纪 90 年代初通过模拟自然
界中蚂蚁集体觅食行为而提出的一种基于种群的启发式仿生类算法。它是继模拟
退火算法、遗传算法、禁忌搜索算法、神经网络算法等启发式算法以后的又一种
应用于组合优化问题的启发式搜索算法。虽然与已经发展完备的一些启发式算法
比较起来，蚁群算法的计算量比较大、搜索时间长、有时候效果并不理想，但是
它的成功运用还是激起了人们对蚁群算法的极大兴趣，并吸引了一批研究人员从
事蚁群算法的研究。众多的研究结果已经证明，蚁群算法具有较强的发现较好解
的能力，该算法不仅利用了正反馈原理加快进化过程，而且是一种本质并行的算
法。不同个体之间不断进行信息的交流和传递，从而能够相互协作，有利于发现
较好解。由于鲁棒性强，使得蚁群算法易于解决各种不同的优化问题。但该算法
的研究毕竟刚刚开始，还未形成系统的分析方法和坚实的数学基础，许多问题还
有待进一步研究。
元胞蚂蚁优化算法及其若干工程应用
2
§1.1 组合优化问题
§1.1.1 组合优化
组合优化是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序
或筛选等，是运筹学（Operations Research）中一个经典且重要的分支，所研究的
问题涉及经济管理、工业工程、交通运输、通信网络等诸多领域，组合优化问题
分为最小化问题和最大化问题，由于两个问题可以互相转化，所以本文只对最小
化问题进行说明。该问题可用数学模型描述为：
)(min xf
(式1-1)
0)(.. xgts
(式1-2)
Dx
(式1-3)
其中
)(xf
为目标函数，
)(xg
为约束函数，
x
为决策变量，
D
表示有限个点组
成的集合。
组合优化问题的一个实例可以用这三个参数
),,( fFD
表示，其中
表示决策
变量的定义域；
表示可行解区域，即
}0)(,{ xgDxxF
，
中的任何一个元
素称为该问题的可行解；
f
是目标函数，满足
})(min{)( Fxxfxf
的可行解
x
称为该题的最优解。组合优化问题的特点是可行解集合为有限点集。由直观可知，
只要将
中有限个点逐一判别是否满足
)(xg
的约束并比较目标值的大小，就可以
得到该问题的最优解。
§1.1.2 计算复杂性基本概念
由于有些优化算法所需要的计算时间和存储空间难以承受，因此算法可解的
问题在实践中不一定可解。所以只有了解所研究问题的复杂性，才能有针对性的
设计算法，进而提高优化效率。
一个算法的有效性可以用执行算法所需要的各种计算资源的量来衡量，最主
要的两个资源是所需的运行时间和存储空间。算法的时间和空间复杂性对计算机
求解能力有重大的影响。
算法或问题的复杂性一般表示为问题规模
n
（如 TSP 问题中的城市数）的函
数，时间复杂度记为
)(nT
，空间复杂性记为
)(nS
。在算法分析和设计中，沿用实
用性的复杂性概念，即把求解问题的关键操作，如加、减、乘、比较等运算指定
为基本操作，算法执行基本操作的次数则定义为算法的时间复杂性，算法执行期
间占用的存储单元则定义为算法的空间复杂性。在分析复杂性时，可以求出算法
摘要：

I目录第一章绪论.............................................................................................................1§1.1组合优化问题...........................................................................................2§1.1.1组合优化.........................................................................

展开>> 收起<<
胞蚂蚁优化算法及其若干工程应用.pdf

共171页,预览10页

还剩页未读， 继续阅读

相关推荐

更多
立即下载
作者：陈辉 分类：高等教育资料 价格：15积分 属性：171 页 大小：4.1MB 格式：PDF 时间：2024-11-19

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

推荐作者

热门标签

/ 171
评分 收藏
分享
立即下载 VIP免费下载
客服
关注