基于汉明距离的改进粒子群算法求解旅行商问题

摘要 针对传统粒子群算法不适合求解离散型问题，提出一种基于汉明距离的改进粒子群算法。该算法保留了粒子群算法的基本思想和流程，并基于汉明距离为粒子定义了一种新型的速度表示。同时，为了使算法寻优能力更高、避免迭代过程陷入局部最优无法跳出，设计了2-opt和3-opt算子，结合随机贪婪规则，使求解质量更高、收敛更快。在算法后期，为了提高粒子在整体解空间中的全局搜索能力，采用一部分粒子重新生成的方式去重新探索解空间。为了验证算法的有效性，采用了众多旅行商问题（TSP）标准算例进行测试。实验结果表明，对于小规模TSP，该算法可以找到历史最优解；对于大规模TSP，如城市数在100以上的问题，也可以找到满意解，与已知最优解之间偏差度较小，通常在5%以内