并行蚁群算法

并行蚁群算法（精选7篇）

并行蚁群算法 篇1

0 引言

1992年，在M.Dorigo的博士论文中首先提出了蚁群算法[1]。该算法是一种基于蚂蚁觅食的生物行为的元启发式搜索算法。开始该算法用于在图中寻找一条最优路径。随后它被应用到了一系列的优化问题中，并且随之衍生出多个ACO的变种，比如MMAS、AS、ACS等。

在原始的蚁群算法中，蚁群中的多只蚂蚁通过协作搜索最优解。蚂蚁之间通讯是通过信息素完成。蚂蚁在觅食的路途中会留下信息素，其它蚂蚁寻路的过程中会选择信息素堆积较多的路径。在真正的蚁群算法的实现过程中，为了防止信息素堆积过快而导致产生过早收敛(又称“假收敛”，即只找到了局部的最优解，并没有获取全局的最优解即发生了收敛)的问题，又引进了信息素的挥发和启发式信息。信息素的挥发有效阻止了信息素的过早收敛，而搜索中的随机启发式信息，使得搜索路径更加发散。

本文的组织如下：第二部分对并行ACO进行扼要的介绍，对现行的相关ACO并行算法进行总结。第三部分提出了一种新的思想，基于任务分发的并行ACO。最后(第四部分)进行了相关的总结以及下一步工作的展望。

1 ACO的并行策略

1998年，Tomas Stutzle也探讨了蚁群的并行策略[3]。他提出了一种最简单的并行方法：在MIMD中，每个节点上走一个蚁群，这些蚁群独自工作，相互之间不交流信息。他在MMAS上的实验表明，这种方法有很好的性能。实际上，这是Bullnheimer等人提出的异步并行策略的一种极端情况。它最大限度地减少了处理器节点之间的通信，更加强调算法的独立运行。

Randall[4]对以上的思想进行了总结，并且在一个真正的并行环境下借助MPI库实现了ACS蚁群算法，得出的结果显示出了并行蚁群的优越性。

Chu[5]在提出了PACS，并行蚁群，他的主要思想是将一个大的蚁群分成一些小的蚁群，这些小的蚁群首先独立工作一段固定的时间或者固定的代数，然后再相互交流信息。这个系统的优点在于综合了Tomas Stutzle的思想和并行蚂蚁思想。它比并行蚂蚁有更少的通讯量，而且各个节点之间相互有所交流，因此能产生比Tomas纯粹的并行蚁群更好的解。

在Chu的基础上，陈崚教授提出了自适应的并行蚁群算法[6]。该算法的核心思想是每个处理器节点根据自身的情况选择跟哪些处理器进行交流信息。

总结以上的观点，得出的一些对本文有启发意义的观点如下：

尽量减少通信是并行ACO设计中最关键的因素;

粗粒度的并行蚁群性能要优于细粒度的蚁群;

目前主要以MIMD的体系结构为主，但是共享内存的SMP架构有利于减少通信;

性能的评价主要有是解的质量和加速比。

本文的思想是在MIMD架构的基础上，通过主控节点对各计算节点进行控制，优化通信时间与计算时间的比例，减少通信量。

2 TD的设计

Ian Foster提出[7]了四步并行算法设计方法，即划分、通信、聚集和映射。其核心思想为，减少通信，负载均衡。TD的设计也即从这一思想出发，采取了功能划分方法，避免不必要的通信，同时要加强对工人(即人工蚂蚁)的控制。

2.1 相关定义

管理者：管理者是指集中是管理中的主控线程，该线程负责算法运行中的同步、任务分发、IO以及信息素更新等信息。管理者会通过广播详细的方式通知工人节点各种信息。

工人：工人是指系统中的计算节点，该节点负责具体的计算任务，除了完成路径搜索任务与接受管理者信息之外，该节点还会同管理者进行主动通信，告知管理者任务已经完成或者发送搜索结果等。该概念对应于原始蚁群算法中的人工蚂蚁。

任务：一个任务就是一次在解空间中单独的搜索。

以下是三者之间的关系图示：

2.2 设计思路

首先，设计是基于MIMD并行系统的。虽然相对于集中式内存管理的硬件系统(SMP架构)，MIMD需要的通信量更大，但是由于目前MIMD架构成为了并行系统的趋势，因此我们仍然采用了基于MIMD的系统架构。

其次，信息素的管理采用集中式管理。所有的节点共享信息素。该信息素存储在主控节点上。每一个节点维护一个本地记录，该记录统计并且维护当前找到的最有解。由主控节点负责所有工人的同步工作。

主控节点负责的任务有：IO操作;向工人节点分发信息素矩阵以及任务;每轮任务结束后负责收集工人的劳动结果并进行统计，更新信息素矩阵。在每一轮任务开始之前，主控节点有一个任务队列，任务队列的长度或者由一个预先设定的时间决定，或者由预先设定的搜索代数决定。工作准备阶段，主控节点向每个工人发送初始任务以及信息素矩阵。虽有任务分发完毕之后，主控节点广播一个“任务结束”信息。各个工人节点收到此信息后，一旦手头工作完成，即向主控节点发送任务“完成报告”，该报告信息中包含了其搜索的结果。然后主控节点对这些信息进行统计并更新，完成后启动下一次搜索。

主控节点负责的任务有：IO操作;向工人节点分发信息素矩阵以及任务;每轮任务结束后负责收集工人的劳动结果并进行统计，更新信息素矩阵。

工人节点的任务是：在构建解的过程中，每个处理器节点完成一次搜索任务之后需要对自己节点上的相关数据进行更新。当手头任务完成之后，主动向主控节点发送任务请求信息，请求再次分配任务。在收到主控节点的结束信号之后，向管理者节点发送自己目前的搜索结果，并且等待下一轮的工作。

2.3 构建解（启发式信息的任意性）

对于MAX-MIN Ant System，在构建解的过程中，所利用的路径选择函数如下：

在构建解的过程中，为了使得各个工人节点尽量发散，在每个处理器节点上都要使用不同的启发式信息权重。这样的结果是各个处理器的搜索侧重点不同：有的更加侧重于沿着信息素信息搜索，而其他的更加侧重于随机启发式信息。在实现过程中，要求主控节点为每一个工人节点随机地产生一个β值。

在收到主控线程的任务分发完毕的信号之后，如果该进程发现自己手头仍然有多于N(N视情况而定，经验值建议设为3)个的任务，则将这些任务抛弃，即完成当前的搜索后立即上报搜索结果。

2.4 任务分发

任务分发由主控节点(管理者)完成。

初始时，管理者设定一个总任务数。该数目通常视要求而定，如果要求是减少搜索时间，则可以设定一定的时间，如果时间结束，则任务分发完毕;如果要求提高解读质量，则可以设定具体的任务数目，完成所有任务则结束该轮循环，进行相关的统计更新操作。

在工作过程中，如果某个收到某个节点的“空闲”信息，则立即为其分发一定数量工作。

管理者瓶颈的解决方法：

显然，同其他的master-slave方法一样，该方法的缺点在于，主控节点的通信量过大，而且执行任务过多，从而成为算法的瓶颈。我们尝试从以下的方面去改善之。

首先，采取任务预取方式。每一轮工作开始时，管理者为每个工人分发多个任务，而不仅仅分发一个任务。另外，当某工人空闲时，分配给该节点的任务数也要大于1。

其次，在广播相关的信息时，可以采取树状广播方式。具体广播方式如下图。

3 结论及TD的进一步探讨

基于TD(task-distribution，任务分发)模式的并行蚁群算法在设计过程中遵循了并行算法设计的两个主要原则：减少通信量与增加处理器节点的使用率。相比于串行蚁群算法，并行算法充分利用了蚂蚁在独立搜索解空间时的并行性，并且通过并行通讯交流信息素。与前文所提到的很多并行算法相比，该算法最大的优点是，在尽量减少节点之间通信的基础上，最大限度地实现了各个处理器节点之间的负载均衡。并且引入了非一致启发式信息，使得各个节点在搜索的过程中，尽量发散搜索，防止过早收敛。

