并行蚁群优化算法的实现外文翻译资料

 2022-10-17 15:18:41

英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料

并行蚁群优化算法的实现

摘要：蚁群优化算法是一类新的优化问题的元启发式搜索技术。由于它是一个基于人群的技术，所以在检查算法每一步众多的解决方案选项中，有各种各样的并行化机会。在本文中，将对平行分解策略进行检查。将这些技术应用到一个特定的问题，即旅行推销员问题，以达到提高效率的效果。

关键词：蚁群优化；并行化；旅行商问题.

  1. 介绍

蚁群优化算法(ACO)是一种建设性的基于人口的启发式搜索技术。由于它是一个相对较新的启发式成果，故作为一个标准工具的它的发展尚处于起步阶段，许多方面还需要大量的研究工作，其中之一是为了提高效率，特别是大的实际问题应用的并行策略。本文对ACO常见的并行策略进行了分类，并在旅行商问题（TSP）中对这些应用进行了介绍。

本文安排如下：第2节给出ACO元启发式的简要概述。第3节描述了适用于ACO的一些通用的并行策略，而第4节介绍解决TSP问题的并行策略实现。结果列于第5节中，结论在第6节总结。

  1. 蚁群算法概述

有许多的元启发式算法ACO，包括蚂蚁系统，MAX-MIN蚂蚁系统和蚁群系统（ACS）。ACS搜索技术用于实现我们的测试方案，因为它是这些不同方法的代表。ACS可以通过使用TSP例子进行说明。考虑一组城市，每对城市之间的距离已知。TSP的目的是找到遍历所有城市恰好一次，并返回到开始的城市的最短路径。将ACS范例以下列方式施加到这个问题。考虑一个TSP有N个城市。城市i和j的距离是d(i,j)。离散度为m的虚拟蚁群算法随机应用在这些城市（M≦N）。在离散时间中，每个虚拟蚂蚁穿过一个边缘，直到所有城市被访问。让蚂蚁的沉积物质信息素作为有关的边缘的效用的菌落进行通信的物质。这表示信息素的积累量在(i,j)和tau;(i,j)的边缘（Denote the accumulated strength of pheromone on edge (i,j) by

Tau;(i,j)）。

在每个时间步，方程（1）和（2）用于目前城市r选择下一个城市s的蚁群算法k。注：qisin;[0,1]是一个随机数,q0是参数。为了保持独特的探视限制，k不能从选择已经访问过的城市。没有被蚁群k访问过的城市通过Jk(r)当索引：

它的典型参数beta;是负的，使得短边更受欢迎。tau;(i,j)确保优先考虑是很好的遍历链接（即具有较高信息素的水平）。公式（1）是一个高度贪婪选择技术，有利于它们具有短距离和大信息素水平的最佳组合的城市。公式（2）通过允许下个城市的概率选择平衡这一点。

选定边的信息素水平是根据公式局部更新规则（3）进行更新。

（3）

其中，r是本地信息素衰减系数，0lt;lt;1；tau;0是沉积在各边缘的信息素的初始量。根据Dorigo和Gambardella[5]，一个良好的初始信息素为，其中Lnn是最近邻启发式的成本。

当一个迭代（即所有的蚂蚁构建了一个旅游）完成后，信息素会进行全局更新。当前最好的解决方案的边缘与他们的信息素的水平的增长是一致的。这些表现在

， （4）

其中 用于加强边缘信息素的解决方案（见公式（5））。L是最好的（最短）日期长度，而Q是问题决策相关常数，它通常的设置见公式[6]：

（5）

其中是全局信息素衰减系数，0lt;lt;1.

ACS的基本操作是由图1中的伪代码描述。

  1. 通用并行化策略

尽管ACO是在多个层面固有的并行搜索技术，但是除了Bullnheimer et al.，St. u utzle，Michel和Middendorf外一些研究已经在这方面进行了。前者的工作是并行的蚂蚁（剂）水平的初步调查。然而，作者没有实现的并行架构的系统。因此，很难确定他们的并行方案的有效性。St. u utzle描述的最简单的并行化的情况，并行独立ACO搜索相互独立。Michel和Middendorf描述一个岛屿模型（改编自遗传算法），其中分离了蚁群交换的路径信息。

