遺傳蟻群系統(tǒng)

1、遺傳蟻群系統(tǒng)    摘要： 在遺傳蟻群系統(tǒng)中，為減少螞蟻構建路徑的時間消耗，引入遺傳操作，使得當前迭代中螞蟻構建的路徑部分來自于之前迭代獲取的優(yōu)秀巡回路徑的遺傳；同時為減少由遺傳操作產(chǎn)生的算法停滯的影響、提高算法解的質(zhì)量，對蟻群構建的路徑施行2opt變異操作。 通過旅行商問題測試算法性能，并與蟻群系統(tǒng)進行比較。實驗表明，遺傳蟻群系統(tǒng)搜索效率高，而且解的質(zhì)量優(yōu)于蟻群系統(tǒng)。 關鍵詞：遺傳蟻群系統(tǒng)； 蟻群優(yōu)化； 遺傳算法； 旅行商問題 0引言 1997年Dorigo等人提出了ACS（ant colony system,蟻群系統(tǒng)）1。它是最成功的ACO2算法之一

2、，并被廣泛地應用于各種組合優(yōu)化問題36，如連續(xù)空間的數(shù)值優(yōu)化、旅行商問題、流水車間調(diào)度、集覆蓋、機器學習、網(wǎng)絡路由等。 蟻群系統(tǒng)是一種啟發(fā)式的構建方法。 以TSP為例，TSP的一條巡回路徑（解）是所有城市的一個排列，不同的相對排列順序?qū)煌慕狻CS通過增量構建的方式構建完整的巡回路徑。具體方式是先將螞蟻隨機地放在一個城市；然后根據(jù)一定的規(guī)則選擇螞蟻下一步訪問的城市，直到訪問完所有的城市。 路徑的增量構建占用了ACS算法的大部分時間。因為當前螞蟻必須有足夠的運算，以對下一步訪問城市作出最優(yōu)選擇。 減少螞蟻在構建路徑上的時間消耗是提高ACS效率的一種有效途徑。 在GAs（genetic al

3、gorithms,遺傳算法）7,8中，路徑的構建是通過對父代個體的繼承和重組或者變異實現(xiàn)，只需要作少量的運算。 因此，構建一條巡回路徑的時間消耗GAs顯著小于ACS。 正是基于這種考慮，本文提出了一種GACS（genetic ant colony system,遺傳蟻群系統(tǒng)）。 在GACS中，螞蟻構建的路徑部分來源于對之前迭代所得的優(yōu)秀路徑的遺傳，并通過變異減少蟻群構建的路徑的相似性，降低算法停滯的概率。 b）變比例遺傳。 變比例遺傳實現(xiàn)方式與定比例遺傳相同，不同的是為克服定比例遺傳的缺陷，在變比例遺傳中，p是一個變量。螞蟻從優(yōu)秀巡回路徑中繼承的部分路徑比例，隨著迭代次數(shù)的增加而增加。 這樣，

4、在迭代初期，當前優(yōu)秀巡回路徑的質(zhì)量較差時，螞蟻繼承的路徑比例被限制在一個較小的范圍內(nèi)，以避免算法陷入一個局部最優(yōu)巡回路徑；而在迭代的后期，優(yōu)秀巡回路徑越來越接近全局最優(yōu)巡回路徑時，螞蟻繼承的比例增加到一個較大的量上，以大幅減少螞蟻在構建路徑上的時間消耗。 c）隨機比例遺傳。 蟻群中的螞蟻從優(yōu)秀巡回路徑繼承隨機比例的部分路徑。在相同迭代中不同螞蟻繼承的部分路徑比例是隨機的。不同迭代中相同螞蟻繼承的部分路徑比例也是隨機的。 隨機比例遺傳的實現(xiàn)方式如下：隨機從優(yōu)秀巡回路徑中選擇兩個城市節(jié)點，將這兩個城市及這兩個城市之間的城市依次遺傳給當前螞蟻。 在理論上，隨機比例遺傳中的部分路徑遺傳比例是50，因此

5、其時間消耗近似于50定比例遺傳。 在ACO算法中，螞蟻有兩種路徑構建方式：a)串行構建。在迭代中，螞蟻依次構建完整的巡回路徑，即只有當一個螞蟻構建了完整的巡回路徑后，其后的螞蟻才開始路徑的構建。b)并行構建。在迭代中，蟻群中所有螞蟻同時開始路徑的構建，并同時完成路徑的構建。 這兩種構建方式對不存在局部信息素更新的ACO算法，如AS和MMAS（maxmin ant system）10,11是沒有區(qū)別的；但對于ACS，這兩種構建方式存在差異。因為ACS局部更新規(guī)則的存在，使用串行構建方式時，先構建路徑的螞蟻會對其后構建路徑的螞蟻路徑構建存在影響；使用并行構建方式時，蟻群中的螞蟻互相影響彼此的路徑構

