CPSO算法：一种高效解决旅行商问题的方法

"粒子群复形法求解旅行商问题 (2007年)，浙江大学学报(工学版)，莫愿斌，陈德钊，胡上序" 粒子群优化算法（Particle Swarm Optimization, PSO）是一种模拟自然界中鸟群或鱼群群体行为的全局优化方法。在本文中，作者提出了粒子群复形法（Complex Particle Swarm Optimization, CPSO），专门用于解决旅行商问题（Travelling Salesman Problem, TSP）。TSP是一个经典的组合优化问题，目标是寻找一个访问每个城市一次且返回起点的最短路径。 CPSO算法的创新之处在于它引入了一种新的点选择和组合策略。在每一轮迭代中，所有粒子（代表可能的解决方案）根据其适应值（fitness value）进行排序，然后将好的粒子（适应值高的）与较差的粒子（适应值低的）进行配对。配对的两点之间的中点被选取，然后根据这个中点的适应值与好点的适应值的比值，确定在连线上的某个位置取出新点。这个新点与差点和全局最优点的差值点进行线性组合，形成的新解会替代原来的差点，从而促进种群的整体进化。 为了更好地适应TSP问题，作者还设计了五种特定的解序列运算。这些运算是对粒子路径的特定操作，可以增强算法在搜索空间中的探索能力，同时保持解的质量。通过这些运算，CPSO能够有效地处理TSP问题，并且在14个点的TSP实例和印刷电路板（PCB）的数控钻走刀路线优化问题上进行了验证。 实验结果表明，CPSO算法相比于传统的遗传算法和蚁群算法，具有更强大的搜索性能和更好的稳定性，而且收敛速度更快。这使得CPSO成为解决TSP问题的一种有竞争力的方法，尤其适用于需要高效求解大规模复杂优化问题的领域。 关键词涉及的领域包括：复形法，粒子群复形，旅行商问题，解序列运算，印刷电路板和走刀路线优化。分类号TP183和文献标识码A表明这是工程技术领域的学术论文，发表于2007年的《浙江大学学报(工学版)》。文章编号1008-973X(2007)03-0369-05提供了具体的文章定位信息。