遺傳蟻群系統(tǒng)

前言：本站為你精心整理了遺傳蟻群系統(tǒng)范文，希望能為你的創(chuàng)作提供參考價值，我們的客服老師可以幫助你提供個性化的參考范文，歡迎咨詢。

摘要：在遺傳蟻群系統(tǒng)中，為減少螞蟻構(gòu)建路徑的時間消耗，引入遺傳操作，使得當(dāng)前迭代中螞蟻構(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)化；遺傳算法；旅行商問題

0引言

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

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

c）隨機比例遺傳。蟻群中的螞蟻從優(yōu)秀巡回路徑繼承隨機比例的部分路徑。在相同迭代中不同螞蟻繼承的部分路徑比例是隨機的。不同迭代中相同螞蟻繼承的部分路徑比例也是隨機的。隨機比例遺傳的實現(xiàn)方式如下：隨機從優(yōu)秀巡回路徑中選擇兩個城市節(jié)點，將這兩個城市及這兩個城市之間的城市依次遺傳給當(dāng)前螞蟻。在理論上，隨機比例遺傳中的部分路徑遺傳比例是50％，因此其時間消耗近似于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（maxminantsystem）[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)建方式。路徑遺傳能有效提高算法效率，但是如果處理不當(dāng)容易造成算法停滯而得不到理想的結(jié)果。因此效仿GAs，將變異運算引入GACS，將螞蟻構(gòu)建的路徑實行變異運算。在GAs中，變異主要目的是防止因交叉操作帶來的染色體相似性而導(dǎo)致的種群收斂。它的變異一般是隨機的，即無論發(fā)生變異后的路徑是變優(yōu)還是變劣都將取代當(dāng)前路徑。在GACS中，只有當(dāng)前最優(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]DORIGOM,GAMBARDELLALM.Antcolonysystem:acooperativelearningapproachtothetravelingsalesmanproblem[J].IEEETransonEvolutionaryComputation,1997,1(1）:53-66.

[2]DORIGOM,STüTZLET.Antcolonyoptimization[M].London:MITPress,2004:65-117.

[3]SOCHAK.ACOforcontinuousandmixedvariableoptimization[C]//Procofthe4thInternationalWorkshoponAntColonyOptimizationandSwarmIntelligence.Brussels,Belgium:SpringerVerlag,2004:300-301.

[4]PEIJian,HANJiawei,MAORunying.Closet:anefficientalgorithmforminingfrequentcloseditemsets[C]//ProcoftheACMSIGMODWorkshoponResearchIssuesinDataMiningandKnowledgeDiscovery.Dallas,Texas:ACMPress,2000:21-30.

[5]ALUPOAEIS,KATKOORIS.Antcolonysystemapplicationtomacrocelloverlapremoval[J].IEEETransonVeryLargeScaleIntegration（VLSI）Systems,2004,12（10）:1118-1122.

[6]GóMEZJF,KHODRHM,DeOLIVEIRAPM,etal.Antcolonysystemalgorithmfortheplanningofprimarydistributioncircuits[J].IEEETransonPowerSystem,2004,19（2）:996-1003.

[7]HOLLANDJH.Geneticalgorithmsinsearch,optimization,andmachinelearning[M].AnnArbor:MichiganPress,1975:1-57.

[8]MICHALEWICZZ.Geneticalgorithms+datastructure=evolutionaryprograms[M].NewYork:Springer-Verlag,1994:211-238.

[9]COLORNIA,DORIGOM,MANIEZZOV.Distributedoptimizationbyantcolonies[C]//Procofthe1stEuropeanConferenceonArtificialLife.London:MITPress,1991:134-142.

[10]STüTZLET,HOOSHH.Themaxminantsystemandlocalsearchforthetravelingsalesmanproblem[C]//ProcofIEEEInternationalConferenceonEvolutionaryComputation.Piscataway:IEEEPress,1997:309-314.

[11]STüTZLET,HOOSHH.Maxminantsystem[J].FutureGenerationComputerSystem,2000,16（8）:889-914.

[12]putersolutionstothetravelingsalesmanproblem[J].BellSystemJournal,1965,44(10):2245-2269.