一种基于子群杂交机制的粒子群算法求解旅行商问题

粒子群算法是在借鉴海鸥群落觅食行为基础上发展起来的仿生学优化算法,为求解复杂的组合优化问题提供了一种新的思路。本文提出一种结合粒子群算法结构和求解TSP问题蚁群算法特点的新算法,将多用于连续空间优化的粒子群成功扩展到TSP领域。算法通过杂交粒子选择机制,运用两种不同设计的杂交算子,成功模拟了自然界同物种不同种群间的协作与交流,将多子群策略和子群间杂交操作引入粒子群结构之中,增强算法的寻优能力。实验结果表明,该算法能有效地保证粒子间多样性差异,通过优化信息在子群间顺畅交流,有效地促进整个群落的进化收敛。该算法在解决TSP问题时,无论在收敛性和鲁棒性方面都优于一般的单群体、非杂交算法,是一种优秀的TSP问题解法。最终优化结果均达到TSPLIB中记录的已知最优解。