参考文献

[1]Marco Dorigo,Thomas Stutzle.Ant Colony Optimization.Reading,MIT Press.

[2]Bullnheimer Bernd,Kotsis Gabriele,Strau Christine.Report Series SFB《Adaptive Information Systems and Modelling in Economics and Management Science》,Nr.8,October 1997.

[3]Thomas Stutzle.Parallelization Strategies for Ant Colony Optimization.In LNCS:722-731.

[4]A Parallel Implementation of Ant Colony Optimization.

[5]Parallel Ant Colony Systems.

[6]自适应的并行蚁群算法.

[7]Ian Foster.Designing and Building Parallel Programs:Concepts and Tools for Parallel Software Engineer.Reading,MA:Addison-Wesley,1995.

并行蚁群算法 篇2

1 C++AMP介绍

GPU计算由来已久, 已经成熟的接口包括NVIDIA的CUDA C和AMD的OPENCL接口, 随着微软公司Visual Studio 2012的发布, 在Build大会上微软向大家呈现了一种新的GPU并行计算模式C++AMP, 其最低运行环境是:Win7系统+Visual Studio 2012+Direct X11, 所以它比另外两种并行端口适用范围更广, 可以实现真正意义上的跨平台运行。C++AMP采用面向对象的C++语言开发, 支持CPU, GPU等跨平台编译运行, 具有逻辑结构简单、数据隐式拷贝、自动负载均衡等特点, 可以快速、稳定地实现并行计算。

一个C++AMP计算过程中最重要的包括:

(1) 数据, 其基本数据类型有array<T, N>, array_view<T, N>, index<N>, extent<N>, tiled_extent<D0, D1, D2>, title_index (D0, D1, D2>, accelerator, accelerator_view, texture<T, N>等;

(2) 迭代函数parallel_for_each函数, 是C++AMP并行计算的核心部分, 负责线程开辟、核函数计算等工作, 基本的计算过程由核函数指定, 通常核函数为Lambda表达式, 也可以是由限定符restrict (amp) 限定的GPU函数;

(3) 线程索引index类, 线程开辟大小extent类, 他们两者是一一对应的。如果extent是二维的, 则index也是二维的, 由index类对象来实现对线程的惟一标示;

(4) 数学函数, 数学函数库有双精度数学函数与快速数学函数两种, 根据需要选择。

C++AMP的执行模式是由CPU线程控制、由parallel_for_each函数作为详细设置、由核函数完成核心计算任务、数据隐式拷贝的执行模型。程序开始运行时, 只有CPU主线程活动, 当执行到并行区域时, 主线程根据parallel_for_each函数的设置, 启动GPU线程组来完成相应的计算任务, 最后拷贝数据回CPU主线程, 这时GPU线程挂起或者退出, 控制流又回到CPU主线程中。

2 蚁群算法介绍

为了更加清楚详细地描述蚁群算法, 本文借助经典的TSP问题来描述 (TSP问题:已知n个城市以及城市两两之间的距离, 求一条遍历所有城市的最短路径, 除初始城市之外每个城市访问且仅访问一次) 。

蚁群算法可以定义如下:设有n个城市, m个蚂蚁, 任意城市i与城市j之间的距离为d (i, j) , 启发函数定义为η (i, j) =1 d (i, j) , 任意城市i与城市j之间的信息素浓度为τ (i, j) , 并且初始时刻信息素浓度相同, 蚂蚁k经过城市i转到城市j的概率计算公式如下所示:

式中:J (k) 是蚂蚁k下一步允许选择的城市的集合;α, β为权重系数。当所有蚂蚁都完成一次循环后, 对信息素矩阵进行更新操作, 这样, 新时刻路径 (i, j) 上的信息素浓度采用调整式 (2) 进行调节:

式中:ρ (0<ρ<1) 表示信息素保留程度, 其值越大表示信息素挥发速率越慢;Δτk (i, j) 表示在本次循环中第k只蚂蚁在路径 (i, j) 上的信息素贡献。每只蚂蚁的信息素贡献可以用式 (3) 进行计算:

式中:Q是信息素强度, 它影响算法的收敛速度;Lk表示第k只蚂蚁在本次循环中所有的路径总和[4]。

3 并行蚁群算法

根据上述介绍, 可以看出每只蚂蚁寻找自己路径依赖于上次循环产生的信息素矩阵以及各城市之间的静态路径长度, 两两蚂蚁之间没有信息素交流, 经过分析, 这是一种符合SIMD模型的过程, 故可以将每只蚂蚁寻找最优路径的过程并行进行, 从而加速算法计算。并行蚁群算法可以用如下算法进行描述:

Step1:初始化所有参数、变量, 如权重系数α, β;蚂蚁个数m;最大迭代步数NC;信息素矩阵初始值τ (i, j) =1。

Step2:按照蚂蚁个数分配线程, 每个线程代表一只蚂蚁。每只蚂蚁独立构造一个解 (解即一条遍历所有城市的路径) , 详细描述为:蚂蚁k随机选取一个城市i作为自己的初始点, 再根据转移概率公式计算转移概率pkij;根据概率最大者选择下一个城市j, 从而蚂蚁走过路径为 (i, j) 。若当前路径长度大于上一循环求得最短路径长度, 则结束本次循环;否则继续循环, 直到蚂蚁k寻找到一个解。

Step3:规约Step2中所有蚂蚁产生的解, 求解出所有解中的最优解和最优值进行保存操作。

Step4:根据当前最优解和最优值信息, 进行信息素矩阵更新操作。

Step5:判断是否满足结束条件, 若满足, 则输出最优解和最优值;否则, 循环执行次数+1, 转Step2。结束条件为循环次数大于NC或者当前解已经稳定 (通常两步解出的最优解与最优值相同即可认为当前解已经稳定) 。

串行蚁群算法的时间复杂度为O (NC⋅m⋅n2) , 计算量主要集中在蚂蚁各自构造一个解的过程。蚁群算法在一代迭代中包括蚂蚁独立求解、相互交流得到较优解和改变信息素的过程, 且信息素的改变直接影响下一代概率计算的结果, 从而产生不同的解, 并向较优解进化。由于把算法并行化, 采用每只蚂蚁并行寻找路径的模式进行, 则并行蚁群算法的时间复杂度减小为O (NC⋅n2) , 使算法有明显的加速。

4 数值实验

4.1 实验环境

实验环境采用NVIDIA Ge Force GT 440环境, 具体参数配置如表1所示。

4.2 数值结果

数值实验采用的数据为随机生成的二维坐标, 取值范围在[0, 1 000], 分城市数目n、蚂蚁数目m、迭代次数NC等三个参数进行实验分析, 实验结果如表2所示。

由表2前三行可知, 串行时间与并行时间随着迭代次数的增加呈现线性增长趋势, 这也符合第3节的理论推导, 此时串行时间与并行时间相当, 加速比在[1-0.01, 1+0.01]范围之内, 可以认为此时没有加速效果。由此三行知道, 加速比和运行时间都与迭代次数无关。下面选取小的迭代次数来进行数值实验, 分析城市数目与蚂蚁数目对串行时间、并行时间、加速比的影响。

由表2整体可以看出, 当城市数目及蚂蚁数目较大时, 对数据普遍有加速效果。由表2第4~6行分析可知, 固定城市数目, 随着蚂蚁数目增大, 串行时间呈现线性增长, 而并行时间的增长率小于线性, 加速比越来越大。这是由于并行线程数目是以蚂蚁数目为参数的, 蚂蚁数目越大, 并行线程数目越多, 从而使得并行时间增长率比线性还小。但是此时并行时间并没有遵循第3节分析的函数O (NC∙n2) , 这是由于虽然并行线程开辟了m个, 但是最终的物理执行过程同时运行的线程个数为96个 (SP个数) , 又涉及到CPU-GPU异构通信时间, 从而使得整体并行时间没有按照理论分析的结果。并行线程数目m越大, 负载相对越均衡, 物理资源占用越充分, 从而加速效果越来越明显, 直到达到相应的物理瓶颈。这也可以由表2的7, 8行得出。

由表2中的第5, 7行和第6, 8行可以对比出, 蚂蚁数目m一定时, 城市数目n对于串行、并行算法时间的影响。对比5, 7两行可以看出, 蚂蚁数目大体一样, 城市数目改变量比较大, 其加速比相差不大;对比6, 8两行可以看出, 蚂蚁数目一样时, 城市数目的改变对于整个算法的加速比影响并不是很大。这个也可以从并行程序中串行执行部分、数据交换所用时间以及算法本身所用时间方面进行分析, 这个加速效果是合理的。

5 结论

并行蚁群算法 篇3

蚁群优化算法[1]是一种全局性邻域搜索算法,具有分布式计算、信息正反馈和启发式搜索的特征,易于与其它方法相结合。该算法得到了具有NP难度的旅行商问题(TSP)[2]的最优解,并应用到连续空间[3]和数据挖掘[4]中。但是蚁群算法也存在着一些缺陷。寻找“精解”和“快速收敛”两者的平衡点成为蚁群算法发展和应用的关键。

并行蚁群算法[5]是最近提出的一种优化结果较好的算法,该算法将所有蚂蚁分为几个子种群,并进行种群间的信息交流。但是其子种群的规模的预先确定有很大的难度:若规模过大,则种群多样性容易被破坏,搜索能力下降;若过小,则使得搜索时间增加。因此,本文中引入“蚂蚁聚度”的概念[6],通过设定“聚度阈值”来自动调整子种群的规模,提出了自适应的并行蚁群算法。传统的蚁群算法以及改进的Ant-Q System[7]和MAX-MIN[8]模型都存在着全局寻优能力不强的缺点,小生境技术[9]的引入正是为了解决这一问题。当自适应并行蚁群系统进入停滞阶段时,除了保留部分蚂蚁对局部最优点继续进行搜索外,其它的蚂蚁重新划分种群,并重新初始化信息素,然后对整个空间进行重新搜索。这样,在减少蚂蚁数量的时候也可以在信息量的“探索”和“利用”之间得到很好的平衡。通过对TSP问题进行计算,证明了该方法的有效性和可行性。

2 并行蚁群算法和小生境技术基本原理

2.1 并行蚁群系统(PACS:Parallel Ant Colony System)

在并行蚁群系统[5]中蚂蚁被分为几个不同的种群,并在一些合适的周期内,通过种群之间的信息交流策略来更新信息素。PACS与基本蚁群算法的主要不同在于:1)将所有蚂蚁分成若干个不同的种群;2)通过局部调整准则、全局调整准则和信息交流调整准则对信息素进行调整。

