1. 研究目的与意义（文献综述）

1.1 研究目的及意义

组合优化问题（或称为离散优化）作为一门古老而又年轻的学科，早在二十世纪后半叶，伴随着工业科技革命和现代管理科学的发展，特别是计算机技术的突飞猛进和在各行业的广泛应用，其已壮大成为运筹学的一个独立分支。一些数百年前数学家们偶然想到的问题和方法，已在网络通信、物流管理、交通规划等行业发挥了重要的作用。

随着实践的发展，出现了越来越多的组合优化问题都很难找到求最优解的多项式时间算法。人们研究整理了一类难以求解的组合优化问题，迄今为止还没有一个能我到最优解的多项式时间算法。其中tsp就属于这一类问题。

2. 研究的基本内容与方案

论文拟以群智能优化算法为基础，利用人工蜂群（ABC）的原理设计解决典型的组合优化问题，以TSP这样的NP问题为主要研究方向，并结合相关解决组合优化的算法，改进ABC算法。

2.1蜂群算法的基本原理

标准的ABC算法通过模拟实际蜜蜂的采蜜机制将人工蜂群分为3类: 采蜜蜂、观察蜂和侦察蜂。整个蜂群的目标是寻找花蜜量最大的蜜源。在标准的ABC算法中，采蜜蜂利用先前的蜜源信息寻找新的蜜源并与观察蜂分享蜜源信息；观察蜂在蜂房中等待并依据采蜜蜂分享的信息寻找新的蜜源；侦查蜂的任务是寻找一个新的有价值的蜜源，它们在蜂房附近随机地寻找蜜源。

采蜜蜂、观察蜂和侦查蜂按照图1所示转化，

图1 三种蜜蜂转化图

假设问题的解空间是D维的，采蜜蜂与观察蜂的个数都是SN，采蜜蜂的个数或观察蜂的个数与蜜源的数量相等。则标准的ABC算法将优化问题的求解过程看成是在D维搜索空间中进行搜索。每个蜜源的位置代表问题的一个可能解，蜜源的花蜜量对应于相应的解的适应度。一个采蜜蜂与一个蜜源是相对应的。

2.2流程

初始化；

重复以下过程：

o 将采蜜蜂与蜜源一一对应，根据上面第一个公式更新蜜源信息，同时确定蜜源的花蜜 量；

o 观察蜂根据采蜜蜂所提供的信息采用一定的选择策略选择蜜源，根据第一个公式更新 蜜源信息，同时确定蜜源的花蜜量；

o 确定侦查蜂，并根据第三个公式寻找新的蜜源；

o 记忆迄今为止最好的蜜源；判断终止条件是否成立；

2.3蜂群算法求解TSP问题

蜂群算法中，求解最优解的过程就是寻找高收益度食物源的过程，引领蜂有保持优良食物源的作用，具有精英特性．跟随蜂增加较好食物源对应蜜蜂数目，加速算法的收敛．侦察蜂随意搜索新的食物源，扩大了解的多样性，帮助算法跳出局部最优，TSP问题与蜂群采蜜行为对应关系如表1所示。

表1 TSP问题与蜂群采蜜行为对应关系

3. 研究计划与安排

第1－3周：查阅相关文献资料，明确研究内容，了解研究所需理论基础。确定方案，完成开题报告。

第4－5周：熟悉掌握基本理论，完成英文资料的翻译，熟悉开发环境。

第6－9周：编程实现各算法，并进行仿真调试。

4. 参考文献（12篇以上）

[1] 霍凤财, 杜颖, 刘洋.人工蜂群算法及其应用.吉林大学学报：信息科学版,2016(4):468-476.

[2] 赵红星,常小刚.人工蜂群算法的改进[j].计算机工程与设计,2018,39(1):260-265.

[3] 徐斌,程武山,陶莉莉, 等.多策略蜂群算法及在数字系统建模中的应用[j].控制工程,2017,24(1):153-160.