当考虑一般并行策略时，并行可以在一个或多个规模下被利用。在通常情况下，整个搜索可以像St. u utzle描述的那样同时执行，首先的两种可能的并行化ACO元启发式算法描述如下。同样的，用并行策略解答原理的时候发现，尤其是当该评价被计算得很费时的。用于对TSP在本文中描述的研究的基础，解答原理评价可以被认为是微不足道的，因此并行这个尺度是不适当的。所有被描述的剩余的策略可寻求利用启发式算法中的并行性。

所有这些，除了并行独立蚁群以外，是基于著名的主/从方式，而且是适合广为流行的多输入，多数据（MIMD）的机器架构。另外，一些标准工具，如消息传递接口（MPI）库可用于ACO程序，以确保跨平台的兼容性。

图1 ACS应用到TSP的伪代码

方法2,4,5对于ACO来说是新的。考虑不同的并行技术，必须指出的是当在进程间有较大的通信时，并行性能可以被降级。所有的方法都假定成分布式而不是在共享存储器系统中，因为这些结构是比较常见的。然而，就像ACO系统通常使用全局存储器结构（如信息素矩阵），一个共享存储器将意味着在并行性能中少了很多的通信，而相应的潜能就会增加。

3.1并行独立蚁群

对于这种方法，许多的ACO搜索顺序是在可用的处理器上运行的。每个算法的关键参数的值是有区别的。虽然任何的参数可以在整个进程中是可以改变的，随机源将做出明确的选择。这种方法的优点是没有进程之间的通信。这是一个像运行的工作站的MIMD机/集群上的一些串行程序一样的初级方法。

3.2并行互动蚁群

该方法类似于上述方法，所不同的是在给定的迭代中，信息的群体之间的交换发生。“最好的”执行蚁群的信息素结构被复制到其他蚁群。问题变成限定表现最好的蚁群之一，可以使用许多不同的措施。由于广播整个信息素的结构的必要性，此方法的通信成本可能相当高，它会是许多问题中最大的问题。

3.3 并行蚁群

在这种方法中，每只蚂蚁（附件）被分配参与构建其解决方案，一个单独的进程。在mgt; P的情况下，汇聚一批每个处理器上的蚂蚁是必需的。主处理器负责接收用户输入，将在随机解决方案选择起点蚂蚁，执行所述全局信息素更新和产生输出。它也可能作为从机以确保更有效的实现。

这种技术有一个适度的通信开销。最大组成部分是维持分开的信息素的结构。该算法的各个步骤完成之后，各蚂蚁必须为了满足本地信息素更新规则发送更新至的每个副本。

3.4 解决方案组件平行评估

在该算法的每个步骤中，每个蚂蚁检查所有可用的解决方案并从中选择一个之前的元素。如果限制需要进行评估，这是一个相当费时计算操作。由于每个解决方案的元件是彼此独立的，它们可以并行评估。因此，每个从属进程被分配相等数目的解决方案元素来评估。这适合高度受限的问题。

这种方法已在并行禁忌搜索中广泛使用，请参阅Randall和Abramson.

3.5 蚂蚁和解决方案组件并联评价组合

给定足够的可用处理器，前两次的组合策略是随机的。在这种情况下，每个蚂蚁被分配的处理器的数目相等（一个小组）。在每个组，一组主负责构建蚂蚁的路线和委托的解决方案元素的评价。例如，每个蚁群给定10只蚂蚁（如在ACS[5]常用）和两个处理器，这相当于20个处理器。对于现代并行机，这并非是不合理的要求。

  1. TSP的应用

在本文中，TSP作为上述并行方案之一，即对并行蚂蚁方案经验进行评估，仅此方案试用，原因如下：并行蚁群相互通信的开销对TSP来说太大。然而，对于其他问题如网络综合问题（见[15]）中，具有更小的信息素结构，这种技术会更合适。解决方案要素技术的并行评价（和以后蚂蚁并联算法和解决方案要素技术的评价的组合）是唯一有效的，如果一个元素的评价的成本高（即，计算是昂贵的或者有许多与难约束来评估），这就不适合的TSP的情况。再次，网络综合问题将受益于这种方法。

图2和图3描述了主程序和附件活动和交流使用的并行蚂蚁方案的伪代码。请注意，术语 蚂蚁 和 奴隶 在本文的其余部分可互换使用。在此算法中，每个进程代表一个蚂蚁和维护其自身的信息素矩阵，这些信息随整个程序的运行逐渐性的更新。这样做是为了保证通信的一个最小量。然而，可以预期，该通信开销的大部分将在信息素的更新。

  1. 实际计算

