一种求解多处理机问题的混合蚁群算法

刘 洋,曾 铮

(信阳职业技术学院 数学与计算机科学学院,信阳 464000)



一种求解多处理机问题的混合蚁群算法

刘 洋,曾 铮

(信阳职业技术学院 数学与计算机科学学院,信阳 464000)

经常用于各种最优化处理过程的蚁群算法具有无法解决数据分类、动态请求、在线事务处理等一系列问题，严重时还可能发生停滞状况.在分析蚁群参数、参数选择、最优调度等问题的基础上，提出一种遗传算子结合蚂蚁任务分配模型的混合蚁群算法.仿真实验表明，这种算法在求解多处理机问题时，能在较短的时间内得到较优的调度策略，且该算法具有良好的有效性和收敛性.

多处理机问题；蚁群算法；遗传算子

0 前 言

目前，计算机逐渐走向智能化、网络化的道路，在发展中便出现了并行分布式计算的难题.克服并行分布式计算的难题的关键需要妥善的处理分布式系统中的任务高度的问题.得出一种最优的运算模式才能在规定的时间内运算得出分布式系统的最优调度.通常情况下我们应用蚁群算法(ant colony optimization，ACO)运算最优的运算模式，但是蚁群算法具有一定的缺陷性，它无法良好的处理数据挖掘的数据分类、动态请求、在线事务处理等等一系列问题，严重时可能引发停滞状况.停滞状况指的是当搜索进程开展到一定程度是所得到的结果不具有真实性，导致所有个体得到到的结果是同样的.因此，本文提出了一种蚂蚁任务分配模型结合遗传算子改良的混合蚁群算法应对多处理机问题的混合算法.

1 多处理机调度问题

多处理机调度问题(multiprocessor scheduling problem)的含义为：若有n台一样的处理机(p1，p2，…，pn)各不相关的对m个问题进行作业(j1，j2，…，jm)，其中的任何作业都不涉及其他处理机.若作业未完成也不允许中断作业且不能划分为更小的子作业，一项任务不能在不同的处理机中进行.同时，调度的任务是给出一种最优的作业解决方式，使m个作业尽量在最短的时间内由n台一样的处理机工作完成.多处理机调度则是在满足优先限制条件的基础上最优的作业解决方式发送至各个处理机上执行，并尽量在最短的时间内完成，则可假设：

①任何任务在开始后便无法中断.

②每台处理机仅仅能够同时处理一项任务.

③任务具有连续性.

④任务之间存在优先约束，这决定了任务的执行顺序，杜绝循环优先关系.

⑤一项任务不能在不同的处理机中进行，也就是设定每台处理机仅能够同时处理一项问题.

⑥全部的处理机的配置是相同的，则任何问题均可在任意处理机中进行，且理论上的处理时间是一致的.

处理机调度是离散优化问题中的一种，而蚁群算法在求解问题上优于离散优化问题，则应用蚁群算法求解处理机调度问题成为了可能.

2 蚁群算法数学模型及其多处理机调度过程

蚁群算法数学模型最早来源于蚂蚁的群体智能，蚂蚁经常出现在我们的生活当中，在通常情况下，都是多个蚂蚁协同作业.在面对复杂、工程量巨大的问题时，蚂蚁通过分配来降低问题的难度.因此，我们可将一台处理机看成一只蚂蚁，则得到了蚁群算法数学的初始模型.要应用蚁群算法数学模型必须对处理机问题设置限定，也就是设定每台处理机仅能够同时处理一项问题，每台处理机的配置是一致的；任何任务在开始后便无法中断；任务具有连续性，任务之间存在优先约束，这决定了任务的执行顺序，杜绝循环优先关系，则任何问题均可在任意处理机中进行等等.

定义1：将一台处理机看成一只蚂蚁，每只蚂蚁均具有它所代表的处理中的信息、属性、储存状态等等信息，例如：过去的使用信息、当前的状况、位置等等.

定义2：人工蚂蚁也就是处理机当前的状态

sti≤0即人工蚂蚁也就是处理机pi当前代表空闲状况，sti≥1即人工蚂蚁pi代表忙碌状况，同时statei为pi的预计处理时间.

