遺傳蟻群系統(tǒng)

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

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

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

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

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

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

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

8、4結(jié)束語 本文提出了具有遺傳特征的遺傳蟻群系統(tǒng)。 該算法通過路徑的遺傳減少了螞蟻在構(gòu)建路徑上的時間消耗，并通過2opt變異運(yùn)算提高了解的質(zhì)量。 在TSP上的仿真實(shí)驗(yàn)表明，該算法的時間性能和優(yōu)化效果均優(yōu)于蟻群系統(tǒng)。 參考文獻(xiàn)： 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