收藏本站 | 联系我们 | 设为首页 | English
当前位置:主页>计算机论文>
一种遗传蚁群系统的研究
来源:  作者:本站

  摘要: 在遗传蚁群系统中,为减少蚂蚁构建路径的时间消耗,引入遗传操作,使得当前迭代中蚂蚁构建的路径部分来自于之前迭代获取的优秀巡回路径的遗传;同时为减少由遗传操作产生的算法停滞的影响、提高算法解的质量,对蚁群构建的路径施行2opt变异操作。 通过旅行商问题测试算法性能,并与蚁群系统进行比较。实验表明,遗传蚁群系统搜索效率高,而且解的质量优于蚁群系统。
  关键词:遗传蚁群系统; 蚁群优化; 遗传算法; 旅行商问题
  0引言
  
  1997年Dorigo等人提出了ACS(ant colony system,蚁群系统)[1]。它是最成功的ACO[2]算法之一,并被广泛地应用于各种组合优化问题[3~6],如连续空间的数值优化、旅行商问题、流水车间调度、集覆盖、机器学习、网络路由等。 蚁群系统是一种启发式的构建方法。 以TSP为例,TSP的一条巡回路径(解)是所有城市的一个排列,不同的相对排列顺序对应不同的解。ACS通过增量构建的方式构建完整的巡回路径。具体方式是先将蚂蚁随机地放在一个城市;然后根据一定的规则选择蚂蚁下一步访问的城市,直到访问完所有的城市。 路径的增量构建占用了ACS算法的大部分时间。因为当前蚂蚁必须有足够的运算,以对下一步访问城市作出最优选择。 减少蚂蚁在构建路径上的时间消耗是提高ACS效率的一种有效途径。 在GAs(genetic algorithms,遗传算法)[7,8]中,路径的构建是通过对父代个体的继承和重组或者变异实现,只需要作少量的运算。 因此,构建一条巡回路径的时间消耗GAs显著小于ACS。 正是基于这种考虑,本文提出了一种GACS(genetic ant colony system,遗传蚁群系统)。 在GACS中,蚂蚁构建的路径部分来源于对之前迭代所得的优秀路径的遗传,并通过变异减少蚁群构建的路径的相似性,降低算法停滞的概率。
  
  b)变比例遗传。 变比例遗传实现方式与定比例遗传相同,不同的是为克服定比例遗传的缺陷,在变比例遗传中,p是一个变量。蚂蚁从优秀巡回路径中继承的部分路径比例,随着迭代次数的增加而增加。 这样,在迭代初期,当前优秀巡回路径的质量较差时,蚂蚁继承的路径比例被限制在一个较小的范围内,以避免算法陷入一个局部最优巡回路径;而在迭代的后期,优秀巡回路径越来越接近全局最优巡回路径时,蚂蚁继承的比例增加到一个较大的量上,以大幅减少蚂蚁在构建路径上的时间消耗。
  c)随机比例遗传。 蚁群中的蚂蚁从优秀巡回路径继承随机比例的部分路径。在相同迭代中不同蚂蚁继承的部分路径比例是随机的。不同迭代中相同蚂蚁继承的部分路径比例也是随机的。 随机比例遗传的实现方式如下:随机从优秀巡回路径中选择两个城市节点,将这两个城市及这两个城市之间的城市依次遗传给当前蚂蚁。 在理论上,随机比例遗传中的部分路径遗传比例是50%,因此其时间消耗近似于50%定比例遗传。
上一页12 下一页

关于本站 | 会员服务 | 隐私保护 | 法律声明 | 站点地图 | RSS订阅 | 友情链接
免责声明:凡本站注明来源为xx所属媒体的作品,均转载自其它媒体转载目的在于传递更多信息,并不代表本站赞同其观点和对其真实性负责。