以n个城市的TSP问题为例说明PACS模型。首先作如下定义:G表示总的种群数目,Nk(K=1,2,…G)表示第k个种群中蚂蚁的个数,且满足蚂蚁总数m=Gk=Nk;dij(i,j=1,2,...,n)表示城市i和城市j之间的距离,τij(t)表示t时刻在城市i,j连线上残留的信息量。随着时间的推移,以前留下的信息逐渐消逝,用参数ρ、α、λ表示信息的挥发因子。所有蚂蚁完成一次迭代以后,各路径上的信息量根据下列准则作调整:

准则1(局部调整准则):局部调整是每只蚂蚁在建立一个解的过程中进行的。随着时间的推移,种群j中两个元素(城市)r和s之间的局部信息素数量要根据下式作调整:

其中Lnn表示用最近邻域启发式(nearest neighbour heuristic)得到的所有城市之间的最小距离。

准则2(全局调整准则):只有生成了全局最优解的蚂蚁才有机会进行全局调整,全局调整规则为:

其中Q是信息素强度,它影响算法的收敛速度。Lj表示第j个群体中蚂蚁找到的最短路径。

准则3(信息交流调整准则):信息交流准则是并行蚁群算法与ACS算法的主要不同点。每经过R1次循环,通过种群间的信息交流对信息素值进行调整。在本文中采用环形结构的种群间信息交流策略。

其中“neighbour”定义为在环形结构中的种群。Lng表示邻域("neighbour")种群中的最短路径。

2.2 小生境技术原理

小生境技术的提出为搜索空间的扩展提供了可能性。共享机制由Goldberg[10]提出,它通过共享函数调整群体中各个个体的适应度,以维护群体的多样性。共享函数是表示两个个体之间密切关系程度的函数,记为sh(dij),dij表示个体i与个体j之间的某种关系。

3 嵌入小生境技术的自适应并行蚁群算法

用K代表子种群规模,则自适应的子种群规模可以通过如下公式确定:

其中σ是“聚度阈值”一般取常数。若聚度值较大,说明蚂蚁上一次从这个城市到达另外城市的路径相对集,在以后的搜索最优程中,过度强化正反馈信息引起停滞现象的可能性就越大。所以当sta大于阈值σ时,子种群规模就降低到最低限度2,以刺激种多样性的提高。相反,当城市聚度越小时,这个城市的信息量分布相对比较分散,导致收敛速度较慢。所以当sta较小时种群的多性较好,子种群由下式确定:

在确定子种群的规模后就按照上述并行蚁群算法的调整准则对信息量进行调整。

在自适应并行蚁群算法进入停滞后采用共享机制重新确定城市之间的信息量,对群体中信息素值较大(认为与局部最优点的相似度较高)的个体通过施加共享函数进行惩罚,阻止新蚂蚁种群再次陷入同一局部最优点。施加共享函数后城市间的共享信息素为:

共享函数sh(x)采用典型的三角共享函数:

式中τshare为共享信息量;τmax为自适应并行蚁群模型中的信息素最大值。

根据图2讨论共享函数对信息量的影响。不失一般性的认为距离局部最优点xi越近的点对应的信息量就越大(虽然会有个别点不满足这个条件,但在蚂蚁数量较多的情况下对结果的影响不会太大)。本文选取τshare=1/2τmax,假设共享前τi1=0.2τshare,τi2=0.4τshare,由式(7)可得x1、x2的共享度都为0,则共享信息素分别为τi1和τi2;同理如果τi3=1.6τshare,x3的共享度为0.6,共享信息量为0.4τi3。由此可见当蚂蚁距离局部最优点较远时共享信息量与原信息量相等;当蚂蚁距离局部最优点较近时共享信息量相应减小。由于蚂蚁在搜索过程中是通过感知信息素的数量进行路径选择的,所以这样的的处理达到了局部最优点对新初始化蚂蚁的排斥作用,能够有效避免蚁群再次陷入同一局部最优。

3.1 算法描述

1)初始化:将m只蚂蚁随机分为G个种群,第k个种群中蚂蚁的个数用Nk(k=1,2,…,G)表示。

2)重复运行直到禁忌表添满为止(这一过程将运行(n-1)次)

对每个蚂蚁,根据传统的选择概率,选择下一个要转移去的数据j;

将第k只蚂蚁转移到第j个数据;

进行局部搜索,根据公式(1)更新每只蚂蚁的信息素;

将数据j插入到禁忌表tabuk(s)。

3)计算种群中每只蚂蚁所走路径的总长度,找出此次搜寻中的最短路径lt。

4)全局信息素更新:在每一种群中按照公式(2)进行全局信息素的更新。

5)种群间信息交流:每经过R1次循环就根据公式(3)进行蚂蚁种群间的信息素交流。

6)自动划分种群规模:按照公式(4)自动地进行种群规模的划分。

7)如果(NC

8)种群重新初始化:当||lt-lt-1||<ε成立,认为自适应并行蚁群算法进入停滞阶段,引入小生境技术。

