群智能算法及其应用

随着人们对生命本质的不断了解，生命科学正以前所未有的速度迅猛发展，使人工智能的研究开始摆脱经典逻辑计算的束缚，大胆探索起新的非经典计算途径。在这种背景下，社会性动物（如蚁群、蜂群、鸟群等）的自组织行为引起了人们的广泛关注，许多学者对这种行为进行数学建模并用计算机对其进行仿真，这就产生了所谓的“群智能”。社会性动物的妙处在于：个体的行为都很简单，但当它们一起协同工作时，却能够“突现”出非常复杂（智能）的行为特征。例如，单只蚂蚁的能力极其有限，但当这些简单的蚂蚁组成蚁群时，却能完成像筑巢、觅食、迁徙、清扫蚁巢等复杂行为；一群行为显得盲目的蜂群能造出精美的蜂窝；鸟群在没有集中控制的情况下能够同步飞行等。在这些自组织行为中，又以蚁群在觅食过程中总能找到一条从蚁巢到食物源的最短路径最为引人注目。

20世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启发，提出了许多用以解决复杂优化问题的新方法，如遗传算法、进化规划、进化策略等。群智能算法作为一种新兴的演化计算技术已成为越来越多研究者的关注焦点，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的联系。群智能理论研究领域目前有两种主要的算法：蚁群算法和粒子群优化算法。本书系统地描述了蚁群算法和粒子群优化算法的理论和实现技术及其应用，着重强调各种算法的混合；讨论了蚁群算法与模拟退火算法的混合、蚁群算法与遗传算法的混合、蚁群算法与混沌理论混合、模拟退火算法遗传算法与粒子群优化算法混合以及蚁群算法与粒子群优化算法的混合。还讨论了群智能算法在旅行商、武器－目标分配、多处理机调度、可靠性优化、聚类等方面的应用。

本书由15章组成。第1章先介绍了蚁群算法的基本原理，综述了蚁群算法理论研究现状和蚁群算法应用研究现状，粒子群优化算法理论研究现状和粒子群优化应用研究现状。第2章先研究了求解一般非线性整数规划的蚁群算法，然后提出了求解武器－目标分配问题、多处理机调度问题、可靠性优化的蚁群算法，最后提出了多样信息素的蚁群算法。第3章提出了一种求解连续优化问题的蚁群算法。第4章提出了求解聚类问题的基本蚁群算法和与K-均值算法混合的蚁群算法。第5章提出了与模拟退火算法混合的蚁群模拟退火算法求解圆排列问题以及模拟退火蚁群算法求解旅行商问题。第6章首先介绍了基本遗传算法，然后提出了与遗传算法混合的遗传蚁群算法，最后与其他算法进行了测试比较。第7章首先介绍了混沌及运动特性，接着提出与混沌理论混合的混沌蚁群算法，最后与其他算法进行了测试比较。第8章针对最短路问题的蚁群算法的收敛性进行了探索性分析，提出的三个定理给出了寻找最短路的蚁群算法收敛的充分条件。第9章介绍了采用模拟退火思想的粒子群算法、混沌粒子群优化算法来解连续性优化问题。第10章提出了采用粒子群优化来求解背包问题、指派问题、武器?目标分配问题和流水作业调度问题等其他组合优化问题。第11章提出了采用求解聚类问题的两种粒子群优化算法。第12章提出了与粒子群优化算法两种混合算法，并用来求解旅行商问题。第13章对粒子群优化算法的收敛性进行了分析，提出收敛的条件。第14章简单地介绍了鱼群算法的基本原理及应用。第15章对本书作了一个总结，提出了今后研究的方向。最后，本书在附录中给出了求解旅行商问题的蚁群基本算法源程序、计算连续性函数的优化的粒子群程序和求解旅行商问题的粒子 群?蚁群算法的MATLAB语言源程序。

