并行蚁群算法及其应用研究[硕士学位论文]

图书分类号：TP301.6国际图书分类号：623西南交通大学研究生学位论文并行蚁群算法及其应用研究并行蚁群算法及其应用研究并行蚁群算法及其应用研究并行蚁群算法及其应用研究年级二〇〇五级姓名汪鹏飞申请学位级别工学硕士专业计算机软件与理论指导教师尹治本教授二〇〇八年六月ClassifiedIndex：TP301.6U.D.C：623SouthwestJiaoTongUniversityMasterDegreeThesisRESEARCHONPARALLELANTCOLONYALGORITHMANDAPPLICATIONGrade:Grade:Grade:Grade:PostgraduatePostgraduatePostgraduatePostgraduate2002002002005555CaCaCaCandidate:ndidate:ndidate:ndidate:WangWangWangWangPengfeiPengfeiPengfeiPengfeiAcademicAcademicAcademicAcademicDegreeDegreeDegreeDegreeAppliedAppliedAppliedAppliedfor:for:for:for:MMMMasterasterasterasterofofofofEngineeringEngineeringEngineeringEngineeringSpeciality:Speciality:Speciality:Speciality:CCCComputeromputeromputeromputerSSSSoftwareoftwareoftwareoftwareandandandandTTTTheoryheoryheoryheorySupervisor:Supervisor:Supervisor:Supervisor:Prof.YinProf.YinProf.YinProf.YinZhibenZhibenZhibenZhibenJune2008西南交通大学西南交通大学西南交通大学西南交通大学学位论文版权使用授权书学位论文版权使用授权书学位论文版权使用授权书学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权西南交通大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位论文。本学位论文属于1．保密□，在年解密后适用本授权书；2．不保密□，使用本授权书。（请在以上方框内打“√”）学位论文作者签名：指导老师签名：日期：日期：西南交通大学学位论文创新性声明本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。本学位论文的主要创新点如下：1、提出了一种求解大规模火力分配问题的并行蚁群算法——ACS-WTA-MPI。从2002年以来，有学者开始研究用蚁群算法求解火力分配问题。第一个用蚁群算法求解火力分配问题的是中国台湾省的学者李仁钟博士。但是，对大规模火力分配问题的蚁群算法的仿真研究却几乎没有。本文将蚁群优化算法用于大规模火力分配问题的求解，设计了求解该问题的一种并行蚁群算法ACS-WTA-MPI，并在机群系统上进行了仿真实验。2、对ACS-WTA-MPI算法的参数设置进行了研究，确定出了参数的一组最优组合。蚁群算法参数之间相互关联性和巨大的参数空间，所以确定参数的最优组合是一个非常复杂的优化问题。本文通过一系列仿真实验，对不同参数下ACS-WTA-MPI算法的性能进行了对比，确定出针对火力分配问题的算法参数的最优组合。3、采用标准C++和MPICH实现ACS-WTA-MPI算法，可移植性好，便于研究成果的工程利用。西南交通大学硕士研究生学位论文第I页摘要蚁群优化（ACO）算法是一种新型的元启发式算法。蚁群优化算法具有较强的鲁棒性、优良的分布式计算机制、易于与其它方法结合等优点，可以用于解决各种组合优化问题，并已经成功解决了包括旅行商（TSP）问题在内的许多组合优化问题。蚁群优化算法具有天然的并行特性，适合并行计算。本文对并行蚁群优化算法进行了研究，主要工作包括：研究蚁群算法的并行化，研究并行蚁群算法的应用，研究算法参数的最优组合。本文采用MPICH在机群系统上对算法进行仿真研究，并选择了适合机群系统以及蚁群优化算法特点的并行策略。针对大规模火力分配问题（WTA）的特点，提出了一种求解该问题的并行蚁群算法（ACS-WTA-MPI）。仿真实验结果表明，本文提出的算法的求解质量比求解此问题的对应的串行ACS算法好，本文提出的并行算法的加速比和并行效率也比较理想，加速比最高达到3.851（处理机个数=4），并行效率最高达到0.963。本文对蚁群算法参数的选取进行了研究，目的是确定出参数的最优组合。蚁群算法有一系列的参数，其中主要包括蚂蚁个数、期望启发式因子、局部信息素挥发因子、全局信息素挥发因子等。本文通过一系列仿真实验，对这些参数的不同设置下ACS-WTA-MPI算法的性能进行了对比，确定出针对火力分配问题的算法参数的最优组合。最后，对全文的研究工作进行了总结，并展望了蚁群优化算法进一步还要研究的课题。关键词：蚁群优化；并行算法；火力分配问题；参数设置西南交通大学硕士研究生学位论文第II页AbstractAbstractAbstractAbstractAntColonyOptimizationAlgorithmisanewmetaheuristicalgorithm.AntColonyOptimizationAlgorithmisrobustandexhibitsgreatdistributingcomputingmechanismsoACOcanbecombinedwithotheroptimizationmethodstosolvevariouscombinationoptimizationproblemssuchasTSP.AntColonyOptimizationAlgorithmisnaturallywithparallelismwhichispropertoparallelcompution.ThethesisisfocusedonAntColonyOptimizationAlgorithmandourworkincluding:researchonparallelismofAntColonyOptimizationAlgorithm;researchonapplicationsofparallelAntColonyOptimizationAlgorithm;researchonoptimalparametercombinationofAntColonyOptimizationAlgorithm.MPICHclustersystemisadoptedtosimulatetheproposedalgorithmswithproperparallelstrategyselectionaccordingtocharacteristicsoftheclusterandAntColonyOptimizationAlgorithm.WeproposeaparallelalgorithmtosolvemassiveWTAproblem.Thesimulatedexperimentdemonstratesthattheproposedalgorithmisorderofmagnitudebetterthanitscounterpartserialalgorithm.Thespeedupfactorofouralgorithm(speedupfactorupto3.851with4CPUs)andparallelefficiency(upto0.963)arefairlyideal.Inordertodeterminetheoptimalparameteroptimizationofthealgorithm,westudytheparameterselectionoftheAntColonyOptimizationAlgorithm.Thereareaseriesofparametersforthealgorithmincludingnumberofants,expectedheuristicfactor,localPheromoneevaporationfactor,globalPheromoneevaporationfactor,etc.WecomparedifferentselectionsoftheseparametersusingACS-WTA-MPIalgorithminaseriesofsimulatedexperimentsandattainoptimalparametercombinationofWTA.Finally,theworkofthisthesisissummarizedandtheprospectiveoffuture西南交通大学硕士研究生学位论文第III页researchisdiscussed.Keywords:Keywords:Keywords:Keywords:Antcolonyoptimization;Parallelalgorithm;Weapon-targetassignment;Parametersetting西南交通大学硕士研究生学位论文第IV页目录第1章绪论......................................................11.1引言...........................................................................................................11.2最优化问题...............................................................................................11.2.1定义................................................................................................11.2.2旅行商问题....................................................................................21.3本文主要研究内容...................................................................................3第2章蚁群优化算法与并行计算概述................................42.1蚁群优化算法概述...................................................................................42.1.1起源与发展....................................................................................42.1.2元启发式算法................................................................................52.1.3蚂蚁系统.................