英语原文共 26 页，剩余内容已隐藏，支付完成后下载完整资料
摘要
用蚁群函数的方法进行了类比，提出了一种新的计算范式的定义，我们称之为蚂蚁系统。我们提出了一种可行的随机组合优化新方法。该模型的主要特点是正反馈、分布式计算和建设性贪婪启发式的使用。正反馈解释了快速发现好的解决方案，分布式计算避免了过早收敛，贪婪启发式有助于在搜索过程的早期阶段找到可接受的解决方案。 将所提出的方法应用于经典的旅行推销员问题(TSP)，并报告了仿真结果。本文还讨论了参数选择和模型的早期设置，并与TSP的禁忌搜索和模拟退火进行了比较。为了证明该方法的优秀性，我们展示了蚂蚁系统(AS)如何应用于其他优化问题，如非对称旅行商、二次分配和作业车间调度。最后，我们讨论了AS的显著特征-全局数据结构修正、分布式通信和概率转换。
导言
本文定义了一种新的通用启发式算法，可用于解决不同的组合优化问题。新的启发式有以下可取的特点：
- 它具有通用性，因为它可以应用于相同问题的类似版本；例如，从旅行商问题(TSP)到非对称旅行商问题(ATSP)有一个简单的扩展)。
- 它能力很强大。它可以应用于其他组合优化问题，如二次分配问题(QAP)和作业车间调度问题(JSP)。
- 这是一种基于人口的方法。这很有趣，因为它允许利用积极反馈作为搜索机制，如本文后面所解释的。它还使系统能够并行实现（尽管本文没有考虑这一点）。
这些理想的特性被一个事实所抵消，即对于某些应用程序，蚂蚁系统可以通过更专门的算法来优于它。其他流行的方法，如模拟退火(SA)和禁忌搜索(TS)所共有的问题，我们将其与蚂蚁系统进行比较。然而，我们认为这，与SA和TS的情况一样，我们的方法是有意义的，因为我们的方法在问题的应用中是有意义的，这些问题虽然与众所周知的和研究过的基本问题非常相似，但却存在着使标准性能最好的算法无法应用的特点。例如，ATSP就是这种情况。
在本文所讨论的方法中，我们将搜索活动分布在所谓的“蚂蚁”上，即具有非常简单的基本能力的代理，在某种程度上模拟了真实蚂蚁的行为。事实上，对真实蚂蚁行为的研究极大地启发了我们的工作（见[10]、[11]、[21]）。伦理学家研究的过一个问题，像蚂蚁这样几乎失明的动物如何能够建立从它们的殖民地到食源和回来的最短路径。研究发现，用于在个体之间传递关于路径的信息，并用于决定去哪里的媒介由信息素轨迹组成。一只移动的蚂蚁在地面上放置一些信息素（不同数量），从而通过这种物质的踪迹标记路径。虽然孤立的蚂蚁基本上是随机移动的，但遇到先前铺设的踪迹的蚂蚁可以检测到它，并以很高的概率决定跟随它，从而用自己的信息素来增强踪迹。出现的集体行为是一种自催化行为，其中蚂蚁跟踪越多，跟踪就越有吸引力。因此，该过程的特点是一个正反馈回路，其中蚂蚁选择路径的概率随着先前选择相同路径的蚂蚁数量的增加而增加。
例如，考虑图中所示的实验设置。1. 有一条蚂蚁行走的路径(例如从食物来源A到巢E，反之亦然，见图1a)。突然出现一个障碍，小径被切断了。因此，在B位，蚂蚁从A到E(或D位，朝相反方向行走)必须决定是向右还是向左(图1b)。选择受前面蚂蚁留下的信息素轨迹强度的影响。在正确的路径上更高水平的信息素会给蚂蚁更强的刺激，从而更高的右转概率。到达点B(或D)的第一个蚂蚁具有相同的右转或左转的概率（因为在两个替代路径上没有以前的信息素）。由于路径BCD比BHD短，跟随它的第一个蚂蚁将在第一个蚂蚁跟随路径BHD之前到达D(图1c)。结果是，从E到D返回的蚂蚁将在路径DCB上找到一个更强的路径，这是由所有偶然决定通过DCBA接近障碍物的蚂蚁中的一半和通过BCD到达的蚂蚁所造成的：因此，它们更喜欢（概率）路径DCB而不是路径DHB。因此，每单位时间跟随路径BCD的蚂蚁数将高于跟随BHD的蚂蚁数。这导致信息素在较短路径上的数量比在较长路径上生长得更快，因此，任何一只蚂蚁选择要遵循的路径的概率都很快地偏向于较短的路径。最后的结果是，所有的蚂蚁都会很快选择较短的路径。
我们将在下一节中定义的算法是从对真实蚂蚁群的研究中导出的模型。因此，我们称之为蚂蚁系统(AS)，并介绍了蚂蚁算法。由于我们对模拟蚂蚁群落不感兴趣，但在使用人工蚂蚁群落作为优化工具时，我们的系统将与真实（自然）的系统有一些重大差异：
- 人工蚂蚁会有一些记忆，
- 他们不会完全失明，
- 他们将生活在一个时间离散的环境中。
e e e
d
h
障碍
c
b
d
h
障碍
c
b
a a a
- b) c)
1.一个真实蚂蚁的例子。
-
- 蚂蚁遵循A点和E点之间的路径。
- 一个障碍被插入；蚂蚁可以选择沿着两条不同的路径中的一条走，概率相等。
- 在较短的路径上，更多的信息素被放置下来。
然而，我们认为蚁群隐喻可以用来解释我们的模型。考虑图的图形。这是对之前所讲的情况的一种可能的解释图b。为了修复这些想法，假设D和H之间、B和H之间以及B和D之间的距离-通过C-等于1，并让C位于D和B之间的一半(见图2a)。现在让我们考虑在正则离散化时间间隔中发生的事情：t=0，1，2，.... 假设30只新蚂蚁从A到B，30只蚂蚁从E在每个时间单位走，每只蚂蚁以每个时间单位1的速度行走，当一只蚂蚁在时间t处放置一条强度为1的信息素轨迹，为了使示例更简单，在连续时间间隔的中间完全瞬间蒸发(t 1，t 2)。
在t=0还没有踪迹，但30只蚂蚁在B，30只蚂蚁在D。他们选择走哪条路完全是随机的。因此，平均每个节点的15只蚂蚁将向H和15只蚂蚁向C(图12b)。
在t=1，从A到B的30只新蚂蚁在通往H的道路上发现了一条强度为15的小径，这条小径由15只从B到C的蚂蚁铺设，在通往C的道路上找到了强度为30的小径，这是从B到D的15只蚂蚁和从C到D的15只蚂蚁铺设的小径的总和(图2c)。因此，选择路径的概率是有偏差的，因此朝向C的蚂蚁的预期数量将是朝向H：20和10的蚂蚁的两倍。来自E的D中的新30只蚂蚁也是如此。
这个过程一直持续到所有的蚂蚁最终都会选择最短的路径。
2. 人工蚂蚁的一个例子。
- 具有距离的初始图。
- 在t=0时，图边上没有轨迹；因此，蚂蚁选择是以相等的概率向右或向左转弯。
- 在时间t=1条小径在较短的边缘上更强，因此，在平均值中，蚂蚁更喜欢这条小径。
其思想是，如果在给定的点上，蚂蚁必须在不同的路径中进行选择，那么前面的蚂蚁（即那些具有较高路径级别的蚂蚁）大量选择的路径就具有更高的概率。此外，高轨迹水平是短路径的同义词。
2.蚂蚁系统
在本节中，我们将介绍AS。我们决定使用著名的旅行商问题[26]作为基准，以使与其他启发式方法的比较更容易[20]。虽然模型定义受问题结构的影响，但我们将在第七节中表明，同样的方法可以用于解决其他优化问题。
给定一组n个城镇，TSP可以被描述为寻找一个最小长度的封闭旅游，访问每个城镇一次的问题。 我们叫Dij 城镇I和j之间路径的长度；在欧几里德TSP的情况下，dij 是i和j之间的欧氏距离(即。dij=[(xi-xj)2 i-yj)2]1/2)。图(N，E)给出了TSP的一个实例，其中N是集合的城镇还有e是的准备好了的边缘之间城镇(a完全连接图表在的欧氏TSP)。
让bi=1，...，n，...，n)是当前小镇在时间t时的蚂蚁数量，让蚂蚁总数
每只蚂蚁都是简单的代理，具有以下特点：
是
-
- 它选择城镇去的概率，这是一个函数的城镇距离和数量的小径存在的连接边缘；
- 为了迫使蚂蚁进行合法的旅行，到已经访问过的城镇的过渡被禁止，直到旅行完成为止（这是由禁忌列表控制的）；
- 当它完成一次旅行时，它在每一个访问的边缘(i，j)上放置了一种叫做小径的物质。
当ij在时间t上，每只蚂蚁在时间t上选择下一个城镇，它将在时间t 1。 因此，如果我们调用AS算法的迭代，m蚂蚁在区间(t，t 1)中进行的运动，那么算法的每n次迭代（我们称为周期），每个蚂蚁都完成了一次旅行。此时，根据以下公式更新跟踪强度
当是一个系数，使得（1-）表示时间t和t n之间的轨迹蒸发，
当k-蚂蚁在时间t和t n之间放置在边缘(i，j)上的每单位长度的TRAIL物质（真蚂蚁中的信息素）的数量；
其中Q是常数，Lk 是第k只蚂蚁的游览长度。
系数rho;必须设置为1lt;值，以避免无限积累的跟踪（见注1）。 在我们的实验中，我们将轨迹的强度设定在时间0，tau;ij（0）到一个小的正常数c。
为了满足蚂蚁访问所有n个不同城镇的约束，我们将一个名为tabu列表的数据结构与每个蚂蚁关联起来2这节省了已经访问过的城镇的时间t，并禁止蚂蚁在n次迭代（巡演）完成之前再次访问它们。当旅行完成时，使用禁忌列表计算蚂蚁的当前解决方案（即蚂蚁所遵循的路径的距离）。然后清空tabu列表，蚂蚁可以自由选择。我们定义了禁忌k的动态的不断增长矢量其中包含的tabu名单s的n的蚂蚁，tabu k 从禁忌元素中获得的集合k还有tabu k(s)清单的第s部分(即目前第k只蚂蚁访问的第s个城镇旅游)。
我们称之为能见度ij 数量1/dij。此数量在AS运行期间不被修改，而不是根据前面的公式（1)更改的跟踪）。
我们定义了k-蚂蚁从城镇I到城镇j的过渡概率为
在允许的地方k={-tubak}，其中alpha;和beta;是控制相对重要性的参数的小径相对于能见度。 因此的过渡概率是a权衡在可见性（这意味着应该以高概率选择接近的城镇，从而实现贪婪的建设性启发式）和时间t的跟踪强度(这意味着如果在边缘(i，j)有大量的流量，那么它是非常可取的，从而实现了自催化工艺)。
3.算法
给定上一节的定义，所谓的蚂蚁周期算法简单地说明如下。在时间为零的时候，一个初始化阶段发生，在此阶段，蚂蚁被安置在不同的城镇上，初始值tau;ij（0）在边缘设置跟踪强度。每个元素的第一个元素蚁的tuba名单是准备好了去是平等去它的开始吧小镇。此后每个人蚂蚁移动从第一镇去小镇 j 选择小镇快走去与 a 的概率，那个是 a 的职能(与参数alpha;和beta;见公式(4))的二可取性措施。首先，的小径 tau;ij(t)， 给予有关的信息怎么做很多蚂蚁在的过去已经被选中了那个一样边缘(i，j)；第二，的能见度tau;ij他说那个的更近一点小镇的更多可取的它是 a 。很明显，设置alpha;= 0,小径水平是不再是了审议，还有 a 随机的贪婪算法与多重开始吧要点是已获得。
经过n次迭代，所有蚂蚁都完成了一次旅行，它们的禁忌列表将是满的；此时，对于每个蚂蚁k，L的值k 是计算还有价值lk根据公式（3)更新）。此外，蚂蚁找到的最短路径(即最小Lk，k=1，...，m)被保存和所有的禁忌列表都是空了。这个过程是迭代直到tour计数器到达的最大值(用户定义)周期数NC最大值或者所有的蚂蚁都做同样的旅行。 我们称之为最后一种情况停滞行为，因为它表示算法停止寻找替代解决方案的情况。我们在第四节中调查了这种情况。
ij
形式上蚂蚁循环算法为：
1。 初始化：
设置t：=0 {t是时间计数器}
设置NC：=0 {NC是循环计数器}
对于每个边(i，j)设置初始值tau;ij(t)=c用于追踪强度和∆tau;ij= 0把m蚂蚁放在n上 节点
- 集合s：=1 {s是禁忌列表索引}
对于k：=1到m做把k蚂蚁的起始镇放在塔布k(s)
- 重复直到tabu列表已满 {此步骤将重复(n-1)次}
集合s：= 1
对于k：=1到m做选择城镇j移动到，概率pk (t)由等式（4)给出）在时间上，第k蚂蚁在我=塔布镇k(s-1)}把第k只蚂蚁搬到j镇在塔布插入城镇jk(s)
ij
- 对于k：=1到m做
从塔布移动第k蚂蚁k(n)到塔布k(1)计算长度Lk 由k-th描述的旅行 蚂蚁 更新发现的最短游览
对于每个边(i，j)，k=1
- 对于每个边缘(i，j)计算根据方程
ij
蚁周期算法的复杂度为Omicron;(NC.n2.m)如果我们在NC周期后停止算法
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[405728]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
