网格负载均衡策略及其蚁群优化算法

第33卷第10期重庆大学学报

V ol.33N o.10

2010年10月Jour nal of Cho ng qing U niv ersity Oct.2010

文章编号:1000 582X(2010)10 102 08

网格负载均衡策略及其蚁群优化算法

陈乙雄1

,吴中福1

,朱郑州

2

(1.重庆大学计算机学院,重庆400044;2.北京大学信息科学技术学院,北京100871)

摘 要:以重庆大学CampusGrid 建设和加入ChinaGr id 的发展规划为背景,研究了多网格环境中出现共用节点(即同时为多个网格系统服务的节点)时资源利用率下降问题,并针对该问题提出了以提高资源利用率为优化目标的负载均衡算法。主要分为问题模型建立、算法设计、以及实验评估3个部分。提出的算法能较好解决该问题,并考虑了网络通信开销对算法执行效果的影响。实验表明,提出的算法能有效防止网格中出现共用节点时资源利用率的下降,并对网格动态变化的特性具有较强的适应能力。

关键词:网格;负载均衡;蚁群优化;任务调度 中图分类号:T P393

文献标志码:A

Load balancing strategy and ant optimization algorithm for grids

CHEN Yi xiong 1,WU Zhong fu 1,ZH U Zheng zhou 2

(1.College o f Co mputer Science,Chongqing University,Chong qing 400044,P.R.China;2.Schoo l of Information Science and T echno logy ,Beijing Univer sity,Beijing 100871,P.R.China)Abstract:In view of the Cam pus Grid construction,w hich is also a crucial part of ChinaGr id project,the performance decline for grid scheduling algor ithms w hen no n dedicated nodes em er ge in m ulti grid environment is studied.A lo ad balancing algorithm to optimize r esource usage r ate is pro posed.T he paper invo lves three parts:problem m odeling,alg orithm design,and experiment evaluation.T he ex perimental results show that the proposed algo rithm is effectiv e fo r solving the problem o f resource usag e rate decline under the discussed grid circumstance.

Key words:g rid com puting;load balance;ant colo ny optim ization;task scheduling

近年来,在高性能计算领域,网格逐渐成为超级计算机以外的另一种选择。由于网格系统中的各节点通常在地理位置上比较分散,而且具有平台异构、跨管理域等特点,因此如何将网格任务在这些节点上进行合理的分配并保证执行效率成为网格研究的1个重要方面[1]

。

1 网格及其负载均衡问题

调度算法是网格资源分配的核心。然而,由于网格动态变化的特性,即使采用了比较先进的调度算法,网格任务在各个节点上的部署仍有可能出现分布不均的情况,从而导致系统资源利用率下降。

这是因为多数算法执行生成的1个优化了的调度方案是以当前网格资源的状态信息作为输入的。但从任务按照调度方案发送到具体网格节点到真正提交执行这段时间,任务队列的任何改变都会导致实际的任务执行时间延后或提前(如作业取消)。此外,任务预计执行的时间也可能会因为不同的估计方法而与实际情况有一定误差。最终造成的结果就是某些节点上的任务很快执行完毕而处于空闲状态,而另一些节点则可能堆积了过多的任务,从而使系统整体的资源利用率降低。为了使每个节点都能充分利用,就需要使任务在各个节点的分布保持均匀,即网格中的负载均衡问题。需要强调的是,论文讨论的节点负载实质上是指任务所需要的执行时间而非存储空间。

在网格环境下,有多种原因可造成节点负载情况的改变,从而导致负载不均衡现象:在硬件方面,可能会因为计算节点部分处理机停止工作而使得执行任务的速度降低,从而导致执行时间延长,可反过来视为负载变大;软件方面,工作在非预留方式下的节点会因为任何某个调度范围之外的任务而增加额外的执行时间,从而导致负载变化。这些负载的变化信息是来不及且不可能反馈给该调度模块并让其对已经分配到各节点任务重新做调度安排的,因而负载不均的情况则有可能出现。当然,节点负载情况也会因核心调度算法的不同而不同。例如负载不均衡的情况在某些时候可以由调度算法在二次调度时加以修正。但这种修正在某些情况下并不及时,尤其是当任务调度是成批进行,且每个批次任务数较大时。如果调度范围之外的任务出现数目较多,发生频率较大,例如在多网格环境下[2],网格中出现若干共用节点(即同时属于2个以上网格的计算节点)的情形[3],则调度算法的执行效果就会受到较明显的影响。

负载均衡的研究成为除调度算法外提高网格资源利用的另一个方面。多数调度算法是从用户的角度出发,强调用户作业的响应时间和服务质量[4 6],而负载均衡则是从系统的角度来考虑全局的任务分配格局,提高资源的利用率。

负载均衡也可看做系统在任务调度后的对资源分配的一种再调整,其具体实现的方法主要有集中式和分布式2种。集中式方法是通过在系统中设置1个专门的负载均衡模块,由它收集所有节点的负载信息,进而做出哪些节点的任务需要迁移、以及迁移到哪个节点的策略。这种方法的优点在于掌握了足够的节点负载信息,可以在全局范围内进行任务的迁移和负载平衡。但该方法最大的缺陷就在于通信开销过大,特别是对于网格而言,通常系统的规模较大,且各个节点属于不同的管理域,不同链路的数据通信时延差别也很大,使得集中式的方法缺乏可扩展性。相比来说,分布式方法则更适合网格平台的诸多特点。这类方法允许任务迁移各自在较小的局部范围内进行,可以避免过多的通信开销,且易于扩展。

2 算法的基本思想

参照文献[7]的思路,笔者将负载均衡分成决策和任务迁移两个阶段来实施。决策机构采用一定的策略来决定系统在何种条件下将会触发任务的迁移;而任务迁移机制则按照算法的优化目标,将任务在节点之间进行转移,使节点负载重新达到均衡状态。2.1 决策机制

对于任何1个任务迁移,或多或少都会产生一定的通信开销,尤其在网格环境下,有时候这种开销会很大,使得这种迁移失去意义。因此,在网格中的各个节点之间进行任务迁移,以求达到负载均衡之前,应当有一定的策略来确保进行任务迁移所付出的代价与获得的性能提升相比是可以接受的,否则宁可放弃这种迁移。

