基于蟻群算法的多維有約束函數優化研究

摘要：利用蟻群算法的基本原理，將多維有約束的優化問題通過罰懲因子方式轉換為統一的多變量目標函數形式，并將所有獨立變量分成不同的等份區域，以螞蟻走過每一變量的一個區域并訪問完所有變量所構成的構造圖作為優化問題的可行解，獲得這一可行解的過程即為蟻群算法的粗搜索；再將粗搜索所獲得的解執行遺傳交叉及變異操作，從而構建另一種精搜索蟻群算法以獲得更精確的全局優化解。給出了基于蟻群算法的多維有約束函數優化的具體算法。通過其他三種優化方法及本文方法對行星輪系優化設計的對比求解，驗證了該優化方法的高效性及準確性。

關鍵詞：蟻群算法； 多維函數優化； 粗搜索過程； 精搜索過程； 具體算法

中圖分類號：TP202.7文獻標志碼：A

文章編號：1001－3695(2008)06－1682－03

0引言

蟻群算法是一類新型進化算法，其主要特點是群體搜索策略和群體之間的信息交換。其主要依據是信息正反饋原理和某種啟發式算法的有機結合。當前這類算法已形成了統一的優化元啟發式統一模式、統一蟻群優化原理及算法描述，它在求解組合優化、函數優化、系統辨識、機器人路徑規劃及數據挖掘等方面取得了很好的效果[1]。其具有許多比遺傳算法等其他傳統群智能算法更多的優點，尤其在求解組合優化問題方面具有其他算法所不具有的優點[2]。本文將多維有約束函數優化通過各變量的細分，以每只螞蟻如何走完所有變量中不同區間的系列作為問題求解的最優解。這樣將多維變量的函數優化問題轉換成類似組合優化的問題來進行求解，并將整個函數優化分成螞蟻粗搜索及精搜索過程。在精搜索過程中利用遺傳交叉、變異算子進一步細化變量區間，對函數的約束變量需要后期圓整處理的變量事先附加不同的整型約束。這樣既縮小了搜索空間，又不至于使設計出的變量值需要后期二次處理，從而在多維有約束的函數優化上具有收斂速度快、易獲得全局最優解的優點。

1蟻群算法的基本原理

蟻群算法是一種基于群體的隨機搜索算法，它是在蟻群優化元啟發式作用下，將待求解問題表示成具有特定含義的構造圖的形式[3]。基于構造圖中的信息通過間接通信與協作的方式搜索問題的最優解，其主要依據是信息正反饋原理與某一種啟發式算法的有機結合。螞蟻正是利用自身獲得的啟發式信息與群體中釋放的信息素多少來決定自身下一步所要搜索的方向，也就是螞蟻利用個體自身信息與其他個體或周圍環境的信息來獲得最優解。

2多變量函數優化的ACO算法

2．1基本思想

蟻群算法的優化過程主要包括選擇、更新以及協調三個過程[4]。整個優化過程將分為粗搜索過程和精搜索過程，并且每一個過程設置不同類的螞蟻。在粗搜索過程中，首先將待求問題的多約束函數通過最小二乘法及懲罰函數法轉換為統一的目標函數，也可在蟻群操作過程中通過特定的子程序判斷候選解是否滿足約束條件來處理，對標準的目標函數將待求問題的獨立變量依據該變量的要求不同劃分為不同的等份小單元，尤其對設計中需要最終變量的值是整數值的變量，對該類變量就劃分成等份整數單元，以便優化的結果直接可用而無須后續二次取整處理。這樣處理極大地縮小了搜索空間，提高了搜索效率。整個粗搜索即是完成每只螞蟻以走完所有的獨立變量中的某一個值而構成一個可行解，然后修改所有路徑上的信息素。在精搜索過程中，將上述粗搜索得到的可行解進行單元細化，以可行解構成初始群體，依據某種概率進行交叉和變異操作，并采用另一類螞蟻執行蟻群算法，最終找到多變量優化問題的全局最優解。

2．2粗搜索過程

假設通過最小二乘法及懲罰函數法轉換后的目標函數為

螞蟻k由式(4)選擇構造路徑，由式(5)更新路徑上的信息素。這兩個步驟重復迭代搜索整個空間，最終搜索到信息素較濃的路徑形成較短的閉合（最優）路徑，從而找到函數的近似優化解；同時也完成了粗搜索過程。

