一種遺傳蟻群系統(tǒng)的研究

摘要： 在遺傳蟻群系統(tǒng)中，為減少螞蟻構(gòu)建路徑的時間消耗，引入遺傳操作，使得當前迭代中螞蟻構(gòu)建的路徑部分來自于之前迭代獲取的優(yōu)秀巡回路徑的遺傳；同時為減少由遺傳操作產(chǎn)生的算法停滯的影響、提高算法解的質(zhì)量，對蟻群構(gòu)建的路徑施行2opt變異操作。 通過旅行商問題測試算法性能，并與蟻群系統(tǒng)進行比較。實驗表明，遺傳蟻群系統(tǒng)搜索效率高，而且解的質(zhì)量優(yōu)于蟻群系統(tǒng)。

關(guān)鍵詞：遺傳蟻群系統(tǒng)； 蟻群優(yōu)化； 遺傳算法； 旅行商問題

中圖分類號：TP301文獻標志碼：A

文章編號：1001-3695(2007)12-0044-03

0引言

1997年Dorigo等人提出了ACS（ant colony system，蟻群系統(tǒng)）^[1]。它是最成功的ACO^[2]算法之一，并被廣泛地應用于各種組合優(yōu)化問題^[3~6]，如連續(xù)空間的數(shù)值優(yōu)化、旅行商問題、流水車間調(diào)度、集覆蓋、機器學習、網(wǎng)絡路由等。 蟻群系統(tǒng)是一種啟發(fā)式的構(gòu)建方法。 以TSP為例，TSP的一條巡回路徑（解）是所有城市的一個排列，不同的相對排列順序?qū)煌慕狻CS通過增量構(gòu)建的方式構(gòu)建完整的巡回路徑。具體方式是先將螞蟻隨機地放在一個城市；然后根據(jù)一定的規(guī)則選擇螞蟻下一步訪問的城市，直到訪問完所有的城市。 路徑的增量構(gòu)建占用了ACS算法的大部分時間。因為當前螞蟻必須有足夠的運算，以對下一步訪問城市作出最優(yōu)選擇。 減少螞蟻在構(gòu)建路徑上的時間消耗是提高ACS效率的一種有效途徑。 在GAs（genetic algorithms，遺傳算法）^[7，8]中，路徑的構(gòu)建是通過對父代個體的繼承和重組或者變異實現(xiàn)，只需要作少量的運算。 因此，構(gòu)建一條巡回路徑的時間消耗GAs顯著小于ACS。 正是基于這種考慮，本文提出了一種GACS（genetic ant colony system，遺傳蟻群系統(tǒng)）。 在GACS中，螞蟻構(gòu)建的路徑部分來源于對之前迭代所得的優(yōu)秀路徑的遺傳，并通過變異減少蟻群構(gòu)建的路徑的相似性，降低算法停滯的概率。

b）變比例遺傳。 變比例遺傳實現(xiàn)方式與定比例遺傳相同，不同的是為克服定比例遺傳的缺陷，在變比例遺傳中，p是一個變量。螞蟻從優(yōu)秀巡回路徑中繼承的部分路徑比例，隨著迭代次數(shù)的增加而增加。 這樣，在迭代初期，當前優(yōu)秀巡回路徑的質(zhì)量較差時，螞蟻繼承的路徑比例被限制在一個較小的范圍內(nèi)，以避免算法陷入一個局部最優(yōu)巡回路徑；而在迭代的后期，優(yōu)秀巡回路徑越來越接近全局最優(yōu)巡回路徑時，螞蟻繼承的比例增加到一個較大的量上，以大幅減少螞蟻在構(gòu)建路徑上的時間消耗。

c）隨機比例遺傳。 蟻群中的螞蟻從優(yōu)秀巡回路徑繼承隨機比例的部分路徑。在相同迭代中不同螞蟻繼承的部分路徑比例是隨機的。不同迭代中相同螞蟻繼承的部分路徑比例也是隨機的。 隨機比例遺傳的實現(xiàn)方式如下：隨機從優(yōu)秀巡回路徑中選擇兩個城市節(jié)點，將這兩個城市及這兩個城市之間的城市依次遺傳給當前螞蟻。 在理論上，隨機比例遺傳中的部分路徑遺傳比例是50％，因此其時間消耗近似于50％定比例遺傳。