按照公式(6)计算共享信息素值;

9)当NC=NCMAX,或者出现停滞时,输出最优解,结束。

4 实例运算及性能分析

从通用的TSPLIB中选用TSP问题,用上述算法、MMAS算法和文献[6]提出的基于分布均匀度的蚁群算法进行了比较测试。根据多次实验所得结论,本文选择α=1,β=2,ρ=0.4,ε=0.5,“聚度阈值”σ根据城市个数的不同选择不同的数值(本文实验中选取为0.8×max sta)。更改蚂蚁的数目,每次迭代的NCMAX取1500次,分别运行50次取平均值列于表1中。

从表1可以看出当蚂蚁数目减少的时候,本文提出的方法较之基于分布均匀度的蚁群算法能够得到效果更好的解。这是因为小生境技术可以使得大部分蚂蚁的搜索具有较强的“爬坡”能力,使得解具有较好的多样性、全局性,避免了早熟现象。虽然在时间消耗上较之基于分布均匀度的蚁群算法要多,但综合考虑搜索结果和收敛时间,本文提出的方法在蚂蚁数量减少的情况下,保证了收敛速度和防止早熟之间的平衡。

5 结论

本文提出了自适应的并行蚁群算法,通过设定“聚度阈值”来自动调整子种群的规模。并行蚁群算表1蚂蚁数量变化对搜索结果的影响法同样存在着搜索多样性的不足、易陷入局部最优的问题,小生境技术的引入正是为了解决这一问题。当自适应并行蚁群系统进入停滞阶段时,除了保留部分蚂蚁对局部最优点继续进行搜索外,其它的蚂蚁重新初始化信息素,然后对整个空间进行重新搜索。通过共享函数来阻止蚂蚁向局部最优移动,这种方法既有效地摆脱了停滞的状态又保留了原有的较优解。

参考文献

[1]Dorigo M,Maniezzo V,Colorni A.Ant system:Optimization by a colony cooperating Agents[C].IEEE Transactions on Systems,Man,and Cybernetics-Part B:Cybernetics,1996,26(1):29-41.

[2]Dorigo M,Gambardella L M.Ant colony system:a cooperative learning approach to the traveling salesman problem[C].IEEE Transac-tions on Evolutionary Computation,1997,1(l):53-66.

[3]李向丽,杨慧中,魏丽霞.基于退火的蚁群算法在连续空间优化中的应用[J].计算机工程与应用,2007,43(23):74-76.

[4]LI X L,YANG H Z.Application of a Novel Algorithm on Clustering Analysis[C].Proceedings of the International Conference on Com-plex Systems and Applications,2006:836-840.

[5]Chu S C,Roddick J F,Pan J S.Ant colony system with communication strategies[J].Information Systems,2004,167(1-4):63-76

[6]陈崚,沈洁,秦玲,等.基于分布均匀度的自适应蚁群算法[J].软件学报,2003,14(8):1379-1387.

[7]Machado L,Schirru R.The ant-Q algorithm applied to the nuclear reload problem[J].Annals of Nuclear Energy,2002,29(12):1455-1470.

[8]Sttzle T,Hoos H.MAX-MIN ant system[J].Future Generation Computer Systems,2000,16(8):889-914.

[9]郏宣耀,王芳.一种改进的小生境遗传算法[J].重庆邮电学院学报:自然科学版,2005,17(6):721-744.

并行蚁群算法 篇4

在经典的调度问题中, 工件的加工时间被认为是一个常数, 然而在实际的生产过程中往往会因为机器效率, 工件自身的状态等外部原因使工件的实际加工时间有所变化。工件的实际加工时间会与它的加工顺序或者开工时间有关, 这样就产生了一类工件的加工时间随加工顺序或者开工时间的增加而变大的调度问题, 这种类型的调度称为退化调度。本文将对加工时间是加工顺序的简单线性函数的退化调度进行讨论。

1 问题的描述

并行机调度是研究n个工件在m台机器上的加工过程, 每个工件仅需在某一台机器上加工一次 (不加特殊说明, 一般约定所有机器的加工性能相同) , 同一工件不能同时在多台机器上加工, 同一机器不能同时加工多个工件, 且加工过程一旦开始不可中断直至加工完成, 要求某调度指标最优。不考虑同一台机器上加工各工件的准备时间, 用t (j) 为工件j所需的加工时间, r (j) 为被加工的顺序, 则可定义在退化调度中工件j在机器i上的实际加工时间是其加工顺序的线性增函数

引入变量wij=1 (i=1, 2, , m;J=1, 2, , n) , 当wij=1时, 表示工件j在机器i上加否则, wij=0。如果用ci表示机器i上所有工件的完工时间, 则:

如果用f表示所有工件的完工时间, 即:

用F表示最小化完工时间, 即:

2 改进蚁群算法的设计

蚁群算法模拟了蚂蚁觅食的过程, 该算法的主要优点为: (1) 正反馈; (2) 分布式计算; (3) 启发性; (4) 鲁棒性; (5) 并行性;但此算法也存在一些缺点, 如:收敛速度慢、计算时间长、易于过早地陷入局部最优等一些问题。为此, 针对这些缺点对蚁群算法做了一下改进:

(1) 对信息素更新规则引入双向收敛策略, 对信息素增量根据路径的优劣情况加以区别增加。根据公式 (5) 对此代蚂蚁所走过的路径进行信息素更新, 根据公式 (6) 判断信息素的增量。

其中,

Q为一常数, Lbest为此代中最优蚂蚁搜索得到的路径的长度, 即为此代的最优蚂蚁的最小完成时间ATbest, Lworst为此代中最差蚂蚁搜索得到的路径长度, 即为此代的最差蚂蚁的最小完成时间ATworst, ρ为信息素挥发系数, 0<ρ<1。

(2) 对转移概率做了修改。在蚁群算法中假设一个链表, 在蚁群算法运行N次后, 将各边的信息素值放入这个链表L中, 为了加快收敛速度把信息素含量特小的边变加入TL中, 蚂蚁k在运动过程中根据各边的信息素量决定选择方向, 则该TL的路径将被排除在选择范围之外, 在搜索过程中蚂蚁根据各个路径上的信息素量及路径的启发信息来计算转移概率如下式, 其中ij不在TL中。

3 改进蚁群算法解决并行机调度的实现

步骤1初始化工件信息

步骤2选择机器

步骤3构造蚂蚁群数组Ants[M], 每台机器对应一个蚂蚁群。

步骤4初始化算法的各种参数。蚂蚁数量i Ant Count=51, 终止条件i It Count=500, 每只蚂蚁遍历一次留下的信息Q=100, 挥发系数ρ=0.5, 启发系数α=1, 期望系数β=5, 并设置一个空链表以存放信息素。

步骤5把蚂蚁随机置放在该台机器待加工的工件上, 对于每一只蚂蚁把初始工件放入禁忌列表TABU, 并设置蚂蚁未访问的工件集AP。

步骤6生成一代蚂蚁进行最短路径搜索。

(1) 对此代中的一只蚂蚁进行路径搜索

根据状态转移规则为可选集AP中的工件计算转移概率, 之后借鉴轮盘赌法则从可选工序集AP中选择目标节点, 将选中的工件加入该蚂蚁路径集TABU中, 记录被选工件的加工次序, 根据公式 (1) 计算出其实际加工时间, 并更新可选工序集AP, 为符合工作的调度顺序, 假设蚂蚁在寻找路径过程中不会走重复路径, 被选择过的工序不会重复选择。

(2) 在蚂蚁爬行了一定次数后, 在此设为n=100次, 开始把信息素值小的放入链表TL中, 此后按照公式 (7) 计算选择概率。

(3) 完成此代所有蚂蚁的路径搜索

步骤5信息素更新根据公式 (6) 对此代蚂蚁所走过的路径进行信息素更新, 引入了双向收敛策略, 根据路径的优劣情况释放一定程度的信息素。

