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

VIP免费
3.0 陈辉 2024-11-19 15 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
。在算法分析和设计中，沿用实
用性的复杂性概念，即把求解问题的关键操作，如加、减、乘、比较等运算指定
为基本操作，算法执行基本操作的次数则定义为算法的时间复杂性，算法执行期
间占用的存储单元则定义为算法的空间复杂性。在分析复杂性时，可以求出算法
第一章 绪论
3
的复杂性函数
)(np
，也可用复杂性函数的主要项的阶
))(( np
来表示。若算法 A
的时间复杂性为
))(()( npnTA
，且
)(np
为
n
的多项式函数，则称算法 A为多项
式算法。时间复杂性不属于多项式时间的算法统称为指数时间算法。
如果一个判定性问题的复杂度是该问题的一个实例的规模 n的多项式函数，
则我们说这种可以在多项式时间内解决的判定性问题属于 P类问题。P类问题就是
所有复杂度为多项式时间的问题的集合。然而有些问题很难找到多项式时间的算
法（或许根本不存在），比如找出无向图中的哈密尔顿回路问题。但是我们发现如
果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答案是否正确。
比如说对于哈密尔顿回路问题，给一个任意的回路，我们很容易判断它是否为哈
密尔顿回路。这种可以在多项式时间内验证一个解是否正确的问题称为 NP 问题。
显然，所有的 P类问题都是属于 NP 问题的，但是现在的问题是，P是否等于 NP？
这个问题至今还未解决。NP 问题不一定都是难解的问题，现在还不知道是否有
P=NP 或者 P<>NP，但是后来人们发现还有一系列特殊 NP 问题，这类问题的特殊
性质使很多人相信 P<>NP，只不过现在还无法证明。
§1.2 TSP 概述
TSP(Traveling Salesman Problem) 【4】问题可描述如下：
旅行商到 n个城市推销商品，每两个城市
ji,
之间的距离为
ij
d
，如何选择一条
道路使商人将所有城市经过一遍后回到起点且所走路径最短。TSP 问题可细分为
对称和非对称距离两大类问题。
用图论来解释：假设一个图
),( evg
，其中
v
是顶点集，
e
是边集，设
)( ij
dD
是由顶点
i
和顶点
j
之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过
所有顶点且每个顶点只通过一次的具有最短距离的回路。这个问题可分为对称旅
行商问题（
jiij dd
，任意
nji ,...,3,2,1,
）和非对称旅行商问题（
jiij dd
，任意
nji ,...,3,2,1,
）。若对于城市
},...,,,{ 321 n
vvvvv
的一个访问顺序为
},...,,...,,,{ 321 ni tttttt
其中
),...,3,2,1( nivti
，且记
11 ttn
，则旅行商问题的数学
模型为：
1
1
)1,()1,(
n
i
ndiid
TSP 问题，又称旅行商问题，是一个典型 NP 难题，其可能的路径数目与城市
数目 n是成指数型增长的，即使在每秒能计算 100 万个解的计算机上穷举遍历 50
元胞蚂蚁优化算法及其若干工程应用
4
个城市 TSP 问题的解空间，也需近 47 个世纪，而 100 个城市的问题则需 140 个世
纪。所以一般很难精确地求出其最优解。目前，对 TSP 问题的研究主要是通过一
些启发式算法，如遗传算法、禁忌搜索算法、模拟退火算法等，且都取得了一定
的成果。
§1.3 本文研究的内容安排
第二章：详细介绍了蚂蚁算法的研究历史及现状，基本原理及其生物学、系
统学、数学模型，分析其时间复杂性、空间复杂性及收敛性，以及蚂蚁算法的缺
陷。
第三章：首先介绍元胞自动机的定义、特征及分类等基本概念；之后对一维
及二维不同规则的元胞自动机进行计算机模拟，旨在从模拟中直观表现不同类型
的元胞自动机；之后文中提出了求解 TSP 问题的元胞蚂蚁算法模型，以及算法流
程图；并对算法进行了复杂度分析；最后，文中对元胞蚂蚁算法进行了收敛性证
明。
第四章：首先提出求解非线性规划问题的元胞蚂蚁算法模型及流程图；之后
详细说明算法的具体实现步骤；在进行一系列实验后，针对实验结果进行了分析；
最后讨论了算法中参数的取值区间。
第五章：首先介绍了 PCB 布线问题的相关概念及布线的基本思路；之后给出
布线时采用的线网顺序安排方法，并对本文给出的方法与以往方法进行了比较；
设计了布线中的避障方法及规则；之后文章提出三种不同的布线方法：基于 UVM
布线思路的蚂蚁算法、基于 CVM 布线思路的元胞蚂蚁算法、基于 UVM 布线思路
的元胞蚂蚁算法；最后对三种算法的布线结果以及传统的 protel 布线结果进行了详
细的比较，并给出了结果分析。
第六章：首先介绍了燃料电池发动机温度控制问题的相关概念；以及燃料电
池发动机的系统及模型描述；之后用蚂蚁算法、元胞蚂蚁算法两种算法解决温度
控制问题，并进行了仿真测试；最后对仿真结果进行了分析
第七章：首先介绍量子算法的概念、研究现状；之后提出求解 TSP 问题的量
子蚂蚁算法模型，并给出了算法的程序流程及具体实现步骤；最后对量子蚂蚁算
法进行了收敛性分析。
第八章：对本文所有研究内容进行了总结，并对将来的研究思路进行了展望。
第二章 基本蚂蚁算法模型
5
第二章 基本蚂蚁算法模型
§2.1 蚂蚁算法研究历史和现状
最先提出的蚁群算法被称为 AS
【9－12】(Ant System)，它是 M.Dorigo、A.Colomi.、
V.Maniezzo 在意大利的米兰理工学院合作研究组合优化问题的计算机智能解决方
法时的研究成果。AS 算法首先应用于解决旅行商问题(TSP)，随后 V.Maniezzo、
A.Colomi 把AS 算法用于解决二次分配问题(QAP)。最初的 AS 算法的效果并不理
想，但是后续的研究将蚁群算法和局部搜索以及其它的一些优化方法相结合获得
的许多令人振奋的成果。
1995 年L.M.Gambardella 和M.Dorigo 提出了 Ant-Q 算法【13，14】
。该算法建立
了AS 与Q-学习机制(Q-Teaming)
【15】
的联系。它在 AS 算法的随机比例规则基础上，
在解构造过程中提出了伪随机比例状态迁移规则 (pseudo-random-proportional state
transition rule) 从而能够实现解构造过程中知识探索(exploration) 和知识利用
(exploitation)的平衡，并引入信息素局部更新过程，信息素局部更新规则使用了 Q-
学习机制。此外，在信息素的全局更新中采用了精英策略。
Ant-Q 是一个非常有效
的算法。
此后，
M.Dorigo 和L.M.Gambardella 在Ant-Q 算法基础上提出了 ACS
【16，
17】(Ant
Colony System)；T.Stutzle 和H.Hoos 提出了 MMAS【18】(MAX-MIN Ant system)。
这两种扩展的蚂蚁算法都被用于解决对称旅行商问题 (TSP)以及非对称旅行商问
题(ATSP)，并取得了比较满意的结果。
MMAS 算法采用了用当前找到的最好解来
更新信息素指引蚂蚁向更高质量的解空间搜索的贪婪策略，并对信息素设立上下
限来避免算法的早熟。
1999 年，
M.Dorigo、
C.DiCaro 和L.M.Gambardella 把此前各种基于 AS 演化而
得的算法归结到一个统一的框架中，并提供了抽象而规范的算法描述，称为 ACO
元启发式算法【19】(Ant Colony Optimization meta-heuristic)，简称为 ACO 算法。
ACO 算法的优点在于：利用了正反馈原理加快进化过程。这是一种本质并行
的算法，不同个体之间不断进行信息的交流和传递，从而能够相互协作，有利于
发现较好的解。由于鲁棒性强，故易于解决各种不同的优化问题。但是，蚁群算
法的计算量比较大、搜索时间长、有时候效果并不理想。国内外的研究人员针对
蚁群算法的这些问题，做了许多研究工作，有的将蚁群算法与其它算法相结合，
有的给蚁群系统加入变异特征，取得了许多研究和应用成果。
B.Bullnheimer 等【20】
提出了一种基于蚂蚁等级的 A.Srenk 算法。
W.J.Gutjahr【21】
元胞蚂蚁优化算法及其若干工程应用
6
提出了基于图的蚂蚁算法 GBAS (Graph-based Ant System)。C.Blum【23】针对可转换
为0-1 整数规划问题的组合优化问题，提出了一种 HC-ACO 算法。该算法利用一
些策略来避免算法陷入局部最优解。
吴庆洪【24】等人提出了具有变异特征的蚁群算法，有机地结合了 2-opt 方法，
提高了算法的搜索速度。吴斌、史忠植【25】在蚁群算法的基础上提出了相遇算法，
其基本思想是在求解 TSP 问题中，用两只蚂蚁共同完成对一条路径的搜索，并将
相遇算法与采用并行策略的分段算法相结合提出一种基于蚁群算法的 TSP 问题分
段求解算法，提高搜索速度。陈峻、沈洁、秦玲【26】等针对蚁群算法加速收敛和早
熟停滞现象的矛盾，提出了一种基于分布均匀度的自适应蚁群算法。该算法根据
优化过程中解的分布均匀度，自适应地调整路径选择概率策略和信息素更新策略，
以求在加速收敛和防止早熟、停滞现象之间取得很好的平衡。朱庆保、杨志军【27】
针对蚁群算法在进行大规模优化时收敛时间过长，提出了基于变异和动态信息素
更新的蚁群优化算法。该算法以最近的邻居节点选择和动态信息素更新策略来加
速全局收敛，以一种独特的变异策略来加快局部寻优，使收敛速度大幅度地提高。
I.Watanabe 和S.Matsui【28】通过自适应的控制候选集合，改善 ACO 算法性能；
P.Koro
s
ges 和J.
S
ilC 【29 】用多级的 ACO 算法解决了网络划分问题(Mesh
Partitioning problem)；C.Solnon 研究了蚁群算法搜索的多样性和快速收敛性之间的
矛盾，通过对算法参数的研究提出了在算法初期增加预处理步骤，希望在不影响
搜索多样性的前提下，提高收敛速度，通过对约束满足问题 ( Constrain Satisfaction
Problem)的仿真试验表明了算法确实能提高速度。
目前大量的研究工作注重于 ACO 的实际应用【31－33】
，然而，近几年的研究发
现： ACO 用于解决组合优化问题时，也会遇到类似进化算法中的 deception 和bias
【34 】现象。例如：C.Blum 和M.Sampels【35 】研究 ACO 用于作业调度问题(shop
scheduling problems)时发现：一段时间之后 ACO 的性能会由于信息素模式和处理
的问题实例而下降，这种现象称为：second-order deception【36】或者 search bias，它
意味着随着时间的推移找到更好解的可能性越来越小。J.Montgomery【37】等试图找
出导致算法 search bias 的原因；
C.Blum 和M.Dorigo 针对蚁群算法求解组合优化时
遇到的 second order deception 问题，做了大量的研究工作。然而算法性能的下降原
因仍然是未知的，这些情况表明我们需要对 ACO 算法行为做更多更深入的了解。
应当指出，现阶段对蚁群算法的研究大多还只是停留在仿真阶段，尚未能提
出一个完善的理论分析，对它的有效性也没有给出严格的数学解释。但是，理论
上的不完善并不妨碍应用，有时应用还会超前于理论，并推动理论研究，蚁群算
法的研究正是如此。
摘要：

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

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

共171页,预览10页

还剩页未读， 继续阅读

相关推荐

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

开通VIP享超值会员特权

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

作者详情

相关内容

更多

推荐作者

热门标签

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