求解TSP问题的多目标进化方法研究

发布时间：2021-02-08 23:10

　　旅行商问题（Traveling Salesman Problem,TSP）是一类经典的组合优化问题,许多科学研究和工程计算中的实际问题都可以描述为TSP问题,对该问题求解算法的研究具有重要意义.本文对求解TSP问题的差分进化算法（Differential Evolution,DE）和进化多目标优化方法进行了研究.主要工作如下:首先,差分进化算法在求解连续优化问题上表现突出,但在TSP这类组合优化问题中的应用较少.为了较好的模拟差分进化算法的进化机制,本文提出了求解TSP问题的离散差分进化算法（Discrete Differential Evolution,DDE）.与传统DE中使用的算术运算符不同,DDE利用个体中城市所在的位置序数来指导个体进行变异和交叉,并采用简化的2-opt局部搜索策略来改善种群中解的质量.同时,运用马尔可夫理论证明了DDE以概率1收敛到全局最优解.其次,考虑到多目标进化算法（Multi-objective Evolutionary Algorithm,MOEA）的种群进化过程蕴含了隐式的自适应多样性保持机制,本文建立了求解TSP问题的双目标优化模型,并针对该模型... 

【文章来源】：武汉理工大学湖北省 211工程院校 教育部直属院校

【文章页数】：59 页

【学位级别】：硕士

【部分图文】：

不同参数下的结果对比

图 3-9 Eil51 最优路径图 3-10 St70 最优路径0 10 20 30 40 50 60 70 80 90 100横坐标0102030405060708090100轨迹图12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849515052535455565758596061626364656667686970

Eil51的最优路径1

【参考文献】：
期刊论文
[1]一种求解旅行商问题的新型帝国竞争算法[J]. 张鑫龙,陈秀万,肖汉,李伟.  控制与决策. 2016(04)
[2]新型蚁群算法在TSP问题中的应用[J]. 张弛,涂立,王加阳.  中南大学学报(自然科学版). 2015(08)
[3]一种简单有效的求解TSP的混合差分进化算法[J]. 曾宇容,王林,顿彩霞.  计算机应用研究. 2012(12)
[4]一种求解TSP初始化种群问题的邻域法[J]. 罗辞勇,卢斌,刘飞.  重庆大学学报. 2009(11)
[5]进化多目标优化算法研究[J]. 公茂果,焦李成,杨咚咚,马文萍.  软件学报. 2009(02)
[6]一种求解TSP的混合遗传蚁群算法[J]. 徐金荣,李允,刘海涛,刘攀.  计算机应用. 2008(08)
[7]求解旅行商问题的位置—次序编码差分演化算法[J]. 贺毅朝,寇应展,陈致明.  计算机应用. 2007(03)
[8]旅行推销员问题的算法综述[J]. 马良.  数学的实践与认识. 2000(02)



本文编号：3024642