基于人工蜂群算法的并行优化处理TSP问题的方法及装置

摘要

本发明实施例公开了一种基于人工蜂群算法的并行优化处理TSP问题的方法及装置，解决了目前对于像解空间随问题规模增大而呈指数增长的NP难题，由于硬件核心的工艺制作已经到达瓶颈，导致的难以通过对单个核心的制造来提高性能的技术问题。本发明实施例方法包括：通过MPI接口建立多个并行进程，通过主进程将初始蜜源信息分发给从进程；通过从进程根据TSP的路径长度确定人工蜂群算法的跟随蜂的搜索的蜜源；通过从进程根据TSP的路径总数及人工蜂群算法的侦察蜂监测到无效蜜源后进行重新随机搜索的蜜源以放弃无效蜜源跳出局部最优解；通过主进程获取到从进程的返回的非放弃的所有蜜源为最优蜜源，最优蜜源为TSP的最短路径。

说明书

技术领域

本发明涉及计算机技术领域，尤其涉及一种基于人工蜂群算法的并行优化处理TSP问题的方法及装置。

背景技术

人工蜂群算法是模仿蜜蜂行为提出的一种优化方法，是集群智能思想的一个具体应用，它的主要特点是不需要了解问题的特殊信息，只需要对问题进行优劣的比较，通过各人工蜂个体的局部寻优行为，最终在群体中使全局最优值突现出来，有着较快的收敛速度。为了解决多变量函数优化问题，Karaboga提出了人工蜂群算法ABC模型(artificial beecolony algorithm)。

作为人工蜂群算法应用，讨论旅行商问题(Travelling Salesman Problem，TSP)：设有n个城市，用数(1,…,n)代表。城市i和城市j之间的距离为d(i，j)i,j＝1,…,n.TSP问题的目标是要找遍访每个域市恰好一次，最后回到出发城市，形成一条回路，且其路径总长度为最短。解空间：解空间S是遍访每个城市恰好一次的所有回路。

目前对于像解空间随问题规模增大而呈指数增长的NP难题，在问题规模较小时，通过一些算法可以在一定程度上较好的解决问题，但问题规模持续增大时，由于现阶段，硬件核心的工艺制作已经到达瓶颈，导致了难以通过对单个核心的制造来提高性能的技术问题。

发明内容

本发明实施例提供的一种基于人工蜂群算法的并行优化处理TSP问题的方法及装置，解决了目前对于像解空间随问题规模增大而呈指数增长的NP难题，在问题规模较小时，通过一些算法可以在一定程度上较好的解决问题，但问题规模持续增大时，由于现阶段，硬件核心的工艺制作已经到达瓶颈，导致的难以通过对单个核心的制造来提高性能的技术问题。

本发明实施例提供的一种基于人工蜂群算法的并行优化处理TSP问题的方法，包括：

通过MPI接口建立多个并行进程，通过所述主进程将初始蜜源信息分发给所述从进程，所述并行进程包括主进程和从进程，人工蜂群算法的所述初始蜜源信息为TSP的路径序列；

通过所述从进程根据TSP的路径长度确定人工蜂群算法的跟随蜂的搜索的蜜源；

通过所述从进程根据TSP的路径总数及人工蜂群算法的侦察蜂监测到无效蜜源后进行重新随机搜索的蜜源以放弃无效蜜源跳出局部最优解；

通过所述主进程获取到所述从进程的返回的非放弃的所有所述蜜源为最优蜜源，所述最优蜜源为所述TSP的最短路径。

可选地，通过所述从进程根据TSP的路径长度确定人工蜂群算法的跟随蜂的搜索的蜜源具体包括：

通过所述从进程根据TSP的路径长度及函数确定人工蜂群算法的跟随蜂的蜜源的收益度蜂；

通过预置概率ρ对所述蜜源进行选择，其中，rank是TSP的一所述蜜源对应的路径的长度排位，path_num则是TSP问题中路径总数。

可选地，通过所述从进程根据TSP的路径总数及人工蜂群算法的侦察蜂监测到无效蜜源后进行重新随机搜索的蜜源以放弃无效蜜源跳出局部最优解具体包括：

