分布估计算法研究及其在tsp问题中的应用

《分布估计算法研究及其在tsp问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：O1学校代码：10109密级：公开太原科技大学硕士学位论文（学术型）学位论文题目：分布估计算法研究及其在TSP问题中的应用英文题目：ResearchingontheEstimationofDistributionAlgorithmandItsApplicationinTSP研究生姓名：闫晓丽导师姓名及职称：何小娟副教授培养单位：应用科学学院学科专业：数学论文提交日期：2016年4月5日论文答辩日期：2016年6月3日答辩委员会主席：魏毅强教授论文独创性声明本人郑重声明：所呈交的论文，是本人在导师指导下，独立进行研究所取得的成果。除文中特别加以标注和致谢的地方外，论文中不包含其他

2、个人或集体已经发表或撰写的研究成果。对本研究所做的任何贡献的个人或集体均已在论文中作了明确的说明并表示了谢意。本声明产生的法律责任由本人承担。论文作者签名：日期：中文摘要中文摘要分布估计算法是一种基于概率分析的进化算法,它有效地将遗传算法和统计学领域的知识进行联系，结合和发挥两者的优势，解决了遗传算法中的“构造块”破坏问题。分布估计算法的特点是通过提取优势群体中的个体结构信息,建立概率分布模型，并从所建立的概率模型中进行采样，依此指导新的群体产生，通过这个过程的不断循环迭代，完成种群的进化和优化，最后搜索到问题的满意解。本文针对离散的复杂优化问题，将二项概率分布和Copula函数引进算

3、法中，改进分布估计算法中概率模型的建立方式，并将改进的算法应用于解决旅行商问题（TSP）。二项分布是一种重要的离散型分布，针对复杂的离散优化问题，分析了利用二项概率分布建立复杂离散优化问题的概率模型的可行性,通过统计优势群体中个体的每个变量在相对位置上出现的次数，计算其二项概率，建立概率模型，并从所建立的概率模型中进行采样，产生新群体。同时将提出的改进算法用于求解TSP问题，实验测试结果表明，提出的算法有较好的求解效率。Copula函数是一种典型的连接函数，它能有效地刻画变量间非线性相关关系。针对目前在二元Copula函数构造中存在的问题，在F类函数的基础上，给出了一种新的构造二元Co

4、pula函数的方法，并对其性质进行了理论证明。另外，将多维Copula函数引入到分布估计算法概率模型建立中，根据所选择的优势群体，利用经验分布函数，统计个体中各变量出现的频率，以频率作为边际分布，再经过经验Copula函数的连接，获得一个多维联合概率分布函数作为概率分布模型，并从该模型中采样，指导新一代群体产生，将改进的算法用于求解TSP问题。仿真测试结果表明，提出的改进算法在求解TSP问题时，有较好的求解和优化效率。关键词：分布估计算法；概率模型；二项分布；经验Copula；TSP问题ABSTRACTABSTRACTEstimationofdistributionalgorithm(

5、EDA)isaclassevolutionaryalgorithmbasedonprobabilityanalysis,itcombinesthegeneticalgorithmwiththeknowledgeofstatisticalstudies,theEDAplaystheadvantagesofbothtosolvetheproblemof“thebuildingblocks”isdamagedingeneticalgorithm(GA).TheEDAtakesadvantagesoftheindividualstructureinformationamongtheadvant

6、agegroups,whichisusedtoestablishtheprobabilitydistributionmodel,samplingfromtheprobabilitymodel,anewpopulationwasgenerated,andsoon.,repeatthisprocess,completetheevolutionofthepopulation.Andfinallyfindasatisfactorysolutionoftheproblem.Inthispaper,forthediscretecomplexoptimizationproblems,thebinom

7、ialprobabilitydistributionandtheempiricalCopulaareintroducedtotheEDA,improvingtheestablishmentwaysoftheprobabilitydistributionmodelinalgorithms,thentheimprovedalgorithmisappliedtosolvethetravelingsalesmanproblem(TSP).Thebino