一种遗传蚁群系统的研究
摘要： 在遗传蚁群系统中，为减少蚂蚁构建路径的时间消耗，引入遗传操作，使得当前迭代中蚂蚁构建的路径部分来自于之前迭代获取的优秀巡回路径的遗传；同时为减少由遗传操作产生的算法停滞的影响、提高算法解的质量，对蚁群构建的路径施行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％定比例遗传。
在aco算法中，蚂蚁有两种路径构建方式：a)串行构建。在迭代中，蚂蚁依次构建完整的巡回路径，即只有当一个蚂蚁构建了完整的巡回路径后，其后的蚂蚁才开始路径的构建。b)并行构建。在迭代中，蚁群中所有蚂蚁同时开始路径的构建，并同时完成路径的构建。 这两种构建方式对不存在局部信息素更新的aco算法，如as和mmas（maxmin ant system）[10,11]是没有区别的；但对于acs，这两种构建方式存在差异。因为acs局部更新规则的存在，使用串行构建方式时，先构建路径的蚂蚁会对其后构建路径的蚂蚁路径构建存在影响；使用并行构建方式时，蚁群中的蚂蚁互相影响彼此的路径构建。 不过没有资料显示哪一种构建方式更优[2]。 使用定比例遗传和变比例遗传时，可以选用并行构建或者串行构建；但使用随机比例遗传时，蚁群中的蚂蚁继承的路径比例是随机的，即蚂蚁继承的城市数量不一定相等。因此此时必须使用路径的串行构建方式。
路径遗传能有效提高算法效率，但是如果处理不当容易造成算法停滞而得不到理想的结果。 因此效仿gas，将变异运算引入gacs，将蚂蚁构建的路径实行变异运算。 在gas中，变异主要目的是防止因交叉操作带来的染色体相似性而导致的种群收敛。它的变异一般是随机的，即无论发生变异后的路径是变优还是变劣都将取代当前路径。 在gacs中，只有当前最优巡回路径的信息才通过全局信息素更新规则传递给其后构建路径的蚂蚁。因此在gacs中，随机变异是不合适的。因为得不到更优秀的路径的变异是无效的。 在gacs中施行定向变异，即巡回路径只向更短的路径发生变异。 变异算子选用2opt[12]变异。 对n城市的巡回路径tour的2opt变异的matlab语言实现原理如下：
由表2可知，含2opt变异的gacs的时间性能和优化效果均优于acs。 关于时间性能，对于berlin52、eil51和rd100，在作相同次数迭代的情况下，gacs消耗的时间约为acs的75％；关于优化效果，如对于rd100，在给定实验条件下，gacs在20次实验中有9次取得最优巡回路径，而acs仅2次取得最优巡回路径。
4结束语
本文提出了具有遗传特征的遗传蚁群系统。 该算法通过路径的遗传减少了蚂蚁在构建路径上的时间消耗，并通过2opt变异运算提高了解的质量。 在tsp上的仿真实验表明，该算法的时间性能和优化效果均优于蚁群系统。
参考文献：
[1]dorigo m, gambardella l m. ant colony system: a cooperative learning approach to the traveling salesman problem[j].ieee trans on evolutionary computation,1997,1(1）:53-66.
[2]dorigo m,stützle t. ant colony optimization[m]. london:mit press, 2004:65-117.
[3]socha k. aco for continuous and mixedvariableoptimization[c]//proc of the 4th international workshop on ant colony optimization and swarm intelligence. brussels, belgium: springerverlag, 2004: 300-301.
[4]pei jian,han jiawei, mao runying. closet: an efficient algorithm for mining frequent closed itemsets[c]//proc of the acm sigmod workshop on research issues in data mining and knowledge discovery. dallas, texas: acm press, 2000: 21-30.
[5]alupoaei s,katkoori s. ant colony system application to macrocell overlap removal[j].ieee trans on very large scale integration （vlsi） systems, 2004,12（10）:1118-1122.
[6]gómez j f,khodr h m,de oliveira p m, et al. ant colony system algorithm for the planning of primary distribution circuits[j].ieee trans on power system, 2004,19（2）:996-1003.
[7]holland j h. genetic algorithms in search, optimization, and machine learning[m]. ann arbor: michigan press, 1975:1-57.
[8]michalewicz z. genetic algorithms+data structure=evolutionary programs[m]. new york: springer-verlag, 1994:211-238.
[9]colorni a,dorigo m, maniezzo v. distributed optimization by ant colonies[c]//proc of the 1st european conference on artificial life. london: mit press,1991:134-142.
[10]stützle t, hoos h h. the maxmin ant system and local search for the traveling salesman problem[c]//proc of ieee international conference on evolutionary computation. piscataway:ieee press, 1997: 309-314.
[11]stützle t,hoos h h. maxmin ant system[j].future generation computer system, 2000,16（8）:889-914.
[12]lin s. computer solutions to the traveling salesman problem[j].bell system journal, 1965,44(10):2245-2269.