約束優化問題算法研究綜述

朱清園

摘 要：約束優化問題是控制和決策領域的重要問題，也是智能算法領域的研究熱點之一。本文對約束優化問題的相關概念進行了介紹，詳細闡釋了求解約束優化問題的四種主要智能算法：教與學優化算法、進化算法、粒子群算法和差分進化算法，對其算法思想、流程和特征進行了總結，并對其在工程中的主要應用進行了介紹，提出了求解約束優化問題的算法發展前景和面臨的問題。

關鍵詞：約束優化問題；TLBO；遺傳算法；粒子群算法；差分進化算法

中圖分類號：TP18 文獻標識碼：A 文章編號：1671-2064（2018）01-0013-04

1 引言

所有的控制與決策問題都可以歸結為優化問題[1]，優化問題在冶金過程、化工管理、作業調度和其它工程應用等領域中廣泛存在，相關優化算法得到了廣泛應用。優化問題一般可分為無約束優化和約束優化兩類，過去數十年來，無約束優化研究的成果多，其技術已經較為成熟，能解決絕大多數的無約束問題。

相較而言，約束優化問題比無約束優化問題更復雜，因為存在約束，導致搜索空間中不可行域增加；搜索時需要平衡約束和優化，某些問題的最優解往往在可行域的邊界，特別是一些強約束問題，尋找到可行解已經非常困難，找到最優的可行解更是艱難[2]。

現有的解約束優化問題的傳統方法主要是解析法和數值法[4][5]，其存在目標函數要求高、算法對初始值依賴性強、簡單性和通用性差等缺點，因此，智能算法對于約束優化問題求解的發展至關重要。

2 約束優化問題算法綜述

智能算法通過對動物智能行為進行模仿來解決實際生活中的問題，在智能算法中，種群個體代表搜索空間中的解，不要求連續或可導，也無需目標函數的梯度信息，更適合求解約束優化問題。下面介紹求解約束問題的常見的幾種智能算法。

2.1 GA算法

在達爾文遺傳學和進化論的啟發下，Holland提出了進化算法（Genetic Algorithm，GA）。該算法在群體遺傳學機理和自然選擇基礎上進行隨機迭代和進化，具有很強的全局優化搜索能力和廣泛適用性。進化算法對自然選擇和遺傳過程中發生的交配、繁殖和變異現象進行模擬，以優勝劣汰、適者生存的自然法則為依據，對選擇、交叉和變異的進化算子加以利用，逐代產生候選解即優選個體，最終搜索得到較優的個體。進化算法是一種以種群中的所有個體為對象的種群型操作[6]。

遺傳算法的基本步驟包括：

步驟1：隨機生成初始種群，評價每個個體適配值；

步驟2：算法是否收斂判斷，如果是，則輸出搜索結果，如果否，執行以下操作；

步驟3：按照某一規則執行復制操作；

步驟4：以概率Pc執行個體間交叉操作；

步驟5：以概率Pm進行個體變異操作；

步驟6：然后轉向步驟2。

流程圖如下圖1所示。

遺傳算法具有以下特征：

（1）算法不被函數的可導性或連續性所限制，從一個問題解的集合開始進行搜索，搜索可以并行進行，速度得以提高；

（2）算法具有較強的全局尋優能力，對求解非線性復雜問題效果顯著；

（3）進行算法的交叉、復制等操作都帶有隨機性，將個體的適應度值結合在探索過程。

2.2 TLBO算法

2010年，Rao等針對機械設計優化問題提出了一種新的高效優化算法——教與學優化算法（Teaching-Learning-Based Optimization，TLBO），其屬于基于種群的啟發式智能算法[7]。

TLBO基于老師對學生的影響，其算法流程大致為：在限制約束空間中隨機生成一系列解，將這些解視為一個班級的“學生”，每個學生都有不同的科目，根據適應度值評價學生表現，其中表現最好的一位學生被任命為“老師”。算法分為教學階段和學習階段等兩個階段。在教學階段，老師向學生“授課”，學生通過在“授課”中向老師“學習”來增加自己科目的知識水平；在學習階段，類似于課后學生們相互交換學習心得，學生間進行學習交流，從而促進每個學生的成績提高。在經過多次老師的“教學”過程和學生之間相互的“學習”過程之后，班級學生的知識水平得到提高，從而等同于在整個限制約束空間中，可行解的搜索空間不斷地趨近于最優解。由于TLBO算法具備收斂能力強、收斂速度快、不需特定信息、且算法簡易、所需參數少等優點，引起了廣大研究者的研究與關注，并已經在多個領域得到了較好的應用。算法具體步驟如下：

步驟1：初始化優化模型參數和優化算法參數，包括種群規模（Population size）Pn，迭代次數Gn，待優化變量維數Dn和變量約束條件等；

