一种基于粒子群优化的蚁群算法求解TSP问题的方法

专利类型：发明专利 

语 言：中文 

申 请 号：CN201810742050.5 

申 请 日：20180709 

发 明 人：廖勇赵萌轩 

申 请 人：重庆大学 

申请人地址：400044 重庆市沙坪坝区沙正街174号 

公 开 日：20181130 

公 开 号：CN201810742050.5 

代 理 人： 

代理机构： 

摘　　要：本发明公开了一种基于粒子群优化的蚁群算法求解TSP问题的方法。该方法在求解TSP问题时，利用粒子群优化的思想，对蚁群算法的参数取值进行优化并选择。在粒子群算法中，将蚁群算法的5个参数(q₀,α,β,ρ,m)看作粒子群算法中的一个粒子，经反复调用蚁群算法计算并更新后，可以优化蚁群算法的性能，使参数通过粒子自适应选取，而不再依靠人工经验选取。这种基于粒子群优化的蚁群算法将计算出的5个参数组合反馈回蚁群算法后，对解决TSP问题有优异的效果。 

主 权 项：1.一种基于粒子群优化的蚁群算法求解旅行商问题的求解方法，其特征在于该方法包括如下步骤：S1.蚁群算法求解TSP问题；TSP问题是指给定n个城市，有一个旅行商从某一城市出发，访问各城市一次且仅有一次后再回到原城市，要求找到一条最短的巡回路径；利用蚁群算法，可根据蚂蚁在访问每条路径后留下的信息素来实现蚂蚁间的相互信息传递，搜索TSP问题中的最短路径；S2.粒子群算法结合蚁群算法进行参数的优化训练；根据粒子群算法的特点，将每个蚂蚁子群的(q0,α,β,ρ,m)5个参数作为粒子群的一个粒子，并重复调用蚁群算法，选取蚁群算法求解到的路径长度作为判断参数优劣的标准；通过粒子群来优化各蚂蚁群的开发与探索的能力，从而避免了蚂蚁群过早的收敛到局部最优解。 

关 键 词： 

法律状态：生效 

IPC专利分类号：G06Q10/04;G06Q10/00;G06N3/00;G;G06;G06Q;G06N;G06Q10;G06N3;G06Q10/04;G06Q10/00;G06N3/00