混合爆炸式人工蜂群算法及应用研究

摘要

优化问题普遍存在，人工蜂群算法（Artificial Bee Colony algorithm，ABC）为求解复杂优化问题提供一种新思路和方法。人工蜂群算法是一种模仿蜜蜂采蜜行为的新兴群智能优化技术。它概念简单，控制参数少，容易实现，既能求解连续优化问题，又能解决离散优化问题，其应用前景广阔。因此，人工蜂群算法受到广泛关注并已成功应用于不同领域。但是，人工蜂群算法的研究及应用仍处于起步阶段，有许多关键问题亟待解决，主要包括其理论基础薄弱、局部搜索与全局搜索不平衡导致该算法收敛速度慢等问题。鉴于ABC存在的不足和佳点集理论、手榴弹爆炸法及柯西分布各自具有的优点，按照优势互补的思想，为有效提高ABC性能和解决更多的工程与管理优化问题，以ABC为主线，分别从提高ABC初始种群的多样性、局部搜索能力和全局搜索能力入手，用佳点集理论、手榴弹爆炸法和柯西分布改进ABC，提出一些新颖的混合人工蜂群算法，并用这些新算法求解函数优化问题、多目标优化问题、电力系统优化调度问题和旅行商问题（Traveling Salesman Problem，TSP），支持决策者正确决策。本文的主要研究工作如下：
　　1、初步探讨蜂群算法的理论基础，认为蜂群算法的理论基础是由核心理论与补充理论构成，其中核心理论为自组织理论和劳动分工理论，而补充理论是对核心理论的补充说明。
　　2、分析ABC的生物学机理、计算框架、主要处理步骤、时间复杂度和收敛性，并着重研究侦察蜂在ABC中的作用。通过5个经典的函数优化问题验证多数情况下多侦察蜂ABC优于单侦察蜂ABC，单侦察蜂ABC优于无侦察蜂ABC，由于这三种算法的时间复杂度是同阶的，在相同条件下其运行时间相差不大，充分说明侦察蜂实施随机搜索过程确实对ABC性能具有积极意义。
　　3、为提高ABC初始种群的多样性，从产生佳点的函数特性入手，分析原有两种佳点取法的有效性，提出一种新的佳点取法。用这三种佳点取法和随机取点法分别初始化ABC的种群，通过其产生种群个体的分布性与6个著名的函数优化问题验证新佳点取法ABCJCA明显优于原有两种佳点取法，在解决10维问题时表现最出色，在求解50维和100维问题多数情况下仅次于ABC。接着，根据Pareto支配概念分别修改ABC和ABCJCA，提出求解多目标优化问题的MABC和MABCJCA，通过4个经典的多目标优化问题验证MABCJCA优于MABC，但MABCJCA比一些流行的多目标优化算法性能稍差。这些表明，ABCJCA和MABCJC A用新佳点取法初始化种群是可行且有效的，但是，佳点集理论布点带有方向性，当佳点个数确定后，其佳点是固定不变的，导致ABCJCA和MABCJCA的全局搜索能力仍不够强。因此，在设计算法时要保证充分的随机性很重要。另外，不同算法按照需要适当调高或调低p值以获得更好性能。
　　4、为提高ABC的局部搜索能力，首先将手榴弹爆炸法分别嵌入ABC的引领蜂阶段和观察蜂阶段，提出两种混合爆炸式人工蜂群算法GABC1和GABC2。用两组函数优化问题验证GABC1和GABC2在多数情况下明显优于与之比较的算法，GABC1和GABC2具有相似的性能，但是GABC2总体表现更稳定、鲁棒性更强。
　　5、为提高ABC的全局搜索能力，将柯西变异算子引入GABC2的侦察蜂阶段，提出一种新的混合爆炸式人工蜂群算法ABCGC。用两组函数优化问题验证ABCGC在绝大多数情况下显著优于与之比较的算法，特别是它能快速收敛到全局最优解。此外，通过1个6-Unit系统算例验证ABCJCA、GABC2和ABCGC这三种新算法均能有效求解电力系统优化调度问题和提供切实可行的最优机组发电调度方案，其中，ABCGC总体表现最好。这些说明，ABCGC能很好地平衡人工蜂群算法的局部搜索和全局搜索，可作为全局优化的一种有效算法。
　　6、模仿ABC的数学模型，提出引领蜂和观察蜂都用随机两点交换法生成新序列，设计三种求解TSP的人工蜂群算法，在此基础上，提出在引领蜂阶段或观察蜂阶段采用手榴弹爆炸交换法与最小路径更新操作生成新序列，设计六种求解TSP的混合爆炸式人工蜂群算法。用6个TSP实例验证九种新算法明显优于与之比较的算法，还用6个随机动态地图验证其中一种混合爆炸式人工蜂群算法ABC2G解决TSP的通用性。此外，借助初始路径图求解Dantzig42问题，获得其最短路径长度为688.31，明显优于已知最短路径长度699。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪 论

1.1 研究背景及意义

1.2 蜂群算法研究现状及前沿问题

1.3 主要研究内容及创新点

1.4 论文的结构安排

1.5 本章小结

第2章 人工蜂群算法的基本原理

2.1 引言

2.2 人工蜂群算法的数学模型

2.3 人工蜂群算法的计算框架

2.4 人工蜂群算法的时间复杂度分析

2.5 人工蜂群算法的收敛性分析

2.6 侦察蜂在人工蜂群算法中的作用

2.7 本章小结

第3章 一种新的佳点取法及在人工蜂群算法中的应用

3.1引言

3.2佳点集理论

3.3一种新的佳点取法

3.4佳点取法在人工蜂群算法中的应用

3.5 本章小结

第4章 两种提高局部搜索能力的混合爆炸式人工蜂群算法

4.1 引言

4.2 手榴弹爆炸法的基本原理及研究现状

4.3 两种新的混合爆炸式人工蜂群算法

4.4 两种新算法求解函数优化问题

4.5 本章小结

第5章 一种提高全局搜索能力的混合爆炸式人工蜂群算法

5.1 引言

5.2 柯西分布特性

5.3 一种新的混合爆炸式人工蜂群算法

5.4 新算法求解无约束函数优化问题

5.5 新算法求解电力系统优化调度问题

5.6 本章小结

第6章 六种混合爆炸式人工蜂群算法在求解TSP中的应用

6.1 引言

6.2 TSP问题描述

6.3 人工蜂群算法求解TSP的设计

6.4 混合爆炸式人工蜂群算法求解TSP的设计

6.5 仿真实验与结果分析

6.6 本章小结

第7章 总结与展望

7.1 论文总结

7.2 展望

参考文献

致谢

附录

附录1 TSP实例

附录2攻读博士学位期间发表的论文

附录3攻读博士学位期间主持与参加的科研项目