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

为将面向连续优化的粒子群优化算法应用于旅行商问题的求解,提出了旅行商问题的权重编码方案。该方案将属于组合优化的旅行商问题转化为连续优化问题,同时保留了粒子群算法的易操作性和高效性。针对粒子群算法易陷入局部最优的问题,提出了适合旅行商问题的基于k-中心点法的改进措施。该措施利用简单匹配系数构建粒子群的相异度矩阵,在此基础上采用k-中心点法对粒子群进行聚类分析,实现了粒子之间的信息交换,扩大了粒子的搜索空间,避免算法陷入局部最优。最后,用旅行商问题标准库的4个算例验证了权重编码方案和改进粒子群算法的有效性。