设定所述侦察蜂的搜索最高限制次数LIMIT，当一所述蜜源在搜索次数达到所述最高限制次数LIMIT后仍未找到更好蜜源，则放弃所述蜜源；

侦察蜂放弃当前蜜源的条件为：其中NP为当前路径总数。

可选地，通过所述主进程获取到所述从进程的返回的非放弃的所有所述蜜源为最优蜜源具体包括：

通过所述主进程获取到所述从进程的返回的非放弃的所有所述蜜源，并同时更新所有从进程的各个所述蜜源信息，收集所有所述蜜源选取为所述最优蜜源。

可选地，通过所述从进程根据TSP的路径长度确定人工蜂群算法的跟随蜂的搜索的蜜源之前还包括：

通过所述从进程的进行人工蜂群算法的引领蜂的领域搜索所述蜜源。

本发明实施例提供的一种基于人工蜂群算法的并行优化处理TSP问题的装置，包括：

进程建立单元，用于通过MPI接口建立多个并行进程，通过所述主进程将初始蜜源信息分发给所述从进程，所述并行进程包括主进程和从进程，人工蜂群算法的所述初始蜜源信息为TSP的路径序列；

跟随蜂单元，用于通过所述从进程根据TSP的路径长度确定人工蜂群算法的跟随蜂的搜索的蜜源；

侦察蜂单元，用于通过所述从进程根据TSP的路径总数及人工蜂群算法的侦察蜂监测到无效蜜源后进行重新随机搜索的蜜源以放弃无效蜜源跳出局部最优解；

返回单元，用于通过所述主进程获取到所述从进程的返回的非放弃的所有所述蜜源为最优蜜源，所述最优蜜源为所述TSP的最短路径。

可选地，跟随蜂单元具体包括：

第一计算子单元，用于通过所述从进程根据TSP的路径长度及函数确定人工蜂群算法的跟随蜂的蜜源的收益度蜂；

第二计算子单元，用于通过预置概率ρ对所述蜜源进行选择，其中，rank是TSP的一所述蜜源对应的路径的长度排位，path_num则是TSP问题中路径总数。

可选地，侦察蜂单元，具体用于设定所述侦察蜂的搜索最高限制次数LIMIT，当一所述蜜源在搜索次数达到所述最高限制次数LIMIT后仍未找到更好蜜源，则放弃所述蜜源；

侦察蜂放弃当前蜜源的条件为：其中NP为当前路径总数。

可选地，返回单元，具体用于通过所述主进程获取到所述从进程的返回的非放弃的所有所述蜜源，并同时更新所有从进程的各个所述蜜源信息，收集所有所述蜜源选取为所述最优蜜源。

可选地，还包括：

引领蜂单元，用于通过所述从进程的进行人工蜂群算法的引领蜂的领域搜索所述蜜源。

从以上技术方案可以看出，本发明实施例具有以下优点：

本发明实施例提供的一种基于人工蜂群算法的并行优化处理TSP问题的方法及装置，其中，基于人工蜂群算法的并行优化处理TSP问题的方法包括：通过MPI接口建立多个并行进程，通过主进程将初始蜜源信息分发给从进程，并行进程包括主进程和从进程，人工蜂群算法的初始蜜源信息为TSP的路径序列；通过从进程根据TSP的路径长度确定人工蜂群算法的跟随蜂的搜索的蜜源；通过从进程根据TSP的路径总数及人工蜂群算法的侦察蜂监测到无效蜜源后进行重新随机搜索的蜜源以放弃无效蜜源跳出局部最优解；通过主进程获取到从进程的返回的非放弃的所有蜜源为最优蜜源，最优蜜源为TSP的最短路径。本实施例中，通过MPI接口建立多个并行进程，通过主进程将初始蜜源信息分发给从进程，并行进程包括主进程和从进程，人工蜂群算法的初始蜜源信息为TSP的路径序列；通过从进程根据TSP的路径长度确定人工蜂群算法的跟随蜂的搜索的蜜源；通过从进程根据TSP的路径总数及人工蜂群算法的侦察蜂监测到无效蜜源后进行重新随机搜索的蜜源以放弃无效蜜源跳出局部最优解；通过主进程获取到从进程的返回的非放弃的所有蜜源为最优蜜源，最优蜜源为TSP的最短路径，解决了目前对于像解空间随问题规模增大而呈指数增长的NP难题，在问题规模较小时，通过一些算法可以在一定程度上较好的解决问题，但问题规模持续增大时，由于现阶段，硬件核心的工艺制作已经到达瓶颈，导致的难以通过对单个核心的制造来提高性能的技术问题。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其它的附图。

