搜索
信息学院郭浩TSP问题算法原理算法实现一、TSP问题实例TSP问题很多实际问题都属于TSP问题的范畴1、旅游景区规划问题，描述的是游客应如何规划旅游线路，使得所经过的路径总和最小；2、物流配送问题，对车辆的配送网络进行优化，缩短配送时间，从而提高顾客满意度；3、公交线路规划问题只在规划路径网络，寻找最优的公交路线设置，从而满足群体的需求。…….TSP问题旅行商问题(TSP，travelingsalesmanproblem)是一个为学术界广泛研究的问题，长期以来它吸引了众多学者对其进行研究。深入地研究TSP问题能够为解决实际的管理问题提供一定的理论基础。思考：群体智能算法群体智能算法(SwarmIntelligenceAlgorithm，SIA)是模拟自然界生物的群体行为而构造的随机优化算法，是在群体智能领域中随着计算智能研究的逐步深入而产生的一种新兴的计算智能模式，它是群体智能研究中的一个重要分支。群体智能算法是从某种由大量个体表现出来的群体行为出发，从它们的群体行为中提取模型，为这些行为建立一些规则，从而提出优化算法。在群体智能算法中，每一个个体都是具有经验和智慧的智能体(Agent)，个体之间存在互相作用机制，通过相互作用形成强大的群体智慧，并用于解决那些因为难以建立有效的形式化模型而用传统优化方法又难以解决甚至无法解决的问题。群体智能算法自上世纪90年代基于蚂蚁觅食行为的蚁群算法(AntColonyOptimization，ACO)提出以来，相继产生了以飞翔的鸟类为模型的粒子群算法（ParticleSwarmOptimization，PSO）、基于鱼类觅食行为的人工鱼群算法（ArtificialFishswarmAlgorithm，AFA）、基于青蛙觅食行为的蛙跳算法(ShuffledFrogLeapingAlgorithm，SFLA)以及模拟蜜蜂行为的人工蜂群算法（ArtificialBeeColony，ABC）等。二、人工蜂群算法的原理算法原理蜂群的智能模型中有三个基本组成元素：食物源（foodsources）、雇佣蜂（employedforagers，EF）、非雇佣蜂(unemployedforagers，UF)；两种最为基本的行为模式：为食物源招募（recruit）蜜蜂和放弃（abandon）某个食物源算法原理食物源：食物源的价值由多个因素控制，如：它距离蜂巢的远近；食物源花蜜的丰富程度；获得食物的困难程度等。算法中使用“食物源的收益率”(profitability)，来综合代表以上各因素。雇佣蜂：也称作引领蜂,模型中引领蜂的数量通常是与食物源对应的。引领蜂具有记忆功能，将自己搜索到的食物源的相关信息(距离蜂巢的远近、方向、花蜜的丰富程度等)存储起来，并以一定的概率分享给其他的蜜蜂。非雇佣蜂：有两种非雇佣蜂。侦察蜂（scoutbees）：在算法的开始和过程中，始终伴随着侦察蜂对食物源的“探索行为。侦察蜂通常在蜂巢周围搜索附近的食物源；根据观察，蜂群中的侦察蜂数量大约占整个蜂群数量的5％一20％。跟随蜂(onlookerbees)：蜂巢附近等待引领蜂共享食物源信息的蜜蜂，他们观察引领蜂的舞蹈，选择自己认为满意的蜜蜂进行跟随。算法原理算法原理假设有两个已经发现的蜜源A、B，刚开始时非雇佣蜂没有关于蜜源的任何信息，有两种选择：(1)作为侦察蜂，自发寻找蜂巢附近的蜜源（‘S’线）。(2)在观察到其他蜜蜂的摇摆舞后,它可以被招募并开始按照获得的信息寻找蜜源。非雇佣蜂发现新的蜜源后，蜜蜂依靠自身的能力记住蜜源的位置，并迅速开始采蜜，因此，非雇佣蜂变成了雇佣蜂，蜜蜂采完蜜回到蜂箱后，它有以下几种选择:（1）放弃蜜源(收益度不高)，成为待工的跟随蜂(UF)。（2）在返回同一蜜源前，跳摇摆舞招募蜂巢其它伙伴(EF1)。（3）不招募其它蜜蜂，继续采蜜(EF2)。算法原理初始时刻,所有蜜蜂没有任何先验知识，其角色都是侦察蜂。随机搜索到食物源后，侦察蜂返回蜂巢的舞蹈区，根据食物源收益度的相对大小。侦察蜂可以转变为上述任何一种蜜蜂。转变的原则如下：当所采集食物源的收益度相对很低时，它可以再次成为侦察蜂搜寻附近的食物源，其转变结果是放弃上次采集的食物源；当所采集食物源的收益度排名小于临界值(如排名在后50%)时，它可以在观察完舞蹈后成为跟随蜂，并前往相应的食物源采蜜；当所采集食物源的收益度排名高于临界值时，它成为引领蜂，继续在同一食物源采蜜,并在舞蹈区招募更多的蜜蜂采集相应食物源（EF1）。算法原理人工蜂群算法在搜索收益度最优解的过程中，引领蜂有保持优良蜜源的作用；跟随蜂增加优良蜜源对应的蜜蜂数目，起到提高算法收敛速度的作用；侦察蜂随机搜索新蜜源，能帮助算法跳出局部最优。人工蜂群算法循环结束条件通常可以设为循环次数递减为零、前N个收益度的花蜜源相同或者前多个花蜜源相同等。算法原理ABC算法在求解优化问题时，食物源的位置被抽象成解空间中的点，蜜蜂采蜜(食物源)的过程也就是搜寻最优解的过程。考虑全局优化问题(P),则问题(P)的多个可行解的一个结合称为一个种群，种群中每个元素(可行解)称为一个食物源，每个食物源的优劣程度取决于待优化问题所确定的适应度值，解的个数(SN)等于引领蜂或跟随蜂的个数。我们用d维向量来表示第i个食物源的位置。首先，ABC算法生成含有SN个解(食物源)的初始种群，每个解是一个d维的向量。然后，蜜蜂对所有的食物源进行循环搜索，循环次数为C(C=1，2，…，MCN)。ix算法原理引领蜂首先对相应的食物源(解)进行一次邻域搜索，如果搜索到的食物源(解)的花蜜质量(适应度)优于以前的，则用新的食物源位置代替旧的食物源位置，否则保持旧的食物源位置不变。所有的引领蜂完成搜索之后，回到舞蹈区把食物源花蜜质量的信息通过跳摇摆舞传达给跟随蜂。跟随蜂根据得到的信息按照概率选择食物源。花蜜越多的食物源，被选择的概率越大。跟随蜂选中食物源后，也进行一次邻域搜索，并保留较好的解。ABC算法就是通过如此重复的搜索，最终来找到最优解。算法流程(1)初始化种群的解为，i=1…，SN，并计算每个解的适应度值；(2)引领蜂根据公式（这两个数都是随机选取的，但是k不能等于i(k是邻域的一个解)。是一个随机数，它控制邻域的生成范围，随着搜索接近最优解，邻域的范围会逐渐减小）做邻域搜索产生新解，并且计算其适应度值；(3)如果新解的适应度值好于原解，则用前者替换后者，将新解作为当前最好解，否则保留不变；ixiv算法流程(4)计算的适应度值，并根据公式（是第i个解的适应度值，SN是解的个数）计算与相关的概率值；(5)跟随蜂根据概率值选择食物源(解)，并根据上一页的公式进行邻域搜索产生新解，计算其适应度值；(6)同(3)；(7)判断是否有要放弃的解，如果存在，则侦察蜂根据公式产生一个新解代替它；(8)记录迄今为止最好的解；(9)判断是否满足循环终止条件，如满足则输出最优结果，否则返回(2)ixip算法特点1、它是一种自然算法。模拟自然界中蜂群高效的寻找食物源的机制。2、具有角色分工、角色转换机制。蜂群中的蜜蜂因角色不同而分别采用不同的搜索方式，并且角色之间可以相互转换。3、较强的协同工作能力。蜂群在对路径进行选择时，不同角色之间利用信息交互方式，倾向于选择以前蜜蜂搜索到较为丰富的食物源路径，从而形成正反馈机制，并能以较大概率找到最优解。4、鲁棒性。结合概率规则和随机性选择进行目标的搜索，不必具有先验的知识，具有鲁棒性和适应性。5、可以与其他启发式算法结合使用。人工蜂群算法之所以能够较快的发现最优解，主要是因为算法中引领蜂和跟随蜂在寻找最短路径时形成的正反馈机制，从而加快了算法的收敛速度。算法实现所有城市的任一种排列即是问题的一个解，解空间由若干解构成，因此初始化解空间就是随机产生多个不同的城市序列。以n个城市为例，从1到n对其进行编号，那么完成一次旅行的路径就用1到n的一个排列组合来表示。在人工蜂群算法中，每一个引领蜂或者跟随蜂的位置就对应一个路径的组合，食物源的丰富程度对应这条路径的长度，用适应度函数值来描述食物源的丰富程度，也就是说，适应度函数值越小的引领蜂或者跟随蜂所在的位置，所代表的路径也最优。算法实现算法具体实现过程中，先给出城市的坐标（即城市的位置），再计算出完全图的赋权邻接矩阵，蜂群初始化后，计算出初始种群的适应度函数值，找出当前的最小值和相应的位置并记录下来。引领蜂的采蜜过程，也就是位置的更新，我们选取这只引领蜂所代表的路径中的任意两处进行位置调换，形成新的位置，并计算新位置对应的适应度函数值，与已经记录的最小值进行比较，如果比它更优，则替换当前的最小值，否则保持不变。跟随蜂的跟随过程，采取的是轮盘赌概率选择法，计算好每只引领蜂被跟随的概率，然后跟随蜂按照相应的概率选取要跟随的引领蜂，并进行采蜜（与引领蜂的采蜜过程一样），按照贪婪准则，保留最优的解。如果某只引领蜂或者跟随蜂采蜜了limit次过后，仍旧没有发现更好的解，则转化为侦察蜂，对其置于一个随机的初试路径，再继续搜索。按照以上所述的三种蜂的采蜜与转换过程，进行算法的迭代，最后找出那条满足条件的最优路径，并保证这条路径的长度最短。算法实现仿真验证一选用burma14.tsp问题进行实验仿真，参数设置为NP=20，（employedbees+onlookerbees）Foodnumber=10，limit=50，maxCycle=500。运行10次，得到结果如下表所示：TSPLIB()TSP的标准测试库运行次数最优路径最小距离19→11→8→13→7→5→6→12→14→4→3→2→1→10→931.879126→5→4→3→14→2→1→10→9→11→8→13→7→12→630.878535→4→3→14→2→1→10→9→11→8→13→7→12→6→530.878547→12→6→5→4→3→14→2→1→9→10→11→8→13→731.3755514→3→4→5→6→12→7→13→8→11→9→10→1→2→1430.878563→14→2→8→1→10→9→11→13→7→12→6→5→4→331.2088711→1→8→13→7→12→6→5→4→3→14→2→10→9→1131.226981→8→2→14→3→4→5→6→12→7→13→11→9→10→131.2088911→9→10→1→2→14→3→4→5→6→12→7→13→8→1130.87851014→2→1→10→9→11→8→13→7→12→6→5→4→3→1430.8785仿真验证二选用ulysses22.tsp问题进行实验仿真，参数设置为NP=60,Foodnumber=30,limit=100,maxCycle=500。下表为人工蜂群算法运行10次的仿真结果。结论一有随机性在里面每次运行结果不一样所以以后运用算法时应多次运行，求得最优解扩展验证另外16个点Elapsedtimeis1.848382seconds.最优路径1-5-3-7-2-8-15-16-10-4-11-14-6-12-9-13-1最小距离31.857119个点（极限！！）Elapsedtimeis1.617617seconds.最优路径9-12-6-14-11-17-16-10-4-19-15-8-2-7-3-18-5-1-13-9最小距离35.965420个点Elapsedtimeis0.985919seconds.最优路径17-12-9-13-6-14-11-7-19-20-18-5-1-3-4-10-2-8-15-16-17最小距离42.0124Elapsedtimeis2.074763seconds.最优路径3-5-1-18-17-20-14-6-13-9