- 1、本文档共9页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
求解旅行商问题的动态邻域差异演化算法改进研究.doc
求解旅行商问题的动态邻域差异演化算法改进研究
摘 要:旅行商问题(Traveling Saleman Problem,TSP)是一个典型的组合优化问题,针对该问题主要采用动态规划和智能优化等算法。为了有效求解TSP问题,设计了一种带邻域操作的差异演化算法。为了克服差异演化算法容易收敛于局部最优的弱点,通过引入簇和邻域的概念,将种群中的个体归入距离其最近的子种群,用个体的当前邻域极值替换群体的当前最佳。同时,算法在进化过程中动态调整邻域大小。通过在多个TSP问题的上的仿真实验表明,该算法在求解TSP问题时鲁棒性强,求解精度高。
关键字:旅行商问题;差异演化;动态邻域有哪些信誉好的足球投注网站;自适应
中图分类号:TP391 文献标识码:A 文章编号:2095-2163(2015)06-
Abastract:Traveling Saleman Problem is a classical Combinatorial Optimization Problem. Dynamic design and intelligence optimization are usually used to solve it. In order to overcome the differential evolution algorithm converges to a local optimum easily weakness by introducing the concept of clusters and neighborhood, the population of individuals classified as its nearest sub-population groups, and replace the current individual neighborhood the most good.. At the same time with extreme values,the number of neighborhood is adjust from two to the size of population. Some experiments on classical TSP problem show that this improved DE algorithm is effective and robust to solve TSP and has higher precision.
Keywords:TSP; Differential Evolution; Dynamic Neighborhood Search; Self- adaptive
0引 言
旅行商问题(Traveling Salesman Problem,TSP)源于EULER提出的骑士旅行问题,在我国又被广泛称为“货郎担问题”、“邮递员问题”等,是计算机科学、管理学、运筹学中的一个重要内容,属于典型的组合优化范畴。Gaery通过理论方法证明了该问题是一个典型的NP难问题。由于NP难问题具有一定的类归属和研究成果扩展性,在TSP问题上取得的理论或者实验成果,可以用于指导求解其它的NP难解问题,又由于TSP问题具有形式简单、易于描述的特点,在组合优化问题中具有一定的代表性,因此该算法经常被用于作为研究组合优化的典型实验和验证平台,而获得了学界多方广泛且深入的研究。
TSP问题的研究具有非常广泛的工程应用背景和学术研究价值,在工程领域中非常多的工程问题其实质就是TSP问题,亦或可以转换为TSP问题,如:网络通讯、电路板钻孔、交通调度、管道铺设、电网规划等等,因此,快速、有效地实施对TSP问题的研发处理将会具有较高的实际应用价值。
为了有效求解TSP问题,文献[1]针对萤火虫算法的特点,提出了一种离散型萤火虫算法,针对TSP问题专门设计了算法的更新方式、种群初始化方式、个体的编解码方式,为了增强算法的局部有哪些信誉好的足球投注网站能力,加快其收敛速度, 在算法中使用了2-opt优化算子。通过实验显示,该算法的求解要较自适应萤火虫算法具有更高的执行精度;文献[2]通过研究蚁群算法的特点,提出了蚁群算法求解TSP问题的方案,并令蚁群算法根据启发函数 信息素进行算法性能优化,提高了算法的收敛速度;文献[3]同样利用蚁群算法来求解TSP问题。在该论文中,针对蚁群算法容易早熟的弱点,算法中引入“优胜劣汰”的进化策略,对每次迭代的随机进化因子大于进化漂变阈值的路径信息素进行二次更新,加快算法的收敛速度;同时利用随机进化因子的增强算法跳出局部最优解的概率基础,得到相对优化的问题求解;文献[4]提出了应用遗传算法求解TSP的方案。初始种群使用贪婪机制来构造,并
您可能关注的文档
- 水利工程管理中存在的问题探讨.doc
- 水利工程管理体制模式分析.doc
- 水利工程结构混凝土外观质量控制要点.doc
- 水利工程维修养护及管理的思考.doc
- 水利工程规划与可行性分析.doc
- 水利工程设计对施工过程的策略研究.doc
- 水利工程质量检测现状与检测管理方式分析.doc
- 水利工程质量检测过程存在问题的思考.doc
- 水利工程造价全过程控制与管理探索.doc
- 水利工程造价管理存在的问题与应对措施.doc
- “共和国勋章”获得者张富清事迹作文7篇(精选).docx
- “学海导航”中学语文课堂教学设计.docx
- “我和我的家乡”征文范本7篇(精选).docx
- 《木兰诗》翻译及原文.docx
- 湖南省衡阳市衡阳县长宁金山区2025届高三数学上学期12月联考试题文含解析.doc
- 2024年高考生物二轮复习核心考点专项突破人体的稳态与免疫调节练习含解析.docx
- 2024_2025学年高中数学第一章统计1.3统计图表学案含解析北师大版必修3.doc
- 二年级语文下册课文311我是一只小虫子教案新人教版.doc
- 2024_2025学年新教材高中历史第二单元中古时期的世界第4课中古时期的亚洲习题含解析新人教版必修中外历史纲要下.docx
- 2024_2025学年新教材高中地理第4章地球上水的运动与能量交换第2节世界洋流的分布与影响课后练习含解析中图版选择性必修1.doc
文档评论(0)