指派问题的启发式算法研究论文.doc

《指派问题的启发式算法研究论文.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中国矿业大学本科生毕业设计姓名：学号：学院：计算机科学与技术学院专业：　设计题目：指派问题的启发式算法研究指导教师：职称：2012年6月中文摘要本文对指派问题设计了一个新的混合单亲遗传算法。首先，设计了一个新的编码方法,并且对这种编码方法，给出了简便的解码方法。其次，设计了一种新的、有效的基因换位算子。同时，为提高该算子的搜索能力，结合一个局部搜索技术来改进该算子。再次，在此基础上，提出了解指派问题的一个新的混合单亲遗传算法。最后进行了计算机仿真，结果表明算法是有效的。关键词：遗传算法;指派问题;组合优化;局部搜索AbstractAnovelhybridpartheno-geneticappr

2、oachforassignmentproblems(APforshort)isproposedinthispaper.First,anewencodingschemeandanewdecodingschemearedesigned.Second,anefficientgene-exchangeoperatorisgiven.Inordertoenhanceitsabilityofexploration,alocalsearchschemeisintegratedintotheoperator.Basedonthese,anovelandeffectivepartheno-geneticalgo

3、rithmforAPispresented.Finally,thesimulationismadeandtheresultsshowtheeffectivenessoftheproposedalgorithm.Keywords:geneticalgorithm；assignmentproblems；combinatorialoptimization；localsearch目录一、引言11.1、指派问题、启发式算法11.2、遗传算法21.2.2、单亲遗传算法的特点131.2.3、单亲遗传算法理论研究现状141.2.4、单亲遗传算法的应用研究现状161.2.5、单亲遗传算法的展望17二、混合单亲遗

4、传算法172.1、算法模型简介172.2、新的遗传算法182.2.1、新的编码方法182.2.2、基因换位算子、局部搜索192.2.3、新的遗传算法212.3、计算机仿真222.4、结束语22主要参考文献24外文论文25中文译文34致谢43一、引言1.1、指派问题、启发式算法在日常生活中经常会遇到这样的问题：某单位需要完成N项任务，恰好M个人可以承担这些任务。由于每个人的专长不同，各人完成不同任务的效率也就不同，于是产生了应该指派哪个人去完成哪项任务，能够使得完成N项任务的总收益最大（或者总费用最小）的问题。这类问题成为指派问题或者分配问题。指派问题（AssignmentProblems,简记

5、为AP）是十分重要的组合优化问题，在经济管理、计算机科学、运筹学及工程等领域都有着广泛的应用。由于AP是NP-困难的，因此从理论的角度看，是不可能设计出理想的（多项式时间的）能求出精确最优解的算法。求解AP精确解的方法，如分枝切割法（Branch-and-cutmethod，），其计算量十分巨大，对较大规模的问题难以应用。目前，启发式算法已被证明是一类用较少计算量可求出较好质量近似解的一类有效方法。为了提高启发式方法的效率，许多研究者将局部优化方法结合进这些方法中，如混合进化算法，从而大大地提高了进化算法的搜索能力，有助于更快找到全局最优解，是一类很有潜力的算法。本文提出了用混合单亲遗传算法求

6、解AP的一种新算法，设计了链式的基因换位算子，将LK算法推广应用到AP。数值实验表明了该算法的有效性。比较常用的求解指派问题的算法有：匈牙利算法、拍卖算法、Munkre算法、次序搜索算法、m-best算法等，但上述算法在不同程度上存在某些不足。如以次序搜索算法、m-best算法为代表的启发式算法存在着难以求得精确解的问题；以匈牙利算法、拍卖算法、Munkre算法为代表的最优算法虽然可以求得精确的全局最优解，但是存在着实现难、处理速度慢等不足，难以满足工程实时应用的需要。因此实际生活中，需要一种既有较高求解精度、又能满足一定效率要求有效求解算法。经典算法包括线性规划和非线性规划的传统算法、动态规

7、划的传统算法、整数规划的传统算法和分枝定界等算法。它们或者对目标函数的解析性质要求较高，或者计算复杂性很大，只适应于求解小规模的简单问题，很难适用于工程中出现的大规模问题。启发式算法：随着20世纪80年代初禁忌算法，模拟退火法(simulatedannealing)、遗传算法和人工神经网络等算法的兴起，非线性规划问题又增添了一些新的解决方案。这些算法涉及生物进化、人工智能、数学和物理学、神经系统和