解非線性優化問題GM(1,1)模型的多子群遺傳算法

劉兵兵，郝慶一

(安慶師范學院 數學與計算科學學院，安徽 安慶 246133)

?

解非線性優化問題GM(1,1)模型的多子群遺傳算法

劉兵兵，郝慶一

(安慶師范學院 數學與計算科學學院，安徽 安慶 246133)

摘要：針對非線性優化問題約束條件中待定參數的時間序列數據，首先使用GM(1,1)方法進行建模預測得到參數的預測值，進而將參數預測值代入原問題中提出一個確定型的非線性優化問題。對該確定型問題設計了一個多子種群并行進化的遺傳算法進行求解，在分析所提算法的收斂性的基礎上，給出了初步的數值算例。數值算例實驗結果表明：該算法能夠較為精確地獲得預測型非線性優化問題的(近似)全局最優解。

關鍵詞：GM(1,1)模型；非線性優化問題；均值白化；多子群遺傳算法；全局最優解

灰色非線性優化問題從上世紀八十年代提出以后，在實際應用中取得了初步成效[1-6]。灰色非線性優化問題可以看作是普通非線性優化問題的拓展，但又與普通非線性優化問題有著明顯不同的特點：灰色非線性優化問題在處理實際問題中的貧信息不確定小樣本的參數數據特別有效。關于灰色非線性優化問題的研究可見[7-13]，文[10]考慮灰色線性和非線性優化問題的約束條件中的約束值的可變性，并給出一個預測型灰色線性模型的算例，通過GM(1,1)對使用時間序列描述的約束值進行建模預測，得到了約束參數變化趨勢的時間序列函數模型。然后將預測值代入線性優化問題中再進行優化。文[10]雖然提出了預測型的灰色非線性優化問題，但是將約束值的預測結果帶入原問題中得到的普通非線性優化問題在實踐中大多呈現非凸非可微性，因此使用傳統的求解方法將不再可行，即使轉化以后的普通非線性優化問題具有可微與凸性，對于規模很大的問題，使用傳統的優化方法難以保證實時性。因此本文首先考慮使用GM(1,1)建模方法來預測得到預測模型的白化問題，進而設計了一個多子種群并行進化的遺傳算法進行求解，最后給出了初步的數值算例。

1灰色非線性優化問題的數學模型

普通的非線性優化模型中所有參數都視為固定不變的，事實上，實際問題的非線性優化問題中參數都在或大或小的范圍內呈現一些波動性，灰色非線性優化問題就應運而生了。對于灰色非線性優化問題求解方法可見文[7-9]等。如果灰色非線性優化問題約束條件中的右端參數是由時間序列描述的，則不僅可以求解當前問題的最優解，而且可以通過灰色預測方法來預測這些參數在將來某特定時間節點的預測值，將這些參數的預測值帶入灰色非線性優化問題中，就可以預測實際問題在將來特定時間節點的目標值，這在實踐中有著非常重要的意義，可以給決策者提供較為可靠的信息以幫助決策者采取更合適的行動策略。下面給出非線性優化問題的灰色預測模型：

定義1設x=(x1,x2,…xn)T為決策變量，?(1)，?(i)(i=1,2,…,m),?(j)(j=1,2,…,l)均為灰參數集，并設r1=(r11,…,ri1,…,rm1)T與r2=(r12,…,rj2,…,rl2)T為約束右端參數向量，均由時間序列來描述，則稱

為預測型灰色非線性優化問題，記為PGCNLOP(Predicted-typeGrayConstrainedNonlinearOptimizationProblem)。其中f(x,?(1))為灰色目標泛函，gi(x,?(i))(i=1,2,…,m)與hj(x,?(j))(j=1,2,…,l)為灰色約束泛函。

如果上述PGCNLOP問題中的約束右端參數向量固定不變，則可以使用灰色優化問題的均值白化技術將PGCNLOP轉化為一個普通的非線性優化問題，定義如下。