笔者设计了一种基于投票的决策机制。即在逻辑上笔者设定一个中心计票器,而每个计算节点可以根据其邻域节点的负载情况来判定自己是否负载过重或过轻,进而做出相应的投票决定。中心计票器收集到这些 选票后则可以根据一定的规则来判断当前系统是否 值得进入任务的迁移阶段。通过这种方式,一方面负载信息在节点和邻域节点之间的传输时延可以控制在一个可以接受的范围内;另一方面 选票可以用很少的比特数进行编码,在更大网络范围中传输的通信开销远小于直接传输节点负载信息。这就有效地避免了以往集中式方法中,频繁的负载信息传递导致通信开销过大的问题;同时由于以间接的选票信息代替了直接的负载信息并在更大范围内传递,就有利于在更大的范围实现负载均衡。

此外,笔者特别允许共用节点以更高频率进行投票,因为这些节点的负载变化情况往往较一般节点更大,使得需要调整负载的频率也更高。

2.2 任务迁移机制

在确定了要将某些节点上的任务进行迁移后,具体如何将任务在候选节点上重新分配则需要在任务迁移阶段完成。该过程也就是系统进行负载均衡的过程,即将一些负荷过重节点上的任务迁移到候选节点上,如图1所示。

103

第10期 陈乙雄,等:网格负载均衡策略及其蚁群优化算法

图1 任务迁移示意图

由于该问题属于NP问题,且允许算法执行的时间在网格中通常很短,因此在采用启发式算法来寻求较优解的同时,还需要尽量提高算法的收敛速度。

笔者采用蚁群算法来进行完成解的搜索。蚁群算法的思想来源于对自然界蚂蚁的行为进行模拟,通过蚂蚁群体合作行为以求获得较优的问题解[8]。同时,为了缩短搜索时间,使用了一种基于任务粒度的预分配方法,并以该方法的分配结果为依据,将初始信息素分布到图上,以达到加快蚂蚁搜索收敛速度的目的。

3 A lba算法

笔者将提出的算法简称为A lba(A CO based load balancing alg orithm),在建立系统模型基础上,介绍算法的实现过程(分投票决策阶段和任务分配阶段)。表1为涉及的主要数学符号:

表1 主要变量表

变量名称描述

M1,M2,!M m(t)t时刻的m(t)个计算节点

T1,T2!T n(t)t时刻的n(t)个待分配的任务

u最低投票数

T T j节点j的传输开销

D(t)[m,m]t时刻节点间传输速度

G(T j)任务j的粒度

K蚂蚁的数量

b信息素挥发速率

T l算法执行时间上限

3.1 系统模型

笔者根据文献[9]介绍的方法,用下列三元组来描述网格的任务分配模型

=Rm,H3 a j,d j,batc h-M f o。(1) 其中 , ,分别表示机器环境、任务性质以及目标函数。

3.1.1 机器环境

在网格中,各计算节点平台通常可以是异构的,但在运行网格作业时是并行方式,这里笔者用RM (related machine)表示。每个计算节点可以包含一个或多个CPU,而每个CPU也可以有不同的处理速度(以M IPS为单位)。网络拓扑允许动态变化,t 时刻节点之间的传输速率由矩阵D(t)[m,m]给出。在节点中的任务分配是以一种层次结构传递的,参照文献[10]的方法,笔者用H3来定义该结构

H3=G Q1{LQ1,LQ2,!!,LQ n}[F Q1,F Q2,!!,FQ m],

(2)其中:G Q为全局队列;L Q为本地队列;FQ表示先进先出队列。

3.1.2 任务性质定义

网格系统中的任务可以不定期的到达,到达时刻由a j表示。同时,每个任务的属性,包括提交时间、运行要求、到期时间d j等均可在任务实体的参数中加以描述。需要指出的是,任务的粒度G(T j)将在算法的任务预分配过程中作为判定依据。G(T j)的值并不是任务T j所占用的存储空间大小,而是其在标定机器(固定M IPS)上所反映出的执行长度。任务的分配以batch M方式,即成批进行调度分配,每个批次的大小为M。

3.1.3 目标函数

由于网格环境的复杂性,根据不同的应用需求往往存在不同的优化目标[10 11]。从用户角度来讲,通常只关心一个作业(由若干任务组成)完成的快慢,即响应时间;而从系统角度而言,系统的吞吐率、资源利用率常常作为衡量的主要指标。在论文中,笔者着重强调算法在保证作业响应时间的同时,尽可能提高资源利用率。并给出了以下目标函数公式

f o=m ax{(TT j+WET j)|j=1...M}

RU

。(3) 在上面的公式中,分子指的是第一个任务到达至最后一个任务完成的整个时间跨度。同时,这个时间值也和所有节点的运转时间的最大值相等。而每个节点的运转时间包括任务发送、结果返回(TT j)、和任务等待与执行所消耗的时间(WET j)。(即Wall Clock时间而非CPU时间)。RU为资源利用率,是所有节点任务执行时间和所有节点运转时间(CPU执行和空闲时间之和)的比值,即

104重庆大学学报 第33卷

RU =

M

j=1

R j

M

j=1

(R j +I j )

。

(4)

3.2 系统结构

根据文献[12]的分类方法,可以把网格系统的结构划分为集中式、分布式、以及层次结构。由于集中式结构不利于系统的扩展,而分布式结构常常不容易收集足够的状态信息来获得1个较优的解,故笔者采用层次结构定义系统框架。这样既有利于信息的收集,也比较容易扩展。该结构的定义如图2所示。

在图2中,笔者假定所有的任务队列都有足够的空间来存储等待运行的任务,即论文没有讨论队列任务溢出的情况。对于共用节点,来自其它网格的任务可以随时出现,从而影响节点的负载情况。笔者假定网络状况发生突变的几率很小,即当前的网络环境是确定的,矩阵的值保持不变。

在实际运行过程中,每个节点允许和它的邻域节点集中的节点交换负载信息。这里笔者引入了邻域集的概念。邻域集是指某个节点附近,传输单位数据的时延小于一定阈值的那些节点所组成的集合。把负载信息的交换限制在邻域集中可以有效地

降低频繁的信息交换所产生的通信开销。

图2 任务调度与执行结构

3.3 投票决策机制

笔者采用了一种类似于投票的策略作为负载均衡的触发规则。根据邻域集的概念,以共用节点为 选民 ,因为这些节点往往会因为外来任务而导致负载不均衡的情形发生。每个共用节点均可以获得其周围节点的负载信息,并且这些信息可以按照一定频率更新以确保准确性。根据这些信息,每个节点都可以向投票决策模块发出1张 选票 来表示支

持或者反对系统进行1次任务分配的均衡化。规则如下规则1:

v =

1M

Y(M

j

),Y(M j )=

1,o(M j )u 2;0,u 1?o(M j )?u 2。

(5)

规则2:

S =0,v ?rx ;1,v >r 。

(6)