步骤6如果蚂蚁全部收敛到一条路径, 或者循环次数大于最大循环数, 则跳出改子程序, 记录最短路径。

步骤7比较每个机器蚂蚁群的最短路径, 得出目标解得最优值。

4 仿真及结果分析

为了验证提出的改进蚁群算法, 本文以文献[2]的并行机调度即10个工件2台机器, 30为例进行仿真实验, 得到结果并与其它算法进行比较。

(1) 未考虑退化特征的并行机调度

(2) 考虑有退化特征的并行机调度

5 结论

文章改进了蚁群算法中, 对信息素的更新规则及选择概率做了修改, 提高了算法的收敛速度, 可以快速获得最优解, 但同时也增加了其复杂性, 使算法的运行时间略微有所增长, 如何减小运行时间是本算法的待改进之处。

摘要：本文讨论了非抢占式独立并行机的退化调度问题, 在这个问题中工件的加工时间是线性增加的, 目标函数是极小化总完工时间。为了有效的解决这种复杂的车间调度问题, 针对并行机调度的特点, 本文提出了一种改进的蚁群算法, 对信息素更新策略以及选择概率做了修改。通过实例仿真, 与传统的粒子群算法, 遗传算法进行比较, 实验结果表明, 本文提出的改进蚁群算法具有较好的收敛性与稳定性。

关键词：退化调度,蚁群算法,并行机

参考文献

[1]陈成, 刑立宁.求解柔性作业车间调度问题的遗传-蚁群算法[J].计算机集成制造系统, 2011, 17 (3) :615-621

[2]史烨, 李凯.并行机问题的模拟退火算法研究[J].运筹与管理, 2011, 20 (4) :104-112

[3]刘志雄.并行机问题粒子群优化研究[J].机械设计与制造, 2010, 10:68-70

[4]赵振, 刘刚.基于双线性链表编码的并行机大规模调度遗传算法[J].计算机集成制造系统, 2011, 17 (2) :301-309

蚁群算法概述 篇5

1、蚁群算法的基本原理

在自然界真实的蚁群觅食过程中, 蚁群在没有视觉的情况下通过个体之间交换信息素, 能够在较短的时间内找到食物和蚁巢之间的最短路径。生物学家的研究已经表明, 一只蚂蚁的记忆和智能是非常有限的, 但是, 由于蚂蚁之间可以通过一些信息素进行协同作用, 实现蚂蚁之间的信息交流和传递, 可以共同做出令人惊讶的行为。

为了阐述蚁群算法的机理[2], 下面以蚂蚁搜索食物的过程为例, 分析蚂蚁是如何通过上述的信息交流和传递的协同作用, 最终找到从蚁穴到食物源的最短路径的。

图1.1中, A为蚁穴, E为食物源, 从A到E有两条路径可走, ABE是长路径, ACE是短路径。蚂蚁走过一条线路以后, 在其路径上会留下信息素气味, 后来的蚂蚁就是根据留在各路径上的这种气味的强度选择应该移动的方向。图1.1 (a) 表示起始时的情况, 假定蚁穴中有4只蚂蚁, 分别用1, 2, 3, 4表示。开始时蚁穴中蚂蚁1, 2向食物源E移动, 由于线路ABE和ACE均没有蚂蚁通过, 在这两条路径上都没有原始的信息素气味, 因此蚂蚁1和2选择这两条线路的机会均等。假设蚂蚁1选择ABE线路, 蚂蚁2选择ACE线路, 并且假定各个蚂蚁行走的速度相同, 当蚂蚁2到达食物源E时, 蚂蚁1还在途中, 如图1.1 (b) 所示。蚂蚁2到达食物源以后就返回, 这时从B点返回也有两条线路的选择, 而哪一条线路上的信息素气味重, 就选择哪一条。因为蚂蚁1还在途中, 没有到达终点, 即此时在EBA线路上靠近B端处, 蚂蚁1还没有留下信息素气味, 所以蚂蚁2返回蚁穴的路径只有一个选择, 就是由原路返回。当蚂蚁2返回到A端时, 蚂蚁3开始出发, 蚂蚁3的线路选择将必定是ACE, 因这时ACE线路上信息素的气味比ABE线路上重 (ACE路径上已有蚂蚁两次通过) , 如图1.1 (c) 所示。当蚂蚁1到达食物源B点时, 由于同样的理由, 蚂蚁1所选择的返回线路必将是ECA, 如图1.1 (d) 所示。如此继续下去, 由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:沿路径ACE移动的蚂蚁越多, 则后来者选择该路径的概率就越大, 这正是蚁穴到食物源的最短路径。蚂蚁个体之间就是通过这种信息的交流达到最佳食物搜索的目的[3]。

在自然界中, 蚁群的这种寻找路径的过程表现为正反馈的过程, 与人工蚁群的寻优算法极为一致。如果我们将在优化求解中那些只具备简单功能的单元看作"蚂蚁", 那么上述寻找路径的过程可以用于解释人工蚂蚁的寻优过程。[4]

由以上分析可知, 人工蚁群和自然界蚁群的相似之处在于:两者优先选择的都是含"信息素"浓度较大的路径;人工蚁群和自然界蚁群的区别在于:

(1) 人工蚂蚁具有记忆或智能功能, 它能够记忆已经访问过的节点。

(2) 人工蚂蚁具有一定的视觉, 人工蚁群在选择下一条路径的时候, 并不是完全盲目的, 而是按一定的算法规律有意识得寻找最短路径。

(3) 人工蚂蚁的生活环境是时域离散的。

2、蚁群算法的特点

从蚁群算法的原理不难看出, 蚁群的觅食行为实际上是一种分布式的协同优化机制。单只蚂蚁虽然能够找到从蚁巢到食物源的一条路径, 但找到最短路径的可能性极小, 只有当多只蚂蚁组成蚁群时, 其集体行为才表现出蚂蚁的智能 (发现最短路径的能力) 。在寻找最短路径的过程中, 蚁群使用了一种间接的通信方式, 即通过向所经过的路径上释放一定量的外激素, 其它蚂蚁通过感知这种物质的强弱来选择下一条要走的路。

在蚁群的觅食行为中, 另一个重要的方面是自催化机制和解的隐式评估。自催化机制实际上是一种正反馈机制, 解的隐式评估指蚁群将先走完较短的路径。自催化机制和解的隐式评估相结合, 极大地提高了问题的求解效率。即对于越短的路径, 蚂蚁将越早走完, 从而使更多的蚂蚁将会选择该路径。当然在使用自催化机制时, 要努力避免早熟现象。在蚁群算法中, 使用外激素蒸发和随机状态转移来弥补自催化机制的缺陷。蚁群算法的主要特点概括如下:

(1) 采用分布式控制, 不存在中心控制。

(2) 每个个体只能感知局部的信息, 不能直接使用全局信息。

(3) 个体可改变环境, 并通过环境来进行间接通讯。

(4) 具有自组织性, 即群体的复杂行为是通过个体的交互过程中突现出来的。

(5) 是一类概率型的全局搜索方法, 这种非确定性使算法能够有更多的机会求得全局最优解。

(6) 其优化过程不依赖于优化问题本身的严格数学性质, 诸如连续性、可导性, 及目标函数和约束函数的精确数学描述。

(7) 是一类基于多主体的智能算法, 各主体间通过相互协作来更好的适应环境。

(8) 具有潜在的并行性, 其搜索过程不是从一点出发, 而是同时从多个点同时进行。这种分布式多智能体的协作过程是异步并发进行的, 分布并行模式将大大提高整个算法的运行效率和快速反应能力。

3、蚁群算法的应用

对蚁群算法的应用研究一直非常活跃。由于蚁群算法不依赖于问题的具体领域, 所以在很多学科有广泛的应用。

(l) 组合优化

