随机局部搜索算法及应用分析.pdf

中圈斜孽数求大誊硕士学位论文随机局部搜索算法及其应用研究作者姓名学科专业导师姓名完成时间高超同皮旦计算机软件与理论李金龙副教授二。一五年五月万方数据1删必UniversityofScienceandTechnologyofChinaAdissertationformaster’SdegreeResearchandApplicationonStochasticLocalSearchAlgorithmsAuthor:Speciality:Supervisor::April,2014万方数据一一万方数据中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文,是本人在导师指导下进行研究工作所取得的成果。除已特别加以标注和致谢的地方外,论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。作者签名:丕窿一签字目期:丛筐筚(目Ⅸ日中国科学技术大学学位论文授权使用声明作为申请学位的条件之一,学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权,即:学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅,可以将学位论文编入《中国学位论文全文数据库》等有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。酣公开口保密——年作者签名:西丝导师签名:签字日期:弘1.∑年圣目西目签字日期:弦f—r7万方数据摘要摘要随机局部搜索算法是?种解决计算机科学和运筹学领域中组合最优化问题的元启发式方法。近年来,由于其简单、高效的特点而得到越来越多的应用。本论文中,我们对随机局部搜索算法进行研究,展示了根据具体问题的特点来设计算法的过程。更具体地讲,我们选择集合覆盖问题作为我们的主要研究目标,主要的工作和贡献有:-;Dn权局部搜素算法(RWLS:RowWeightingLocalSearch),它具有以下特点1)一个扰动搜索的框架,该框架由两个操作函数(ADD和REMOVE)实现:2)多种禁忌策略来避免搜索的重复和循环,包括时问戳的方法,禁忌表和布尔状态检查的策略;3)一个权值调整的策略来帮助算法跳出局部最优。我们对RWLS和文献中最好的方法进行了比较,在OR,Library上的80个实例上的比较结果显示RWLS‘共更新了14个己知最好的解,并且在剩下的66实例上都能够达到己知的最好结果。在7个超大规模的铁路调度实例上,结合一种降低问题规模的方法,在4个实例上,RWLS的表现要好于CPLEX。,我们进一步抽象出了~个平衡多样性和探索性的扰动局部搜索算法框架(BIDPLS:BalancingIntensificationandDiversificationPerturbativeLocalSearch),这个算法框架的有效性在多维度多选择背包问题得到了验证。关键词:随机局部搜索,组合优化,集合覆盖问题,多维度多选择背包问题万方数据ABSTRACTStochasticLocalSearch(SLS)algorithmisameta—puta.·Inrecentyears,SLSalgorithmshavebeenpaidincreasingattentionduetotheirhlghef-,,,。tionisaRowWeightingLocalSearch(RWLS)algorkhmforthesetcovermgproblemt11athasthefollowingfeatures..aperturbativesearchtrameworkthatusesapairofefficientoperatortoiteratiVereducethesizeofthecandidatesolution;.avarityoftabustrategiestoavoidpossibleosscilationofthesearch,includingatimestam