0-1非線性規劃問題改進的教與學優化算法?

0-1非線性規劃問題改進的教與學優化算法?

張林李會榮

（商洛學院數學與計算機應用學院商洛726000）

將0-1非線性規劃問題轉化為約束優化問題，采用動態雙目標的約束處理方法，對教與學優化算法的迭代方程進行改進，提出了一種求解0-1非線性規劃問題的改進教與學優化算法。數值實驗表明，新算法具有較快的收斂速度和較好的全局尋優能力，顯示了算法的有效性和通用性。

0-1非線性規劃；約束優化；教與學優化算法

Class NumberTP18

1 引言

教與學優化（Teaching-learning-based optimi?zation，TLBO）算法是一種新型的群體智能優化算法，由印度學者Rao R V等于2011年提出，主要模擬教師的教學過程和學生之間的相互學習與交流過程［1～2］。TLBO算法結構簡單，易于實現，參數少，有極強的收斂能力和較好的全局搜索能力，所以自算法提出以來已經涌現出許多對算法的改進和應用方面的研究。例如：文獻［3］將差分進化算法的交叉操作引入到TLBO算法中，提出了一種帶有交叉操作的教－學優化算法，有效地融合了教學階段和學習階段，增強了算法的局部搜索；文獻［4］將差分進化算法中變異策略融入到TLBO中，對學習階段迭代方程進行改進，提出了一種融合差分變異的教－學優化算法；文獻［5］提出了一種融合模擬退火的改進的教與學優化算法，文獻［15］引入反饋階段和準確性因子，提出了一種改進的教與學的優化算法等等，目前TLBO已經成功應用到很多工程實際問題，例如非線性連續大規模優化［1］、約束優化問題［6］、多目標優化問題［7］等。

本文考慮0-1非線性規劃問題如下：

其中f(x):Rn→R; gi(x):Rn→R, i=1,…m; hk(x):Rn→R,k=1,…,l是Rn上的可微函數。

非線性約束優化問題廣泛存在于科學與工程領域，是一類比較難以解決的優化問題，沒有普遍適用的解法。0-1非線性規劃應用很廣，很多問題可以歸結為0-1非線性規劃問題，例如指派問題、資本預算問題、背包問題、旅行商問題等［8～10］。

本文首先把0-1非線性規劃問題轉化為約束優化問題，采用動態雙目標的約束處理方法，提出了一種求解0-1非線性規劃問題的改進教與學優化算法，數值結果表明，提出的算法簡單，易于實現，具有較快的全局搜索能力。

2 基本TLBO算法

基本TLBO算法模擬了班級教學的過程，通過教師的講授和學生之間的相互學習，來達到班級整體成績上升的目的。在該算法中，學生的人數代表種群的規模，學生學習的科目個數表示優化問題搜索空間的維數，學生學習成績類似于優化問題的適應度，在整個群體中教師被認為學習的最好者，代表最優解。TLBO算法的搜索過程分為教學階段和學習階段具體如下。

2.1教學階段

教師通過提高班級平均成績的方式來達到教育學生的目的。假設m表示班級學習的科目（空間的維數），n表示班級的學生人數（種群規模），Mi,j表示班級在第i次迭代中第j門課程平均值，Xi,kbest,j表示到第i次迭代班級中第j門課程中學習成績最好者作為教師。則學生與教師之間的差異可以表示為

其中k=1,2,…,n，j=1,2,…,m，ri表示[0,1]之間的隨機數，TF稱為教學因子，表示平均值的變化程度，通常設置為1或2。TF按照下式隨機地等概率的變化［1-2］：

其中rand表示[0,1]之間產生的隨機數，round[]表示四舍五入取整。

在教學階段，新產生的學習者主要使得每門課程的平均值向教師的知識水平移動，所以在Difference_Meani,k,j基礎之上，第k個學習者在教學階段按照下式產生新的學習者：

其中Xi,k表示第i次迭代中第k個學習者的學習能力。如果X′i,k優于Xi,k，則更新Xi,k，如果X′i,k優于Xi,kbest，則更新Xi,kbest（其中Xi,kbest表示直到第i次迭代中最好的學習者）。

f(Xi,k)表示第i次迭代中第k個學習者的適應值。如果xnewi,k優于Xi,k，則更新Xi,k，如果xnewi,k優于Xi,kbest，則更新Xi,kbest。

2.2學習階段

班級學生之間可以相互學習。隨機選擇兩個學習者k,k′，且k≠k′，第i次迭代中由學習者k,k′相互影響而產生新的學習者如下式：

3 改進的TLBO算法（ITLBO）

3.1線性遞減的教學因子

