| 一种新的求解ATSP问题的PBIL算法 |
| |
| 引用本文： | 汪存富,蔚承建.一种新的求解ATSP问题的PBIL算法[J].计算机工程与应用,2005,41(27):66-68,183. |
| |
| 作者姓名： | 汪存富 蔚承建 |
| |
| 作者单位： | 南京工业大学信息工程学院,南京,210009 |
| |
| 摘 要： | 该文将二进制的人口增量学习算法(PBIL)改进为整数(集值)形式(multiplePBIL),并提出了一种新的基于城市间连接关系的非对称旅行商问题(ATSP)的解法。这种解法结合了集值人口增量学习算法和TSP问题的启发式搜索3-opt加强方法。混沌定位,分布式随机遍历构架和判断进化结束条件的可能性分布的熵的确定是该解法的三大创新之处。
|
| 关 键 词： | 人口增量学习算法 非对称旅行商问题 进化计算 |
| 文章编号： | 1002-8331-（2005）27-0066-03 |
| 收稿时间： | 2004-12 |
| 修稿时间： | 2004-12 |
A New Population-based Incremental Learning Method for the Asymmetric TSP |
| |
| Wang Cunfu,Wei Chengjian.A New Population-based Incremental Learning Method for the Asymmetric TSP[J].Computer Engineering and Applications,2005,41(27):66-68,183. |
| |
| Authors: | Wang Cunfu Wei Chengjian |
| |
| Affiliation: | College of Information Science and Engineering,Nanjing University of Technology,Nanjing 210009 |
| |
| Abstract: | In this paper the binary population-based incremental learning is extended to an integer form,a new approach to the asymmetric traveling salesman problem based on linkage relations between cities is proposed.The main properties of this method are combining multiple PBIL with 3-opt aided by chaos equation,a distributed stochastic tour construction,and the decision of entropy of probability distribution for terminate condition on process of evolution.19 asymmetric traveling salesman problems gained from the Intemet are all solved.The results show that the method proposed in this paper is comparable to the intemational advanced level on ATSP problems and is capable of finding high quality solutions to the problems in short times,particular for large instances. |
| |
| Keywords: | Population-Based Incremental Learning(PBIL) ATSP evolutionary computation |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