步驟2：根據種群規模和變量維數隨機生成初始種群，并計算個體的成績（適應度值）。對于TLBO算法而言，種群規模表示學員的數量，待優化變量表示所提供的課程；

步驟3：教學階段，計算班級每一維的平均值mi，得到平均個體，將其中的最優解作為教師，教師意圖通過教學將均值從xold移至xteacher，通過下式得到新個體xnew：

步驟4：在學習階段，學員間通過相互交流增長知識。在教師完成教學后，從學員中隨機選擇兩個學員i和學員j，比較二者成績，成績較差的學員向成績好的學員學習；

步驟5：當達到最大迭代次數后，終止迭代，否則重復步驟3和步驟4。

TLBO算法流程圖如圖2所示。

2.3 PSO算法

粒子群算法（Particle Swarm Optimization， PSO）是由美國社會心理學家James Kennedy和電氣工程師Russell Eberhart在1995年共同提出[8]，該算法模仿鳥類群體的覓食行為，進而利用群體智能建立的一個簡化模型。粒子群算法模擬鳥類的覓食行為，用鳥類的飛行空間類比問題的搜索空間，把每只鳥抽象成一個沒有質量和體積的微粒，用以表示問題的一個候選解，用尋找食物的過程類比尋找問題最優解的過程，從而求解約束優化問題。endprint

粒子群算法的過程包括：

步驟1：種群隨機初始化；

步驟2：計算種群內每個個體的適應值，適應值和最優距離相關；

步驟3：種群根據適應值進行更新；

步驟4：判斷終止條件，如果滿足則停止，否則轉向步驟2。

其流程如圖3所示：

粒子群算法具有以下特征：

（1）通過群體概念尋求最優值，最優值可以是一個或多個；通過將大量的個體行為聚合成群體行為尋求目標值，這與遺傳算法相同；

（2）不依賴于函數本身，通過適應值來表征粒子是否滿足條件，適用于生產，這種思想繼承了當代算法的特質；

（3）從鳥群棲息出發，充分考慮鳥群的特征，每個鳥都對其他鳥產生直接和間接影響，鑒于這些影響，需要從社會部分和自適應部分這兩個部分來改變單個粒子的變化趨勢，主要體現在粒子群算法的速度更新模型。

2.4 DE算法

差分進化（Differential Evolution，DE）算法是由Rainer Storn和Kenneth Price在1995年共同提出的一種采用浮點矢量編碼在連續空間進行隨機搜索的優化算法[9]，初衷是為了求解切比雪夫多項式。差分進化算法是一種求解不可微、非線性、多極值和高維復雜函數的有效、魯棒的方法，其受控參數少，原理簡單，可以實施并行、隨機、直接的全局搜索，并且易于理解和實現。差分進化算法基于群體進化，優化問題的求解通過種群內個體間的競爭與合作來實現，具有種群內信息共享和記憶個體最優解等特點，本質是一種基于實數編碼的具有保優思想的貪婪遺傳算法。差分進化算法應用領域十分廣泛，除了約束優化問題，還包括：生物系統建模、模式識別、信號處理、決策和模擬多目標優化問題、神經網絡訓練、系統設計等。差分進化算法目前已經在模糊控制系統、機器人學、電力系統、函數優化、神經網絡訓練、組合優化及其它進化算法常用的應用領域得到成功運用。

差分進化算法的具體步驟包括：

步驟1：確定差分進化控制參數和差分參量；

步驟2：初始化種群，進化代數G=0；

步驟3：通過計算初始種群中的每個個體的適應值對其進行評價；

步驟4：判斷終止條件滿足與否或者進化代數是否達到最大進化代數，若是，則終止迭代，此時輸出的最優解即為的最優個體，否則，繼續下一步；

步驟5：對個體進行變異和交叉，并處理邊界條件，得到試驗種群；

步驟6：通過計算試驗種群中每個個體的適應值來評價試驗種群；

步驟7：進行選擇操作，得到下一代種群；

步驟8： G=G+1，轉至步驟4。

其流程圖如圖4所示。

差分進化算法具有以下特征[10]：

（1）算法通用，獨立于具體問題條件；

（2）算法原理簡單，受控參數少，容易實現；

（3）具有群體搜索能力，并能記憶個體最優解；

（4）具有良好的魯棒性，對算法稍加改動可以適應不同的應用環境；

（5）算法收斂速度快；

（6）協同搜索，可根據個體局部信息和種群全局信息引導算法進行進一步搜索；

（7）易于與其他算法相結合，因為差分進化算法在本質上為進化算法，因此容易與其他算法相互融合以提高穩定性和算法精度等，構造出更好算法。

3 約束優化算法的工程應用