在基本的教與學優化算法中，教學因子TF的大小決定著平均值的變化情況，由式（4）可以看出，TF要么取值為1，或者取值為2，即表示學習者從教師那里沒有學到知識，要么學習者從教師那里學到全部知識。但是在實際的教學中而是介于兩者之間。TF越小則表示搜索的步長較小，收斂速度比較慢；而TF越大則加速算法的收斂速度，但減少算法局部探測能力。為此將TF設置隨著迭代次數而自適應變化如下：

其中Imax表示最大的迭代次數，i表示當前的迭代次數。從式（7）可以看出，教學因子隨著迭代次數的增加由2逐漸減小到0，表示隨著迭代的進行，知識難度的逐漸增加，學習者學習知識的能力開始下降，有利于加強算法的局部搜索能力。

3.2TLBO算法的改進策略

由于TLBO算法主要針對連續函數進行搜索運算，不能直接應用于0-1非線性規劃問題，所以必須對其進行改進。為此，首先引入Sigmoid函數［11］求參數s，Sigmoid函數是神經網絡中常用的一種模糊函數，形式如下

當Xmax=6時，參數s的取值范圍為[0.0025, 0.9975]。對TLBO算法中每次迭代所產生的學習者的每個分量進行改進，形式如下其中rand為(0,1)中的隨機數。這樣，改進后的TLBO算法就可以應用求解0-1非線性規劃問題。為了進一步改進粒子的全局搜索能力，按照一定的概率pm對當前學習者在{0,1}空間進行隨機賦值。

4 0-1非線性規劃問題的改進TLBO算法

4.1約束的處理技術

用粒子群優化算法求解約束優化問題時，處理約束條件是關鍵。本文采取動態雙目標的處理方法［12］來求解0-1非線性規劃問題，它的主要思想是將約束違反度函數作為優化的第一個目標，將目標函數作為第二個目標進行優化。為此定義約束違反度函數：

顯然，φ(x)是所有違反約束的和，φ(x)≥0，并且φ(x)=0當且僅當x∈F（F表示非線性約束優化問題（2）的可行域）。因此求解約束優化問題（COP）就可以轉化為無約束雙目標優化問題：

由式（10）可以看出，φ(x)=0的所有解構成了約束優化問題的可行域，因此只有當φ(x)=0時，才開始優化min f(x)。但是許多優化問題的最優解就在可行域的邊界附近，位于最優解附近的不可行解對于尋找最優解是很有幫助的。為此，本文設置一個約束容忍度δ≥0，使得φ(x)≤δ時，就開始優化f(x)。如果一個粒子在可行域的外面，即φ(x)＞δ，則這個粒子以φ(x)為其優化目標，否則的話，粒子以目標函數f(x)進行優化。

4.2改進TLBO算法的描述（ITLBO）

由此，求解0-1非線性規劃問題（1）的改進TL?BO算法（ITLBO）的流程如下：

步驟1（初始化）設置當前迭代代數t=1，確定種群的大小N，搜索空間的維數M，在｛0，1｝空間內初始化班級和優化問題f(x)。

步驟2按照式（10）計算每個學生的約束違反度φ(Xk)≤δ，如果A={Xk|φ(Xk)≤δ}≠?，則當前群體中最優個體（即教師）gbest=argf(x)，否則gbest=argφ(x)。

步驟3教學階段。根據式（5）、式（11）更新每個學習者和教師的知識水平。

步驟4學習階段。根據式（6）在班級中隨機選擇兩個學習者，通過對比差異進行相互學習。

步驟5變異階段。按照概率pm對當前學習者在{0,1}空間進行隨機賦值。

步驟6讓t=t+1，返回到步驟3，直到獲得一個預期的適應值或達到設定的最大迭代次數停止。

5 數值實驗

文獻［13］利用最速下降法來求解0-1非線性規劃問題，為了比較仍采用文獻［13］中的例子來說明算法的有效性。其中例1～2為0-1線性規劃問題，例3～4為0-1非線性規劃問題，例題如下：

例4［14］：求0-1二次規劃min f(x)=xTQx, x∈{0,1}5，其中

數值實驗在Matlab2014a中進行，在計算中，學生的規模N=20，最大的迭代次數為200，教學因子TF從2線性遞減到0。約束容忍度δ=10-10，變異概率pm=0.3。每組實驗在相同的條件下獨立運行30次，30次運行的最優解、最優值、成功率、以及運行的平均時間與文獻［8］的結果比較結果見下表1（其中“--”表示文獻中沒有提供數據）。

表1 新算法與文獻［8～9］的運行結果比較表

從表1中可以看出ITLBO算法很快找到了最優解，同時也不需要初始點，具有較快的收斂速度和較好的全局尋優能力。與文獻［13］中相比特別是例2，文獻［13］中利用最速下降法迭代9次時才得到局部最優解x*=(1,1, 0,1,1)，最優值為f(x*)=-2，而利用新算法每次都得到了最優解，得到的全局最優值f(x*)=-6，從而顯示了新算法的有效性和通用性。

6 結語

