基于蚁群算法的m-团队定向问题研究

基于蚁群算法的m-团队定向问题研究

定向运动是一项工人运动。参与者可以通过识别和使用地图来使用正确的地图和指针，从起点出发，在规定的时间内，尽可能多地访问具有不同分数的固定点，并达到规定的结束点。超过此点的人将失去资格，并以获得更高的分数。在获得相同分数的情况下，总时间最短的人将获得胜利。定向运动的目标就是在总的时限情况下,最大化获取的总分数。因为存在时限,参赛选手必须精心设计自己的路线,选择点标子集进行到访,以最大化获取分数,这就是单选手定向运动。团队定向运动是对单选手定向运动的扩展,比赛中一个团队由多名选手组成,根据比赛规则,每名选手从相同的出发点出发,在规定的时限条件下选择点标到访,并最终到达设定的终止点。比赛中,每个点标只能由一名队员到访并获取相应的分值。团队比赛中需要设计每名选手的行进路线,以求取在设定条件下团队总分最大化。定向问题与有总旅行费用限制的TSP问题类似,可用来建模许多实际问题,如总能力限制条件下车辆路径问题、多目标售货问题、家庭燃料配送问题等。目前对定向问题的优化有多种方法,如启发式方法、车辆路径法、分枝界定法、整数规划法、动态规划法、人工神经网络法等。本文针对团队定向问题,提出了子群个体协作模式,子群中个体通过访问禁忌表交换彼此访问点标信息,最终给出每位选手参赛路径的蚁群优化算法。1cij点标集记G=(V,E)为完全图,V={1,2,…,n}为点标集,E为点标集之间的边集,各点标之间的距离为cij(cij>0,cii=∞,i,j∈V),cij也可表示为i,j点之间其他类型旅行代价。在点标集V中,每个点标i具有相应的分值si>0(i≠1,n)。设团队中有m个队员,则目标为在V中寻找m条路径经过点标集的分值和最大,且每个队员通过每条路径的时间不能超过Tmax,定义变量:则m–团队定向问题为其中,Pk表示第k个选手越野速度,式(4)限定了每位选手不能超时,式(5)保证每处点标只能由至多一位选手到访,式(6)、式(7)确保m条路线均从出发点出发,到终止点结束。2基于控制策略的残留信息考量蚁群算法是近年来出现的一种新的仿生类算法,它吸收了生物世界中蚂蚁的行为特性。研究发现,在蚂蚁群找到食物时,它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁与蚂蚁之间有一种非常重要的通信媒介,即它们在移动过程中所释放的一种特有分泌物——信息素(pheromone),蚂蚁可以觉察到彼此之间的信息素并影响自己的行为。当某些路径上走过的蚂蚁较少时,其信息素量也就相应较小,且信息素随着时间而逐渐挥发,信息素强度会越来越弱,后来蚂蚁选择这些路径的可能性就会越来越小。与之相对,当某条路径上走过的蚂蚁较多时,信息素数量就越多,以致强度增大,将吸引更多的蚂蚁选择该路径。通过这种内在的搜索机制,便逐渐形成了一种最佳路线。蚁群算法具有并行性、鲁棒性、正反馈等特点。蚁群算法自问世以来,已在多方面表现出相当好的性能,如在TSP问题,二次分配问题(QAP0、多目标TSP、交通分配、着色问题、集成电路布线、网络路由等)。利用蚁群算法解TSP问题时,将m只蚂蚁放入到n个随机选择的城市中,每只蚂蚁的每一步行动是,根据一定的依据选择下一个它还没有访问的城市;同时在完成一步(从一个城市到达另一城市0或一个循环(完成对所有n个城市访问0后,更新所有路径上的残留信息浓度。选择下一城市的依据主要是两点:τij(t)为t时刻连接城市i和j的路径上残留信息浓度,ηij为由城市i转移到城市j的启发信息,该启发信息是由要解决的问题给出的,由一定算法实现。t时刻位于城市i的蚂蚁k选择城市j为目标城市的概率是式中,α为残留信息的相对重要程度;β为期望值(或启发性信息)的相对重要程度;Nik为所有可能的目标城市,即还没有到访的城市;P_(ij)k(t)为t时刻蚂蚁k由i城市到j城市的概率。对于残留信息素在算法中引发挥发机制进行处理,以避免信息素过渡积累。每只蚂蚁完成一个循环后,相应边上的信息素浓度为式中,ρ为残留信息的保留部分;1-ρ为残留信息在t到t+n时间段内挥发部分,ρ为小于1的常数;∆τkij为蚂蚁k在时间段t到t+n内的访问过程中,在i到j的路径上留下的残留信息浓度。3签到路径迭代定向问题求解与一般TSP问题、VRP问题不同,定向问题解为点标集V的子集。求解过程是一个选择到访的点标集,并优化到访路径的过程。在各种启发式求解方法中,首先采用不同选择到访的点标集,然后利用TSP、VRP等方法优化到访路径,此过程反复迭代,最终满足条件获取分数最高的解为最终解。m–定向问题求解需为每名参赛选手选择行进路线,并优化到访顺序,最终满足约束条件的团队总分最高者为最终解。适用于m–定向问题蚁群优化算法伪代码如下://终止条件是否满足?//判断子群中每只蚂蚁是否到终点//随机确定子群中哪只蚂蚁应前进//蚂蚁确定前行,随机前行?if(nextpointisfeasible)//下一点标满足条件elseif(nopointisfeasible)//已无可行点标//子群中该蚂蚁到达终点}//局部优化每条路线}//在线更新信息素//最优p个子群参与离线更新}3.1团队合作关系m–团队定向问题求解中需为m个参赛选手选择不同越野路线,在蚁群算法为表示团队中m个参赛选手之间这种关系,设计的算法中采用子蚁群的概念表示团队之间合作关系,子蚁群的内蚂蚁的个数为m,每只蚂蚁表示一名参赛选手,不同蚂蚁个体间通过到访点标禁忌表实现已访问点标信息交换。蚁群子群表示m–团队,不同子群通过信息素交换经过路径信息实现协作,控制蚁群中每只蚂蚁的行进路线,实现优化路线的选择。3.2团队定向问题P_(ij)k中的启发性信息ηij与优化目标直接相关,它直接影响每只蚂蚁的行进方向,m–团队定向问题中,优化目标是在满足时限条件下团队得分最高,在算法中ηij定义为该启发性信息ηij定义提高了得分率高的点标的被选择概率。3.3间数确定与随机进线通过算法设计的优化算法中为保证最大概率找到最优解,算法中两处采用随机选择的方式控制蚁群的行为,但随着优化时间或代数0的增加,逐渐降低随机性,提高确定性,保证算法收敛。子群中各蚂蚁以相同概率被选择行进,随着时间推进,子群中各蚂蚁按顺序交替行进;每只蚂蚁行进中,采用以下方式选择下一点标:p为间均匀分布的随机数,λ、ζ为蚂蚁行确定与随机控制变量。随着时间推移,ζ→ε,在后面实例计算中ε=0.1,λ=0.7。3.4进路线局部寻优在子群中每只蚂蚁均到达终点后,采用启发式方法对行进路线局部寻优,采用的主要优化策略有不同路线点标交叉、同路线中单点移动、未经过点标插入等,如果总的得分值或所需时间有改善,则以新解作为子群可行解。3.5线更新信息素浓度式在所有蚂蚁均从起始点标到达终止点标,并对路线进行局部寻优后,在线更新信息素浓度式中,ρ为0～1之间的常系数;在所有子群中蚂蚁从起始点标到达终止点标后,从所有子群中找出总分值最高的p个子群,利用p个子群的信息素进行离线更新式中,γ为0～1之间的常系数。4团队定向问题求解算法为验证提出算法的可行性和有效性,对m–团队问题进行建模,模型中共有20个点标,其中1号点标为出发点,20号点标为终点,其余18个点标如果到访可获得相应分值,不能直接到访两点标间距离为一非常大的数值,可直接到访两个点标间均有相应的距离,在给定队员人数和每名队员允许最大经过距离条件下,求解最大得分和每名队员的行进路线。采用提出的优化算法,对3名队员20个点标问题的团队定向问题进行求解,计算过程采用子群规模为50,每个子群内有3只蚂蚁协作,每只蚂蚁代表1名队员,在线更新信息素时ρ取0.7,离线更新中γ取0.5,最优子群个数p取4。经过优化后,20个点标中有17个点标被选择经过,3个队员的经过路线分别为:1→6→13→16→14→10→9→12→20,1→15→7→19→5→20,1→2→18→4→3→20。5基于昆虫群的m–团队问题求解方法本文描述了团队定向问题模型和目标,并针对m–团队定向问题提出了基于蚁群算法的求解方法。算法中利用子群中蚂蚁表示团队中队员合作,子群中蚂蚁间通过禁忌表方式交换已到达访点标,保证了团队中队员到访点标的唯一性。算法中蚁群在各条可行路径上留下的信息素影响各子群的路径选择行为,进而影响到访点标集的选择,算法中局部寻优和个体行进路线选择机制进行路径优化。仿真实验结果证明了提出的基于蚁群算法的m–团队问题求解方法的可行性和有效性。begin:initialize://初始化所有参数及系统τij=C;tabu＿pointsk=startpoint;while(notterminationcondtion){fork=1toant＿num//依次计算每个子群{while(existantnotarriveendpoints){randomselectoneantmovenext;selectnextpointsbyP_(ij)~korrandom;{calculateget＿scorekj;calculateroute＿lengthkj;addnextpointtoroute;a