继M.Dorigo首先将蚁群算法应用于TSP问题之后, V Maniezzo[5]等人将蚁群算法应用于QAP。最近几年, Gambardella[6], Taillard[7]和Stutzle[8]也发表了一些用蚁群算法求解QAP问题的文章。目前, ACO己是求解QAP问题最有效的算法之一。A Colomi[9]等人首先将蚁群算法应用于车间作业调度问题 (Jobshop Scheduling Problem, 简称JSP) 。Costa和Herz[10]提出增强的蚁群算法, 并将其应用于分配类型的问题。该算法在求解图的作色问题时, 得到了完全可以和其它启发式算法相媲美的结果。

(2) 通讯领域

蚁群算法在通讯网络领域 (特别是解决网络路由问题) 方面的应用研究受到越来越多学者的关注。由于网络中信息的分布式性、动态性、随机性和异步性与蚁群算法一非常相似, 如利用局部信息发现解, 间接的通讯方式和随机状态的转换。Di Caro和Dorigo己在相关的文献中将蚁群算法应用于网络路由问题, 并称这种算法为Ant Net[11]。

(3) 大规模集成电路的线网布局

在大规模集成电路的线网布局中, 需要根据电路和工艺的要求完成芯片上单元或功能模块的布局, 然后实现它们之间的互连。此问题可看作是寻找一个网格平面上两端点之间绕过障碍的最短路径问题。线网上的每个Agent根据启发策略, 像蚂蚁一样在开关盒网格上爬行, 所经之处便设置一条金属线, 历经一个线网的所有引脚之后, 线网便布通了[12]。应用蚁群算法, 可以找到成本最低、最合理的线网布局, 而且由于其本身的并行性, 比较适合于解决此类问题。

(4) 函数优化

虽然蚁群算法在离散空间的寻优能力十分突出, 但是对于连续空间的优化也是蚁群算法应用的领域之一, 也是评价蚁群算法性能的主要方法[13,14]。

此外, 蚁群算法在计算机领域、机器人设计与控制领域、数据挖掘、系统辨识、化工领域等方面也有广泛应用。特别需要指出的是:由于蚁群算法在求解复杂组合优化问题方面具有并行化、正反馈、鲁棒性强等先天优越性, 所以在解决一些组合优化问题时所取得的结果无论是在解的质量上, 还是在收敛速度上都要优于或至少等效于模拟退火以及其它一些启发式算法[2]。

摘要：本世纪50年代中期创立了仿生学, 人们从生物进化的机理中受到启发, 提出了许多用于解决复杂优化问题的新方法, 如遗传算法、蚁群算法、进化规划、进化策略等。研究成果已经显示出这些算法在求解复杂优化问题 (特别是离散优化问题) 方面的具有很强的优越性。本文将对蚁群算法做详细的介绍。

蚁群算法发展评述 篇6

蚂蚁作为一种社会性昆虫, 其单个个体的行为能力是有限的, 但是当这些个体组成群体时, 却可以完成许多复杂的工作, 其中最令人称奇的是蚁群在觅食过程中总可以找到一条从蚁巢到食物源的最短路径。经研究发现:蚂蚁在觅食过程中能够在所经过的路径上留下一种称为信息素的物质, 而且蚂蚁在觅食过程中能够感知这种物质的存在及其强度, 并以此指导自己的运动方向, 它们倾向于朝着该物质强度高的方向移动。因此, 由大量蚂蚁组成的集体觅食行为就表现出一种信息正反馈现象:某一路径越短, 该路径上走过的蚂蚁就越多, 所留下的信息素强度也就越大, 后来者选择该路径的概率也就越大。蚂蚁个体之间通过这种信息交流来选择最短路径并达到搜索食物的目的。受蚁群觅食行为的启发, M.Dorigo和他的同事们于20世纪90年代提出了第一个蚁群优化算法 (Ant Colony Optimization Algorithm, 简称ACOA) —蚂蚁系统 (Ant System, 简称AS) 。蚁群优化算法已经被成功地用于解决各种复杂的组合优化 (Hard Combinatorial Optimization, 简称HCO) 问题, 并且取得了令人欣喜的效果。蚁群优化算法具有较好的鲁棒性, 并行分布式计算及易于与其他启发式方法结合等优点。但同时也有收敛速度慢, 容易发生停滞及容易陷入局部最优解等不足。当前, 对蚁群算法的研究主要集中在如何改进蚁群算法。

1 基本蚁群算法

蚂蚁算法首先被成功地用于解决TSP问题, 下面就以TSP问题为例来介绍蚁群算法。给定n座城市, 所谓TSP问题就是寻找一条经过每座城市一次且仅一次的长度最短的闭环路径。设dij代表城市i和j之间的距离, 由平面上两点之间的距离公式可得dij=[ (xi-xj) 2+ (yi-yj) 2]1/2。TSP问题的实例可以用一个完全图G= (N, E) 来表示, 其中N是图的顶点的集合, 这些顶点代表实际问题中的城市, E是图的边的集合, 这些边把图完全连接起来。TSP问题可分为对称型和不对称型两种。在对称型TSP问题中, 城市之间的距离和访问城市的顺序是没有关系的, 也就是对每一对顶点来说dij=dji。在不对称型TSP问题中, 至少存在一对顶点, 对这对顶点来说dij≠dji。在这里我们所选用的实例为对称型TSP问题。设bi (t) (i=1, ···, n) 表示在时刻t位于城市i上的蚂蚁的数量;表示总的蚂蚁的数量;τij表示在时刻t边 (i, j) 上的信息素的浓度, 在对称型TSP问题中τij=τji;ηij表示蚂蚁有城市i转移到城市j的启发式因子, 这个值在算法的运行过程中保持不变, 一般取作ηij=1/dij (dij为城市之间的距离) ;pijk (t) 表示在时刻t蚂蚁k有城市i转移到城市j的概率。为了模拟真实蚂蚁以及考虑到实际问题的情况, 每只蚂蚁应具有以下特征:

每只蚂蚁以一定的概率来选择下一个要访问的城市, 此概率为城市之间的距离以及连接城市的边上的信息素浓度的函数。

为了使蚂蚁走过的路径符合问题的约束条件, 直到一次周游完成之前, 不允许蚂蚁访问已经被访问过的城市。此过程可以用禁忌表来实现, 设tabuk为蚂蚁k的禁忌表, 当蚂蚁访问过城市i以后, 便将i加入禁忌表, 直到一次周游完成之前, 位于禁忌表中的城市是不能被再次访问的城市。

完成一次周游以后, 蚂蚁在其所经过的边上留下相应数量的信息素。

基本的蚁群算法AS可以简单表述如下:在算法的初始时刻, 将m只蚂蚁随机地放到n座城市上, 各条边上的信息素的浓度被设置为τij (0) =c (c为很小的正常数) 。然后, 蚂蚁便以一定的概率来选择下一座要访问的城市, 在时刻t, 蚂蚁k在城市i选择下一座城市j的概率pkij (t) 可表述为:

其中allowedk={N-tabuk}, α和β分别表示信息浓度和启发式因子的重要程度。当所有蚂蚁完成一次周游以后, 各条边上的信息素的更新按如下规则进行。

其中ρ (0≤ρ<1) 表示信息素的残留系数, 1-ρ表示信息数的挥发系数。△τkij (t) 表示蚂蚁k在其所经过的边上所留下的信息素的数量。挥发机制有助于避免边上的信息无限地聚集下去, 没有蚂蚁经过的边上的信息素的数量会呈指数级地减少, 这样一些不好的路径将会被遗忘。在AS中, △τkij (t) 的定义如下:

这里Q是一个常数, Lk表示第k只蚂蚁所经过的路径的长度。M.Dorigo还提出了另外两种△τkij (t) 的定义:

众多研究表明, 蚁群算法具有发现较好解的能力。但与其他算法相比, 该算法收敛速度慢, 需要较长的搜索时间。另外, 该算法容易出现停滞现象, 也就是说, 搜索到一定程度以后, 所有个体发现的解完全一致, 不能对解空间进行进一步的搜索, 不利于发现更好的解。

