周 頔

（四川文理學(xué)院 達(dá)州 635000）

1 引言

當(dāng)前在工農(nóng)業(yè)、國防、信息、經(jīng)管等領(lǐng)域中的諸多問題都可轉(zhuǎn)化為組合優(yōu)化問題，而在使用智能優(yōu)化算法解決這些問題時，都表現(xiàn)出自身的優(yōu)勢與不足［1］。所以不少的研究是針對特定問題，基于各自優(yōu)化互補(bǔ)思想，以融合、結(jié)合等方式，建立多種智能優(yōu)化算法相結(jié)合的混合型智能算法，增強(qiáng)其求解復(fù)雜問題的能力。在這些混合型智能算法中，充分結(jié)合了各種算法的優(yōu)點(diǎn)，得到了廣泛的關(guān)注與重視。遺傳算法是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法［2］。它在求解過程不需要求導(dǎo)，非常適用于大規(guī)模并行計算。蟻群算法是通過模擬自然界蟻群尋食過程中通過信息素的相互交流從而找到由蟻巢至食物的最短路徑的現(xiàn)象，而提出的一種基于信息正反饋原理的蟻群優(yōu)化算法［2～3］。這兩種智能算法都具有并行性、魯棒性和自組織性等特點(diǎn)，基于群體的能力來求解問題，獲得最優(yōu)解。因此獲得了廣泛的研究及應(yīng)用。如邵曉巍等［4］提出一種基于蟻群算法信息量留存的遺傳算法；彭沛夫等［5］提出基于遺傳因子的自適應(yīng)蟻群算法；張應(yīng)輝等［6］提出基于蟻群信息素和選擇基因的概率的選擇基因的方法；陶利民等［7］提出一種帶有近鄰節(jié)點(diǎn)選擇策略和遺傳算子的蟻群算法；董蓉等［8］提出一種混合遺傳—蟻群算法，用于求解柔性作業(yè)車間調(diào)度問題；劉傳領(lǐng)［9］提出一種改進(jìn)蟻群優(yōu)化算法，用于結(jié)合遺傳算法，進(jìn)而提出一種混合智能算法；陳亞云等［10］提出一種新的融合遺傳算法和蟻群算法的啟發(fā)式算法；蔡延光等［11］提出一種基于遺傳算子的自適應(yīng)蟻群算法；黃永青等［12］提出一種使用精英保留策略的交互式蟻群遺傳算法；田增瑞等［13］提出一種基于遺傳算法與蟻群算法相結(jié)合的混合算法，用于設(shè)計最佳旅游路線。很多專家和學(xué)者針對特定求解問題，還提出了許多基于遺傳算法和蟻群算法的混合智能優(yōu)化算法［14～18］。

這些遺傳算法和蟻群算法的混合算法，較好地解決了某些特定問題，但還存在求解效率和精度較低。因此，本文在分析遺傳算法和蟻群算法的動態(tài)特性、機(jī)理、尋優(yōu)策略及收斂性基礎(chǔ)上，引入多種群、遺傳算法的選擇、交叉、變異和蟻群算法的尋優(yōu)多策略有機(jī)結(jié)合，實(shí)現(xiàn)參數(shù)的自適應(yīng)調(diào)整，提出一種基于多種群多策略的混合遺傳-蟻群（HPSGAO）算法，以充分體現(xiàn)HPSGAO的整體尋優(yōu)能力，動態(tài)地平衡算法收斂速度和搜索范圍之間的矛盾，克服遺傳算法搜索到一定階段效率低和蟻群算法初始信息素分布盲目等問題。

2 遺傳算法和蟻群優(yōu)化算法

2.1 遺傳算法

遺傳算法（Genetic algorithm，GA）是一種自適應(yīng)隨機(jī)迭代搜索方法，它通過個體的選擇、交叉和變異等操作來產(chǎn)生新的個體，進(jìn)而構(gòu)成新的種群。該算法通過不斷重復(fù)進(jìn)化，使求解問題的解逐漸優(yōu)化，獲得最優(yōu)解。遺傳算法一般由編碼機(jī)制、適應(yīng)值函數(shù)、遺傳算子、控制參數(shù)等組成，其計算流程如圖1所示。

2.2 蟻群算法

蟻群算法（Ant colony optimization，ACO）是一種基于螞蟻尋徑行為的群智能優(yōu)化算法算法［3］。它源于自然界中的真實(shí)螞蟻在尋找食物時相互協(xié)作行為的啟發(fā)，通過信息素的調(diào)整較好地控制了種群的多樣性，具有較強(qiáng)的全局優(yōu)化能力。蟻群算法求解TSP的流程圖，如圖2所示。

圖1 遺傳算法流程圖

圖2 蟻群算法求解TSP流程圖

3 多種群與多策略

3.1 多種群

在HPSGAO算法中，充分利用了多個子種群的平行進(jìn)化。在每個子種群的內(nèi)部，除了GA的選擇操作、交叉操作和變異操作外，還引入了一種替代操作。該操作是利用ACO算法搜索到的解去替代種群中的較差個體。而蟻群搜索是基于各子種群的最優(yōu)個體，所以引入的替代操作能夠共享優(yōu)良個體、改善種群，并能有效加速算法的進(jìn)化。

