基于遺傳算法智能改進(jìn)優(yōu)化蟻群算法

◆宋楊

基于遺傳算法智能改進(jìn)優(yōu)化蟻群算法

◆宋楊

（徐州生物工程職業(yè)技術(shù)學(xué)院 江蘇 221006）

作為進(jìn)化模擬新算法之一，蟻群算法旨在找尋最短路徑。但蟻群算法存在一定的缺陷，如停滯、收斂慢等。所以，以遺傳運(yùn)算為基礎(chǔ)，提出了一種改進(jìn)后的蟻群算法，通過路徑交叉與變異運(yùn)算，更新了信息素，很好地優(yōu)化全局、避免停滯等。基于此，本文從遺傳算法出發(fā)，主要探討了蟻群算法的智能改進(jìn)與優(yōu)化，僅供參考。

蟻群算法；智能優(yōu)化；遺傳算法

遺傳和蟻群這兩種算法均是啟發(fā)類型的算法，且均用于最優(yōu)組合求解上。但是，這兩種算法均有一定的缺陷：通過遺傳算法，無法發(fā)揮反饋信息的作用，會引起冗余迭代、緩慢求解等問題；通過蟻群算法，則匱乏最初信息素，會減緩算法速度。但以遺傳算法為基礎(chǔ)，適當(dāng)改進(jìn)螞蟻算法，便能充分利用兩種算法各自的優(yōu)點(diǎn)，完全突破他們的缺陷，達(dá)到優(yōu)勢互補(bǔ)的效果。現(xiàn)階段，在蟻群算法的基礎(chǔ)上，優(yōu)化完善遺傳算法已經(jīng)獲得了很理想的效果。

1 蟻群基本算法概述

1.1 算法原理

在蟻群算法中，基本原理就是：在行進(jìn)途中，螞蟻會釋放信息素，如果螞蟻沿這樣的軌跡前進(jìn)，就能明顯感覺到該激素。通過信息素，可以吸引螞蟻前進(jìn)。所以，螞蟻往往會選擇跟隨信息素更濃的途徑，而產(chǎn)生內(nèi)在的催化反應(yīng)，又或加強(qiáng)自己的正反饋效果。經(jīng)由數(shù)量龐大的螞蟻集體，而形成的行為便體現(xiàn)了正反饋信息現(xiàn)象。而通過這樣的行為，蟻群就能準(zhǔn)確找到到達(dá)目標(biāo)位置的最理想的途徑。

1.2 轉(zhuǎn)移規(guī)則

在螞蟻行進(jìn)中，常常會根據(jù)某種轉(zhuǎn)移規(guī)則。基于轉(zhuǎn)移概率函數(shù)Pij，可以模擬螞蟻選擇的邊（i，j）。在這個(gè)函數(shù)中，融入了信息素tij濃度、啟發(fā)函數(shù)hij。針對第i點(diǎn)位置的第k只螞蟻，當(dāng)j不屬于tabuk時(shí)，則選j的概率計(jì)算方法就是

在其他時(shí)候，pij（k）=0。而tij（t）—t時(shí)刻邊（i，j）對應(yīng)的信息素濃度，屬于全局信息，體現(xiàn)出蟻群的先驗(yàn)路段經(jīng)驗(yàn)；hij——啟發(fā)函數(shù)，通過源問題下的貪婪算法獲得，僅思考本地信息，體現(xiàn)螞蟻運(yùn)動(dòng)中出現(xiàn)的諸如長度等啟發(fā)信息；α、?—信息素基礎(chǔ)下的啟發(fā)、能見度因子；tabuk—第k只螞蟻集合發(fā)不可行節(jié)點(diǎn)。比如，從TSP問題上看，已經(jīng)過路線上的點(diǎn)，便為不可行類型的點(diǎn)。

1.3 更新信息素

根據(jù)轉(zhuǎn)移規(guī)則，螞蟻會沿各種節(jié)點(diǎn)向前行進(jìn)，一直到形成源問題的一個(gè)處理方案。譬如，針對TSP問題的一個(gè)有效解決方案，便為螞蟻找出一條可以遍歷一切點(diǎn)的準(zhǔn)確線路。而當(dāng)螞蟻得出解決方案后，就是蟻群算法基礎(chǔ)下的一次循環(huán)。當(dāng)循環(huán)一次后，就會根據(jù)更新策略，再次更新各邊信息素整體濃度。

式中，ρ—?dú)埩粜畔⑺叵禂?shù)（0，1）；Dtijk—當(dāng)前循環(huán)中第k只螞蟻邊（i，J）上出現(xiàn)的增量；p—整體上的蟻群規(guī)模，常見更新策略：Ant—quantity；Ant—density； Ant—cycle。其中的區(qū)別就是信息素更新方式。在前兩種模型中，螞蟻均不是在終結(jié)路徑后才開始釋放信息素，也就是使用局部信息，而在最后一個(gè)模型中，用到了整體信息。