本书可作为信息类的高年级本科生、硕士生、博士生以及广大研究智能算法的科技工作者的参考书。由于作者水平有限，对于本书的不足之处，诚望读者批评指正。

感谢江苏科技大学的张再跃教授、邓志良教授、吴小俊教授、刘同明教授、韩斌副教授等以及有关部门给予的支持，感谢南京理工大学603教研室老师的支持。此外，本书的完成得到了苏州大学江苏省计算机信息处理技术重点实验室开放课题、江苏省自然科学基金、江苏科技大学博士启动基金等项目的资助，在此表示衷心感谢。

作者

2006年2月

前言
第1章 绪论 1
1.1 引言 1
1.2 蚁群算法的基本原理 2
1.3 粒子群优化算法基本原理 6
1.4 蚁群算法理论研究现状 10
1.5 蚁群算法应用研究现状 12
1.6 粒子群优化算法研究现状 13
1.7 粒子群算法应用研究现状 15
第2章 求解整数规划的蚁群算法 17
2.1 求解一般非线性整数规划的蚁群算法 17
2.1.1 引言 17
2.1.2 求解非线性整数规划的蚁群算法 17
2.1.3 算例分析 19
2.2 武器－目标分配问题的蚁群算法 21
2.2.1 引言 21
2.2.2 WTA问题 21
2.2.3 武器－目标分配问题的蚁群算法 22
2.2.4 仿真结果 23
2.3 多处理机调度问题的蚁群算法 24
2.3.1 引言 24
2.3.2 多处理机调度问题数学模型 24
2.3.3 解多处理机调度问题模拟退火算法 25
2.3.4 解多处理机调度问题蚁群算法 26
2.3.5 算法比较 26
2.4 可靠性优化的蚁群算法 28
2.4.1 引言 28
2.4.2 最优冗余优化模型及解法 28
2.4.3 可靠性优化的模拟退火算法 29
2.4.4 可靠性优化的遗传算法 29
2.4.5 可靠性优化的蚁群算法 31
2.4.6 算例分析 32
2.5 求解旅行商问题的多样信息素的蚁群算法 34
2.5.1 信息素更新的3个模型 34
2.5.2 多样信息素更新规则 34
2.5.3 算法测试 34
2.6 本章小结 36
第3章 连续优化问题的蚁群算法研究 38
3.1 无约束非线性最优化问题 38
3.2 连续优化问题的信息量分布函数方法 38
3.3 一种简单的连续优化问题的蚁群算法 39
3.4 数值分析 41
3.5 本章小结 42
第4章 聚类问题的蚁群算法 43
4.1 引言 43
4.2 聚类问题的数学模型 43
4.3 K均值算法 44
4.4 解聚类问题的模拟退火算法 44
4.5 基于巡食思想的蚁群聚类算法 44
4.6 解聚类问题的新的蚁群算法及数值分析 46
4.6.1 解聚类问题的蚁群算法 46
4.6.2 数值分析 46
4.7 解聚类问题的与K-均值算法混合的蚁群算法及数值分析 48
4.7.1 解聚类问题的K-均值算法混合的蚁群算法 48
4.7.2 数值分析 48
4.8 本章小结 49
第5章 蚁群算法与模拟退火算法混合 50
5.1 引言 50
5.2 解圆排列问题的蚁群模拟退火算法 50
5.2.1 圆排列问题及与旅行商问题等价 50
5.2.2 解旅行商问题的模拟退火算法 51
5.2.3 几种算法的比较 52
5.2.4 算例分析 53
5.3 解旅行商问题的模拟退火蚁群算法 54
5.3.1 混合的基本思想 54
5.3.2 找邻域解策略 55
5.3.3 模拟退火蚁群算法 55
5.3.4 算法测试 56
5.4 本章小结 57
第6章 蚁群算法与遗传算法混合 58
6.1 引言 58
6.2 基本遗传算法 58
6.3 蚁群算法与遗传算法的混合 59
6.3.1 混合的基本思想 59
6.3.2 变异操作 59
6.3.3 交叉操作 60
6.3.4 遗传蚁群算法 60
6.4 算法测试 61
6.5 本章小结 62
第7章 蚁群算法与混沌理论混合 63
7.1 引言 63
7.2 混沌及运动特性 63
7.3 基本蚁群算法改进 63
7.3.1 混沌初始化 63
7.3.2 选择较优解 65
7.3.3 混沌扰动 65
7.4 混沌蚁群算法 66
7.5 算法测试 66
7.6 本章小结 68
第8章 最短路的蚁群算法收敛性分析 69
8.1 引言 69
8.2 最短路的蚁群算法收敛性分析 69
8.3 仿真算例 71
8.4 本章小结 76
第9章 解连续性优化问题的粒子群优化算法 77
9.1 模拟退火思想的粒子群算法 77
9.1.1 几种模拟退火思想的粒子群算法 77
9.1.2 算法测试 78
9.2 混沌粒子群优化算法研究 79
9.2.1 基本粒子群算法不足 79
9.2.2 混沌粒子群优化算法 80
9.2.3 算法测试 80
9.3 其他改进的粒子群优化算法 82
9.3.1 杂交PSO算法 82
9.3.2 协同PSO算法 83
9.3.3 离散PSO算法 83
9.4 本章小结 84
第10章 解组合优化问题的粒子群优化算法 85
10.1 背包问题的混合粒子群优化算法 85
10.1.1 背包问题数学模型 85
10.1.2 解0-1背包问题的混合粒子群算法 85
10.1.3 数值仿真与分析 87
10.2 指派问题的交叉粒子群优化算法 89
10.2.1 求解指派问题的交叉粒子群优化算法 89
10.2.2 算法测试 90
10.3 武器－目标分配问题的粒子群优化算法 91
10.3.1 解武器－目标分配问题的粒子群优化算法 91
10.3.2 算例分析 92
10.4 流水作业调度问题的粒子群算法 93
10.4.1 流水作业调度问题 93
10.4.2 求解流水作业调度问题混合粒子群算法 93
10.4.3 算法测试 95
10.5 非线性整数规划的粒子群优化算法 96
10.5.1 引言 96
10.5.2 求解非线性整数规划的粒子群优化算法 96
10.5.3 算例分析 97
10.6 本章小结 99
第11章 解聚类问题的粒子群算法 100
11.1 引言 100
11.2 整数规划形式 100
11.3 连续性优化形式 101
11.4 本章小结 103
第12章 蚁群算法与粒子群优化算法的混合 104
12.1 引言 104
12.2 求解旅行商问题的混合粒子群优化算法 104
12.2.1 混合粒子群算法思路 104
12.2.2 变异操作和交叉操作 104
12.2.3 混合粒子群算法步骤 105
12.2.4 算法测试 105
12.3 求解旅行商问题的粒子群－蚁群算法 108
12.3.1 粒子群－蚁群算法思想 108
12.3.2 粒子群－蚁群算法步骤 108
12.3.3 算法测试 109
12.4 本章小结 111
第13章 粒子群优化算法收敛性分析 112
13.1 引言 112
13.2 PSO算法收敛性分析 112
13.3 数值仿真 114
13.4 参数选取 117
13.5 本章小结 117
第14章 鱼群算法 118
14.1 引言 118
14.2 鱼群算法基本原理 118
14.3 人工鱼的行为描述 119
14.4 鱼群算法的应用 122
14.5 本章小结 122
第15章 总结 124
附录A 求解旅行商问题的蚁群基本算法源程序 127
附录B 计算连续性函数的优化的粒子群程序 131
附录C 求解旅行商问题的粒子群?蚁群算法的源程序 134
参考文献 143

1. 人工智能算法与实践 [主编　梁琨　张翼英]