图1为本发明实施例提供的一种基于人工蜂群算法的并行优化处理TSP问题的方法的一个实施例的流程示意图；

图2为本发明实施例提供的一种基于人工蜂群算法的并行优化处理TSP问题的方法的另一个实施例的流程示意图；

图3和图4为图2的应用例示意图。

具体实施方式

本发明实施例提供的一种基于人工蜂群算法的并行优化处理TSP问题的方法及装置，解决了目前对于像解空间随问题规模增大而呈指数增长的NP难题，在问题规模较小时，通过一些算法可以在一定程度上较好的解决问题，但问题规模持续增大时，由于现阶段，硬件核心的工艺制作已经到达瓶颈，导致的难以通过对单个核心的制造来提高性能的技术问题。

为使得本发明的发明目的、特征、优点能够更加的明显和易懂，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，下面所描述的实施例仅仅是本发明一部分实施例，而非全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其它实施例，都属于本发明保护的范围。

请参阅图1，本发明实施例提供的一种基于人工蜂群算法的并行优化处理TSP问题的方法的一个实施例包括：

101、通过MPI接口建立多个并行进程，通过主进程将初始蜜源信息分发给从进程，并行进程包括主进程和从进程，人工蜂群算法的初始蜜源信息为TSP的路径序列；

102、通过从进程的进行人工蜂群算法的引领蜂的领域搜索蜜源；

103、通过从进程根据TSP的路径长度确定人工蜂群算法的跟随蜂的搜索的蜜源；

通过从进程根据TSP的路径长度及函数确定人工蜂群算法的跟随蜂的蜜源的收益度蜂；

通过预置概率ρ对蜜源进行选择，其中，rank是TSP的一所述蜜源对应的路径的长度排位，path_num则是TSP问题中路径总数。

104、通过从进程根据TSP的路径总数及人工蜂群算法的侦察蜂监测到无效蜜源后进行重新随机搜索的蜜源以放弃无效蜜源跳出局部最优解；

设定侦察蜂的搜索最高限制次数LIMIT，当一蜜源在搜索次数达到最高限制次数LIMIT后仍未找到更好蜜源，则放弃蜜源；

侦察蜂放弃当前蜜源的条件为：其中NP为当前路径总数。

105、通过主进程获取到从进程的返回的非放弃的所有蜜源为最优蜜源，最优蜜源为TSP的最短路径。

通过主进程获取到从进程的返回的非放弃的所有蜜源，并同时更新所有从进程的各个蜜源信息，收集所有蜜源选取为最优蜜源。

下面以一具体应用场景进行描述，如3和图4所示，应用例包括：

旅行商TSP问题

作为人工蜂群算法应用，讨论旅行商问题(Travelling Salesman Problem，TSP)：设有n个城市，用数(1,…,n)代表。城市i和城市j之间的距离为d(i，j)i,j＝1,…,n.TSP问题的目标是要找遍访每个域市恰好一次，最后回到出发城市，形成一条回路，且其路径总长度为最短。

解空间：解空间S是遍访每个城市恰好一次的所有回路，是{1,……,n}的所有循环排列的集合，S中的成员记为(w₁,w₂,…,w_n)，并记w_n+1＝w₁。初始解可选为(1，……，n)

目标函数：目标函数f(w₁,w₂,...,w_n)即为访问所有城市的路径总长度，或称为代价函数，并且求最小值。

人工蜂群算法

自然界中的蜂群总是能自如发现优良蜜源，人工蜂群算法模拟蜜蜂寻找优良蜜源的过程。人工蜂群算法中主要对象有表1以下四种：

表1

三种蜜蜂协同合作，可以在较短时间内找到“最好的”蜜源。

以下表2为算法与TSP问题的一一对应关系：

表2

人工算法流程图如图3所示。