最初在不同城市放m只螞蟻，控制各邊信息素具有一樣的濃度，即tij（0）=C。各螞蟻tabuk首個(gè)元素初始值就是其節(jié)點(diǎn)。在螞蟻均搜索完一次后，算出tijk，再更新各邊信息素實(shí)際濃度，即進(jìn)入下一個(gè)循環(huán)。如果循環(huán)預(yù)定次數(shù)，又或螞蟻均選擇某路徑，就應(yīng)終止所有算法。

2 交叉智能優(yōu)化變異改進(jìn)

和別的優(yōu)化算法相同的是，蟻群算法和容易出現(xiàn)局部最優(yōu)情況。因此，應(yīng)添入交叉、變異后的算子，令螞蟻基礎(chǔ)算法在出現(xiàn)局部最優(yōu)并且停滯不前的情況時(shí)，豐富螞蟻種群，以防算法過于早熟。在廣闊的自然界，重組遺傳基因和生物的變異，在生物進(jìn)化當(dāng)中發(fā)揮著核心作用。而在遺傳算法中，遺傳交叉算子也具有核心作用。其中的交叉指的是先替換重組2個(gè)父代個(gè)體，再產(chǎn)生新的個(gè)體。在交叉以后，可以大幅提升遺傳算法在搜索方面的能力。作為交叉算子，可按交叉率，隨機(jī)交換種群兩個(gè)體的基因，并形成基因新組合，以組合有益基因。通過遺傳算法變異，旨在賦予遺傳算法隨機(jī)搜索和豐富群體的能力。基于交叉算子，遺傳算法接近到蟻群最優(yōu)解鄰域時(shí)，通過隨機(jī)搜索，就能加速收斂至最優(yōu)解。在以上情況下，無疑應(yīng)取較小變異概率，不然就會因變異破壞接近最優(yōu)解以后的積木塊。而通過維持算法多樣性，還能避免非成熟收斂，所以需取較大收斂概率。

在遺傳算法當(dāng)中，考慮到全局搜索，宜以交叉算子為關(guān)鍵性算子，以變異算子為輔助算子。從遺傳算法上看，通過配合交叉、變異，能兼顧均衡搜索全局、局部的能力。這里說的彼此配合指的就是在群體進(jìn)化中，無法憑借交叉，擺脫搜索空間當(dāng)中陷入的某超平面時(shí)，借助變異操作，便能幫助擺脫。而彼此競爭指的就是在交叉過程中形成積木塊時(shí)，而在變異操作下，卻常常會破壞掉積木塊。所以，在遺傳算法中，應(yīng)注意有機(jī)配合交叉與變異操作。

在算法當(dāng)中，賦予了螞蟻一定的粒子性，并有參考粒子群算法理論：針對粒子而言，適應(yīng)值均由優(yōu)化函數(shù)直接決定，并且還存在一個(gè)速度，來直接決定粒子的飛翔距離及方向，這樣粒子群便會隨著最優(yōu)粒子不斷搜索解空間。作為粒子群，常用優(yōu)化算法時(shí)，先初始化形成隨機(jī)粒子群，再基于迭代尋找最優(yōu)解。每次粒子進(jìn)行迭代時(shí)，都會跟蹤2個(gè)極值來統(tǒng)一進(jìn)行自我更新。其中一個(gè)就是個(gè)體pbest極值，而另一個(gè)則是種群尋找出的gbest最優(yōu)解。針對TSP問題，具體位置就是路徑，需根據(jù)遺傳算法來采取交叉變異措施：

其中，c0vk—遺傳算法基礎(chǔ)下的變異；后面兩項(xiàng)相加，可視為遺傳算法基礎(chǔ)下的交叉，也即螞蟻均交叉運(yùn)算了當(dāng)前解和全局及個(gè)體極值，而得到的解就是新位置，再按新位置，算出最終的最短路徑。

通過變異，經(jīng)由c0路徑變異至c1路徑，從1～n個(gè)城市中，選取訪問j1次后的城市，并在c0中直接交換訪問第j1~第j1+1次的城市，再維持其他不變，就形成c1路徑。例如，c0=1~9，j1=3，可得c1=12435~9。通過交叉，在第2串中選擇某交叉區(qū)域，再在一定的old1位置，添加old2交叉區(qū)，并刪掉old2交叉區(qū)已有的old1城市。譬如，有父串old1=1~9，old2=9~1，當(dāng)交叉區(qū)是7654，可得new1=127~389。

針對TSP問題，具體算法步驟：

（1）初始化

針對隨機(jī)出現(xiàn)的m個(gè)初始解，設(shè)置有S個(gè)初始解途徑（i，j）路徑，且總長L1，L2~Ls，可得初始路徑信息量：

（2）迭代

While not結(jié)束的do條件；

For j對n個(gè)城市展開循環(huán)，也即為1 to n do；

for k對m只螞蟻展開循環(huán)，也即1 to m do。