定义3：人工蚂蚁活动空间的限制

通过网格Grid=[0..w(n)-1]×[0..h(n)-1]来表示人工蚂蚁所能够活动的空间，则它便成为全部格点(x，y)所构成的二维数组，其中x∈[0..w(n)-1],y∈[0..h(n)-1],h(n)∈Z+所代表的是人工蚂蚁个数n的函数值.

定义4：调度选择概率

Aij代表处理机pi所得出的需求浓度为sj的jobj几率，其中sj是jobj的需求强度值，需要用jobj来表示紧急需要的程序.

定义5：蚁群算法的数学模型

蚂蚁模型任务包括五元组，也就是TAM=(Grid，State，n，m，DAG)，其中Grid的含义为二维网格，则：agent的活动范畴有限，其中state代表agent(处理机)的有限状态.m所代表的是任务的数量，n所代表的是处理机的数量，也等于agent的数量.因此，DAG所表示的是任务间关系，DAG图G=J，E，Et.

则蚁群算法的多处理机的调度方法如下：

(1)将全部的人工蚂蚁也即是处理机P随机放入网格Grid中的格子内，且将任务job随机放置在Grid中的格子内，从而计算每个人工蚂蚁到每个任务job的d(pi,jobj)距离值.

(2)在系统时钟的设定中，为了确定算法最后时段tmax.在(0，tmax)时段内，人工蚂蚁将不间断的晕组任务序列.但完成所有任务后，算法将输出该次人工蚂蚁调度序列.并准备运行下一次的人工蚂蚁调度.当时间至tmax后，在全部的输出结果中，筛选出计算结果的最优解.

3 加入遗传算子的混合蚁群算法

蚂蚁任务分配模型包括：处理数据挖掘的数据分类、数据分类聚类、动态请求、在线事务处理、规则发现等等.在蚁群算法中加入遗传算子便可得出混合蚁群算法的雏形.

蚁群算法结合遗传算子使之成为蚂蚁任务分配模型，需要解决繁殖算子、变异算子、交叉算子方面的问题.首先，设每个处理器中的任务是以高度升序的方式进行排列的.不同的交叉点选取导致交叉点出现了不同的高度，且在交叉点最前面的最优任务的高度是一直的，则刚生成的符号为有效符串号.

其中，任务Ji的高度为max(Height(Ji))+1和max(Height(Ji))-1中的任意随机数.在此可认为适应值较高的有效符串号存活的几率最高.在旧的群体中得到适应值最高的有效符串号来构成新的群体从而实现有效符串号自我繁殖.在随机选择两个相同高度的问题进行变异运算.

由此可得到混合算法的实现关键代码，其中部分代码如下：

Begin

算法的初始化参数α,β,sj,θij,tmax的矩阵state，则矩阵R与网格G

…

while(not termination)

while t

t←t+1,state←state-1

运算得出的调度方案将以符串号的形式在Group中保存，从而计算Group中每个方案的适应度范畴.

调用繁殖算法

令BESTTSIRING为Group中适应值的最大有效符串号

for i=1to GroupNum/2do

在Group中得出两个有效符串号并以概率P调用交叉操作；

if(则交叉操作发生)

将生成的有效符串号加入Temp；

else

将原符号串加入Temp；

end if

对Temp中的每个有效符串号，可通过概率q调用突变算法；

if(则突变算法出现)

将新生成的有效符串号加入NewGroup

else

在原符号串加入NewGroup；

并用BESTSIRING带图Group中得出适应度值最小的有效符串号

end if

end for

end while

output所有P的调度方式

end while

End

4 仿真实验与分析

为验证算法的有效性、收敛性，构建了仿真环境进行实践验证.在分析中，遗传算法中解的群体规模为10、杂交概率为pc=1.0、变异概率为pm=0.04.算法最多可延伸至1000代，其中，迁移概率为pmirgration=0.3、内部杂交概率为pINCX=0.7.混合蚁群算法所包含的DAG图是一项随机生成的图，每个节点中有1～4个后继节点，运算的预计运行实践为1～50之间的随机数，演化策略的参数为μ/λ=4.

