新型混沌粒子群算法在tsp中的应用-武汉科技大学学报.pdf

第 卷第 期 武 汉 科 技 大 学 学 报 ， ３４ ２ 犞狅犾．３４犖狅．２ 年 月 ２０１１ ４ 犑狅狌狉狀犪犾狅犳犠狌犺犪狀犝狀犻狏犲狉狊犻狋狅犳犛犮犻犲狀犮犲犪狀犱犜犲犮犺狀狅犾狅 犃狉．２０１１ 狔 犵狔 狆  新型混沌粒子群算法在 ＴＳＰ中的应用 李九永，王 京 　 （北京科技大学冶金工程研究院，北京， ） １０００８３ 摘要：针对旅行商问题，提出一种结合混沌优化和粒子群算法的新型混沌离散粒子群方法（ ）。新算法 ＣＩＰＳＯ 根据此类组合优化问题解的固有地形特征，利用混沌运动的遍历性、随机性等特点进行求解，其基本思想是在 求解过程中对粒子进行混沌扰动避免陷入局部最优，并引入群体间粒子的交叉作用来提高寻优效率。通过与 遗传算法、蚁群算法和模拟退火算法等比较以及不同ＴＳＰ问题的仿真实验发现，该方法是一种能进行有效优 化的新方法。 关键词：粒子群算法；旅行商问题；混沌理论；信息交流策略 中图分类号： 文献标志码： 文章编号： （ ） ＴＰ３０１．６ Ａ １６７４３６４４２０１１０２０１３１０６ 　　 　　 旅行商问题（ ）属于一类非连续域优化的 优化算法的新方法，且在其中引入信息交流策略， ＴＳＰ 　　 ＮＰｈａｒｄ组合优化问题，即不存在一个多项式时 以期对 ＴＳＰ问题的求解效率作出改进，并针对其 ［］ １ 间内的算法可求尽此问题 ，其求解目标是求得 收敛速度慢的问题，提出在计算前期加入混沌优 一个依次经过各个城市并最终回到出发点的哈密 化理论的离散化方法，以加快算法的收敛和跳出 顿回路，使所经过的总路程最短。已有研究发 局部最优；同时针对随之产生的求解精度不高的 ［］ ２ 现 ，不同规模的ＴＳＰ问题具有不同的适应度地 问题引入信息交流策略，以使计算后期在求解全 形，随着城市规模的扩大，其多峰值特性也逐渐增 局最优进行细有哪些信誉好的足球投注网站时表现出较好的效果。 强。求解该离散问题的主要方法目前主要有模拟 １ 基本粒子群算法的定义 退火算法、遗传算法、启发式有哪些信誉好的足球投注网站法、Ｈｏｆｉｅｌｄ神 　 ｐ 经网络算法和蚁群算法等，这些算法在求解速率 １．１ 粒子群算法及其离散化定义 　 和精度上往往不能兼顾。 ＰＳＯ算法模拟鸟群的捕食行为，随机初始化 粒子群优化算法（ ）是一种进化计算技 ＰＳＯ