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