[發明專利]一種基于局部Lipschitz估計的區域動態剖分群體全局優化方法

在審

• 申請號: 201410420989.1
• 申請日: 2014-08-25
• 公開（公告）號: CN104200084A
• 公開（公告）日: 2014-12-10
• 發明（設計）人: 張貴軍;周曉根;郝小虎;梅珊;李章維
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 杭州斯可睿專利事務所有限公司 33241
• 代理人: 王利強

1.一種基于局部Lipschitz估計的區域動態剖分群體全局優化方法，其特征在于： 所述全局優化方法包括以下步驟：

1)初始化：設置常數C，種群規模N_P，各變量的下界a_i和上界b_i，置無效區域 IR為空，代g＝0，較差個體數目為N_j＝0，較差個體重新初始化數目t＝0，在 各變量定義域范圍內隨機生成初始種群

2)支撐矩陣初始化：

2.1)根據公式(1)對單位單純形區域S的各頂點進 行轉換得到點x¹,x²,...,x^N+1；

xi=xi′Σi=1N(bi-ai)+ai,i=1,2,...,N---(1)]]>

其中a_i為x_i的下界，b_i為x_i的上界，其中x_i′為各頂點在S中的坐標值，N 為問題維數；

2.2)根據公式(2)計算各點的支撐向量l¹,l²,...,l^N+1，式中f(x^k)表示x^k對應的目 標函數值；

lk=(f(xk)C-x1k,f(xk)C-x2k,...,f(xk)C-xN+1k)---(2)]]>

其中，C為足夠大的常數；

2.3)建立初始矩陣支撐矩陣支撐矩陣L如公式(3)；

L=l1k1l2k1···lN+1k1l1k2l2k2···lN+1k2············l1kN+1l2kN+1···lN+1kN+1---(3)]]>

3)判斷是否滿足終止條件：計算出當前群體中的最優個體x_best和最差個體x_worst， 如果滿足終止條件|f(x_best)-f(x_worst)|≤ε，其中，ε為允許誤差，則保存結果并 退出，否則進入步驟4)；

4)建立n叉樹保存各下界估計值：以支撐矩陣L＝{l¹,l²,...,l^N+1}為根建立樹；

5)交叉、變異產生新個體x_trial：

5.1)任意選取三個個體{x^a,x^b,x^c|a,b,c∈{1,2,...,popSize},a≠b≠c≠k}；

5.2)根據公式(4)對{x^a,x^b,x^c}執行變異操作，生成變異個體

x^k=xa+F·(xb-xc)---(4)]]>

5.3)根據公式(5)對目標個體x^k和變異個體執行交叉操作，生成新個體x_trial：

xtrial[i]=x^ikif(randb(0,1)≤CR)ori=rnbr(i)xikif(randb(0,1>CR)ori≠rnbr(i)i=1,2,...,N---(5)]]>

其中，randb(0,1)表示為產生0到1之間的隨機小數，rnbr(i)表示隨機產 生1到N之間的整數；

6)提取新個體的鄰近信息構建支撐向量對可行域進行剖分：找出離新個體x_trial最 近的兩個個體，并對其構建支撐向量：

6.1)根據公式(6)將x^k轉換到單位單純形空間中得到x^k′；

xi′≡(xi-ai)/Σi=1N(bi-ai)xN+1′≡1-Σi=1Nxi′,i=1,2,...,N---(6)]]>

6.2)根據公式(2)計算x^k′的支撐向量l^k；

6.3)根據條件關系式(7)(8)更新樹：

∀i,j∈I,i≠j:likj>liki---(7)]]>

∀r∉{k1,k2,...,kN+1},∃i∈I:Lii=liki≥lir---(8)]]>

其中，表示存在；

a)找出針對步驟6.2)構建的支撐向量l^k不滿足條件(8)的葉子節點；

b)用l^k替換步驟a)中找到的葉子節點矩陣中的第i個支撐向量從 而形成新的葉子節點；

c)判斷步驟b)中產生的新的葉子節點是否滿足條件關系式(7)，如果滿 足，則保留，否則刪除；

7)計算新個體x_trial的下界估計值：

7.1)根據公式(6)對x_trial個體作變換得到x_t′_rial；

7.2)根據公式(9)從樹中找出包含x′_trial個體的樹葉在節點TreeNode，其中x^*用 x′_trial代替；

(xj*-xjkj)<(xi*-xikj),i,j∈I,i≠j---(9)]]>

其中為所找的葉子節點矩陣中的元素；

7.3)根據公式(10)計算出x′_trial所在節點TreeNode的下界估計值y_trial，其中xⁱ用 x′_trial代替；

HK(x)=maxk≤Kmini=1,...N+1C(lik+xi)---(10)]]>

其中max表示求最大值，min表示求最小值，xⁱ為單位單純形空間中的 向量；

8)選擇：通過如下操作決定新個體x_trial是否可以替換其對應的目標個體x^k：

8.1)如果x_trial被包含在無效區域IR中，則保留x^k不變，并轉到步驟8.10)，否 則繼續步驟8.2)；

8.2)利用新個體的下界估計值指導種群更新：如果x_trial的下界估計值y_trial大于 目標個體的函數值f(x^k)，則目標個體不變，并轉到8.3)，否則轉到步驟 8.6)；

8.3)根據下界估計值建立較差個體評定線(面)，并找出較差個體：將y_trial所在 的水平線(面)定位較差個體評定線(面)，即如果種群中個體的目標函數值 大于y_trial，則將其視為較差個體，并記錄；

8.4)繼續根據公式(11)計算出節點TreeNode所對應的下界估計區域的極小值 d_min；

d(L)=HK(xmin′)=C(Trace(L)+1)N+1---(11)]]>

其中Trace(L)表示矩陣的跡，即正對角線元素之和，其中L為支撐矩陣；

8.5)根據下界估計區域的極值信息有效的識別出無效區域：如果d_min大于當前 最優值f(x_best)，則將TreeNode所對應的區域視為無效區域，并加入IR中；

8.6)如果x_trial個體的目標函數值f(x_trial)小于f(x_i)，則x_trial個體取代目標個體 x^k，并轉到步驟8.8)，否則轉到步驟8.7)；

8.7)根據更新結果對優化區域進一步剖分，進一步識別出無效區域：根據公式 (2)對x_trial構建支撐向量，并按照步驟6.3)更新樹，根據公式(11)計算出 新生成的估計區域的極值，按照步驟8.5)通過各極值與當前種群的最優值 的比較進一步識別出無效區域,并加入IR中,同時轉到步驟8.9)；

8.8)繼續作局部增強，進行如下操作：

a)繼續根據公式(12)計算出TreeNode對應區域的下界支撐函數的極小值 點x′_min，式中L用TreeNode對應的支撐矩陣代替；

xmin′(L)=dC-lik---(12)]]>

b)根據公式(1)對x′_min轉換得到x_min；

c)計算x_min對應的目標函數值f(x_min)；

d)如果f(x_min)小于目標個體的函數值f(x^k)，則x_min取代目標個體x^k；

8.9)將部分較差個體重新初始化:從較差個體中隨機選取t(1≤t≤N_j)個重新 初始化；

8.10)刪除樹并轉到步驟3)；

9)設置g＝g+1，并轉到步驟3)。