一种新的混合并行蚁群算法研究应用

一种新的基于混合蚁群算法的聚类方法
高尚;汤可宗;杨静宇
【期刊名称】《微电子学与计算机》
【年(卷),期】2006(23)12
【摘要】建立了聚类分析问题模型,分析了K-均值算法、模拟退火算法和基本蚁群算法的优缺点。

对蚁群算法作了改进,思路是K-均值方法混合,利用K-均值方法的结果作为初值。

经过比较测试,两种混合蚁群算法的效果都比较好,特别混合方法二的效果最好。

【总页数】4页(P38-40)
【关键词】聚类分析;蚁群算法;K-均值算法;模拟退火算法
【作者】高尚;汤可宗;杨静宇
【作者单位】江苏科技大学电子信息学院;南京理工大学计算机科学与技术系【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.一种新的混合XML文档聚类方法 [J], 王桐;刘大昕
2.一种基于蚁群算法的聚类组合方法 [J], 杨燕;靳蕃;Mohamed Kamel
3.一种新的混合球壳形数据聚类方法 [J], 吴变样
4.一种基于混合蚁群算法的关联规则挖掘方法 [J], 陆琳
5.一种基于聚类技术和蚁群算法的社团发现方法 [J], 宋智玲;贾小珠
因版权原因，仅展示原文概要，查看原文内容请购买。