3.2 多策略

1）遺傳策略

遺傳策略是具有較強(qiáng)的全局快速收斂能力，它主要包括選擇策略、交叉策略和變異策略。

（1）選擇策略

針對引發(fā)超級個體和相似個體問題的盤賭方法，提出采用聯(lián)賽選擇方法來選擇算法的個體，目的是為了避免算法的早熟現(xiàn)象，保證選出具有較高適應(yīng)值的個體。

（2）交叉策略和變異策略

本文的交叉策略采用一種非常規(guī)碼的常規(guī)交配法，實(shí)現(xiàn)個體之間的交叉。變異策略采用一種交換的變異算子，通過隨機(jī)選擇的兩個變異點(diǎn)，實(shí)現(xiàn)兩個基因的變異。

2）蟻群算法尋優(yōu)策略

當(dāng)蟻群算法被用于求解不同的組合優(yōu)化問題時，蟻群算法的尋優(yōu)策略具有不同的表達(dá)形式。本文主要分析螞蟻的尋優(yōu)策略。根據(jù)蟻群算法自適應(yīng)偽隨機(jī)比率選擇規(guī)則，選擇下一節(jié)點(diǎn)：

其中：λ(t)∈[2，N]表示算法在第 t次迭代時的ANB，N表示節(jié)點(diǎn)數(shù)，q(λ(t))∈[2/N，1]，q(t)為［0，1］區(qū)間上一致分布的隨機(jī)數(shù)。S根據(jù)下列公式進(jìn)行選擇：

其中αc是α的初始值，βc是 β的初始值，rand()是隨機(jī)函數(shù)。

3）參數(shù)自適應(yīng)調(diào)整策略

（1）GA參數(shù)自適應(yīng)調(diào)整策略

Srinivas提出了一種自適應(yīng)遺傳算法用于平衡GA的搜索范圍與能力。該算法利用種群平均適應(yīng)值與最優(yōu)個體適應(yīng)值的差來確定種群的多樣性，但存在過早收斂現(xiàn)象。因此可以將適應(yīng)度值大于fˉ(t)的個體適應(yīng)值再做一次平均得到，定義表示種群的過早收斂程度，這樣就能提高遺傳算法參數(shù)的自適應(yīng)性。

（2）ACO參數(shù)自適應(yīng)調(diào)整策略

針對ACO算法信息素?fù)]發(fā)系數(shù)ρ(t)過大帶來了降低算法全局搜索能力和過小帶了降低算法的收斂速度的問題，采用ACO算法信息素?fù)]發(fā)系數(shù)自適應(yīng)方法。該方法具體為初始值取ρ=0.999；在T次循環(huán)內(nèi)最優(yōu)值沒有明顯變化時，ρ值減為

其中rand()是隨機(jī)函數(shù)，最小取值ρmin是防止過小的ρ而降低收斂性。該方法能有效保證搜索的有效性，提高全局搜索能力。

4 基于多種群多策略的混合遺傳-蟻群算法

4.1 混合遺傳-蟻群算法思想

GA具有快速和全局的搜索能力，但求解效率較低；ACO算法具有較強(qiáng)的魯棒性和并行求解質(zhì)量好，但存在收斂速度慢、易陷入局部最優(yōu)等問題。為了充分利用GA和ACO算法各自的優(yōu)點(diǎn)，克服它們的不足，形成優(yōu)勢互補(bǔ)，引入多種群和多策略思想，將GA和ACO算法相結(jié)合，提出一種時間效率高于ACO算法、求解效率高于GA的混合遺傳-螞蟻（HPSGAO）算法。HPSGAO算法的基本思想：在HPSGAO算法的每次循環(huán)中，GA和ACO算法基于更新全局最優(yōu)解來相互指導(dǎo)，ACO算法獲得的較優(yōu)解作為精英個體，加入到GA中，以提高GA的求解問題的精度和效率；GA獲得的較優(yōu)解作為ACO算法當(dāng)前的最優(yōu)路徑，用于更新ACO算法的信息素濃度，以提高ACO算法的全局擇優(yōu)性能。通過多次循環(huán)，HPSGAO算法從GA獲得全局擇優(yōu)能力和ACO算法獲得較快的收斂速度和較高的求解精度。因此，在理論上HPSGAO算法具有較好的時間效率和求解精度。

4.2 HPSGAO算法模型及步驟

基于多種群多策略的混合遺傳-螞蟻算法描述如下：

Step1：初始化遺傳算法的參數(shù)

根據(jù)待求解優(yōu)化問題，初始化算法種群個體、搜索點(diǎn)以及速率等約束，確定種群的規(guī)模，設(shè)定遺傳算法相關(guān)參數(shù)：選擇方式、交叉概率、變異概率、迭代次數(shù)等。

Step 2：計算適應(yīng)度值

根據(jù)待求解優(yōu)化問題，確定適應(yīng)度函數(shù)，并計算所有個體的適應(yīng)度值，并按序排列。

