基于k-中心点法的改进粒子群算法在旅行商问题中的应用

被引:16
作者
张旭梅
邱晗光
机构
[1] 重庆大学经济与工商管理学院
关键词
旅行商问题; 粒子群优化算法; 聚类分析; k-中心点法;
D O I
10.13196/j.cims.2007.01.101.zhangxm.016
中图分类号
TP301.6 [算法理论];
学科分类号
摘要
为将面向连续优化的粒子群优化算法应用于旅行商问题的求解,提出了旅行商问题的权重编码方案。该方案将属于组合优化的旅行商问题转化为连续优化问题,同时保留了粒子群算法的易操作性和高效性。针对粒子群算法易陷入局部最优的问题,提出了适合旅行商问题的基于k-中心点法的改进措施。该措施利用简单匹配系数构建粒子群的相异度矩阵,在此基础上采用k-中心点法对粒子群进行聚类分析,实现了粒子之间的信息交换,扩大了粒子的搜索空间,避免算法陷入局部最优。最后,用旅行商问题标准库的4个算例验证了权重编码方案和改进粒子群算法的有效性。
引用
收藏
页码:99 / 104
页数:6
相关论文
共 6 条
[1]   一种基于子群杂交机制的粒子群算法求解旅行商问题 [J].
谭皓 ;
王金岩 ;
何亦征 ;
沈春林 .
系统工程, 2005, (04) :83-87
[2]   改进微粒群优化算法求解旅行商问题 [J].
肖健梅 ;
李军军 ;
王锡淮 .
计算机工程与应用, 2004, (35) :50-52
[3]   求解旅行商问题的混合粒子群优化算法 [J].
高尚 ;
韩斌 ;
吴小俊 ;
杨静宇 .
控制与决策, 2004, (11) :1286-1289
[4]   改进的基本粒子群优化算法 [J].
王存睿 ;
段晓东 ;
刘向东 ;
周福才 .
计算机工程, 2004, (21) :35-37
[5]   带时间窗车辆路径问题的粒子群算法 [J].
李宁 ;
邹彤 ;
孙德宝 .
系统工程理论与实践, 2004, (04) :130-135
[6]   粒子群优化算法求解旅行商问题 [J].
黄岚 ;
王康平 ;
周春光 ;
庞巍 ;
董龙江 ;
彭利 .
吉林大学学报(理学版), 2003, (04) :477-480