定義2對PGCNLOP中的灰色參數進行白化，可得如下的普通非線性約束優化問題

稱該問題為PGCNLOP的白化問題。

如果對PGCNLOP中的約束右端參數的時間序列進行GM(1,1)建模，預測得到在未來特定時間節點的參數值，分別記為ri1(t)和rj2(t)。將ri1(t)和rj2(t)代入定義2中的白化問題，則可以得到如下的預測型白化問題。

定義3稱下面的非線性約束優化問題

為問題PGCNLOP的預測型白化問題。

2約束參數向量的GM(1,1)建模

考慮問題PGCNLOP約束中的右端參數向量設r1=(r11,…,ri1,…,rm1)T與r2=(r12,…,rj2,…,rl2)T，設分量ri1(i=1,…,m)和rj2(j=1,…,l)均由時間序列來刻畫，可采用GM(1,1)建模方法來得到它們的預測函數模型，具體建模步驟如下(以參數ri1為例)：

(2)ρ(s)∈[0,ε],s=2,3,…,m;

(3)ε<0.5，

第六步：確定序列預測模型的白化方程及時間響應式分別為

第八步：檢驗誤差。算出殘差平方和進而得到平均相對誤差。若滿足精度要求，則建模結束；否則可對殘差序列建立GM(1,1)模型，對原來的模型進行修正。

3多子群遺傳算法與數值算例

3.1多子群并行進化遺傳算法

對于定義3中給出的預測型均值白化問題，使用上節中的GM(1,1)建模得到預測型均值白化問題的約束右端參數向量在時刻點T(T>k)預測值并代入該模型中，便可得到下面的確定型約束非線性優化問題，記為DNLOP(T)

由于在實踐建模中得到的約束非線性優化問題大多都是非凸非光滑的，甚至連續性都難以保證，因此使用傳統的基于導數的優化方法基本不再可行。即使問題滿足凸性和光滑性，當問題的數據規模很大時，傳統的求解方法也難以保證實時性。基于此，我們設計了一個多子種群并行進化的遺傳算法來求解該問題。

遺傳算法是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，它是一種通過模擬自然進化過程搜索最優解的方法，由密西根大學Holland教授在1975年首先提出來。基本遺傳算法的步驟主要包括：生成初始種群、通過適應度函數進行選擇、對種群中的個體進行交叉與變異操作以得到下一代種群。為了保證能夠找到問題的最優解，在遺傳操作中一般都是用最優保存策略，也就是把當前種群中最好解保存起來與下一代種群的所有個體的適應度相比較，如果有更好的個體，則將該個體替換所保存的個體，否則不替換。

為了加快進化速度，提高計算結果的實時性，我們設計了一個采用實數編碼多子種群并行進化的遺傳算法，算法的主要思想是：采用實數編碼，將整個種群分成N(N≥2)個子群，每個子群各自獨立遺傳進化，在當前種群中所有子群都進化完畢時，將各自保存的最優解比較得到整個種群在當前代的最優解并保存。然后進入下一代遺傳操作，如此反復，直到最大進化迭代次數為止，輸出最終保存的最優解。

3.1.1初始種群的選取

根據問題DNLOP(T)的約束域，按照均勻分布隨機產生算法的初始種群。

3.1.2適應度評價函數的選取

算法中個體的適應度用來表示該個體適應環境的能力，同時也表示其繁殖后代的能力。適應度越大表明該個體適應環境和繁殖后代的能力越強，又因為適應度函數在比較排序的基礎上計算選擇概率，所以適應度評價函數要取正值。因此在本文中我們采用如下的適應度評價函數，即

3.1.3選擇算子

采用無回放隨機選擇算子，即根據種群中個體在下一代種群中的生存期望值進行選擇，具體選擇步驟如下：

步1：計算個體xi的生存期望值

步2：如個體xi未被選中，則令Ei=Ei-0.5；否則Ei=Ei-1；

