基于聚类集成的蚁群优化与受限解空间的TSP算法

发布时间：2018-05-19 02:23

  本文选题：蚁群算法 + TSP　； 参考：《中国科学技术大学学报》2016年09期

【摘要】：蚁群算法是一种元启发式搜索算法,能有效地解决TSP这类NP问题.针对该算法的信息素更新机制易导致陷入局部最优的缺点,提出了一种基于聚类集成的蚁群优化与受限解空间的TSP算法.其主要思想如下:先用三角形TSP算法生成初始TSP并构建蚁群的初始转移概率矩阵,以减少蚂蚁选择的随机性;然后运用k-means聚类集成生成关联矩阵,作为扰动因子以优化蚂蚁对城市的选择概率,即关联城市相互吸引,不关联城市相互排斥,以避免过早陷入局部最优;最后提出一种重组受限解空间的边的方法再次优化蚁群的解.实验结果表明,与同类算法相比,该算法具有较优的结果.
[Abstract]:Ant colony algorithm is a meta-heuristic search algorithm, which can effectively solve NP problems such as TSP. Aiming at the disadvantage that the pheromone updating mechanism of the algorithm is easy to fall into local optimum, an ant colony optimization and constrained solution space TSP algorithm based on clustering ensemble is proposed. The main ideas are as follows: first, the initial TSP is generated by triangular TSP algorithm and the initial transition probability matrix of ant colony is constructed to reduce the randomness of ant selection, and then the association matrix is generated by k-means clustering integration. As a disturbance factor to optimize the ant selection probability to the city, that is, the associated cities attract each other, the unrelated cities mutually repel each other, so as to avoid falling into local optimum prematurely. Finally, a method of reorganizing the edge of constrained solution space is proposed to optimize the solution of ant colony again. The experimental results show that the algorithm has better results than similar algorithms.
【作者单位】： 宁波大学信息科学与工程学院;宁波大学科学技术学院;
【基金】：国家自然科学基金(61175054)资助
【分类号】：TP18

【相似文献】

相关期刊论文 前10条

1 张邦楚;彭琛;余新荣;周晓华;邹丽君;;基于蚁群优化的多弹协同目标分配算法[J];弹箭与制导学报;2012年04期

2 徐永成;陈];;基于蚁群优化的二分网络社区挖掘[J];计算机科学与探索;2014年03期

3 崔世钢;徐雪莲;赵丽;田立国;杨耿煌;;蚁群优化在移动机器人路径规划上的研究[J];制造业自动化;2009年01期

4 李文江;杨崔;王涛;;基于蚁群优化的模糊神经网络控制器的应用研究[J];工矿自动化;2009年03期

5 刘延风;刘三阳;;基于蚁群优化的置换流水车间调度算法[J];系统工程与电子技术;2008年09期

6 姜万录;刘伟;张瑞娟;陈海军;;基于蚁群优化的神经网络智能PID控制策略研究[J];机床与液压;2010年13期

7 朱思峰;刘方;柴争义;;一种基于蚁群优化的无线传感器网络路由算法[J];北京理工大学学报;2010年11期

8 舒期梁;赵丽萍;;基于改进蚁群优化的无线传感器网络路由算法[J];计算机测量与控制;2011年05期

9 吴文铁;宋曰聪;李敏;;蚁群优化神经网络的网络流量混沌预测[J];计算机工程与应用;2012年34期

10 邬欢欢;张任;;基于蚁群优化的无线传感器网络路由算法[J];智能计算机与应用;2014年03期

相关会议论文 前1条

1 姜万录;刘伟;张瑞娟;陈海军;;基于蚁群优化的神经网络智能PID控制策略研究[A];中国机械工程学会流体传动与控制分会第六届全国流体传动与控制学术会议论文集[C];2010年

相关博士学位论文 前1条

1 胡小兵;蚁群优化原理、理论及其应用研究[D];重庆大学;2004年

相关硕士学位论文 前6条

1 伍祥红;基于蚁群优化的自主水下机器人路径决策方法研究[D];哈尔滨工程大学;2007年

2 仵振东;基于蚁群优化的遥感影像分类研究[D];安徽理工大学;2014年

3 王乐衡;考虑多元设备类型的超启发式跨单元调度方法[D];北京理工大学;2015年

4 刘伟;基于蚁群优化的神经网络智能PID控制策略研究[D];燕山大学;2010年

5 翟晨汐;基于蚁群优化的视觉板球系统的直接自适应模糊滑模控制[D];大连理工大学;2015年

6 任平;基于蚁群优化的WSN路由算法研究[D];西安科技大学;2012年

，

本文编号：1908294