即在某个节点的邻域中,如果有超过r %的节点其负载o (M j )过轻或过重,u 1的取值通常可以在0~60(负载相对太轻);u 2的取值通常在140(负载相对过重),则该节点投支持票,反之投反对票。而投票决策模块最终会根据选票数量,按照规则2来确定是否需要启动负载均衡过程。此外,某些情况下还可以给不同节点的选票加上一定的权重,如某些节点的CPU 时间更贵,其选票权重就可以设大一些。

3.4 基于任务粒度预分配

当前面的布尔变量S 为真时,系统便进入了任务迁移过程。使用了一种基于粒度的预分配方法,并将其结果生成为初始信息素,则可以大大加快蚂蚁的搜索速度。这里,任务粒度的大小并非其指令条数或占用的存储空间,而是标定机器下任务的执行长度,因而往往循环语句较多的任务会具有较大的粒度。

预分配方法的过程就是将任务按照粒度的大小从高到低排序,而节点则按照负载的多少按由轻到重排序,然后尽量将任务粒度大的任务分配到负载最轻的节点,并在每次更新后不断重复这个过程直到所有任务分配完毕。

上述过程可以由图3所示实例加以说明。

假设有6个任务需要分配到5各节点机上,则

第一步:分别将任务和节点机按照粒度和负载情况排序,如图3所示;

第二步:将当前粒度最大的任务4分配到负载最轻节点上,并将其标识为已分配;

第三步:更新节点的负载信息,并重新排序;第四步:若还存在未分配的任务则回到第二步,反之预分配结束。

需要指出的是,在预分配过程中并没有考虑通信开销的问题。这是因为频繁的计算每一种分配的通信开销会导致预分配过程变慢,从而影响算法的

105

第10期

陈乙雄,等:网格负载均衡策略及其蚁群优化算法

图3 按任务粒度分配示意图

执行效率。该问题可以留到蚁群优化过程中,让蚂蚁在相应的路径上通过信息素的数量来避免将任务分派到传输时延大的节点上去。

3.5 蚁群优化

在任务预分配的基础上,笔者采用了蚁群算法对问题的解进行了优化。借鉴文献[13]蚁群优化方法的思路,笔者将优化过程分为了以下4个步骤进行。

第一步:构造搜索图。

首先构造1个图,将问题的求解转化为搜索图中的1条最优路径,如图4

。

图4 蚁群优化搜索图

图4的每行节点代表了任务集合的所有可能组合(包括空集)。图节点的行数与节点机数目相同。增加1个初始节点S ,并且每行节点均发出有向边指向下一行的每个节点。

第二步:放置信息素。

如果图中无信息素,初期收敛速度较慢,故可以

将预分配的结果作为初始信息素,并以高斯公式分布到图中,则可以大大加快蚁群优化过程

Gauss (x ,!,?)=

1?2#

e -(x -!)2

2?

2。(7)

这里,x 是节点到当前最佳路径节点的汉明距离,变量!和?可以分别用来控制信息素放置的中心和扩散程度,在初始状态!=0,?=1。

第三步:蚂蚁行进。

算法执行时,在图中放置若干只蚂蚁,每只蚂蚁按照下面的规则前进

1)每只蚂蚁都从初始节点S 发,由上至下行进。

在蚂蚁行进过程中,根据后续节点的信息素浓度来确定移动到该节点的可能性。若?表示某个节点上信息素的数量,则蚂蚁 从i 移动到j 的可能性为

P j ( ,i)=

?(v i,j )

1?k ?m i

?(v i,k )。(8)

2)蚂蚁在前进过程中还应遵循以下约束。

S iq #S jr =%(1?q

(9)

S 1p ?!?S iq ?!?S jr ?!?S m t ={J 1,J 2,!,J n (t)}。

这里,S 1p ,!,S iq ,!,S jr ,!,S mt 为1条有效路径上节点所代表的任务子集。通过该公式就可以保证蚂蚁不会行进到1个包含有已被分配任务的子集节点上。

根据蚁群算法,蚂蚁在找到一条可行路径的同时会在其经过的道路上放置一定数量的信息素。为了使整个搜索朝着更优的解推进,信息素的分布应该依据当前的最优路径进行更新。即找到一条可行的路径后,将其对应的目标函数值X new 与当前的最优值X 进行比较,如果X new

值得注意的是,在蚂蚁搜索最佳路径的早期,有可能会找到一个局部次优解而使得信息素在相应路径上堆积过快,从而吸引更多的蚂蚁并放置更多的信息素,最后算法过早收敛于局部次优解。为了防止这种过快收敛情况的发生,可允许信息素按照一定的比率b 挥发,以增大蚂蚁寻找更大范围内最优

解的可能性

!new =(1-b )!old ;

?new =

(1+b )?old ,(1+b)?old

(10)

整个搜索过程会不断重复直到满足一定的终止条件,通常网格中允许这类算法执行的时间比较有限,这里可以简单的定义1个算法执行的期限Tl 为终止变量。

106

重庆大学学报 第33卷

图5 激素更新示意图

归结起来,上述过程也可以由下面的伪代码加以描述

Procedure ACO_Optimizatio n

变量初始化:

在预先分配过程后得到的路径上放置信

息素;