按所處位置算出不同路徑長，以ptbest個(gè)體極值為適應(yīng)值，以pcbest個(gè)體極值為當(dāng)前位置，按粒子個(gè)體極值，尋找ptbest全局極值及其gcbest位置。在當(dāng)前解集，放置每螞蟻初始點(diǎn)，并根據(jù)pijk，移動(dòng)螞蟻k（k=1~m）到下個(gè)城市j，并在當(dāng)前解集納入頂點(diǎn)。針對螞蟻展開這樣的操作：交叉C0（j）和gcbest，獲得C′1（j），再交叉C′1（j）和pcbest，獲得C″1（j），然后C″1（j）基于某概率變異，獲得C1（j）。按當(dāng)前位置算保護(hù)路徑長，如果目標(biāo)新函數(shù)得到優(yōu)化，就納入新值，不然就應(yīng)拒絕。C1（j）也即C0（j），再次尋找個(gè)體極值ptbest與pcbest位置，以及全局極值gtbest與gcbest位置。算出螞蟻總路徑長Lk（k=1~m），記下最佳解。針對Lk在給定值以下的路徑，適當(dāng)更新信息素結(jié)果。

從m只螞蟻出發(fā)，終止循環(huán)，也即end for k；

在這m只螞蟻當(dāng)中，如果存在當(dāng)前已經(jīng)遍歷路徑長、已超出上次迭代最優(yōu)路徑長，就要終止本次該螞蟻的遍歷迭代。

從n個(gè)城市出發(fā)，終止循環(huán)，也即end for j；

針對各城市路徑，更新總的信息量；

完成算法，獲得最終解，也即end while。

3 結(jié)論分析

在實(shí)驗(yàn)當(dāng)中，以50個(gè)城市為問題對象，依次通過蟻群算法、新提出算法來統(tǒng)一運(yùn)算。已知α、β為1、5，增強(qiáng)信息素系數(shù)Q=100，揮發(fā)信息素系數(shù)ρ=0.95。一共有50只螞蟻，迭代次數(shù)最多200次，在一臺機(jī)器上，先同等設(shè)置參數(shù)，再計(jì)算這些城市問題。結(jié)果顯示，新算法既有強(qiáng)大的搜索能力，又能更快接近最優(yōu)解，還能在得到最優(yōu)解后，繼續(xù)穩(wěn)定在其附近。由此可見，新算法在TSP的對稱、非對稱問題上，均能有效收斂，算出城市最終路徑。

在分析實(shí)驗(yàn)數(shù)據(jù)信息后，根據(jù)蟻群算法，算出路徑最短值457.5103，而根據(jù)優(yōu)化后的新算法，得到最終解475.3594，要大于蟻群算法得到的結(jié)果。這說明新算法具有一定的優(yōu)勢，如有效防止早熟、出現(xiàn)局部收斂等，尤其適合解決大型TSP問題。在新算法應(yīng)用當(dāng)中，螞蟻可以從上次迭代出發(fā)，動(dòng)態(tài)地更新信息量。相較于傳統(tǒng)算法下常用的搜索機(jī)制，尤其是蟻群基礎(chǔ)算法下的搜索，不再會由于只是更新最優(yōu)行駛路徑產(chǎn)生的信息量，而太過強(qiáng)化其中的最優(yōu)信息。這么一來，螞蟻便能在搜索時(shí)“隨機(jī)應(yīng)變”，令大多數(shù)螞蟻搜索，可以進(jìn)化到適應(yīng)度更強(qiáng)的方向。所以，改進(jìn)后的新算法可以動(dòng)態(tài)平衡收斂速率與避免早熟措施，整體上的最優(yōu)解探索能力更強(qiáng)、進(jìn)化速度更快。

4 結(jié)語

綜上所述，以遺傳算法為基礎(chǔ)，通過智能化地優(yōu)化改進(jìn)蟻群算法后，能夠更適合解決多目標(biāo)大規(guī)模優(yōu)化問題，并且很好地克服權(quán)重系數(shù)方面的缺陷。經(jīng)過改進(jìn)后的新算法，可以利用遺傳算法來初始分布信息素，并且發(fā)揮出蟻群算法的優(yōu)勢，來提高求解效率，迅速獲得多目標(biāo)優(yōu)化的最優(yōu)解，從而增強(qiáng)蟻群新算法的穩(wěn)定性、收斂性，賦予解更強(qiáng)的豐富多樣性，妥善處理各種優(yōu)化問題。

[1]秦浩森，丁咚，王祥東，李廣雪，權(quán)永崢.蟻群算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)聲學(xué)底質(zhì)分類方法[J].中國海洋大學(xué)學(xué)報(bào)（自然科學(xué)版），2019，49（S2）：60-68.

[2]金超迪.基于改進(jìn)蟻群算法的無線傳感網(wǎng)分簇與路徑規(guī)劃[D].南京郵電大學(xué)，2017.

[3]邱莉莉.基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃[D].東華大學(xué)，2015.