求解旅行商问题的人工蜂群算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇求解旅行商问题的人工蜂群算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要： 采用人工蜂群算法对旅行商问题进行求解，给出了人工蜂群算法求解该问题的具体方案，对不同的旅行商问题算例进行了仿真实验。结果表明，算法可以有效、快速地找到较小规模问题的最优解。
Abstract： The article uses artificial bee colony algorithm to solve traveling salesman problems， gives the specific solutions of artificial bee colony algorithm for solving traveling salesman problem， and makes simulation experiment for the different traveling salesman. The results show that the algorithm can efficiently and quickly find optimal solutions to small problems.
关键词： 人工蜂群；旅行商问题；组合优化
Key words： artificial bee colony；travelling salesman problem；combinatorial optimization
中图分类号：TP18 文献标识码：A 文章编号：1006-4311（2013）09-0206-02
0 引言
旅行商问题（Traveling salesman problem）是一个典型的易于描述却难以大规模处理的NP难题，有效地解决该问题具有重要的理论意义和实用价值。许多学者为该问题的求解提供了独特的思路，都对其进行了比较深入的研究[1-4]。
旅行商问题可以简单的描述为[2]：给定N个城市C=（C1，C2，C3，…，CN），求一条经过C中所有城市一次且仅一次的一条路径（Cn （1），Cn （2），Cn （3），…Cn （N）），其中任意两个城市的距离记为d（Ci，Cj），使得闭合路径■d[Cn （i），Cn （i+1）mod N]为最小。
人工蜂群算法[5-8]（Artificial Bee Colony，ABC）是Karaboga于2005年提出的一种随机优化算法，蜜蜂根据各自分工进行活动，算法模拟蜜蜂群体的采蜜行为。实现蜂群信息的共享和交流，从而找到最优解。目前算法在离散优化领域的研究和应用相对较少，主要集中在连续优化领域。仿真实验的结果说明该方法求解较小规模旅行商问题是有效可行的。本文将人工蜂群算法应用于求解旅行商问题。
1 人工蜂群算法
在人工蜂群算法中，每个蜜源的位置代表优化问题的一个可能解，蜂群由采蜜蜂、观察蜂和侦察蜂三个部分组成，蜜源的收益度对应于问题的适应度。首先，人工蜂群算法随机产生初始种群，每个解xi（i=1，2，…，N）为一个D维的向量（D为搜索空间的维数）。即N个初始解（N为采蜜蜂的数目也为蜜源数目）。采蜜蜂记住自己以前的最优解，在采蜜源邻域搜索，经过初始化，采蜜蜂、观察蜂和侦察蜂进行循环搜索。公式为x■■=xij+？准（xij-xkj）（1）
式中，k∈{1，2，…，N}和j∈{1，2，…，D}是随机选择的下标，并且k≠i，？准是[-1，1]上均匀分布的随机数。
采蜜蜂采用贪婪准则，比较记忆中的最优解和邻域搜索解，当搜索解优于记忆最优解时，替换记忆解；反之，保持不变。观察蜂选择某个蜜源的概率为：qi=■（2）
假如一个蜜源经过限定的的循环次数limit之后不能被改进，上式中fiti为第i个解的适应值。则该蜜源处的采蜜蜂成为侦察蜂，假设被放弃的位置为xi，则侦察蜂通过下列公式替换xi，该蜜源位置将会被侦察蜂在解空间内发现的随机新位置代替：x■■=x■■+rand（0，1）（x■■-x■■）（3）
新算法把旅行商问题中城市的个数作为向量的维数，计算这条路径的长度作为该个体的适应值，每个向量的元素的大小顺序作为旅行商问题一个可行解。
求解旅行商问题的人工蜂群算法
步骤1：设置迭代次数gen，群体规模N，循环次数limit，最大进化代数Maxgen；
步骤2：初始化种群X（N×n），n
步骤3：X xi i=1，2，…，N计算适应值；
步骤4：令gen=1；
步骤5：令s=1；
步骤6：采蜜蜂按公式（1）产生新解x■■，如果新解的适应值优于xi，则xi=x■■，否则不变；
步骤7：观察蜂根据qi选择蜜源，如果新解的适应值优于xi，则xi=xx■■，否则不变，并按公式（1）产生新解xx■■；
步骤8：计算xi的适应值，并根据公式（2）
计算概率qi；
步骤9：记录最好解；
步骤10：s=s+1；
步骤11：gen=gen+1；
步骤12：如果s
步骤13：经过limit次循环后，判断是否有需要丢掉的解，若有，则侦察蜂按公式（3）产生新解；
步骤14：如果gen
3 仿真实验
以文献[3]提供的2个算例来验证算法的有效性。算例1是14个城市的旅行商问题；算例2是10个城市的旅行商问题。
算法实现时，算例1参数设置为N=120，Maxgen=10000，limit=100；算例2参数设置为：N=80，Maxgen=10000，limit=100。在上述参数设置下，每个算例分别连续运行10次，每次都可以较快的找到最优路径，并且在种群规模相同的情况下与与文献[3]的求解进行比较。比较结果如下：
仿真实验的结果表明本文算法在求解较小规模旅行商问题上是行之有效的。
4 结论
旅行商问题是经典的NP问题，本文采用人工蜂群算法来求解该问题，具有收敛速度快，计算量小等良好的性能，主要是在求解较小规模旅行商问题时采用这种方案。尽管算法比目前求解旅行商问题的经典算法还有一定的差距，但它对于组合优化问题无疑具有启发性，可以将人工蜂群算法应用到离散问题，为进一步深入研究奠定了基础，应用人工蜂群算法来解决旅行商问题是目前的一种新的尝试。
参考文献：
[1]陈，秦玲，陈宏建，等.具有感觉和知觉特征的蚁群算法[J].系统仿真学报，2003，15（10）：1418-1425.
[2]蔡之华，彭锦国，高伟，等.一种改进的求解TSP问题的演化算法[J].计算机学报，2005，28（5）：823-828.
[3]胡中波，熊盛武.差分演化算法求解旅行商问题[J].计算机应用与软件，2008，25（7）：257-259.