一种求解多处理机问题的混合蚁群算法刘洋;曾铮【摘要】经常用于各种最优化处理过程的蚁群算法具有无法解决数据分类、动态请求、在线事务处理等一系列问题,严重时还可能发生停滞状况.在分析蚁群参数、参数选择、最优调度等问题的基础上,提出一种遗传算子结合蚂蚁任务分配模型的混合蚁群算法.仿真实验表明,这种算法在求解多处理机问题时,能在较短的时间内得到较优的调度策略,且该算法具有良好的有效性和收敛性.【期刊名称】《湖南工程学院学报（自然科学版）》【年(卷),期】2016(026)002【总页数】4页(P37-40)【关键词】多处理机问题;蚁群算法;遗传算子【作者】刘洋;曾铮【作者单位】信阳职业技术学院数学与计算机科学学院,信阳464000;信阳职业技术学院数学与计算机科学学院,信阳464000【正文语种】中文【中图分类】TP391.41目前，计算机逐渐走向智能化、网络化的道路，在发展中便出现了并行分布式计算的难题.克服并行分布式计算的难题的关键需要妥善的处理分布式系统中的任务高度的问题.得出一种最优的运算模式才能在规定的时间内运算得出分布式系统的最优调度.通常情况下我们应用蚁群算法(ant colony optimization，ACO)运算最优的运算模式，但是蚁群算法具有一定的缺陷性，它无法良好的处理数据挖掘的数据分类、动态请求、在线事务处理等等一系列问题，严重时可能引发停滞状况.停滞状况指的是当搜索进程开展到一定程度是所得到的结果不具有真实性，导致所有个体得到到的结果是同样的.因此，本文提出了一种蚂蚁任务分配模型结合遗传算子改良的混合蚁群算法应对多处理机问题的混合算法.多处理机调度问题(multiprocessor scheduling problem)的含义为：若有n台一样的处理机(p1，p2，…，pn)各不相关的对m个问题进行作业(j1，j2，…，jm)，其中的任何作业都不涉及其他处理机.若作业未完成也不允许中断作业且不能划分为更小的子作业，一项任务不能在不同的处理机中进行.同时，调度的任务是给出一种最优的作业解决方式，使m个作业尽量在最短的时间内由n台一样的处理机工作完成.多处理机调度则是在满足优先限制条件的基础上最优的作业解决方式发送至各个处理机上执行，并尽量在最短的时间内完成，则可假设：①任何任务在开始后便无法中断.②每台处理机仅仅能够同时处理一项任务.③任务具有连续性.④任务之间存在优先约束，这决定了任务的执行顺序，杜绝循环优先关系.⑤一项任务不能在不同的处理机中进行，也就是设定每台处理机仅能够同时处理一项问题.⑥全部的处理机的配置是相同的，则任何问题均可在任意处理机中进行，且理论上的处理时间是一致的.处理机调度是离散优化问题中的一种，而蚁群算法在求解问题上优于离散优化问题，则应用蚁群算法求解处理机调度问题成为了可能.蚁群算法数学模型最早来源于蚂蚁的群体智能，蚂蚁经常出现在我们的生活当中，在通常情况下，都是多个蚂蚁协同作业.在面对复杂、工程量巨大的问题时，蚂蚁通过分配来降低问题的难度.因此，我们可将一台处理机看成一只蚂蚁，则得到了蚁群算法数学的初始模型.要应用蚁群算法数学模型必须对处理机问题设置限定，也就是设定每台处理机仅能够同时处理一项问题，每台处理机的配置是一致的；任何任务在开始后便无法中断；任务具有连续性，任务之间存在优先约束，这决定了任务的执行顺序，杜绝循环优先关系，则任何问题均可在任意处理机中进行等等. 定义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)以公式来计算处理机pi实施任务处理jobj的几率，运算完成后生成随机函数，以函数进行筛选任务.蚂蚁任务分配模型包括：处理数据挖掘的数据分类、数据分类聚类、动态请求、在线事务处理、规则发现等等.在蚁群算法中加入遗传算子便可得出混合蚁群算法的雏形.蚁群算法结合遗传算子使之成为蚂蚁任务分配模型，需要解决繁殖算子、变异算子、交叉算子方面的问题.首先，设每个处理器中的任务是以高度升序的方式进行排列的.不同的交叉点选取导致交叉点出现了不同的高度，且在交叉点最前面的最优任务的高度是一直的，则刚生成的符号为有效符串号.其中，任务Ji的高度为max(Height(Ji))+1和max(Height(Ji))-1中的任意随机数.在此可认为适应值较高的有效符串号存活的几率最高.在旧的群体中得到适应值最高的有效符串号来构成新的群体从而实现有效符串号自我繁殖.在随机选择两个相同高度的问题进行变异运算.由此可得到混合算法的实现关键代码，其中部分代码如下：Begin算法的初始化参数α,β,sj,θij,tmax的矩阵state，则矩阵R与网格G…while(not termination)while t<tfinisht←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(则突变算法出现)将新生成的有效符串号加入NewGroupelse在原符号串加入NewGroup；并用BESTSIRING带图Group中得出适应度值最小的有效符串号end ifend forend whileoutput所有P的调度方式end whileEnd为验证算法的有效性、收敛性，构建了仿真环境进行实践验证.在分析中，遗传算法中解的群体规模为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.此外，还可通过Job-Shop中的常见问题MT10、MT06来进行比较，应用遗传算子的蚁群算法(IJSA)与一般蚁群算法(JSA)的效率比较.从图1中可见，通过混合蚁群算法可到出更优化的解，混合蚁群算法在满足优先约束的条件下最大限制的保存下调度中任务的优先顺序排列，进而使最优的计算结果能够保存下来.在一般蚁群算法(JSA)中加入遗传算法中的混合蚁群算法IJSA.混合蚁群算法IJSA与原算法JSA相比收敛性更快，且一般不会使运算陷入局部最优解的状况中.算法通过实验实践证实，混合蚁群算法能在较短的时间内得到较优的调度策略，且该算法具有良好的有效性、收敛性，可优化全局性能.本文对传统蚁群算法加以改进，提出了一种蚂蚁任务分配模型结合遗传算子改良的混合蚁群算法应对多处理机问题的混合算法.在处理多处理机的任务调度问题中得到了良好的收效.但是，蚁群算法在处理机的任务调度问题中仅为初步尝试.在改进和优化蚂蚁任务分配模型结合遗传算子改良的混合蚁群算法而得出更好的时间性能以及测试时间不稳定性、环境影响等问题仍需要业内人士加以研究.。

带容量约束车辆路径问题的混合蚁群算法研究带容量约束的车辆路径问题是运输、物流和配送等领域中的经典问题之一，其目标是在满足每辆车的容量限制的情况下找到一条最优路径来完成运输任务。

混合蚁群算法是一种将蚁群算法与其他优化算法相结合的方法，可以有效解决带约束车辆路径问题。