智能優化算法在各個領域的應用中取得了很多研究成果。在機械設計優化中，Rao等人[11]采用TLBO算法分別對機器人機械手、多片離合器制動、錐形滑輪、靜壓推力軸承以及滾動軸承等機械設計問題進行了優化設計。在熱交換器優化設計中，文獻[12]采用改進的多目標TLBO算法對二階段熱交換器進行優化設計，分別針對板翅式換熱器（plate-fin heat exchanger，PFHE）和管殼式換熱器（shell-and-tubeheat exchanger，STHE）兩種產品進行了測試，其結果顯示TLBO算法對于熱交換器優化方面有著很強的優化性能。

生產調度是制造企業的生產計劃控制和管理的重要環節。在生產調度優化設計中，Liao等人[13]擴展傳統的二元離散粒子群算法用于求解流水車間調度問題，并且和遺傳算法進行了對比；Lian等人提出了求解調度問題的一種基于PSO思想的進化算法，他們直接利用GA的交叉和變異操作作為PSO算法中粒子速度和位置的更新操作，并將其用于求解置換流水車間調度問題[14]和作業車間調度問題[15]。

機器人是一類復雜的難以精確建模的系統，在機器人領域的優化設計中，文獻[16]中利用DE算法求解復雜環境下的機器人路徑規劃問題，結果表明該方法對解決大范圍、復雜障礙環境下的機器人運動路徑規劃問題具有普遍適用性。神經網絡訓練問題是一種高度復雜、非線性的優化問題，在神經網絡訓練優化設計中，文獻[17]將DE算法應用于在線訓練神經網絡，并在醫療圖像識別上得到運用，均取得了滿意的結果。

4 結語

本文從約束優化問題的概念出發，對求解約束優化問題的四種主要智能算法，教與學優化算法、進化算法、粒子群算法和差分進化算法的算法思想、主要步驟和特征等進行了介紹，并約束優化問題在工程中的相關應用進行了闡述。盡管近年來學者已經對約束優化問題展開了研究，但是對于非線性多變量多目標的復雜優化問題，目前還缺乏解決有效穩定的方法，因此對此還需要進行更深入研究。

參考文獻

[1]王凌，劉波.微粒群優化與調度算法[M].清華大學出版社，2008.

[2]劉云連.求解約束優化問題的智能算法研究[D].湖南科技大學，2014.

[3]Joines J A， Houck C R. On the use of non-stationary penalty functions to solve nonlinear constrained optimization problems with GA's[C]// Evolutionary Computation， 1994. IEEE World Congress on Computational Intelligence.Proceedings of the First IEEE Conference on. IEEE， 1994：579-584 vol.2.endprint

[4]希梅爾布勞.D.M.實用非線性規劃[M].科學出版社，1983.

[5]胡一波.求解約束優化問題的幾種智能算法[D].西安電子科技大學，2009.

[6]王凌.智能優化算法及其應用[M].清華大學出版社，2001.

[7]Rao R V， Savsani V J， Vakharia D P. Teaching–learning-based optimization： A novel method for constrained mechanical design optimization problems[J]. Computer-Aided Design， 2011， 43（3）：303-315.

[8] Kennedy J， Eberhart R. Particle swarm optimization[C]// IEEE International Conference on Neural Networks， 1995. Proceedings. IEEE， 2002：1942-1948 vol.4.

[9]Storn R， Price K. Differential Evolution A Simple and Efficient Heuristic for global Optimization over Continuous Spaces[J]. Journal of Global Optimization，1997，11（4）：341-359.

[10]趙曉芬.求解約束優化問題的差分進化算法[D]. 西安電子科技大學， 2012.

[11]Rao R V， Savsani V J， Vakharia D P. Teaching–learning-based optimization： A novel method for constrained mechanical design optimization problems[J]. Computer-Aided Design， 2011， 43（3）：303-315.

[12]Rao R V， Patel V. Multi-objective optimization of heat exchangers using a modified teaching-learning-based optimization algorithm[J]. Applied Mathematical Modelling， 2013， 37（3）：1147-1162.

[13] Liao C J， Tseng C T， Luarn P. A discrete version of particle swarm optimization for flowshop scheduling problems[J]. Computers & Operations Research， 2007， 34（10）：3099-3111.

[14] Lian Z， Gu X， Jiao B. A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan[J]. Applied Mathematics & Computation， 2008， 175（1）：773-785.

[15]Lian Z， Gu X， Jiao B. A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan[J]. Applied Mathematics & Computation， 2008， 175（1）：773-785.

[16]Magoulas G D， Plagianakos V P， Vrahatis M N. Neural network-based colonoscopic diagnosis using on-line learning and differential evolution[J].Applied Soft Computing，2004，4（4）：369-379.

[17]馮琦，周德云.基于微分進化算法的時間最優路徑規劃[J].計算機工程與應用，2005，41（12）：74-75.endprint