步3：若種群中某個體的生存期望值小于等于零，則淘汰該個體，并使用最優保存策略將上一代的最優個體代替該個體。

3.1.4交叉算子

采用啟發式交叉算子，設x(t)和y(t)為第t代進行交叉運算的兩個指定個體，則兩個子代個體的第j個分量的交叉運算公式為

xj(t+1)=xj(t)+λ[xj(t)-yj(t)]，

yj(t+1)=xj(t)-λ[xj(t)-yj(t)]。

3.1.5變異算子

采用非均勻變異算子，設對個體x(t)的第j個分量xj(t)進行變異操作，其中又知xj(t)∈[U,L]，U和L分別為xj(t)的上下界，則

其中Δ(t,w)=w(1-r(1-t/s)θ)，這里的S為最大進化迭代次數，r是(0,1)內均勻產生的隨機數，θ是系統參數，決定著算法的收斂壓力。

3.1.6算法終止條件

若算法完成最大進化代數且問題的最優值連續n代無變化則算法停止，輸出最優解。

綜上，設計算法的主要步驟如下。

步1：設定最大迭代次數為S，種群規模為M，交叉概率為pc，變異概率pm，子群組數為N，并保證N能整除M，令t∶=0；

步2：在約束域中隨機生成M個初始個體，把整個種群分成N個子群；

步3：計算各子群中所有個體的適應度值，并對每個子群進行交叉，變異，選擇操作，

步4：將各子群的最優個體比較并保存整個種群的最優個體；

步5：若滿足終止條件，則算法停止輸出保存的最優解，否則令t∶=t+1，轉步3。

算法的收斂性分析如下：采用最優保存策略的遺傳算法已經被證明能夠以概率1收斂到問題的近似最優解[14-15]。在種群的初始化階段，因種群的所有個體都是在問題的約束域中隨機生成，所以在該階段的時間復雜度為O(M)，在算法的運行階段，由算法的第三步，可知時間復雜度為O(S×M)。綜合兩個階段可知，該算法的時間復雜度為O(S×M)。

3.2數值算例

設使用甲、乙、丙三種有限資源生產A，B，C，D四種產品，產品的資源消耗系數由表1給出，四種產品的需求函數分別為：p1=8-?1x1，p2=

9-?2x2，p3=10-?3x3和p4=11-?4x4，其中x1，x2，x3和x4分別為四種產品的生產量，?為灰色系數。資源甲和乙在一個生產周期內可供應量分別為200單位和300單位，資源丙的供應量是由時間序列描述，見表2。問在第6周期應如何安排生產計劃，才能使工廠的總收益最大？

表1　產品的資源消耗系數

表2　資源丙供應量的時間序列

解對該問題建模可得如下灰色非線性優化問題：

maxf(x,?)=(8x1+9x2+10x3+11x4)-

其中?1∈[0,0.02]，?2∈[0.01,0.03]，?3∈[0.03,0.05]和?4∈[0.02,0.08]。

約束中r(t)的時間序列經檢查均滿足準光滑條件和準指數規律，故按照第2節的方法進行GM(1,1)建模，得

則有

時間響應式為

進而可預測第6周期資源丙的供應量為375。將問題均值白化以后可得如下確定性非線性優化問題：

maxf(x)=(8x1+9x2+10x3+11x4)-

使用多子種群遺傳算法進行求解，設定最大迭代次數為S=200，種群規模為M=80，交叉概率為pc=0.7，變異概率pm=0.2，子群組數N=2。使用MATLAB 2010a平臺編程求出最優解為x=(0,9.592,20.376,50.661)，最優效益預測值為700.586。

4結語

針對灰色非線性優化問題的灰色預測數學模型，基于GM(1,1)模型對約束中的參數時間序列進行預測，并使用均值白化模型將其轉化為確定型的非線性優化問題，進而設計了一個多子群遺傳算法，實際算例表明求解策略和算法是可行的。

參考文獻:

[1] 馬良荔, 李剛, 陶道強. 基于灰色GM(1,1)模型的故障預測方法[J]. 計算機應用與軟件, 2013, 30(4): 198-200.

