文档介绍：兰州理工大学
硕士学位论文
分布式系统任务分配问题的蚁群优化算法研究
姓名:王灵霞
申请学位级别:硕士
专业:计算机软件与理论
指导教师:张远平
20080520
摘要任务分配问题是一类典型的组合优化问题。多处理器系统上的最优任务分配的研究是有效利用系统资源处理实际问题的热点课题,这方面的研究结果在大规模数值计算、Ⅵ图扑慊缂际醯确矫娑加泻芎玫挠τ帽尘啊T诶砺鄯矫妫捎谌挝穹峙湮侍馐被公认的难问题,所以如何构造有效的启发式算法或近似算法是目前研究的热点领域。蚁群优化算法是受自然界中的蚂蚁觅食行为启发而提出的一种新颖的仿生进化算法,适用于求解复杂组合优化问题。目前,蚁群优化算法己成功应用于求解旅行商问题、二次分配问题,取得了很好的实验效果。受其影响,国内外许多学者对其进行了大量的研究工作,将其推广到了诸多优化领域,并已经取得了相当丰富的研究成果。虽然蚁群优化算法的应用范围几乎涉及到各个优化领域,但是还存在很多不足。比如:对于蚁群优化算法求解分布式系统中的任务分配问题的研究大都是在对该问题试验条件或约束条件进行简化的前提下进行的。本文将蚁群优化算法应用于求解约束条件更复杂的任务分配问题:一个任务只能分配给一个处理机处理,而一个处理机可以处理多个任务,其中每个处理机都有固定成本和能力限制。将该任务分配问题表示成完全二部图,通过蚂蚁在完全二部图上搜索较优路径来寻求该问题的较优解。选择不同规模的几组数据进行实验,对每一组数据,通过反复试测探索了信息素挥发系数,信息素启发式因子和期望值启发式因子的合理设定,并将所得的计算结果与禁忌搜索和随机方法作比较。结果表明蚁群优化算法对不同规模的任务分配问题都有较优的结果,具有比禁忌搜索算法和随机方法更优的性能。将另一任务分配问题抽象为一种新的有别于二部图的图形表示形式。针对蚁群优化算法易陷入局部最优的不足,提出了一种求解任务分配问题的混合算法,该算法将简单禁忌搜索算法嵌入蚁群优化算法,利用禁忌搜索算法较强的局部搜索能力,提高了蚁群优化算法的优化能力,改善了任务分配问题解的质量。仿真实验表明混合算法的性能优于基本蚁群算法。最后,对本文的研究工作进行了总结,并指出了蚁群优化算法在该领域进一步还要研究的问题。关键词:蚁群优化算法:任务分配问题:分布式系统;组合优化硕士学位论文
∞蟬‘他蜘舢〆哪,***伽岫啪托砌柚砌卸砌鱨岫猧彻岫,籭血璐穋’緄∞啪%咖纄撒辄呐∞碼他∞∞畁北∞删妇畁虢骶辮印讹轪巧∞∞屯∞蚰鷗砧蛇祎∞蓿膟蚰∞陀叽财∞衄辴鹤噪辻轪羇他小辬∞∞膟蛐蟆轪砌∞积’瑃佃辀辢瑃蛆籽猘辧閕掣衄瓵鷗。璐锄甑辒鷜鷗镮瓼∞鷗,膖譱璐既鮝孕觚’辬鉯謙∞鼯锄锄篹锄分布式系统任务分配问题的蚁群优化算法研究鮧甴舛鮬笛恤,衏鮰鼢瑃琻坨他∞胊∞孕甌,衧种∞∞絢筫畂,緄,Ⅱ’
琣晁齛伽甿鲥毁琸批簍砌咖渤皿趾∞·籇觰蚰印心矧’辤·鷄瑃∞搋齞陀篈;纳
插图索引图分布式系统示意图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图四类问题的关系图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。图蚂蚁寻找最短路径示意图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图信息素挥发系数与总的花费代价的关系⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图参数设定界面⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。图程序运行结果界面⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.:.⋯.图混合算法求解任务分配问题的总体框架⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图任务分配问题的图形表示⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图混合算法和基本蚁群算法的性能比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯分布式系统任务分配问题的蚁群优化算法研究Ⅳ
附表索引表任务分配矩阵⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯表启发式因子口和卢的不同组合对算法性能的影响⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。表不同算法的计算结果比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.表混合算法与基本蚁群算法计算结果比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。硕士学位论文
作者签名:互灵寝日期:础年翵乡日白期:幻。辟歹月房日兰州理工大学学位论文原创性声明和使用授权说明日期:》谚年二月原创性声明学位论文版权使用授权书研究成果。除了文中特别加以标注引用的内容外,本论文不包含任何其他个人或权保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和库》,并通过网络向社会公众提供信息服务。本人郑重声明:所呈交的论文是本人在导师的指导下独立进行研究所取得的集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。本学位