基于汉明距离的改进粒子群算法求解旅行商问题
来源：计算机应用杂志2017年第10期北京时间：
作者：乔屾, 吕志民, 张楠
单位：1. 北京科技大学 工程技术研究院, 北京 100083;2. 北京科技大学 钢铁共性技术协同创新中心, 北京, 100083
摘要：针对传统粒子群算法不适合求解离散型问题，提出一种基于汉明距离的改进粒子群算法。该算法保留了粒子群算法的基本思想和流程，并基于汉明距离为粒子定义了一种新型的速度表示。同时，为了使算法寻优能力更高、避免迭代过程陷入局部最优无法跳出，设计了2-opt和3-opt算子，结合随机贪婪规则，使求解质量更高、收敛更快。在算法后期，为了提高粒子在整体解空间中的全局搜索能力，采用一部分粒子重新生成的方式去重新探索解空间。为了验证算法的有效性，采用了众多旅行商问题（TSP）标准算例进行测试。实验结果表明，对于小规模TSP，该算法可以找到历史最优解；对于大规模TSP，如城市数在100以上的问题，也可以找到满意解，与已知最优解之间偏差度较小，通常在5%以内。
关键词：粒子群优化算法,汉明距离,随机贪婪规则,2-opt算子,3-opt算子,旅行商问题
基金资助：国家自然科学基金资助项目（51274043）。