2 对基本蚁群算法的改进

鉴于蚁群算法的缺点, 对蚁群算法的改进主要从两方面进行。一是加快算法的收敛速度;二是避免过早地出现停滞现象。有许多算法都从这两方面对蚁群算法进行了改进, 如M。Dorigo等人提出的蚁群系统 (ACS) , T.Stützle等人提出的最大最小蚂蚁系统 (MMAS) 等。

2.1 蚁群系统

ACS在状态转移规则和信息素更新规则方面对AS进行了改进:

2.1.1 状态转移规则

在城市r, 第k只蚂蚁选择下一个城市s的规则为:

其中Jk (r) 表示还没有被访问的城市, τ (r, u) 表示城市r与城市u之间的信息素, η (r, u) 表示城市r和城市u之间的启发式因子, β表示启发式因子的相对强弱, q是在区间[0···1]上呈均匀分布的一个随机数, 0≤q0≤1。一只位于城市r上的蚂蚁在选择转移到下一座城市s之前, 首先生成一个随机数q (0≤q≤1) , 如果q≤q0, 则从第k只蚂蚁所有可以转移的城市中选择一个[τ (r, u) ]·[η (r, u) ]β最大的进行转移。否则, 按下式来选择下一座城市。

这种状态转移规则既有利对解空间进行全局搜索, 又能克服蚁群算法收敛速度慢以及易陷入局部最优解的缺点。

2.1.2 ACS的全局更新规则

在ACS中, 只有全局最优解所属路径上的信息素才会被更新, 更新规则如下式所示。

其中,

0<α<1表示信息素挥发系数, Lgb表示求得的全局最优路径的长度。由于只有全局最优解所属路径上的信息素才会被更新, 从而加强了算法的正反馈作用, 加快了算法的收敛速度。

2.1.3 ACS的局部更新规则

在构造解的过程中, 蚂蚁每进行一次转移, 都要对其所经过的边上的信息素进行更新, 其更新规则如下。

其中, 0<ρ<1。△τ (r, s) 的取值一般有三种:△τ (r, s) =0, △τ (r, s) =τ0, 。实验表明第一种的效果较差, 第二种和第三种的效果较好。局部更新规则的作用便是对每条边上的信息素进行动态更新, 每当一只蚂蚁经过一条边以后, 这条边上的信息素便会减少, 这样便减少了已经被选择的路径被再次选择的概率, 从而有利于对解空间进行全局搜索。

2.2 最大最小蚂蚁系统

MMAS主要从三个方面对AS进行了改进: (1) 在所有蚂蚁完成一次周游以后只允许最优解所属路径上的信息素被更新, 信息素的更新规则如下:

其中, △τijbest=1/f (sbest) , f (sbest) 表示最优解的路径的长度。这样便加快了算法的收敛速度。 (2) 各条边上的信息素的量被限制在[τmin, τmax]范围内, 这样便不会出现某些边上的信息素的量远大于其他边的情况, 有效地避免了算法收敛于非全局最优解以及收敛中的停滞现象。 (3) 在初始时刻, 每条边上的信息素的值被初始化为τmax, 这样能够增强对解空间的搜索能力, 有助于发现更多的可行解。另外, 在MMAS中增加了信息素平滑 (pheromone trail smoothing, 简称PTS) 机制。在算法运行过程中, 当已经收敛或快接近收敛时, 该机制用来对信息素进行调整, 更新规则如下:

其中, 0<δ<1, τij (t) 和τ*ij (t) 分别表示信息素更新前后的值。信息素平滑机制的目的是通过增加选择信息素浓度较低的路径的概率来达到对解空间进行进一步搜索的能力。MMAS是目前解决复杂的组合优化问题的最优算法之一。

3 蚁群算法的应用

自从蚁群算法在TSP问题上的应用取得成功以来, 蚁群算法的应用已经不断地渗透到了领域。将蚁群算法应用于通信中的路由问题, 目前可以解决包括带宽、延时、包丢失率和最小花费等约束条件在内的QoS组播路由问题, 比现有的链路状态路由算法具有明显的优越性;将蚁群算法应用于电力系统, 可以寻求一个周期内各个负荷水平下机组的最优组合方式以及开停机计划, 从而使运行费用最小;将蚁群算法应用于二次分配问题, 在二次此问题中分配费用是分配方式的函数, 从而可以寻求一种分配方式, 使分配费用最小;将蚁群算法应用于生产调度问题, 因为蚁群算法机制可以不断地从过去的加工经历中学习, 能很自然地适应外部环境的变化, 从而可以实现动态调度, 这种动态调度比静态调度具有更好的应用前景。

4 结束语

经过十几年的发展, 蚁群算法已经被证明是求解优化问题的有效工具, 但是该算法还

不像遗传算法和人工神经网络那么成熟, 还缺少足够的理论支持。在今后的工作中, 还要对以下方面作进一步的研究:

(1) 加强对蚁群算法的理论研究。虽然说现在蚁群算法已经被成功地用于解决各种复杂的组合优化问题, 但现在蚁群算法的多数成果都是基于大量实验的数据分析, 还没有坚实的数学基础, 其中各种参数的选取也比较复杂, 所以从算法的理论方面还有许多需要解决的问题。

(2) 研究蚁群算法的并行实现, 蚁群算法的群体特性为其并行实现提供了坚实的基础。

(3) 研究蚁群算法与其他算法的结合, 蚁群算法具有很好的耦合性, 例如与局部搜索算法结合往往可以取得较好的结果。

(4) 研究蚁群算法与其他的概率学习算法的关系, 这样有助了解蚁群算法的工作原理。

参考文献

[1]DORIGO M, MANIEZZO V, COLORNI A.Ant system:optimization bya colony of cooperating agents[M].IEEE Trans.on Systems, Man, andCybernetics-Part B:Cybernetics, 1996 (1) .

[2]DORIGO M, GAMBARDELLA LM.Ant colony system:a cooperativelearning approach to the traveling salesman problem[M].IEEETrans.on Evolutionary Computation, 1997 (1) .

[3]ST?TZLE T, HOOS HH.MAX-MIN ant system.Future GenerationComputer Systems 2000.

[4]DORIGO M, BLUM C.Ant colony optimization theory:a survey[M].Theoretical Computer Science, 2005.

[5]STUTZLE T, HOOS HH.MAX-MIN ant system and local search forthe traveling salesman problem[C].In:IEEE Int'1 Conf.on Evolu-tionary Computations.Indianapolis:IEEE Press, 1997.

[6]吴斌, 史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报, 2001 (12) .

[7]孙力娟, 王良俊, 王汝传.改进的蚁群算法及其在TSP中的应用研究[J].通信学报, 2004 (10) .

[8]朱庆保, 杨志军.基于变异和动态信息素更新的蚁群优化算法[J].软件学报, 2004 (2) .

蚁群算法与粒子群算法的比较研究 篇7

由简单个体组成的群落与环境以及个体之间的互动行为称群智能(swarm intelligence)。群智能算法作为一种新兴的演化计算技术已成为越来越多研究者的关注焦点,群智能在没有集中控制且不提供全局模型的前提下,为寻找复杂的分布式问题求解方案提供了基础。目前,群智能理论研究领域主要有两种算法:蚁群算法(Ant Colony Optimization,ACO)和粒子群算法(Particle Swarm Algorithm,PSO),前者是蚂蚁群落食物采集过程的模拟,后者是鸟群觅食过程的模拟。本文对这两种算法的原理、模型、应用等方面进行比较分析,并对这两种算法的改进以及与其它算法的混合做出总结。

一、蚁群算法