许多TSP问题的实例已选定用来测试ACS工具。这些问题来自TSPLIB[16]，并在表1中给出。

图2 蚁群并行策略算法应用到TSP的主进程的伪代码

图3 蚁群并行策略算法应用到TSP，附进程的伪代码

这些问题是，在使用在表2中给出这些已设定的参数运行时发现在[5,6]中有良好的性能。用于执行实验的计算机平台是IBM SP2，具有18个RS6000模型590处理器每个节点有266 GFLOPS的峰值性能。最多8个专用处理器，可用于这台机器上的并行计算。

平行实验服从了报告中的描述的准则[2]。

表1 本研究中用到的问题实例

表2 本研究中所用参数的设定

并行算法的有效性的最常见的测量是由加速比给出的.加速比的定义如下：

(6)

根据Barr和Hickman，平均值不能用于公式(6)，需要给加速比新的定义。其结果是，只有一个每种子问题实例（和处理器分组为方法4和5）被使用公式中的分子（6）由CPU时间，而分母是由挂钟时间测定。联码的效率按下面的公式计算得到：

(7)

结果在表3中展示。对于小问题，因为通信量意味着由并行代码所花费的时间远远超过了串行代码，这表明并行化是无效的，适得其反。然而，当平行效率稳定（接近线性）增加时，增加了处理器数量和问题规模。当城市的数量超过200个事，并行算法的偶是就会比较明显。

图4所示图形使用六个处理器。虽然其他情况下加速比较差，即加速比gt;1是图和表3显示实现了问题lin318以上，以3.3的最高增速。 加快本增效作为问题大小的增加。因此，对于大的问题，这并行策略可以用来减少的所需要的实际收敛时间。

为了进一步研究并行行为，实验串行分数对于并行化获得效益四个更大的问题来计算，Karp和Flatt的方法后.这个量通过下式计算出：

。

表3 并行加速和效率的结果。每个单元中的第一项是速度提升，而第二项是效率

对于每个问题，绘制针对使用的处理器的数量的结果，示于图5可以看出，实验的效率随着问题的规模的增加而变得显著，这意味着提高了并行性能。实验表明需要大约至少需要6个处理器，当问题规模扩大之后，处理器的数量也会随之变大。

图4 使用6个处理器的每个问题的加速比

图5 每个问题的实验串行比

然而，为了获得的实验结果，也并不是处理器的数量越多越好。

这一措施的意义可以看出，当实验串行比可用于导出使用Amdahl定律的理论最大加速比。对于代码与s的串行部分，这个规定的增速接近上限四个问题的理论最大加速比如图6所示.虽然有问题的规模日益扩大，当问题规模扩大时，加速比增加的速度减慢了。此外，如果下降趋势仍在继续，用更大规模的问题来进一步验证。另外，从表3中可以看出，当使用一个比较普通的处理器数量时，也可以得到最大的加速比。

图6 每个问题的理论最大加速比

这表明，当问题的规模扩大后，使用更多的处理器将产生显著的效果。

  1. 结论

并行技术是否有效最终取决于问题的本质是否被解决。对于问题的大部分计算集中在问题解的有效性的评价时，方法3-5比较适合。像TSP问题，其中每个待解决的子问题是很容易计算的，但每个解决方案包含很多这样的内容，方法3比较适合。对于具有小信息素结构的问题，方法2是可行的选择。以上规则只指导ACO的并行元启发式，因此，一个更加正式和通用的选择应当做进一步的研究。

本文的并行蚁群方案中对用并行蚁群算法解决旅行商问题的方案进行了评价。一个主蚂蚁进程用于协调其他从属蚂蚁的活动。 这个方案是对MIMD流行的MPI模型概念的简化。结果表明，可接受的加速比和效率对于较大的问题DNgt;200是试用的。然而，缺点之一是保持信息素矩阵需要大量的沟通。与更大的问题和处理器的更多数量完全表征该方案的可扩展性需要进一步研究。

如果算法纳入一个更大的并行组件，并行效率将提高。例如，在他们的巡演的施工结束，每个蚂蚁可以添加一个本地搜索。另一种方法是使用共享存储器电脑。我们今后的工作将集中在减少（包括绝对和相对）迭代的次数和通信的频率。我们也调查候选列表策略，通过在每个步骤每个蚂蚁检查的节点以减少解的数量。候选列表策略与并行策略有效的相结合应该产生有效的ACO解决方案。

目前，我们的并行代

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[151017]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章