分布式并行蚁群算法的设计与分析

《分布式并行蚁群算法的设计与分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Y1019．546分类号密级UDC编号浙江大学博士后研究工作报告．盆查蠢羞堑垫登簋鲞煎遮盐鱼金堑．闯育工作完成日期：2QQ鱼：5：里提交报告日期：2凶鱼二5生浙江大学(浙江)2006年5月摘要对于类似TSP的NP难规划问题，以及一些模型复杂、解空间巨大的复杂大系统动态优化问题，智能优化算法成为最有希望的、有时甚至楚唯一可用的求解手段。然而智能优化算法一直由于需要大量计算和存储资源，在一些动态优化和大规模优化等应用场合受到很大限制。计算技术发展至今，单个处理机的计算能力逐渐到达瓶颈，采用基于网络连接的分布式并行计算系统求解复杂大系统动态优化问题成为

2、当今的研究热点。本论文深入研究并行计算理论，并在此基础上设计出适应大规模复杂优化问题的分布式并行AC0算法。具体的研究成果有以下几点：(1)基于LogP模型设计了一个分布式并行计算环境的串行仿真系统。该仿真系统采用Lo扩模型抽象并屏蔽了计算与通信设备中与并行算法性能瓶颈无关的具体底层细节，同时还运用计算独立于网络通信平台的思想设计体系结构，不仅可以方便地实现各种并行算法，还可以在不同物理设备和鼹络平台上潞试分析并行算法的可移植性、扩展性等性能。(2)提出了一种求解复杂多阶段决策问题的分布式并行ACO算法的设计方法．通过将大规模复杂系统动态优化问题

3、转换为复杂多阶段决策问题，可一致地将其解空间映射为ACO算法的层状解构造图。再将层次解构造图按层数均匀分配给各个计算节点，使全局解构造图分布存储于各个计算节点上。运用移动Agent技术实现蚂蚁在各个计算节点问的迁移以完成在整个解构造图上的路径搜索，并将最终搜索到的路径及相应的信息素广播给各个计算节点以更新其本地的解构造图信息素。该并行设计方法将蚂蚁每步的解构造块评价和更新解构造图信息素的计算都分配到各个计算节点来实现，比现有的并行ACO算法更好地解决了计算需求分配的均衡性和全局解构造图信息素的更新等问题。(3)提出了一种分析并行智能优化算法的pe

4、sM模型。遥过将智能优化算法抽象概括为生成候选解、评价候选解和学习解空间知识三个主要步骤，提出以生成一个候选解的计算时间P，评价一个候选解的计算时间g，学习一次解空间知识的计算时间J以及生成的候选解总数肘等四个参数组成的pesM并行智能优化算法计算模型。在pesM模型基础上。结合LogP模型，系统地提出了分析并行智能优化算法性能瓶颈的理论框架。在此基础上，对上面所提出的分布式并行ACO算法与并行蚂蚁算法进行了理论分析比较．关键字：蚁群优化算法；LogP模型；pesM模型；多阶段决策问题；分布式：并行IIIAbstractFortheNP-hard

5、programmingproblemsasTSP,andsomedynamicoptimizationproblemsoflarge-scalesystemswithcomplexmodelsandhugesolutionspace，intelligentoptimizationalgorithmsarethemostpromising，andsometimestheonlyfeasiblechoice．However,intelligentoptimizationalgorithmsusuallyneedalotofcomputationand

6、storageresources，whichleadstolimitedapplicationinthefieldofdynamicoptimizationandlarge—scaleoptimization．Withthedevelopmentofcomputingtechnologies，thecomputingpowerofsingleCPUisapproachingitslimit．Solvingdynamicoptimizationproblemsofcomplexsystemswithadistributedparallelcompu

7、tingsystemconnectedbynetworksisaresearchhotspotnowadays．Thispaperpaysattentiontotheparallelcomputingtheory,anddesignsanoveldistributedparallelantcolonyoptimizationalgorithmforlarge—scalecomplexoptimizationproblems．(1)Designedaserialsimulationsystemfordistributedparallelcomput

8、ingenvironmentonthebasisofLogPmodel．ThesimulationsystemadoptsLogPmod