本实施例对基于TSP问题的人工蜂群算法的改进优化

蜜源选择策略改进

在原人工蜂群算法中，跟随蜂的选择策略是轮盘赌的方式，这是一种贪婪策略的选择方式，即每次都通过选择局部最优来期望得到全局最优，但并不能保证一定能取得全局最优。因此在此进行改进，在依照路径长短，f(i)函数计算得到蜜源的收益度蜂：

然后通过一定的概率ρ进行选择，而不是直接选择最优，可在一定程度避免很快陷入局部最优。

其中rank是TSP的一所述蜜源对应的路径的长度排位，path_num则是TSP问题中路径总数。

侦察蜂检测策略改进

如果一个蜜源的位置一直没有更新，往往意味着算法进入了局部最优解。为了避免这种情况，需要设定一个搜索最高限制次数LIMIT，当某一蜜源在搜索次数达到LIMIT后仍未找到更好蜜源，则舍弃该蜜源，以跳出局部最优解。虽然局部最优容易导致搜索无效，但局部最优可能就是全局最优，如果只是简单的判断搜索次数达到LIMIT就舍弃该最优解，容易导致误判。因此简单的从LIMIT参数上判定还不够，必须从全局范围考虑是否应当舍弃该蜜源，若该蜜源在全局范围属于较优则不应舍弃该蜜源。侦察蜂放弃当前蜜源的条件改进为：

其中NP为当前路径总数。侦察蜂搜索策略

侦察蜂在监测到无效蜜源后进行重新随机搜索的蜜源以放弃无效蜜源跳出局部最优解。但在蜜蜂活动后期，随机搜索蜜源不利于快速收敛，为了能既可以跳出局部最优又能获得更好的收敛速度，可以在当前”全局”最优的基础上较大范围进行随机搜索，这样可以获得较好的效果。

本实施例基于MPI技术对人工蜂群算法的并行改进优化

MPI即消息传递界面/接口(Message Passing Interface,MPI)，是一个并行计算的应用程序接口(API)。MPI是一种基于消息传递的高性能并行体系结构并行编程环境，它的并行处理开销比较大，适合于大粒度的进程级并行计算，相对其他并行编程环境，它具有很好的移植性。同时MPI具有完备的异步通信功能，能按照用户要求很好地分解问题、组织不同进程问数据交换，适合于规模可扩展性并行算法。

在整个人工蜂群算法中包含了大量的迭代操作，而迭代操作就潜在并行的思路。通过分析发现，蜜蜂在采蜜过程中是互不干扰的，因此可以采用并行算法以简短整个算法的执行时间。本算法使用MPI进行优化时，程序分为几个并行进程，并行策略如下：

0号进程为主进程，负责初始化路径信息并将蜜源信息分发给从进程，并收集每个从进程计算出来的结果

分发信息后所有进程负责模拟每一次的路径搜索与更新，也就是一次并行更新多条路径，最后进行数据收集

算法过程，如图4所示：

初始化蜜源

while(cycle<Max_cycle)do

MPI_Scatterv():数据分散到各进程

EmployedBee():引领蜂邻域搜索

OnlookerBee():跟随风跟随采蜜

ScoutBee():侦察蜂放弃局部优蜜源

MPI_Gatherv():数据收集到主进程

Pp():更新各个蜜源信息

cycle++

end

收集所有蜜源并选取最优蜜

本实施例中，通过MPI接口建立多个并行进程，通过主进程将初始蜜源信息分发给从进程，并行进程包括主进程和从进程，人工蜂群算法的初始蜜源信息为TSP的路径序列；通过从进程根据TSP的路径长度确定人工蜂群算法的跟随蜂的搜索的蜜源；通过从进程根据TSP的路径总数及人工蜂群算法的侦察蜂监测到无效蜜源后进行重新随机搜索的蜜源以放弃无效蜜源跳出局部最优解；通过主进程获取到从进程的返回的非放弃的所有蜜源为最优蜜源，最优蜜源为TSP的最短路径，解决了目前对于像解空间随问题规模增大而呈指数增长的NP难题，在问题规模较小时，通过一些算法可以在一定程度上较好的解决问题，但问题规模持续增大时，由于现阶段，硬件核心的工艺制作已经到达瓶颈，导致的难以通过对单个核心的制造来提高性能的技术问题。