6、建。 不過沒有資料顯示哪一種構建方式更優(yōu)2。 使用定比例遺傳和變比例遺傳時，可以選用并行構建或者串行構建；但使用隨機比例遺傳時，蟻群中的螞蟻繼承的路徑比例是隨機的，即螞蟻繼承的城市數(shù)量不一定相等。因此此時必須使用路徑的串行構建方式。路徑遺傳能有效提高算法效率，但是如果處理不當容易造成算法停滯而得不到理想的結果。 因此效仿GAs，將變異運算引入GACS，將螞蟻構建的路徑實行變異運算。 在GAs中，變異主要目的是防止因交叉操作帶來的染色體相似性而導致的種群收斂。它的變異一般是隨機的，即無論發(fā)生變異后的路徑是變優(yōu)還是變劣都將取代當前路徑。 在GACS中，只有當前最優(yōu)巡回路徑的信息才通過全局信息素更新

7、規(guī)則傳遞給其后構建路徑的螞蟻。因此在GACS中，隨機變異是不合適的。因為得不到更優(yōu)秀的路徑的變異是無效的。 在GACS中施行定向變異，即巡回路徑只向更短的路徑發(fā)生變異。 變異算子選用2opt12變異。 對n城市的巡回路徑tour的2opt變異的MATLAB語言實現(xiàn)原理如下： 由表2可知，含2opt變異的GACS的時間性能和優(yōu)化效果均優(yōu)于ACS。 關于時間性能，對于Berlin52、Eil51和Rd100，在作相同次數(shù)迭代的情況下，GACS消耗的時間約為ACS的75；關于優(yōu)化效果，如對于Rd100，在給定實驗條件下，GACS在20次實驗中有9次取得最優(yōu)巡回路徑，而ACS僅2次取得最優(yōu)巡回路徑。

8、4結束語 本文提出了具有遺傳特征的遺傳蟻群系統(tǒng)。 該算法通過路徑的遺傳減少了螞蟻在構建路徑上的時間消耗，并通過2opt變異運算提高了解的質(zhì)量。 在TSP上的仿真實驗表明，該算法的時間性能和優(yōu)化效果均優(yōu)于蟻群系統(tǒng)。 參考文獻： 1DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problemJ.IEEE Trans on Evolutionary Computation,1997,1(1）:53-66. 2DORIGO M,STü

9、;TZLE T. Ant colony optimizationM. London:MIT Press, 2004:65-117. 3SOCHA K. ACO for continuous and mixedvariableoptimizationC/Proc of the 4th International Workshop on Ant Colony Optimization and Swarm Intelligence. Brussels, Belgium: SpringerVerlag, 2004: 300-301. 4PEI Jian,HAN Jiawei, MAO Runying.

10、 Closet: an efficient algorithm for mining frequent closed itemsetsC/Proc of the ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery. Dallas, Texas: ACM Press, 2000: 21-30. 5ALUPOAEI S,KATKOORI S. Ant colony system application to macrocell overlap removalJ.IEEE Trans on Ver

11、y Large Scale Integration （VLSI） Systems, 2004,12（10）:1118-1122. 6GóMEZ J F,KHODR H M,De OLIVEIRA P M, et al. Ant colony system algorithm for the planning of primary distribution circuitsJ.IEEE Trans on Power System, 2004,19（2）:996-1003. 7HOLLAND J H. Genetic algorithms in search, optimization,

12、 and machine learningM. Ann Arbor: Michigan Press, 1975:1-57. 8MICHALEWICZ Z. Genetic algorithms+data structure=evolutionary programsM. New York: Springer-Verlag, 1994:211-238. 9COLORNI A,DORIGO M, MANIEZZO V. Distributed optimization by ant coloniesC/Proc of the 1st European Conference on Artificial Life. London: MIT Press,1991:134-142. 10STüTZLE T, HOOS H H. The maxmin ant system and local search for the traveling salesman problemC/Proc of IEEE International Conference on Evolutionary Computation. Piscataway:IEEE Press, 1997: 309-314. 11STüT