約束優(yōu)化問題算法研究綜述

朱清園

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

關(guān)鍵詞：約束優(yōu)化問題；TLBO；遺傳算法；粒子群算法；差分進(jìn)化算法

中圖分類號：TP18 文獻(xiàn)標(biāo)識碼：A 文章編號：1671-2064（2018）01-0013-04

1 引言

所有的控制與決策問題都可以歸結(jié)為優(yōu)化問題[1]，優(yōu)化問題在冶金過程、化工管理、作業(yè)調(diào)度和其它工程應(yīng)用等領(lǐng)域中廣泛存在，相關(guān)優(yōu)化算法得到了廣泛應(yīng)用。優(yōu)化問題一般可分為無約束優(yōu)化和約束優(yōu)化兩類，過去數(shù)十年來，無約束優(yōu)化研究的成果多，其技術(shù)已經(jīng)較為成熟，能解決絕大多數(shù)的無約束問題。

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

現(xiàn)有的解約束優(yōu)化問題的傳統(tǒng)方法主要是解析法和數(shù)值法[4][5]，其存在目標(biāo)函數(shù)要求高、算法對初始值依賴性強(qiáng)、簡單性和通用性差等缺點(diǎn)，因此，智能算法對于約束優(yōu)化問題求解的發(fā)展至關(guān)重要。

2 約束優(yōu)化問題算法綜述

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

2.1 GA算法

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

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

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

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

步驟3：按照某一規(guī)則執(zhí)行復(fù)制操作；

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

步驟5：以概率Pm進(jìn)行個體變異操作；

步驟6：然后轉(zhuǎn)向步驟2。

流程圖如下圖1所示。

遺傳算法具有以下特征：

（1）算法不被函數(shù)的可導(dǎo)性或連續(xù)性所限制，從一個問題解的集合開始進(jìn)行搜索，搜索可以并行進(jìn)行，速度得以提高；

（2）算法具有較強(qiáng)的全局尋優(yōu)能力，對求解非線性復(fù)雜問題效果顯著；

（3）進(jìn)行算法的交叉、復(fù)制等操作都帶有隨機(jī)性，將個體的適應(yīng)度值結(jié)合在探索過程。

2.2 TLBO算法

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

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

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

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

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

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

步驟5：當(dāng)達(dá)到最大迭代次數(shù)后，終止迭代，否則重復(fù)步驟3和步驟4。

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

2.3 PSO算法

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

粒子群算法的過程包括：

步驟1：種群隨機(jī)初始化；

步驟2：計算種群內(nèi)每個個體的適應(yīng)值，適應(yīng)值和最優(yōu)距離相關(guān)；

步驟3：種群根據(jù)適應(yīng)值進(jìn)行更新；

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

其流程如圖3所示：

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

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

（2）不依賴于函數(shù)本身，通過適應(yīng)值來表征粒子是否滿足條件，適用于生產(chǎn)，這種思想繼承了當(dāng)代算法的特質(zhì)；

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

2.4 DE算法

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

差分進(jìn)化算法的具體步驟包括：

步驟1：確定差分進(jìn)化控制參數(shù)和差分參量；

步驟2：初始化種群，進(jìn)化代數(shù)G=0；

步驟3：通過計算初始種群中的每個個體的適應(yīng)值對其進(jìn)行評價；

步驟4：判斷終止條件滿足與否或者進(jìn)化代數(shù)是否達(dá)到最大進(jìn)化代數(shù)，若是，則終止迭代，此時輸出的最優(yōu)解即為的最優(yōu)個體，否則，繼續(xù)下一步；

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

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

步驟7：進(jìn)行選擇操作，得到下一代種群；

步驟8： G=G+1，轉(zhuǎn)至步驟4。

其流程圖如圖4所示。

差分進(jìn)化算法具有以下特征[10]：

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

（2）算法原理簡單，受控參數(shù)少，容易實(shí)現(xiàn)；

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

（4）具有良好的魯棒性，對算法稍加改動可以適應(yīng)不同的應(yīng)用環(huán)境；

（5）算法收斂速度快；

（6）協(xié)同搜索，可根據(jù)個體局部信息和種群全局信息引導(dǎo)算法進(jìn)行進(jìn)一步搜索；

（7）易于與其他算法相結(jié)合，因為差分進(jìn)化算法在本質(zhì)上為進(jìn)化算法，因此容易與其他算法相互融合以提高穩(wěn)定性和算法精度等，構(gòu)造出更好算法。

3 約束優(yōu)化算法的工程應(yīng)用

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

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

機(jī)器人是一類復(fù)雜的難以精確建模的系統(tǒng)，在機(jī)器人領(lǐng)域的優(yōu)化設(shè)計中，文獻(xiàn)[16]中利用DE算法求解復(fù)雜環(huán)境下的機(jī)器人路徑規(guī)劃問題，結(jié)果表明該方法對解決大范圍、復(fù)雜障礙環(huán)境下的機(jī)器人運(yùn)動路徑規(guī)劃問題具有普遍適用性。神經(jīng)網(wǎng)絡(luò)訓(xùn)練問題是一種高度復(fù)雜、非線性的優(yōu)化問題，在神經(jīng)網(wǎng)絡(luò)訓(xùn)練優(yōu)化設(shè)計中，文獻(xiàn)[17]將DE算法應(yīng)用于在線訓(xùn)練神經(jīng)網(wǎng)絡(luò)，并在醫(yī)療圖像識別上得到運(yùn)用，均取得了滿意的結(jié)果。

4 結(jié)語

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

參考文獻(xiàn)

[1]王凌，劉波.微粒群優(yōu)化與調(diào)度算法[M].清華大學(xué)出版社，2008.

[2]劉云連.求解約束優(yōu)化問題的智能算法研究[D].湖南科技大學(xué)，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.實(shí)用非線性規(guī)劃[M].科學(xué)出版社，1983.

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

[6]王凌.智能優(yōu)化算法及其應(yīng)用[M].清華大學(xué)出版社，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]趙曉芬.求解約束優(yōu)化問題的差分進(jìn)化算法[D]. 西安電子科技大學(xué)， 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ìn)化算法的時間最優(yōu)路徑規(guī)劃[J].計算機(jī)工程與應(yīng)用，2005，41（12）：74-75.endprint