混合蚁群算法的基本思想是利用蚁群算法的策略和局部能力，结合其他优化算法的局部能力和全局能力，以提高算法的收敛速度和解的质量。

对于带容量约束的车辆路径问题，混合蚁群算法可以通过考虑每辆车的容量限制来生成合理的路径，并利用局部策略进一步优化路径。

混合蚁群算法的具体实现可以分为两个步骤：路径生成和路径优化。

在路径生成阶段，蚂蚁根据信息素和启发式信息进行路径选择，同时考虑每辆车的容量限制，确保路径的可行性。

在路径优化阶段，采用局部算法（如2-opt算法或3-opt算法）对生成的路径进行优化，以进一步改善路径的质量。

在混合蚁群算法中，信息素的更新和挥发因子的设定是关键的步骤。

信息素的更新可以通过蚂蚁在路径上释放的信息素量来实现，优化路径的过程中要考虑每辆车的容量限制。

而挥发因子的设定可以通过控制信息素的挥发速度来平衡全局和局部的能力，以避免算法陷入局部最优解。

混合蚁群算法在解决带容量约束车辆路径问题中具有一定的优势。

首先，通过引入局部算法，可以在蚁群算法的基础上进一步优化路径，提高解的质量。

其次，通过考虑每辆车的容量限制，可以生成合理且可行的路径，减少运输成本。

最后，混合蚁群算法具有较快的收敛速度和高效的能力，可以在较短的时间内找到较优解。

尽管混合蚁群算法在解决带容量约束车辆路径问题中具有一定的优势，但也存在一些挑战和不足之处。

首先，算法的参数设置和调整是一个复杂的过程，需要根据具体问题进行调整，以取得良好的效果。

其次，对于复杂的问题，混合蚁群算法可能会陷入局部最优解，并难以找到全局最优解。

因此，进一步研究如何提高算法的全局能力是一个重要的方向。

改进启发式的并行蚁群算法在置换流水线调度问题上的应用的开题报告1. 研究背景流水线调度问题是一种经典的优化问题，尤其在制造业中有着广泛的应用。

在流水线调度问题中，需要对一些作业任务的执行顺序进行调度，以使得整个流水线的效率最大化。

同时，为了最大化流水线的效率，还需要考虑到一些限制条件，例如各个作业之间的依赖关系、流水线上的空闲时间等。

同时，在解决流水线调度问题时，我们也可以采用启发式算法，例如蚁群算法等。

但是在处理大规模的流水线调度问题时，传统的单个蚁群算法已经无法满足要求。

因此，引入并行蚁群算法可以有效提高解决问题的效率和精度。

2. 研究内容本文将主要研究如何改进启发式的并行蚁群算法在置换流水线调度问题上的应用。

具体来说，本文将探索以下研究内容：（1）对传统的蚁群算法进行改进，以提高算法的效率和精度。

例如，可以引入局部搜索算法、双向搜索算法等，以克服传统蚁群算法的局限性；（2）采用并行化的方法，使得算法能够处理更大规模的流水线调度问题。

并且，可以通过多处理器或者GPU等平台进行并行计算，以充分利用硬件的性能；（3）对算法进行实证研究，验证改进的算法在流水线调度问题中的实际应用效果，并与其他现有的算法进行比较。

3. 研究意义本研究将在以下方面具有重要意义：（1）对于流水线调度问题的解决，提供了一种新的、高效的算法。

（2）对于并行算法的研究，为其他类型的优化问题提供了一些新的思路和方法。

同时，可以进一步探索并行算法的性能极限。

（3）验证算法的实际效果，为现实问题的解决提供了一些参考。

同时，也可以为流水线调度问题的实际应用提供一些改进的建议。

4. 研究方法本文采用实证研究的方法。

具体来说，将首先对现有的蚁群算法进行改进，并采用并行化的方式对算法进行优化。

然后，通过对流水线调度问题进行实验研究，验证算法的实际应用效果，并与其他现有算法进行比较。

最后，对实验结果进行分析和总结，提出改进建议。

5. 预期结果本研究预计可以实现以下结果：（1）改进的启发式算法能够更快、更准确地解决流水线调度问题。