Step 3：選擇、交叉和變異操作

采用聯(lián)賽選擇方法從4N個體種群中選擇適應(yīng)度值最優(yōu)的2N個，組成算法子種群。再采用一種非常規(guī)碼的常規(guī)交配法進(jìn)行交叉操作。按照交叉概率（Pc）隨機(jī)進(jìn)行兩兩配對，實(shí)現(xiàn)個體之間的交叉。假設(shè)在2個個體xi和xi+1之間進(jìn)行交叉，則交叉后產(chǎn)生的親個體為

在式（6）和（7）中，pi為算術(shù)交叉系數(shù)，取值為均勻分布的［0，1］之間的隨機(jī)數(shù)，xi表示第i個粒子的位置。

以變異概率（Pm）對個體進(jìn)行變異操作，公式表述為

Step4：獲得問題的優(yōu)化解

比較HPSGAO算法得到的適應(yīng)度值，獲得全局最優(yōu)值gBest。如果全局最優(yōu)值滿足精度，則執(zhí)行Step5；否則循環(huán)Step2到Step4，直到獲得最優(yōu)解或達(dá)到最大迭代。

Step5：初始化ACO算法信息素

利用Step4獲得最優(yōu)解來初始化ACO算法的信息素。根據(jù)以下公式計算兩個城市間路徑的信息素濃度（T(i)）：

其中，k、α是常量，k＞0，0＜α＜1；Xi是第i只螞蟻的位置，f(Xi)是目標(biāo)函數(shù)值。

Step 6：計算轉(zhuǎn)移概率

按照轉(zhuǎn)移概率式（2），計算第i個子群中第k只螞蟻的轉(zhuǎn)移概率。

Step7：計算每只螞蟻完成一次旅行所經(jīng)過的路徑長度。

Step 8：按照信息素更新式（10）更新第i個子群中第k只螞蟻的信息素濃度。

Step9：輸出最優(yōu)值

比較獲得的優(yōu)化解，如果是最優(yōu)解，則更新全局最優(yōu)解；否則循環(huán)Step5～Step8，直到獲得最優(yōu)解或達(dá)到最大迭代。

5 混合遺傳-蟻群算法求解TSP問題

為了測試混合遺傳-蟻群算法的有效性，選擇了GA、ACO和HPSGAO算法進(jìn)行實(shí)驗分析比較。10個來自于TSPLIB庫的TSP標(biāo)準(zhǔn)實(shí)例被用于測試算法優(yōu)化性能。為了獲得這些算法合理的初始參數(shù)值，測試可供選擇的參數(shù)取值，選定的參數(shù)值具有算法的最優(yōu)解和最合理的運(yùn)行時間。因此，為這3個算法選擇的最合理參數(shù)取值，如表1所示。每個TSP實(shí)例連續(xù)運(yùn)行10次，實(shí)驗結(jié)果如表2所示。

表1 GA、ACO和HPSGAO算法的參數(shù)設(shè)置

表2 實(shí)驗結(jié)果

從表2可以看出，對于 berlin52、pr76、rad100、eil101、lin105、ch130、kroA150、kroA200、lin318 和d1655共計10個TSP實(shí)例來說，提出的HPSGAO算法求解所獲得最優(yōu)解明顯要優(yōu)于GA和ACO算法，而且eil51實(shí)例求得了最優(yōu)值426，eil101實(shí)例所求解得到的最優(yōu)解643幾乎接近于最優(yōu)值629。HPSGAO算法在求解TSP時，如果城市規(guī)模較小時，該算法的優(yōu)化效果較明顯。當(dāng)城市規(guī)模逐漸增加時，HPSGAO算法優(yōu)化效果逐漸降低，較難獲得最優(yōu)解。因此，提出的HPSGAO算法表現(xiàn)出較強(qiáng)的全局優(yōu)化能力。

HPSGAO算法求解eil51實(shí)例所獲得的最優(yōu)路徑，如圖3所示。

圖3 eil51的最好值路徑（426）

6 結(jié)語

本文充分利用了遺傳算法的和蟻群算法各自的優(yōu)點(diǎn)，基于多種群和多策略，提出一種帶有參數(shù)自適應(yīng)調(diào)整的混合遺傳-蟻群算法。該算法利用遺傳算法產(chǎn)生的較優(yōu)解來初始化蟻群算法的信息素分布，進(jìn)而有效融合了蟻群策略和遺傳策略，動態(tài)平衡HPSGAO算法的收索范圍與收斂速度間的矛盾，進(jìn)而提高HPSGAO算法的全局擇優(yōu)能力。10個TSP實(shí)例被用來驗證HPSGAO算法的優(yōu)化性能。仿真實(shí)驗結(jié)果表明，提出的HPSGAO算法能較好地求解到TSP問題，很多TSP實(shí)例能夠獲得近似的最優(yōu)解，充分展現(xiàn)出HPSGAO算法較快的收斂速度和較高的求解精度，具有較強(qiáng)的全局優(yōu)化能力。