導(dǎo)語：遺傳蟻群系統(tǒng)研究思考一文來源于網(wǎng)友上傳，不代表本站觀點(diǎn)，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

摘要：在遺傳蟻群系統(tǒng)中，為減少螞蟻構(gòu)建路徑的時(shí)間消耗，引入遺傳操作，使得當(dāng)前迭代中螞蟻構(gòu)建的路徑部分來自于之前迭代獲取的優(yōu)秀巡回路徑的遺傳；同時(shí)為減少由遺傳操作產(chǎn)生的算法停滯的影響、提高算法解的質(zhì)量，對(duì)蟻群構(gòu)建的路徑施行2opt變異操作。通過旅行商問題測(cè)試算法性能，并與蟻群系統(tǒng)進(jìn)行比較。實(shí)驗(yàn)表明，遺傳蟻群系統(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)度、集覆蓋、機(jī)器學(xué)習(xí)、網(wǎng)絡(luò)路由等。蟻群系統(tǒng)是一種啟發(fā)式的構(gòu)建方法。以TSP為例，TSP的一條巡回路徑（解）是所有城市的一個(gè)排列，不同的相對(duì)排列順序?qū)?yīng)不同的解。ACS通過增量構(gòu)建的方式構(gòu)建完整的巡回路徑。具體方式是先將螞蟻隨機(jī)地放在一個(gè)城市；然后根據(jù)一定的規(guī)則選擇螞蟻下一步訪問的城市，直到訪問完所有的城市。路徑的增量構(gòu)建占用了ACS算法的大部分時(shí)間。因?yàn)楫?dāng)前螞蟻必須有足夠的運(yùn)算，以對(duì)下一步訪問城市作出最優(yōu)選擇。減少螞蟻在構(gòu)建路徑上的時(shí)間消耗是提高ACS效率的一種有效途徑。在GAs（geneticalgorithms,遺傳算法）[7,8]中，路徑的構(gòu)建是通過對(duì)父代個(gè)體的繼承和重組或者變異實(shí)現(xiàn)，只需要作少量的運(yùn)算。因此，構(gòu)建一條巡回路徑的時(shí)間消耗GAs顯著小于ACS。正是基于這種考慮，本文提出了一種GACS（geneticantcolonysystem,遺傳蟻群系統(tǒng)）。在GACS中，螞蟻構(gòu)建的路徑部分來源于對(duì)之前迭代所得的優(yōu)秀路徑的遺傳，并通過變異減少蟻群構(gòu)建的路徑的相似性，降低算法停滯的概率。

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

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

在ACO算法中，螞蟻有兩種路徑構(gòu)建方式：a)串行構(gòu)建。在迭代中，螞蟻依次構(gòu)建完整的巡回路徑，即只有當(dāng)一個(gè)螞蟻構(gòu)建了完整的巡回路徑后，其后的螞蟻才開始路徑的構(gòu)建。b)并行構(gòu)建。在迭代中，蟻群中所有螞蟻同時(shí)開始路徑的構(gòu)建，并同時(shí)完成路徑的構(gòu)建。這兩種構(gòu)建方式對(duì)不存在局部信息素更新的ACO算法，如AS和MMAS（maxminantsystem）[10,11]是沒有區(qū)別的；但對(duì)于ACS，這兩種構(gòu)建方式存在差異。因?yàn)锳CS局部更新規(guī)則的存在，使用串行構(gòu)建方式時(shí)，先構(gòu)建路徑的螞蟻會(huì)對(duì)其后構(gòu)建路徑的螞蟻路徑構(gòu)建存在影響；使用并行構(gòu)建方式時(shí)，蟻群中的螞蟻互相影響彼此的路徑構(gòu)建。不過沒有資料顯示哪一種構(gòu)建方式更優(yōu)[2]。使用定比例遺傳和變比例遺傳時(shí)，可以選用并行構(gòu)建或者串行構(gòu)建；但使用隨機(jī)比例遺傳時(shí)，蟻群中的螞蟻繼承的路徑比例是隨機(jī)的，即螞蟻繼承的城市數(shù)量不一定相等。因此此時(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)巡回路徑的信息才通過全局信息素更新規(guī)則傳遞給其后構(gòu)建路徑的螞蟻。因此在GACS中，隨機(jī)變異是不合適的。因?yàn)榈貌坏礁鼉?yōu)秀的路徑的變異是無效的。在GACS中施行定向變異，即巡回路徑只向更短的路徑發(fā)生變異。變異算子選用2opt[12]變異。對(duì)n城市的巡回路徑tour的2opt變異的MATLAB語言實(shí)現(xiàn)原理如下：

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

4結(jié)束語

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

參考文獻(xiàn)：

[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.