蚁群算法是由Colorni、Dorigo和Maniezzo通过对蚁群觅食行为的研究,于1991年提出的一种仿生进化算法[1],利用蚁群在搜索食物源的过程中所体现出来的寻优能力来解决一些离散系统优化中的问题。蚂蚁是一种社会性昆虫,通过一种特有的通信机制,其群体行为展现出高度协作性,能够完成复杂的任务,并且,蚂蚁还能够适应环境变化随时调整搜索路径。作为一种随机搜索处算法,与其他模型进化算法一样,ACO也是通过侯选解组成的群体的进化过程来寻求最优解。

蚁群算法首先被成功应用于旅行商问题(TSP)上,以此为例算法的寻优过程[2]:设有m只蚂蚁,每只蚂蚁根据信息素浓度选择下一个城市(tij(t)为t时刻城市i和j之间路径上残留的信息素浓度,dij(i,j=1,2,...,n)表示城市i和j之间的距离),规定蚂蚁走合法路线,除非周游完成,不允许转到已访问城市。完成周游后,更新蚂蚁访问过的每一条边上的信息素。

初始时刻,各路径的信息量tij(0)相等,m只蚂蚁被放置到不同的城市上。蚂蚁k(k=1,2...,m)在运动过程中,根据各条路径上信息量决定转移方向,表示在t时刻蚂蚁k由位置i转移到j的概率。

其中,allowedk表示蚂蚁k下一步允许转移到的城市集合,随k的行进而改变;信息量τij(t)随时间的推移会逐步衰减,用1-ρ表示它的衰减程度;α,β分别表示蚂蚁在运动过程中积累信息量及启发式因子在蚂蚁选择路径中所起的不同作用;ηij为由城市i转到j的期望程度,可根据某种启发算法而定。

经过n个时刻,蚂蚁k走完所有城市,完成一次循环。此时,根据式(2)一(4)更新各路径的信息素:

其中:ρ表示信息素挥发系数,Δtij表示本次循环中路径ij上的信息量增量,表示蚂蚁k在本次循环中在城市i和j之间留下的信息量,其计算方法根据不同模型而定,最常用的是ant-cycle system:

其中:Lk表示蚂蚁k环游一周的路径长度,Q为常数。

算法流程如图1所示:

二、粒子群算法

Kennedy和Eberhart于1995年受鸟群觅食行为的启发提出了粒子群优化算法(Particle Swarm Optimization,PSO)[3]。PSO中,每个优化问题的解视为d维搜索空间中的一个粒子,粒子在搜索空间中以一定速度飞行,所有的粒子都有一个由被目标函数决定的适应值,并且知道自己到目前为止发现的最好位置,每个粒子利用个体和全局最好位置更新位置和速度。

假设m个粒子组成一个种群并在D维空间搜索,第i个粒子在第t代的位置表示为一个D维的向量Xi(t)=(xi1,,xi2,…,xD),飞翔速度为Vi(t)=(vi1,vi2,...,vD),粒子本身历史最佳位置为Pi(t)=(pi1,pi2,...,pD),群体历史最佳位置为Pg(t)=(pg1,pg2,...,pD)。PSO算法迭代公式如下:

其中,w为惯性权重,使粒子保持运动的惯性,使其有扩展搜索空间的趋势;c1和c2为加速系数,代表了将每个粒子拉向Pi和Pg的随机加速项的权重;r1和r2是两个独立的介于[0,1]之间的随机数,t为进化代数。

算法流程如图2所示:

三、两种算法的比较分析

1算法各自优缺点

(1)由于群智能算法采用的是概率搜索算法,ACO和PSO具有共同的优点[4]:

①鲁棒性:由于算法无集中控制约束,不会因个别个体的故障而影响整个问题的求解。

②扩展性:信息交流方式是非直接的,通信开销少。

③并行分布性:可充分利用多处理器,适合于网络环境下的工作状态。

④优化过程无需依赖具体问题的数学特性,例如可微、线性等。

⑤算法简单容易实现:系统中个体能力简单,执行时间短。

另外,PSO还具有如下优点:

①群体搜索,并具有记忆功能,保留个体和全局的最优信息;

②协同搜索,同时利用个体和全局的最优信息指导进一步搜索。

(2)ACO和PSO也存在着局限性:

①优化性能在很大程度上依赖于参数设定,受初始值影响较大。

②容易产生早熟收敛。

另外,ACO收敛速度慢,只有小部分的ACO算法能够被证明是值收敛的,并且在实际应用中常常出现一种有害的搜索偏向现象,即二级欺骗现象。

PSO局部搜索能力差,搜索精度不高,并在理论研究上尚未完善,缺少算法设计的指导原则。

2应用领域

●ACO本质上适合于求解离散组合优化问题,在旅行商问题上取得成功应用后陆续渗透到其它领域。在指派、调度、子集、带约束满足等组合优化问题时达到了高效的优化性能。并在图着色、电路设计、二次分配问题、数据聚类分析、武器攻击目标分配和优化、大规模集成电路设计、网络路由优化、数据挖掘、车辆路径规划、区域性无线电频率自动分配、集合覆盖等优化领域得到了成功应用。

●PSO本质上适合于处理连续优化问题,但如果对求解问题进行变形或修正速度和位置更新公式也能将其应用于离散优化问题上。并且,鉴于其通用性和有效性,在解决一些典型优化问题时,其性能甚至超过了遗传算法,已成功应用于训练人工神经网络、函数优化、约束优化、多目标优化、动态优化、参数优化、组合优化、模糊系统控制、电力系统、信号处理、模式识别、生物医学等领域中。

3与其它算法混合

由于ACO与PSO具有容易与其它算法结合的特点,根据各算法的优缺点,在算法中结合其它优化技术,以提高算法的优化性能。

①蚁群算法与差分演化结合:针对蚁群算法对参数控制的依赖性、早熟和停滞等现象,以及易与其他算法结合的特点,将差分演化算法应用到蚁群算法的参数选取中,将蚁群算法的参数作为差分演化算法解空间的向量元素,自适应地寻找蚁群算法最优参数组合的同时求解问题的最优解。

②蚁群算法与粒子群算法结合:针对蚁群算法容易出现早熟现象以及算法执行时间过长的缺点,将粒子群算法引入到蚁群算法中,让蚂蚁也具有粒子的特性。

③粒子群算法与模拟退火结合:先利用PSO算法的快速搜索能力得到一个较优的群体,然后利用SA的突跳能力对部分较好的个体进行优化。

④粒子群算法与遗传算法结合:针对PSO容易早熟的缺点,在PSO中引入启发性变异机制,以扩展了算法的搜索区域,提高了算法的速度和精度且不容易陷入局部最优。

⑤粒子群算法与差分演化结合:针对粒子群算法易陷入局部极小点、搜索精度不高等缺点,在算法改进方面引用差分演化算法的变异操作,从而避免算法收敛到局部。

四、展望

群智能算法采用分布式计算机制、鲁棒性强、可扩充性好、优化效率高、并且简单易于实现,为解决实际优化问题提供了新的途径和方法。除了本文提出的ACO和PSO,群智能算法还包括研究蜜蜂通过与环境之间的信息交互实现安排工作的蜂群算法[5]、李晓磊博士通过模拟鱼群觅食行为和生存活动提出的鱼群算法[6]。作为一门新兴领域,群智能算法尚缺乏系统的分析和坚实的数学基础,实现技术不规范,在适应度函数选取、参数设置、收敛理论等方面还需要做进一步研究与探索。在此基础上,对算法加以改进或混合其他技术,以提高算法优化性能也是值得深入研究的一个方向。并且需不断拓宽其应用领域,以进一步推广群智能算法的应用。

参考文献

[1]A.Colorni,M.Dorigo,G.Theraulaz.Swarm intelligence: From natural to artificial systems[M].New York:Oxford Universyty Press,1999.

[2]宋雪梅,李兵.蚁群算法及其应用[J].河北理工学院学报,2006年2月,第28卷第1期:42-45.

[3]Kennedy J,Eberhart R.Particle Swarm Optimization[R].In:IEEE International Conference on Neural Networks,perth,Australia 1995:1942-1948.