2．3精搜索過程

精搜索是指螞蟻在整個種群中開展大幅度、開創式搜索，該操作由另一類螞蟻執行。由粗搜索過程的螞蟻產生G個新解，在這G個新解中對每一個變量的區間進行細化。其目的是跳出某些變量所構成的局部極值，從而更可能獲得全局最優解。其具體操作是將上述G個新解構成遺傳算法的初始群體，并對每個解的分量進行交叉和變異算子操作；然后采用另一類螞蟻對該解分量組成的構造圖執行蟻群算法，并更新各變量子區間組成路徑上的信息素，最終搜索到信息素較濃的各解變量子區間所組成的路徑為問題的全局最優解，從而結束精搜索過程。其交叉操作及變異操作如下[6]：

a)交叉操作。隨機地從初始種群中選擇兩個個體p1、p2作為父代，并以交叉概率pc調用式(6)生成子代個體c的各分量，其上的信息素按式(8)更新。

總之，變異操作使變異量將隨迭代次數的遞增而衰減，以此收縮到全局搜索的范圍。

在進行精搜索尋優后，個體螞蟻從空間的原位置x移至新位置x′，其上的信息素更新原則為

2．4基本算法

基于蟻群算法的多維有約束函數優化問題，其整體分為粗、精搜索過程。具體算法如下：

a)將約束函數通過懲罰函數法轉換為規范的目標函數min Z(x)，并確定所有的獨立變量xi;

b)依據約束條件估計各變量的取值范圍：xjl≤xj≤xju(j=1，2，…，n);

3設計實例

為了驗證上述方法的有效性，以行星輪系優化設計為例進行如下分析。圖2所示為2k－H型行星輪系機構簡圖[7]。要求以質量最小（重量最輕）為目標對其進行優化設計。假設作用于太陽輪上的轉矩T1=1 140 N·m，傳動比u=4.64，齒輪材料均為38SiMnMo，表面淬火；HRC45~55，行星輪個數C=3。

1)設計變量影響行星輪系機構質量的獨立參數為太陽輪的齒數、齒寬、模數，即

通過表1的結果可以看出：前三種方法所求的解因第1、3變量需最后進行圓整處理，無疑給變量2帶來極大的差異，從而使最終結果與真實值差異更大；本文方法事先就考慮了需要圓整的變量，這樣計算的結果無須后續處理，同時因取整變量的區間整數劃分縮小搜索空間，使計算的效率比較高。從計算結果對比分析可知，表1中第四種方法得出的結果也比前三種的結果更精確。

4結束語

將多維變量函數優化問題通過變量的區間劃分使問題轉換為類似組合優化問題的方法進行求解；利用蟻群算法原理，將多維變量函數優化問題分成粗搜索過程和精搜索過程，在精搜索過程中融入遺傳算法的基本操作算子，從而更易獲得全局最優解；將機械設計中需要圓整的變量直接附加整數約束，這便于蟻群搜索空間的減少，且獲得的最優解不需要后期二次處理；通過行星輪系問題的常規優化、懲罰函數法、遺傳算法及基于蟻群算法的多維函數優化四種算法的對比可知，本文方法在求解精度、獲得全局解的能力等方面均優于前三種方法。

參考文獻：

［1］AFSHAR M H． Partially constrained ant colony optimization algorithm for the solution of constrained optimization problems: application to storm water network design[J]．Advances in Water Resources，2007，30(4):954－965.

[2]TOKSARI M D．Ant colony optimization for finding the global minimum[J]．Applied Mathematics and Computation，2006，176(1):308－316.

[3]LIM A，LIN Jing，RODRIGUES B，et al．Ant colony optimization with hill climbing for the bandwidth minimization problem[J]．Applied Soft Computing，2006，6(2):180－188.

[4]李智，周龍，王東.基于蟻群算法的往復振動篩運行參數優化設計[J].農業機械學報，2004，35（3）：76－78，82.

[5]高尚，楊靜宇． 群智能算法及其應用[M]． 北京：中國水利水電出版社，2006:40－42．

[6]舒服華． 基于蟻群算法的飼料螺旋輸送機優化設計[J]． 飼料工業，2006，27（15）：1－4．

[7]周廷美， 藍悅明． 機械零件與系統優化設計建模及應用[M]． 北京：化學工業出版社，2005:51－53.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文