在ACO算法中，螞蟻有兩種路徑構(gòu)建方式：a)串行構(gòu)建。在迭代中，螞蟻依次構(gòu)建完整的巡回路徑，即只有當一個螞蟻構(gòu)建了完整的巡回路徑后，其后的螞蟻才開始路徑的構(gòu)建。b)并行構(gòu)建。在迭代中，蟻群中所有螞蟻同時開始路徑的構(gòu)建，并同時完成路徑的構(gòu)建。 這兩種構(gòu)建方式對不存在局部信息素更新的ACO算法，如AS和MMAS（maxmin ant system）^[10，11]是沒有區(qū)別的；但對于ACS，這兩種構(gòu)建方式存在差異。因為ACS局部更新規(guī)則的存在，使用串行構(gòu)建方式時，先構(gòu)建路徑的螞蟻會對其后構(gòu)建路徑的螞蟻路徑構(gòu)建存在影響；使用并行構(gòu)建方式時，蟻群中的螞蟻互相影響彼此的路徑構(gòu)建。 不過沒有資料顯示哪一種構(gòu)建方式更優(yōu)^[2]。 使用定比例遺傳和變比例遺傳時，可以選用并行構(gòu)建或者串行構(gòu)建；但使用隨機比例遺傳時，蟻群中的螞蟻繼承的路徑比例是隨機的，即螞蟻繼承的城市數(shù)量不一定相等。因此此時必須使用路徑的串行構(gòu)建方式。

路徑遺傳能有效提高算法效率，但是如果處理不當容易造成算法停滯而得不到理想的結(jié)果。 因此效仿GAs，將變異運算引入GACS，將螞蟻構(gòu)建的路徑實行變異運算。 在GAs中，變異主要目的是防止因交叉操作帶來的染色體相似性而導致的種群收斂。它的變異一般是隨機的，即無論發(fā)生變異后的路徑是變優(yōu)還是變劣都將取代當前路徑。 在GACS中，只有當前最優(yōu)巡回路徑的信息才通過全局信息素更新規(guī)則傳遞給其后構(gòu)建路徑的螞蟻。因此在GACS中，隨機變異是不合適的。因為得不到更優(yōu)秀的路徑的變異是無效的。 在GACS中施行定向變異，即巡回路徑只向更短的路徑發(fā)生變異。 變異算子選用2opt^[12]變異。 對n城市的巡回路徑tour的2opt變異的MATLAB語言實現(xiàn)原理如下：

由表2可知，含2opt變異的GACS的時間性能和優(yōu)化效果均優(yōu)于ACS。 關(guān)于時間性能，對于Berlin52、Eil51和Rd100，在作相同次數(shù)迭代的情況下，GACS消耗的時間約為ACS的75％；關(guān)于優(yōu)化效果，如對于Rd100，在給定實驗條件下，GACS在20次實驗中有9次取得最優(yōu)巡回路徑，而ACS僅2次取得最優(yōu)巡回路徑。

4結(jié)束語

本文提出了具有遺傳特征的遺傳蟻群系統(tǒng)。 該算法通過路徑的遺傳減少了螞蟻在構(gòu)建路徑上的時間消耗，并通過2opt變異運算提高了解的質(zhì)量。 在TSP上的仿真實驗表明，該算法的時間性能和優(yōu)化效果均優(yōu)于蟻群系統(tǒng)。

參考文獻：

[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 mixedvariableoptimization[C]//Proc of the 4th International Workshop on Ant Colony Optimization and Swarm Intelligence. Brussels， Belgium: SpringerVerlag， 2004: 300-301.

[4]PEI Jian，HAN Jiawei， MAO Runying. 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 maxmin 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. Maxmin 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.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”