本文提出了一種求解0-1非線性規劃問題的改進教與學優化算法，首先把0-1非線性規劃轉化為約束優化問題，采用動態雙目標的約束處理方法，引入Sigmoid函數，對基本教與學優化算法進行改進，使之適合求解0-1非線性規劃問題。最后數值試驗說明了提出的算法簡單，易于實現，具有良好的收斂性。

［1］Rao R V，Savsani V J，Vakharia D P.Teaching-learn?ing-based optimization：A novel method for constrained mechanical design optimization problems［J］.Comput?er-Aided Design，2011，43：303-315.

［2］Rao R V，Savsani V J，Vakharia D P.Teaching-Learn?ing-Based Optimization：An optimization method for con?tinuous nonlinear large scale problems［J］.Information Sciences，2012，183：1-15.

［3］高立群，歐陽海濱，孔祥勇，等.帶有交叉操作的教-學優化算法［J］.東北大學學報（自然科學版），2014，35（3）：323-327.

GAO Liqun，OUYANG Haibin，KONG Xiangyong，et al. Teaching-Learning Based Optimization Algorithm with Crossover Operation［J］.Journal of Northeastern University（Natural Science），2014，35（3）：323-327.

［4］李會榮，喬希民，趙鵬軍.融合差分變異的教-學優化算法［J］.計算機工程與應用，2016，52（5）：36-40.

LIHuirong，QIAOXimin，ZHAOPengjun.Teach?ing-Learning Based Optimization Algorithm by using dif?ferential mutation［J］.Computer Engineering and Applica?tion，2016，52（5）：36-40.

［5］岳振芳，高岳林.融合模擬退火的改進教與學優化算法［J］.河南師范大學學報（自然科學版），2016，44（1）：149-154.

YUE Zhenfang，GAO Yuelin.Modified Teaching-Learn?ing-Based Optimization Algorithm by Using Simulated An?nealing［J］.Journal of Henan Normal University（Natural Science Edition），2016，44（1）：149-154.

［6］Rao R V，Patel Vivek.An elitist teaching-learning-based optimization algorithm for solving complex constrained op?timization problems［J］.International Journal of Indus-tri?al Engineering Computations，2012，3：535-560.

［7］Rao R V，Patel Vivek.Multi-objective optimization of heatexchangersusingamodifiedteaching-learn?ing-based optimization algorithm［J］.Applied Mathemati?cal Modelling，2013，37：1147-1162.

［8］Bazaraa M S，Sherali H D，Shetty C M.Nonlinear Program?ming，Theory and Algorithm，Seconded［M］.New York：Academic Press，1979.

［9］Rao S S.Optimization（Theory and Application）Publica?tion，No.161，vol.2，1977.

［10］Hilier F S，Liberman G J.Introduction to Mathematical Programming［M］.New York：Graw-Hill，1981.

［11］紀震，廖惠連，吳青華.粒子群優化算法及應用［M］.北京：科學出版社，2009.

JI Zhen，LIAO Huilian，WU Qinghua.An Improved Teaching-Learning-Based Optimization Algorithm［M］. Beijing：Science press，2009.

［12］Haiyan Lu，Weiqi Chen.Dynamic-objective particle swarm optimization for constrained optimization problems［J］.J Glob Optim，2006，12：409-419.

［13］ANJIDANI M，EFFATI S.Steepest descent method for solving zero-one nonlinear programming problems［J］. Applied Mathematics and Computation，2007，193：197-202.

［14］雍龍泉.一類0-1二次規劃最優解的新算法［J］.數學的實踐與認識，2009，39（6）：194-197.

YONG Longquan.A New Method for Zero-one Quadratic Programming［J］.Joumal of Mathematics in Practice and Theory，2009，39（6）：194-197.

［15］李會榮，李甜.一種改進的教與學的優化算法［J］.商洛學院學報，2016，30（2）：1-5.

LI Huirong，LI Tian.An Improved Teaching-Learn?ing-Based Optimization Algorithm［J］.Journal of Shan?gluo University，2016，30（2）：1-5.

Improved Teaching-learning-based Optimization Algorithm for Solving Zero-one Nonlinear Programming Problems

ZHANG LinLI Huirong
（Department of Mathematics and Computer Science，Shangluo University，Shangluo726000）

The zero-one nonlinear programming problems is converted constrained optimization problems，an improved teach?ing-learning-based optimization（ITLBO）for solving the zero-one nonlinear programming is proposed using dynamic bi-objection constraint-handling method and modifying the iterative equation of TLBO algorithm.Simulation results show that ITLBO is effective?ness in terms of convergence speed and global optimization ability.

zero-one nonlinear programming，constrained optimization，teaching-learning-based optimization

TP18

10.3969/j.issn.1672-9722.2017.05.010

2016年11月20日，

2016年12月27日

張林，男，教授，研究方向：計算機應用，網絡安全。李會榮，男，副教授，研究方向：圖像處理。