仿真实验与分析的实验数据为：设定3台处理机、9项作业，则作业所需的运行时间分别为：79、 41、27、 6、62、96、54、73、18.文中采用基本蚁群算法、遗传算法(Genetic Algorithm)以及本文算法，则0.8}Q=100)，经过50次循环后得到结果，如表1所示，所得最优解为P1(98，53)，P1(73，47，26，5)，P1(68，63，20)，完成时间为151.

表1 实验结果比较

此外，还可通过Job-Shop中的常见问题MT10、MT06来进行比较，应用遗传算子的蚁群算法(IJSA)与一般蚁群算法(JSA)的效率比较.

图1 两种蚁群算法的minmaxtime比较

从图1中可见，通过混合蚁群算法可到出更优化的解，混合蚁群算法在满足优先约束的条件下最大限制的保存下调度中任务的优先顺序排列，进而使最优的计算结果能够保存下来.在一般蚁群算法(JSA)中加入遗传算法中的混合蚁群算法IJSA.混合蚁群算法IJSA与原算法JSA相比收敛性更快，且一般不会使运算陷入局部最优解的状况中.算法通过实验实践证实，混合蚁群算法能在较短的时间内得到较优的调度策略，且该算法具有良好的有效性、收敛性，可优化全局性能.

5 结论

本文对传统蚁群算法加以改进，提出了一种蚂蚁任务分配模型结合遗传算子改良的混合蚁群算法应对多处理机问题的混合算法.在处理多处理机的任务调度问题中得到了良好的收效.但是，蚁群算法在处理机的任务调度问题中仅为初步尝试.在改进和优化蚂蚁任务分配模型结合遗传算子改良的混合蚁群算法而得出更好的时间性能以及测试时间不稳定性、环境影响等问题仍需要业内人士加以研究.

[1] 邓 酩,谢晓兰,程小辉.多处理机调度问题的蚁群优化算法[J].桂林工学院学报,2013(2):329-332.

[2] 张 勇,张曦煌.改进型蚁群算法的多处理机任务调度研究[J].计算机工程与应用,2007,43(35):74-76.

[3] 陈 晶,刘加中.一种求解多处理机调度问题的自适应蚁群算法[J].聊城大学学报(自然科学版),2009,22(4):86-89.

[4] 段传林,谢伟铎.一种混合粒子群与蚁群算法在多处理机调度中的应用研究[J].计算机时代,2008(9).

[5] 孙 凯,吴红星,王 浩,丁家栋.蚁群与粒子群混合算法求解TSP问题[J].计算机工程与应用,2012,48(34):60-63.

[6] 管显笋,石伟铂,邓成玉,刘永山.基于粒子群优化和禁忌搜索的混合调度算法[J].计算机应用与软件,2011,28(5).

[7] SU Rina,WANG Yu.Research of Grid Task Schedule Based on Quantum Ant Colony Algorithm[J].Computer Engineering and Applications,2011,47(12):46-48.

[8] XIAO Hong-feng,TAN Guan-zheng.Study on Fusing Genetic Algorithm into Ant Colony Algorithm[J].Mini-micro Systems,2009,30(3).

Research on a Hybrid Ant Colony Algorithm Solving the Multiprocessor Problem

LIU Yang，ZENG Zheng

(College ofmathematics and Computer Science,Xinyang Vocational and Technical College,Xinyang 464000,China)

The ant colony algorithm commonly used in the optimization process has a series of problems.It is unable to solve data classification,dynamic request and no-online transaction processing.Sometimes,it turns out to be stagnant.Based on the analysis of ant colony algorithm parameters,this paper parameter selection and optimal scheduling,presents an ant colony algorithm combining genetic operators with the ant task allocationmodel.The simulation experiment shows that this algorithm can get a better scheduling strategy in a relatively short period of time when solvingmultiprocessor problems,and it has good effectiveness and convergence.

multiprocessor problem; Hybrid ant colony algorithm; genetic operator

2015-11-05作者简介：刘 洋(1975-)，男，硕士，讲师，研究方向：高等数学、计算数学.

TP391.41

A

1671-119X(2016)02-0037-04