While(执行时间

蚂蚁搜索;

当前解=min{f ob j(P k)|k=1,2, K};//即所

有蚂蚁得到的路径中最佳的一条

IF X new

信息素更新;END。4 实验与分析

4.1 实验环境

由于网格平台规模较大且跨管理域,因此算法的评估测试主要以仿真实验[14 15]为主。具体笔者采用了基于GRIDSIM的网格模拟器,并针对共用节点的情况对数据集进行了部分修改。使用了6组不同的数据集,每个数据集中均定义了机器环境(包括CPU数目,运行速率等)和任务性质(包括到达时间,到期时间,任务大小,运行要求等属性)。

笔者在共用节点上以随机的方式提交了一定数量的任务,绕过了调度模块直接提交来观察对已有任务运行情况的影响,并和未出现共用节点的情况做了对比。为了不失一般性,笔者测试了3种调度算法,包括1个基本调度策略FIFO(first in first o ut),1个高级调度策略EDFBF(earliest deadline first back filling),以及一个使用了启发式算法(禁忌搜索)进行优化的调度方法。

4.2 实验结果分析

首先,笔者使用了6个不同的数据集对上述3种算法在没有共用节点的条件下进行了测试,测试结果如表2。

上述结果表明在不存在共用节点的条件下,随着采用的调度策略的不同,先进的调度方法对任务执行的效率有显著的提高。随后,笔者将参与测试的节点的1部分(40%)设置为共用节点,再使用相同的调度策略和数据集重新进行了测试,且为了提高数据可信度,每次运行重复10遍获取1个平均值作为最后的测试数据。结果见表3。

表2 初始测试结果

数据集

执行时间任务完成时间资源利用率

F IFO F B T B FIF O EDF T B FI FO ED F T B

10.1137.8520.5754923.714643.1054226.1392.34593.60593.345

20.124.1119.114376.9254219.773808.49591.82593.41590.825

30.1112.0916.333831.633542.733327.73591.06593.12588.025

40.11526.06519.034671.654374.153939.6591.78593.72593.755

50.10516.85517.2954208.7053928.6253592.77591.3393.60589.22

60.1217.64519.2954360.664008.073787.90591.67592.79588.775107

第10期 陈乙雄,等:网格负载均衡策略及其蚁群优化算法

表3 目标环境测试结果

数据集

执行时间

任务完成时间

资源利用率

F IFO

F B T B FIF O EDF T B FI FO ED F T B 10.10538.05522.2955142.7604723.7154689.90592.33093.22086.22020.11024.03021.0304987.0804450.1204210.10291.02593.37583.37530.10012.65018.1104670.1023747.1053765.22590.88593.22081.02540.12026.29520.9955084.2704600.4954401.66591.22093.75585.95550.10217.11019.0304831.9904115.2554002.38591.75593.82582.3306

0.110

17.975

21.395

4715.619

4199.025

4173.550

91.345

92.345

80.995

通过上表不难发现,当环境中的共用节点数目逐渐增多时,平均而言任务执行的完成时间会延长(有个别情况这种影响不明显,而另一些则有显著变化),同时资源的利用率也会出现下降。这证明共用节点对任务调度确实存在影响,并可导致执行效率降低。为此,笔者再次测试了相同的数据,分别将参与测试的节点的20%,40%,60%,80%设置为共用节点集并集成了论文提出的算法。同一比例共用节点情况下用不同数据集测试取平均值。测试的各项主要指标见图6~图9

。

图6

任务完成时间测试结果

图7 时间跨度测试结果

上述结果表明,提出的算法在环境中出现不同数目的共用节点条件下,均能有效地防止任务执行的主要性能指标降低情况的出现,特别对资源利用

率有较好的保证。原因在于研究算法能有效将某些

图8 任务延迟测试结果

图9 资源使用率测试结果

负载过重节点上的任务迁移到较为空闲的节点,使各个节点的任务分配比较均衡,因而机器空闲时间

大大减小,从而提高了利用率。此外,笔者用不同的任务批次和任务数,对ALBA 在共用节点环境下(共用节点数60%)进行了测试,结果如图10。

图10 不同批次下资源使用率测试结果

108

重庆大学学报 第33卷

结果表明,随着任务批次的加大,任务执行效率受共用节点的影响也越大,而ALBA被触发的几率也大大提高。这是因为当任务批次较小时,前一批任务因共用节点导致的分布不佳情况能够较快反馈到调度模块而在后一批任务调度时加以修正,而任务批次较大时,上述情况的影响无法及时纠正,此时ALBA算法的作用则更加明显。

5 结 语

研究了网格中的负载均衡问题,并特别针对系统中出现共用节点时,任务调度算法执行效率下降的问题,提出一种基于蚁群优化的负载均衡算法ALBA,算法考虑了共用节点对任务分配的影响和特殊性,并采用了一种类似于投票的决策机制,较好地处理了任务迁移和通信开销之间的矛盾。在算法的优化上,使用了基于任务粒度的预分配机制,使得优化过程的收敛速度得以提高。

参考文献:

[1]FO ST ER I,M ORG A N K.T he gr id:blueprint fo r a

new com puting infr astructure2nd edition[M].U SA.

Elsevier,2004.

[2]YA N G C T,HU W J,L A I K C.A resource broker

with cross g rid info rmat ion serv ices on computat ional multi g r id env ir onments[J].L ecture N otes in Co mputer Science,2009.20 31.

[3]万军洲,李腊元.非专用分布式系统中任务调度的性

能预测模型的研究[J].武汉理工大学学报,

2004,28(4).

WA N JU N ZH O U,LI N A YU A N.A perfo rmance pr ediction model for task scheduling in a non dedicated sy stem[J].Journal of Wuhan U niver sity of

T echnolog y,2004,28(4):72 80.

[4]李春林,郑辉.网格计算中基于Q oS的资源调度优化

模型[J].武汉理工大学学报,2008,32(2):58 62.

LI CH U N L IN,ZH ENG H U I.Q oS based r eso ur ce scheduling o pt imizatio n policy in computational g r id [J].Jo urnal of W uHan U niv ersity o f T echnolog y,

2008,32(2).

[5]LI C L,L I L Y.A system centr ic scheduling po licy for

optimizing objectiv es o f application and r eso ur ce in g r id

co mputing[J].Computer s and Industrial Eng ineering,

2009,57(10):1052 1061.

[6]刘海迪,杨裔,马生峰,等.基于分层遗传算法的网格

任务调度策略[J].计算机研究与发展,2008,45(1):

35 39.

L IU H A I DI,Y A N G Y I,M A SHEN G F ENG,et al.

A gr id task scheduling str ategy based on multi-lev el

g enetic alg or ithm[J].Jo ur nal of Computer Resear ch

and D ev elo pment,2008,45(Sup1):35 39.

[7]A L BERT Y,ZO M A YA,Y T.O bser vatio ns on using

genetic alg or ithms fo r dy namic lo ad balancing[J].

IEEE T ransact ions on Par allel and Dist ributed Sy stems,2001,12(9):899 911.

[8]M ARCO D,T H OM AS S.Ant colony o ptimization[M].

USA:the M IT Press,2004:57 72.

[9]P ET ER B.Scheduling algo rit hms(5th ed)[M].

Germany:Spr inger V erlag,2007:12 29.

[10]P A VEL l F,L U DEK M,H A N A R.M odel of g rid

scheduling pro blem[J].G rid and A utonomic Co mputing,2005(2):17 24.

[11]L I C L,X IU Z J,L I L Y.R eso ur ce scheduling w it h

co nflicting objectiv es in gr id environments:M odel and ev aluatio n[J].Jo ur nal o f N etw ork and Co mputer Applications,2009,3(25):760 769.

[12]M AOYHEN L,M ARK B.T he grid:core

technologies[M].England:John Wiley&Sons Ltd.,2005.

[13]P ET ER K,JU R IJ S,K L EM EN O,et al.T he

differ ent ial ant stig merg y algo rithm:an ex per imental ev aluatio n and a real w or ld applicatio n[J].

Ev olutionary Co mputation,2007,9:157 164.

[14]A NT HO N Z S,U RO S C,SRIK U M A R V,et al.A

toolkit for mo delling and simulating data gr ids:an ex tension to gr idSim[J].Co ncurr ency and Co mputatio n:P ractice and Ex perience,2007,11:

532 626.

[15]XHA F A F,BA ROL L I L,et al.A static benchmarking

for g rid scheduling pro blems[C]//P ro ceedings of

Inter nat ional Conference o n Advanced Infor matio n Netw or king and A pplications.[S.L.]:IEEE,2009,

AI NA:170 175.

(编辑 侯 湘)

109

第10期 陈乙雄,等:网格负载均衡策略及其蚁群优化算法

蚁群算法的基本原理

2.1 蚁群算法的基本原理 蚁群优化算法是模拟蚂蚁觅食的原理，设计出的一种群集智能算法。蚂蚁在觅食过程中能够在其经过的路径上留下一种称之为信息素的物质，并在觅食过程中能够感知这种物质的强度，并指导自己行动方向，它们总是朝着该物质强度高的方向移动，因此大量蚂蚁组成的集体觅食就表现为一种对信息素的正反馈现象。某一条路径越短，路径上经过的蚂蚁越多，其信息素遗留的也就越多，信息素的浓度也就越高，蚂蚁选择这条路径的几率也就越高，由此构成的正反馈过程，从而逐渐的逼近最优路径，找到最优路径。 蚂蚁在觅食过程时，是以信息素作为媒介而间接进行信息交流，当蚂蚁从食物源走到蚁穴，或者从蚁穴走到食物源时，都会在经过的路径上释放信息素，从而形成了一条含有信息素的路径，蚂蚁可以感觉出路径上信息素浓度的大小，并且以较高的概率选择信息素浓度较高的路径。 (a) 蚁穴 1 2 食物源 A B (b) 人工蚂蚁的搜索主要包括三种智能行为： （1）蚂蚁的记忆行为。一只蚂蚁搜索过的路径在下次搜索时就不再被该蚂蚁选择，因此在蚁群算法中建立禁忌表进行模拟。 （2）蚂蚁利用信息素进行相互通信。蚂蚁在所选择的路径上会释放一种信息素的物质，当其他蚂蚁进行路径选择时，会根据路径上的信息素浓度进行选择，这样信息素就成为蚂蚁之间进行通信的媒介。 （3）蚂蚁的集群活动。通过一只蚂蚁的运动很难达到事物源，但整个蚁群进行搜索就完全不同。当某些路径上通过的蚂蚁越来越多时，路径上留下的信息素数量也就越多，导致信息素强度增大，蚂蚁选择该路径的概率随之增加，从而进一步增加该路径的信息素强度，而通过的蚂蚁比较少的路径上的信息素会随着时间的推移而挥发，从而变得越来越少。3.3.1蚂蚁系统 蚂蚁系统是最早的蚁群算法。其搜索过程大致如下： 在初始时刻，m 只蚂蚁随机放置于城市中， 各条路径上的信息素初始值相等，设为：0(0)ij ττ=为信息素初始值，可设0m m L τ=，m L 是由最近邻启发式方法构 造的路径长度。其次，蚂蚁(1,2,)k k m = ，按照随机比例规则选择下一步要转

利用蚁群算法优化前向神经网络

利用蚁群算法优化前向神经网络 来源：深圳发票 https://www.wendangku.net/doc/d03913757.html,/ 内容摘要：蚁群算法（ant colony algorithm，简称ACA）是一种最新提出的新型的寻优策略，本文尝试将蚁群算法用于三层前向神经网络的训练过程，建立了相应的优化模型，进行了实际的编程计算，并与加动量项的BP算法、演化算法以及模拟退火算法进行比较，结果表明该方法具有更好的全局收敛性，以及对初值的不敏感性等特点。关键词：期货经纪公司综合实力主成分分析聚类分析 人工神经网络（ANN）是大脑及其活动的一个理论化的数学模型，由大量的处理单元（神经元）互连而成的，是神经元联结形式的数学抽象，是一个大规模的非线性自适应模型。人工神经网络具有高速的运算能力，很强的自学习能力、自适应能力和非线性映射能力以及良好的容错性，因而它在模式识别、图像处理、信号及信息处理、系统优化和智能控制等许多领域得到了广泛的应用。 人工神经网络的学习算法可以分为：局部搜索算法，包括误差反传（BP）算法、牛顿法和共轭梯度法等；线性化算法；随机优化算法，包括遗传算法（GA）、演化算法（EA）、模拟退火算法（SA）等。 蚁群算法是一种基于模拟蚂蚁群行为的随机搜索优化算法。虽然单个蚂蚁的能力非常有限，但多个蚂蚁构成的群体具有找到蚁穴与食物之间最短路径的能力，这种能力是靠其在所经过的路径上留下的一种挥发性分泌物（pheromone）来实现的。蚂蚁个体间通过这种信息的交流寻求通向食物的最短路径。已有相关计算实例表明该算法具有良好的收敛速度，且在得到的最优解更接近理论的最优解。

本文尝试将蚁群算法引入到前向神经网络的优化训练中来，建立了基于该算法的前向神经网络训练模型，编制了基于C++语言的优化计算程序，并针对多个实例与多个算法进行了比较分析。 前向神经网络模型 前向人工神经网络具有数层相连的处理单元，连接可从一层中的每个神经元到下一层的所有神经元，且网络中不存在反馈环，是常用的一种人工神经网络模型。在本文中只考虑三层前向网络，且输出层为线性层，隐层神经元的非线性作用函数（激活函数）为双曲线正切函数： 其中输入层神经元把输入网络的数据不做任何处理直接作为该神经元的输出。设输入层神经元的输出为(x1,x2,Λ,xn)，隐层神经元的输入为(s1,s2,Λ,sh)，隐层神经元的输出为 (z1,z2,Λ,zh)，输出层神经元的输出为(y1,y2,Λ,ym)，则网络的输入-输出为： 其中{w ij}为输入层-隐层的连接权值，{w i0}隐层神经元的阈值，{v ki}为隐层-输出层的连接权值，{v k0}为输出层神经元的阈值。网络的输入-输出映射也可简写为： 1≤k≤m (5)

智能优化算法(蚁群算法和粒子群算法)

7.1 蚁群优化算法概述 ?7.1.1 起源 ?7.1.2 应用领域 ?7.1.3 研究背景 ?7.1.4 研究现状 ?7.1.5 应用现状

7.1.1 蚁群优化算法起源 20世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等，这些算法成功地解决了一些实际问题。

20世纪90年代意大利学者M．Dorigo，V．Maniezzo，A．Colorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法——蚁群算法，是群智能理论研究领域的一种主要算法。

背景：人工生命 ?“人工生命”是来研究具有某些生命基本特征的人工系统。人工生命包括两方面的内容。 ?研究如何利用计算技术研究生物现象。?研究如何利用生物技术研究计算问题。

?现在关注的是第二部分的内容，现在已经有很多源于生物现象的计算技巧。例如，人工神经网络是简化的大脑模型，遗传算法是模拟基因进化过程的。 ?现在我们讨论另一种生物系统－社会系统。更确切的是，在由简单个体组成的群落与环境以及个体之间的互动行为，也可称做“群智能”(swarm intelligence)。这些模拟系统利用局部信息从而可能产生不可预测的群体行为（如鱼群和鸟群的运动规律），主要用于计算机视觉和计算机辅助设计。

?在计算智能(computational intelligence)领域有两种基于群智能的算法。蚁群算法(ant colony optimization)和粒子群算法(particle swarm optimization)。前者是对蚂蚁群落食物采集过程的模拟，已经成功运用在很多离散优化问题上。

粒子群算法和蚁群算法的结合及其在组合优化中的应用e

2007年第2期空间电子技术收稿日期：2006-04-03；收修改稿日期：2006-04-30 粒子群算法和蚁群算法的结合及其在 组合优化中的应用 张长春苏昕易克初 （西安电子科技大学综合业务网国家重点实验室，西安710071） 摘要文章首次提出了一种用于求解组合优化问题的PAAA 算法。该算法有效地 结合了粒子群算法和蚁群算法的优点，先利用粒子群算法的随机性、快速性、全局性得到 初始信息素分布（即粗搜索），再利用蚁群算法的并行性、正反馈性、求解精度高等优点求 精确解（即细搜索）。将文中提出的算法用于经典TSP 问题的求解，仿真结果表明PAAA 算 法兼有两种算法的优点，同时抛弃了各自的缺点。该算法在时间效率上优于蚁群算法，在 求精效率上优于粒子群算法，是综合了两种算法长处的一种新的启发式算法，达到时间性 能和优化性能上的双赢，获得了非常好的效果。 主题词蚁群算法粒子群算法旅行商问题PAAA 0引言 近年来对生物启发式计算（Bio-inspired Computing ）的研究，越来越引起众多学者的关注和兴趣，产生了神经网络、遗传算法、模拟退火、粒子群算法、蚁群算法等许多用于解决复杂优化问题的新方法。然而，面对各种问题的特殊性和复杂性，每种算法都表现出了自身的优势和缺陷，都存在时间性能和优化性能不能兼得的矛盾。 粒子群优化（Particie Swarm Optimization ，PSO ）算法[1， 2]是由Eberhart 和Kennedy 于1995年提出的一种全局优化算法，该算法源于对鸟群觅食行为的模拟。它的优势在于：（1） 算法简洁，可调参数少，易于实现；（2） 随机初始化种群，具有较强的全局搜索能力，类似于遗传算法；（3）利用评价函数衡量个体的优劣程度，搜索速度快；（4）具有较强的可扩展性。其缺点是：不能充分利用系统中的反馈信息，求解组合优化问题的能力不强。 蚁群算法[3，4]（Ant Coiony Optimization ，ACO ） 是由意大利学者M.Dorigo ，V.Maniezzo 和A.Coiorni 于20世纪90年代初提出的一种新型的智能优化算法，已经被应用到TSP 问题[5，6]、二次分配问题、工 件调度问题、图着色问题等许多经典组合优化问题中，取得了很好的效果。它的优点是：（1）采用一种正反馈机制，通过信息素的不断更新，达到最终收敛于最优路径上的目的；（2）是一种分布式的优化方法，易于并行实现；（3）是一种全局优化的方法，不仅可用于求解单目标优化问题，而且可用于求解多目标优化问题；（4）适合于求解离散优化问题；（5）鲁棒性强。但由于在算法的初始阶段信息素匮乏，所以求解速度较慢。 文章将粒子群算法和蚁群算法有机地结合，提出了PAAA 算法。它利用粒子群算法的较强的全局搜索能力生成信息素分布，再利用蚁群算法的正反馈机制求问题的精确解，汲取各自的优势，以达空间电子技术 SPACE ELECTRONIC TECHNOLOGY !"

蚁群算法路径优化算法

其中，表示在t时刻蚂蚁k由元素（城市）i转移到元素（城市）j的状态转移概率。allowedk = C ? tabuk表示蚂蚁k下一步允许选择的城市。α为启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间的协作性越强。β为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越 大，则该状态转移概率越接近于贪心规则；ηij(t) 为启发函数，表达式为。式中，dij表示相邻两个城市之间的距离。（6）修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素（城市），并把该元素（城市）移动到该蚂蚁个体的禁忌表中。（7）若集合C中元素（城市）未遍历完，即k

for i=1:NC % 计算各城市间的距离 for j=1:NC distance(i,j)=sqrt((CooCity(i,2)-CooCity(j,2))^2+(CooCity(i,3)-CooCity(j,3))^2); end end MAXIT=10;%最大循环次数 Citystart=[]; % 起点城市编号 tau=ones(NC,NC); % 初始时刻各边上的信息痕迹为1 rho=0.5; % 挥发系数 alpha=1; % 残留信息相对重要度 beta=5; % 预见值的相对重要度 Q=10; % 蚁环常数 NumAnt=20; % 蚂蚁数量 routelength=inf; % 用来记录当前找到的最优路径长度 for n=1:MAXIT for k=1:NumAnt %考查第K只蚂蚁 deltatau=zeros(NC,NC); % 第K只蚂蚁移动前各边上的信息增量为零 %[routek,lengthk]=path(distance,tau,alpha,beta,[]); % 不靠率起始点[routek,lengthk]=path(distance,tau,alpha,beta,Citystart); % 指定起始点if lengthk

基本蚁群优化算法及其改进毕业设计

摘要 自意大利学者M. Dorigo于1991年提出蚁群算法后，该算法引起了学者们的极大关注，在短短十多年的时间里，已在组合优化、网络路由、函数优化、数据挖掘、机器人路径规划等领域获得了广泛应用，并取得了较好的效果。本文首先讨论了该算法的基本原理，接着介绍了旅行商问题，然后对蚁群算法及其二种改进算法进行了分析，并通过计算机仿真来说明蚁群算法基本原理，然后分析了聚类算法原理和蚁群聚类算法的数学模型，通过调整传统的蚁群算法构建了求解聚类问题的蚁群聚类算法。最后，本文还研究了一种依赖信息素解决聚类问题的蚁群聚类算法，并把此蚁群聚类算法应用到对人工数据进行分类，还利用该算法对2005年中国24所高校综合实力进行分类，得到的分类结果与实际情况相符，说明了蚁群算法在聚类分析中能够收到较为理想的结果。 【关键词】蚁群算法；计算机仿真；聚类；蚁群聚类

Study on Ant Colony Algorithm and its Application in Clustering Abstract： As the ant colony algorithm was proposed by M. Dorigo in 1991,it bringed a extremely large attention of scholars, in past short more than ten years, optimized, the network route, the function in the combination optimizes, domains and so on data mining, robot way plan has obtained the widespread application, and has obtained the good effect.This acticle discussed the basic principle of it at first, then introduced the TSP,this acticle also analysed the ant colony algorithm and its improved algorithm, and explanated it by the computer simulates, then it analysed the clustering algorithm and the ant clustering algorithm, builded the ant clustering algorith to solution the clustering by the traditioned ant algorithm. At last, this article also proposed the ant clustering algorith to soluted the clustering dependent on pheromon. Carry on the classification to the artificial data using this ant clustering algorithm; Use this algorithm to carry on the classification of the synthesize strength of the 2005 Chinese 24 universities; we can obtain the classified result which matches to the actual situation case. In the next work, we also should do the different cluster algorithm respective good and bad points as well as the classified performance aspect the comparison research; distinguish the different performance of different algorithm in the analysis when the dates are different. Key words： Ant colony algorithm; Computer simulation; clustering; Ant clustering 目录

蚁群优化算法

蚁群优化算法
目录 [隐藏]
? ?
比较
1 2
蚁群算法的提出： 人工蚂蚁与真实蚂蚁的异同
o o ? ? ? ? ?
3 4 5 6 7
2.1 2.2
相同点比较 不同点比较
蚁群算法的流程图 基本蚁群算法的实现步骤 蚁群算法的 matlab 源程序 蚁群算法仿真结果 版权声明
[编辑]蚁群算法的提出：
人类认识事物的能力来源于与自然界的相互作用，自然界一直是人类创造力 的源泉。 自然界有许多自适应的优化现象不断地给人以启示，生物和自然中的生 态系 统可以利用自身的演化来让许多在人类看来高度复杂的优化问题得到几乎完美 的解决。近些年来，一些与经典的数学问题思想不同的，试图通过模拟自然生态 系统 来求解复杂优化问题的仿生学算法相继出现，如蚁群算法、遗传算法、粒子群算 法等。 这些算法大大丰富了现在优化技术，也为那些传统最优化技术难以处理的 组 合优化问题提供了切实可行的解决方案。 生物学家通过对蚂蚁的长期的观察发现，每只蚂蚁的智能并不高，看起来没 有集中的指挥，但它们却能协同工作，集中事物，建起坚固漂亮的蚁穴并抚养后 代， 依靠群体能力发挥出超出个体的智能。 蚁群算法是最新发展的一种模拟昆虫王国 中蚂蚁群体智能行为的仿生优化算法，它具有较强的鲁棒性、优良的分布式计算 机 制、易于与其他方法相结合等优点。尽管蚁群算法的严格理论基础尚未奠定，国 内外的相关研究还处于实验阶段， 但是目前人们对蚁群算法的研究已经由当初单 一 的旅行商问题(TSP)领域渗透到了多个应用领域，由解决一维静态优化问题发展 到解决多维动态组合优化问题， 由离散域范围内的研究逐渐扩展到了连续域范围 内的

蚁群算法原理与应用讲解

蚁群算法在物流系统优化中的应用 ——配送中心选址问题 LOGO https://www.wendangku.net/doc/d03913757.html,

框架 蚁群算法概述 蚁群算法模型 物流系统中配送中心选择问题 蚁群算法应用与物流配送中心选址 算法举例

蚁群算法简介 ?蚁群算法(Ant Algorithm简称AA)是近年来刚刚诞生的随机优化方法，它是一种源于大自然的新的仿生类算法。由意大利学者Dorigo最早提出，蚂蚁算法主要是通过蚂蚁群体之间的信息传递而达到寻优的目的，最初又称蚁群优化方法(Ant Colony Optimization简称ACO)。由于模拟仿真中使用了人工蚂蚁的概念，因此亦称蚂蚁系统(Ant System，简称AS)。

蚁群觅食图1 ?How do I incorporate my LOGO and URL to a slide that will apply to all the other slides? –On the [View]menu, point to [Master],and then click [Slide Master]or [Notes Master].Change images to the one you like, then it will apply to all the other slides. [ Image information in product ] ?Image : www.wizdata.co.kr ?Note to customers : This image has been licensed to be used within this PowerPoint template only. You may not extract the image for any other use.

蚁群优化算法在解决TSP问题中的应用

还有页眉没有添加，页眉上写章标题，把我给你标注的问题改完就 可以打印了 摘要 根据蚂蚁生态学提出的蚁群算法是一种新颖的用于求解复杂组合优化问题的模拟进化算法,具有典型的群体智能特征,表现出较强的学习能力和适应能力。本文阐述了该算法的基本原理、算法模型和在TSP( Traveling Salesman Problem，旅行商)问题中的具体应用过程,并对算法进行了总结和展望。 关键词：蚁群算法，旅行商问题，外激素

目录 摘要Ⅰ 目录II 第一章引言 (1) 第二章蚁群算法的基本原理和模型 (2) 2.1 蚁群算法的基本原理 (2) 2.2 蚁群算法的模型 (3) 第三章基于蚁群算法的TSP求解 (5) 3.1 TSP问题的描述 (5) 3.2 基于蚁群算法的TSP求解 (5) 3.3 蚁群算法的局限性 (6) 第四章蚁群算法的改进 (8) 4.1 优选参数m (8) 4.2 参数 的调整 (8) 4.3 信息素的更新 (8) 4.4 信息素链表L 和禁忌链表TL 的构建 (9) 第五章改进的算法基本流程 (10) 第六章结论 (11) 参考文献 (12)

第一章引言 研究群居性昆虫行为的科学家发现，昆虫在群落一级上的合作基本上是自组织的，在许多场合中尽管这些合作可能很简单，但它们却可以解决许多复杂的问题。蚁群算法就是利用群集智能解决组合优化问题的典型例子。蚁群算法（Ant Colony Algorithm, ACA）是由意大利学者M.Dorigo，V.Mzniezzo，A.Colorni 等人在20世纪90年代初首先提出来的。它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等元启发式搜索算法以后的又一种应用于组合优化问题的启发式搜索算法。 蚁群算法不仅能够智能搜索、全局优化，而且具有稳健性A、鲁棒性B、正反馈、分布式计算、易与其它算法结合等特点。利用正反馈原理，可以加快进化过程；分布式计算使该算法易于并行实现，个体之间不断进行信息交流和传递，有利于找到较好的解，不容易陷入局部最优；该算法易与多种启发式算法结合，可改善算法的性能；由于鲁棒性强，故在基本蚁群算法模型的基础上进行修改，便可用于其它问题。因此，蚁群算法的问世为诸多领域解决复杂优化问题提供了有力的工具。 TSP 问题，又称旅行商问题，就是一个销售商从n 个城市中的某一城市出发，不重复地走完其余n﹣1 个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条。它是组合优化中研究最多的问题之一，是一个经典的NP 难题。 第二章蚁群算法的基本原理和模型

蚁群优化算法

蚁群优化算法ACO 一、蚁群算法的背景信息 蚁群优化算法(ACO)是一种模拟蚂蚁觅食行为的模拟优化算法，它是由意大利学者Dorigo M等人于1991年首先提出，之后，又系统研究了蚁群算法的基本原理和数学模型，并结合TSP优化问题与遗传算法、禁忌搜索算法、模拟退火算法、爬山法等进行了仿真实验比较，为蚁群算法的发展奠定了基础，并引起了全世界学者的关注与研究 蚁群算法是一种基于种群的启发式仿生进化系统。蚁群算法最早成功应用于解决著名的旅行商问题(TSP)，该算法采用了分布式正反馈并行计算机制，易于与其他方法结合，而且具有较强的鲁棒性。 二、蚁群算法的原理[1] 蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。 基本的ACO模型由下面三个公式描述： 式（2-1）、式(2-2)和式(2-3)中：m为蚂蚁个数；n为迭代次数；i为蚂蚁所在位置；j为蚂蚁可以到达的置；为蚂蚁可以到达位置的集合；为启发性信息

，这里为由i到j的路径的能见度，即；为目标函数，这里为两点间欧氏(Euclidean)距离；为由i到j的路径的信息素强度；为蚂蚁k由i到j的路径上留下的信息素数量；为路径权；为启发性信息的权；为路径上信息素数量的蒸发系数；Q为信息素质量系数；为蚂蚁k从位置i移动到位置j的转移概率。 三、改进的蚁群算法[3] 蚁群算法具有如下一些优点：①通用性较强，能够解决很多可以转换为连通图结构的路径优化问题；②同时具有正负反馈的特点，通过正反馈特点利用局部解构造全局解，通过负反馈特点也就是信息素的挥发来避免算法陷入局部最优； ③有间接通讯和自组织的特点，蚂蚁之间并没有直接联系，而是通过路径上的信息素来进行间接的信息传递，自组织性使得群体的力量能够解决问题。 但是，基本蚁群算法也存在一些缺点：①从蚁群算法的复杂度来看，该算法与其他算法相比，所需要的搜索时间较长；②该算法在搜索进行到一定程度以后，容易出现所有蚂蚁所发现的解完全一致这种“停滞现象”，使得搜索空间受到限制 3.1基于遗传学的改进蚁群算法研究 该文献[2]提出的算法弥补了基本蚁群算法中“容易陷入停滞状态”和“盲目随机搜索”的不足。文献中提出的解决办法是在每一次迭代搜索后，都把当前解和最优解进行交叉变异,这样既能搜索更大的解空间，又能使系统陷入局部最优后跳出停滞状态。 这种基于遗传学的蚁群算法（G-蚁群算法）的基本思想是在以蚁群算法为主体的基础上引入遗传算法的思想，目的是让蚁群算法经过迭代产生遗传算法所需的初始种群数据，提高种群数据的多样性。然后，遗传算法经过选择、交叉和变异操作,将处理后的数据交由蚁群算法模块进行判断处理，若满足结束条件则退出系统，否则重新进行迭代操作。 该文献中的交叉操作采用了Davis提出的OX交叉算子，即按照交叉概率Pc进行交叉操作，通过一个亲体中挑选出的子序列路径作为后代相对位置的子序列，变异操作以变异概率Pm执行变异操作，在子代序列路径中随机选择两点进行变异操作，在交叉变异操作结束后，判断当前解是否满足收敛条件，若满足收敛条件则更新当前最优解，返回蚁群算法程序,执行下一次的迭代操作。若不满足收敛条件则继续进行遗传算法的交叉变异操作。

蚁群优化算法的JAVA实现

蚁群优化算法的JAVA实现 一、蚁群算法简介 蚁群算法是群智能算法的一种，所谓的群智能是一种由无智能或简单智能的个体通过任何形式的聚集协同而表现出智能行为，它为在没有集中控制且不提供全局模型的前提下寻找复杂的分布式问题求解方案提供了基础，比如常见的蚂蚁觅食，大雁南飞等行为。蚁群算法是模拟自然界中蚂蚁觅食的一种随机搜索算法，由Dorigo等人于1991年在第一届欧洲人工生命会议上提出[1] 。 二、蚁群算法的生物原理 通过观察发现，蚁群在觅食的时候，总能找到一条从蚁巢到食物之间的一条最短的路径。这个现象引起了生物学家的注意，根据研究，原来是蚂蚁在行进的过程中，会分泌一种化学物质——信息素，而蚂蚁在行进时，总是倾向于选择信息素浓度比较高的路线。这样，在蚁巢和食物之间假如有多条路径，初始的时候，每条路径上都会有蚂蚁爬过，但是随着时间的推迟，单位时间内最短的那条路上爬过的蚂蚁数量会比较多，释放的信息素就相对来说比较多，那么以后蚂蚁选择的时候会大部分都选择信息素比较多的路径，从而会把最短路径找出来。 蚁群算法正是模拟这种蚁群觅食的原理，构造人工蚂蚁，用来求解许多组合优化问题。 有关蚁群算法的详细信息，可参考[2]——[5]。 三、蚁群算法的JAVA实现 我个人认为利用JAVA编写一些计算密集型的算法不是一个好的选择。本身一些算法是要要求高效率的，但是我感觉JAVA语言的性能不够，所以编写算法最好用c，其次也可以用c++。当然，这仅是一家之言，欢迎拍砖。 四、算法说明 算法以求解TSP问题为例，用来演示ACO的框架。 算法设定了两个类，一个是ACO，用来处理文件信息的读入，信息素的更新，路径的计算等；另一个是ant，即蚂蚁的信息。 算法中用到的数据，可以从TSPLib 上面下载，使用的是对称TSP数据，为了简化算法的代码，下载下来的数据需要做一个简单处理，即把TSP文件中除去城市节点信息部分之外的内容都删除掉，然后在文件首插入一行，写入此文件包含的城市的数目，以att48.tsp为例，下载下来的文件内容如下：