使用MPI技术对算法进行并行计算。对于NP难题，解空间随问题的规模增大呈指数级增长，因此求解时间大大增加，MPI并行技术可大大地缩短求解时间。通过对原算法的改进，使算法的结构更优，在原算法的基础上得到更好的运行效率。

请参阅图2，本发明实施例提供的一种基于人工蜂群算法的并行优化处理TSP问题的装置的一个实施例包括：

进程建立单元201，用于通过MPI接口建立多个并行进程，通过主进程将初始蜜源信息分发给从进程，并行进程包括主进程和从进程，人工蜂群算法的初始蜜源信息为TSP的路径序列；

引领蜂单元202，用于通过从进程的进行人工蜂群算法的引领蜂的领域搜索蜜源。

跟随蜂单元203，用于通过从进程根据TSP的路径长度确定人工蜂群算法的跟随蜂的搜索的蜜源；

跟随蜂单元203具体包括：

第一计算子单元2031，用于通过从进程根据TSP的路径长度及函数确定人工蜂群算法的跟随蜂的蜜源的收益度蜂；

第二计算子单元2032，用于通过预置概率ρ对所述蜜源进行选择，其中，rank是TSP的一所述蜜源对应的路径的长度排位，path_num则是TSP问题中路径总数。

侦察蜂单元204，用于通过从进程根据TSP的路径总数及人工蜂群算法的侦察蜂监测到无效蜜源后进行重新随机搜索的蜜源以放弃无效蜜源跳出局部最优解，跟随蜂单元204，具体用于设定侦察蜂的搜索最高限制次数LIMIT，当一蜜源在搜索次数达到最高限制次数LIMIT后仍未找到更好蜜源，则放弃蜜源；

侦察蜂放弃当前蜜源的条件为：其中NP为当前路径总数。；

返回单元205，用于通过主进程获取到从进程的返回的非放弃的所有蜜源为最优蜜源，最优蜜源为TSP的最短路径。

返回单元205，具体用于通过主进程获取到从进程的返回的非放弃的所有蜜源，并同时更新所有从进程的各个蜜源信息，收集所有蜜源选取为最优蜜源。

本实施例中，通过MPI接口建立多个并行进程，通过主进程将初始蜜源信息分发给从进程，并行进程包括主进程和从进程，人工蜂群算法的初始蜜源信息为TSP的路径序列；通过从进程根据TSP的路径长度确定人工蜂群算法的跟随蜂的搜索的蜜源；通过从进程根据TSP的路径总数及人工蜂群算法的侦察蜂监测到无效蜜源后进行重新随机搜索的蜜源以放弃无效蜜源跳出局部最优解；通过主进程获取到从进程的返回的非放弃的所有蜜源为最优蜜源，最优蜜源为TSP的最短路径，解决了目前对于像解空间随问题规模增大而呈指数增长的NP难题，在问题规模较小时，通过一些算法可以在一定程度上较好的解决问题，但问题规模持续增大时，由于现阶段，硬件核心的工艺制作已经到达瓶颈，导致的难以通过对单个核心的制造来提高性能的技术问题。

使用MPI技术对算法进行并行计算。对于NP难题，解空间随问题的规模增大呈指数级增长，因此求解时间大大增加，MPI并行技术可大大地缩短求解时间。通过对原算法的改进，使算法的结构更优，在原算法的基础上得到更好的运行效率。

所属领域的技术人员可以清楚地了解到，为描述的方便和简洁，上述描述的系统，装置和单元的具体工作过程，可以参考前述方法实施例中的对应过程，在此不再赘述。

在本申请所提供的几个实施例中，应该理解到，所揭露的系统，装置和方法，可以通过其它的方式实现。例如，以上所描述的装置实施例仅仅是示意性的，例如，所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，装置或单元的间接耦合或通信连接，可以是电性，机械或其它的形式。

所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。

另外，在本发明各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。

所述集成的单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器(ROM，Read-OnlyMemory)、随机存取存储器(RAM，Random Access Memory)、磁碟或者光盘等各种可以存储程序代码的介质。

以上所述，以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。