[2] 曾振東. 基于灰色支持向量機的網絡輿情預測模型[J]. 計算機應用與軟件, 2014, 31(2): 300-302, 311.

[3] 李茂達, 樊磊, 李磊, 等. 隧道與地下工程圍巖變形的灰色優化與預測[J]. 土木建筑與環境工程, 2013, 35(S2): 143-145.

[4] 張岐山, 陳華, 劉虹. 灰需求下供應鏈配送網絡優化研究[J]. 中國管理科學, 2013, 21(S1): 26-30.

[5] 楊悅. 基于離散灰色模型的優化方法研究[J]. 科學技術與工程, 2013, 13(26): 7856-7861.

[6] 王渭明, 王國富, 馮玉國. 三角模糊數型多屬性決策灰色優化模型及其在工程設計方案評價中的應用[J]. 數學的實踐與認識, 2012, 42(12): 21-27.

[7] 鄧聚龍．灰色多維規劃[M]．武漢: 華中理工大學出版社, 1988.

[8] 張曙紅, 陳綿云. 灰色非線性規劃問題及其遺傳算法求解方法[J]. 系統工程理論與實踐, 2002, 22(7): 128-130.

[9] 劉思峰, 黨耀國, 方志耕, 等. 灰色系統理論及其應用[M]. 北京: 科學出版社, 2010.

[10] 何勇. 灰色線性和非線性規劃的一種通用解法[J]. 科技通報, 1988, 4(4): 16-19.

[11] 劉兵兵, 郭亞君. 灰色多隨從二層線性規劃問題及其解法[J]. 吉林大學學報(理學版), 2011, 49(04): 625-632.

[12] 劉兵兵. 一類灰色二層線性多目標規劃問題及其算法[J]. 山東大學學報(理學版), 2012, 47(5): 122-126.

[13] 周偉平, 劉兵兵. 解灰色非線性規劃問題的一種隨機搜索算法[J]. 計算機應用, 2013, 33(10): 2819-2821.

[14] 徐宗本, 陳志平, 章祥蓀. 遺傳算法基礎理論研究的新近發展[J]. 數學進展, 2000, 46(2): 97-114.

[15] 張文修，梁怡. 遺傳算法的數學基礎[M]. 西安: 西安交通大學出版社, 2000.

A Multi-subgroup Genetic Algorithm for Solving GM (1, 1)Model of Nonlinear Optimization Problem

LIU Bing-bing， HAO Qing-yi

(School of Mathematics and Computation Science, Anqing Teachers College, Anqing 246133, China)

Abstract:According to the historical data of the time series of the constraints parameters in the nonlinear optimization problem, the values of the constraints parameters are modeled and predicted using GM(1,1) method. Substituting the predicted values of the parameters into the grey nonlinear optimization problem, we obtain a determinate nonlinear optimization problem. Then, we design a multi-subgroup genetic algorithm genetic algorithm to solve the resulting problem. Moreover, we analyze the convergence of our method and develop preliminary the numerical experiment which shows that the (approximated) global optimal solution of the predicted nonlinear optimization problem can be found using the proposed method.

Key words:GM(1,1) model，nonlinear optimization problem，mean whitenization，multi-subgroup genetic algorithm，global optimal solution

文章編號：1007-4260(2015)03-0026-05

中圖分類號：TP391.9

文獻標識碼：A

DOI：10.13757/j.cnki.cn34-1150/n.2015.03.008

作者簡介：劉兵兵，男，河北武安人，碩士，安慶師范學院副教授，研究方向為優化理論與方法。

基金項目：安徽省高校省級自然科學基金重點項目(KJ2014A139)。

收稿日期：2014-12-09

郝慶一，男，安徽霍邱人，博士，安慶師范學院副教授，主要研究領域為博弈論及其應用。

網絡出版時間：2015-8-25 15:40網絡出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20150825.1540.008.html