基于改進邊際優(yōu)化的離散變量優(yōu)化設計算法

吳詩輝, 李正欣, 劉曉東, 周 宇, 賀 波

(空軍工程大學裝備管理與無人機工程學院, 陜西 西安 710051)

0 引 言

離散變量仿真優(yōu)化區(qū)別于連續(xù)變量仿真優(yōu)化,其主要特點是參數(shù)取值是離散化的,這在多參數(shù)設計問題中廣泛存在[1-8]。事實上,在實際應用中,尤其是工程問題,由于變量的精度要求或變量性質特點,離散變量的優(yōu)化比連續(xù)變量更具有實際意義。

傳統(tǒng)優(yōu)化方法主要適用于連續(xù)變量的優(yōu)化,由于離散變量不連續(xù)、約束函數(shù)限制等特點,許多傳統(tǒng)優(yōu)化方法不再適用。通常的處理方法,一種是基于連續(xù)變量優(yōu)化的方法。比如圓整法,即將所有離散變量視為連續(xù)變量,找出局部最優(yōu)解,然后將其圓整到附近的離散解上,該方法可能找到局部滿意解,但是大多數(shù)情況下,這些離散解不是離散變量優(yōu)化問題的最優(yōu)解[2-3]。兩步搜索法在圓整法的基礎上,以圓整法找到的解作為起點,按照某種方式搜索離散最優(yōu)解,但是離散最優(yōu)解不一定在連續(xù)最優(yōu)解附近。第二種是遺傳算法[2,4-6]。通過設計適用于離散搜索的遺傳算子在離散空間進行搜索,從而找到最優(yōu)解。但是遺傳算法在復雜最優(yōu)化問題尤其是高維度最優(yōu)化問題中,可能出現(xiàn)效率低、難以找到最優(yōu)解等問題,有時找到的滿意解周邊就是局部最優(yōu)解,卻不能發(fā)現(xiàn)(如例2中對文獻[4]得到解的分析),這是遺傳算法非連續(xù)、跳躍性搜索的原理決定的。第三種是各種啟發(fā)式算法,如蟻群算法[7],粒子群算法[8-9],模擬退火算法[10],螢火蟲算法[11],禁忌搜索算法[12]等,這些算法原本是用于對連續(xù)變量問題進行優(yōu)化,通過對算法從編碼、搜索算子、懲罰函數(shù)等方面進行適應性改進,能夠解決離散變量的優(yōu)化問題,但是這些算法往往需要對目標函數(shù)值進行大量的測試和計算。比如,對于一個雙變量的問題,數(shù)量級達到10 000次[13],對于需要較長時間完成一次目標函數(shù)值測算的問題,如仿真優(yōu)化問題[14-15],是不切實際的。

因此,如何針對高維度的復雜離散變量優(yōu)化問題,以最少的迭代次數(shù)得到滿意解或局部最優(yōu)解,是本文的研究目標。由于現(xiàn)實中的離散變量優(yōu)化設計問題,多是有限區(qū)域的,即離散變量存在上下界,本文主要研究有限區(qū)域、高維度的復雜離散變量優(yōu)化問題。通過借鑒邊際優(yōu)化思想、模式搜索算法的搜索策略,設計了一種基于邊際優(yōu)化的離散變量優(yōu)化算法,可以快速、收斂地找到局部最優(yōu),通過引入變異操作,能夠盡可能找到更多局部最優(yōu)或得到全局最優(yōu)。該方法不需要目標函數(shù)的先驗信息(如梯度等)，適合于多變量的優(yōu)化、離散變量的仿真優(yōu)化等問題。

1 基本原理

離散變量優(yōu)化問題可描述為

(1)

式中,XD為離散空間。

定義 1對于離散變量優(yōu)化問題,稱點A(用XA表示)為可行點,即當點A在可行域內(XA∈XD),且gi(XA)≤0,hj(XA)=0均滿足時;若以可行點A為起點,向其周圍進行單位步長搜索,即每次僅對一個變量進行單步長增減,其余變量不變,稱得到的所有點構成點A的周圍單位步長空間Ω(A)。

比如,點A為(x1,x2),x1和x2的離散步長分別為d1和d2,則其周圍單位步長空間定義為集合Ω(A)={(x1+d1,x2), (x1-d1,x2), (x1,x2+d2), (x1,x2-d2)}。如圖1所示的E點,其周圍單位步長空間為Ω(E)={B,D,F,H},由于圖1中的d1=d2,則其周圍單位步長點剛好位于以E點為圓心,以d1為半徑的圓上。由于單位步長空間每次僅改變單個元素,通過增加或減少單位步長得到,因此單位步長空間包含點的個數(shù)為2n,n表示維數(shù)。

圖1 邊際搜索與單位步長Fig.1 Marginal search and unit step

對于邊界上的點,仍假定其周圍單位步長空間點為2n個,但其中超出邊界的點為不可行點,規(guī)定不可行點的目標函數(shù)值均為∞,如圖1中的邊界點C,其超出邊界的周圍單位步長空間點K和J的目標函數(shù)值均設為∞。

定義 2對于離散變量優(yōu)化問題,假設可行點A為起點,若存在點B滿足B∈Ω(A),B≠A,且B點的目標函數(shù)值在Ω(A)中最小,稱B點為單步邊際優(yōu)化點,稱路線A→B為單步邊際優(yōu)化搜索路線。

定義 3對于離散變量優(yōu)化問題,稱點A為一個局部極小點,當且僅當A在其周圍單位步長空間Ω(A)內目標函數(shù)值最小時。

以圖1為例,考慮一個簡單的二維離散變量優(yōu)化問題。該問題的取值區(qū)間為[-1,1]2,x1和x2的離散步長均為1,該區(qū)間內共有9個離散點,將各點的目標函數(shù)值標在點上,如圖1(a)所示。圖中E點的目標函數(shù)值為3,其周圍單位步長空間Ω(E)={B,D,F,H}上各點的目標函數(shù)值均大于3,則可認為E點為1個局部極小點。同樣,C點為另一個局部極小。該問題如按照連續(xù)變量優(yōu)化,則E點可能不是一個局部極小,因為假設在EC連線方向上目標函數(shù)值是不斷降低的,則只有C點為局部極小,如圖1(b)所示。這也說明了離散變量優(yōu)化問題與連續(xù)變量優(yōu)化問題的不同，即離散變量極小點只比較周圍單位步長空間內的點,而連續(xù)變量極小點則要比較周圍空間的所有點。

定理 1對于離散變量優(yōu)化問題,如果邊際優(yōu)化搜索在可行點A的周圍單位步長空間內均找不到更好的解,則點A可看作一個局部極小點。

根據(jù)定義3,即可得出定理1。

從圖1可以看出,根據(jù)定義3,E點為1個局部極小,C點為另一個局部極小。當搜索起點為D,H,G時,將搜索得到E點,而當搜索起點為A,B,I,F時,將搜索得到C點。比如,以A為搜索起點,經(jīng)過路線A→B→C,搜索得到局部極小點C;以I為搜索起點,經(jīng)過路線I→F→C,搜索得到局部極小點C;以G為搜索起點,經(jīng)過路線G→H→E,搜索得到局部極小點E。

推論 1(收斂性) 對于離散變量優(yōu)化問題,給定足夠的搜索步數(shù),邊際優(yōu)化搜索一定能夠找到局部極小點。

證明由于邊際優(yōu)化搜索總是朝著使得目標函數(shù)值f(x)下降最多的方向,以等步長均勻下降,則可能存在兩種情形:一種對應于圖2中的A5點,該點為局部極小值點,其以A1點為初始點,經(jīng)過等步長搜索:A1→A2→A3→A4→A5得到?？梢钥吹?當搜索到A5點時,比較周圍鄰近的可行點A4和A6,都大于A5點，因此停止搜索,得到一個局部極小點A5。另一種對應于圖2中的B6點,其以B1點為初始點,經(jīng)過等步長搜索:B1→B2→B3→B4→B5→B6得到,假設B6點位于邊界上,則其也可看作一個局部極小。這是由離散變量優(yōu)化的邊界點必然也是離散值決定的,比如假設步長為1,B5點為x=4時,邊界點B6點只可能為x=5,而不可能為x=4.4(因為不到1個步長)。由于邊界點B6也可看作局部極小,且B6小于周圍鄰近的可行點B5,因此停止搜索,得到一個邊界局部極小。所以,以上兩種情況下,邊際優(yōu)化搜索均能搜索得到局部極小點。

證畢

圖2 邊際優(yōu)化搜索算法尋找局部極小點示意圖Fig.2 Schematic diagram of marginal optimization search algorithm for finding local minimum point

事實上,離散變量優(yōu)化問題的離散特點以及非線性約束條件,決定了離散變量優(yōu)化相比連續(xù)變量存在更多的局部最優(yōu)點。因此,設計有效的算法跳出局部最優(yōu)點非常重要。研究發(fā)現(xiàn),很多文獻的結論都陷入局部最優(yōu)[4-5,16-17],詳見本文例2和例3。其中,文獻[16]采取傳統(tǒng)邊際優(yōu)化法得到的解為一個局部最優(yōu)解(4, 7, 5, 4),對應系統(tǒng)可靠度為0.996 7,本文方法得到的最優(yōu)解為(5, 6, 5, 4),對應系統(tǒng)可靠度為0.997 47。說明傳統(tǒng)的邊際優(yōu)化法、遺傳算法等在解決離散變量優(yōu)化問題上容易陷入局部最優(yōu)。這也是本文算法的設計初衷。

推論 2(唯一性) 對于離散變量優(yōu)化問題,一個初始點經(jīng)過邊際優(yōu)化搜索只能得到一個局部極小點,且搜索路徑唯一。

證明根據(jù)定義2,從初始點開始,單步邊際優(yōu)化搜索的路線是唯一的,找到的單步邊際優(yōu)化點也是唯一的,則執(zhí)行多次單步邊際優(yōu)化搜索直到找到局部極小,整個搜索路線也是唯一的。因此也只能得到唯一的一個局部極小點。

證畢

離散變量優(yōu)化的邊際優(yōu)化搜索算法,與連續(xù)變量優(yōu)化的模式搜索算法[14]不同。模式搜索算法由于搜索步長會根據(jù)搜索效果發(fā)生變化,因此可能漏掉局部極值點。同時,連續(xù)變量優(yōu)化可能產生邊界噪聲點[14],而非局部極小。但對于離散變量優(yōu)化,邊際優(yōu)化搜索找到的邊界極小點必然是局部極小點,這在推論1中已進行了說明。

整個搜索過程,可以想象成1個n維的球體在離散空間滾動,每次滾動1個單位步長,且總是朝著最低的方向(即目標函數(shù)值最小)持續(xù)滾動,直到達到1個局部極小點,球體停止?jié)L動。

2 基于邊際優(yōu)化的離散變量優(yōu)化算法設計

2.1 傳統(tǒng)邊際優(yōu)化

邊際效應分析理論是當代經(jīng)濟學理論中的基礎方法之一。該理論認為市場上一個商品的價值不是由最初的效用決定的,也不是由平均效用決定,而是由人們使用的最后一個單位商品的效用——邊際效用決定的,把這種通過比較邊際效用進行優(yōu)化的方法,稱為邊際優(yōu)化法。除了在經(jīng)濟學領域的應用,邊際優(yōu)化法還被廣泛應用于備件庫存的最優(yōu)決策[18-19]、可靠性分配問題[16]、層次分析法(analytic hierarchy process, AHP)優(yōu)化決策[20]等。

傳統(tǒng)邊際優(yōu)化法的基本思想是:假設變量的維數(shù)為n,初始值為所有變量的下界值組成。假設初始值為x0=(0,0,…,0),從x0開始,每次只對1個變量增加1,得到n個新解,即{(1,0,…,0), (0,1,…,0), …, (0,0,…,1)}。比較這些新解的收益增量Δf與資源耗費的增量Δc的比值,比值最大說明增加該變量帶來的邊際效費比最大。因此,選擇對該變量增加1。按照此方法不斷迭代,直到資源耗費達到規(guī)定值。該方法能夠實現(xiàn)一定資源約束條件下的收益值最大化。

2.2 改進邊際搜索算法

借鑒傳統(tǒng)邊際優(yōu)化的思想,針對離散變量優(yōu)化問題,做以下改進。

一是初始點不是選擇所有變量的下界值,而是隨機生成一個可行解。這和離散變量優(yōu)化問題的特點是相關的:對于一個離散變量優(yōu)化問題,所有變量的下界值組成的解不一定為可行解(即約束條件可能不滿足,見例1);同時,可能存在很多的局部極小,而不是像備件庫存的最優(yōu)決策[18-19]等問題中只有1個最優(yōu)解(因為備件數(shù)量越多,目標函數(shù)值——滿足率必然越大,不會減小)。根據(jù)定理1,1個初始點只能搜索得到1個局部最優(yōu),故需要多個隨機的初始可行解才能得到全部局部最優(yōu),從而找到最優(yōu)解。因此,設置變異操作生成初始解,以跳出局部極小(詳見第2.3節(jié))。

二是邊際增量不是每次增加1,而是增加或減少1個單位步長(取決于離散變量的步長間隔)。這是由初始點選擇的隨機性決定的,因為局部最優(yōu)點可能位于初始點的增量方向,也可能位于減量方向。

三是設置禁忌搜索策略。傳統(tǒng)邊際優(yōu)化因為是從0開始,逐步增加1,不可能出現(xiàn)新搜索點與已搜索點相同的情況。而改進算法需要設置多個初始點進行搜索,為防止與已搜索點重復,對所有搜索過的點進行記錄,并在發(fā)現(xiàn)與已搜點重復時,立即變異,以減少重復搜索。當發(fā)現(xiàn)1個搜索點重復時,根據(jù)推論2,即以該搜索點為起點的剩余搜索路線具有唯一性,若不執(zhí)行變異,則剩余搜索過程將全部是重復搜索。

2.3 變異操作

為防止算法陷入局部極小,同時避免重復搜索,設計變異操作。文獻[21]設計了整數(shù)變量優(yōu)化問題的單點變異方法,由于離散變量優(yōu)化問題一般涉及較多的變量,本文考慮多點變異,變異點的個數(shù)應介于[1,n/2]之間,n為問題的維數(shù)。

同時,為保證變異操作起到變異效果,對于單點變異的情況,改變的元素值應該不屬于周圍單位步長空間內。比如,考慮一個4維離散變量優(yōu)化問題,4個變量可行域均為[1, 5],離散步長分別為(0.1, 0.5, 1, 0.01),對局部極小點x1=(3,1,2,5)進行單點變異。隨機選擇對第3個元素進行變異,則第3個元素將只可能變異為{4, 5}中的一個,因為{1, 3}均在點x1的周圍單位步長空間內。對該問題執(zhí)行單點變異和多點變異操作,如圖3所示。

圖3 變異操作Fig.3 Mutation operation

例如,對于一個確定性函數(shù),假設y1和y2都是整數(shù):

(2)

式中,y1∈[-3 000, 3 000],y2∈[-2 000, 2 000]。

該問題是一個二維的無約束離散變量優(yōu)化問題,搜索過程如圖4所示。

圖4 改進邊際優(yōu)化的尋優(yōu)過程(不同視角的等高線圖)Fig.4 Optimization process of the improved marginal (contour plots from different perspectives)

若初始點為(1 000, 200),設定的搜索次數(shù)為2 000次,則本文算法能夠在第894次搜索時,找到局部極小點:y*=(611,-305),函數(shù)極小值為f(y*)=-0.641 4。此時執(zhí)行一次變異操作,得到第二次搜索的初始點為:y1=(-479,-305),算法經(jīng)過1 091次搜索后,再次找到同一局部極小點y*。從圖4中可以清晰地看到,改進邊際優(yōu)化算法執(zhí)行的兩條搜索路徑均沒有走任何多余的彎路,而是直接找到了局部極小點,實現(xiàn)了問題的最快搜索,而且當找到一個局部極值后,算法執(zhí)行了一次單點變異,完成了兩次不同的搜索。

2.4 算法步驟

步驟 1初始化。在可行域內隨機生成符合條件的初始點x0=[x10,x20,…,xn0],設置最大搜索次數(shù)為N,令j=1,禁忌搜索點集合Ψ=?。

步驟 2判斷是否達到最大搜索次數(shù)。如果j≥N,達到最大搜索次數(shù),輸出找到的極小值xmin和Fmin;否則,進入步驟3。

步驟 3計算邊際值。令離散步長矩陣v為

(3)

式中,vri表示v的第i行向量;di表示變量xi的離散步長。

以初始點x0為中心,分別計算其周邊單位步長各點的目標函數(shù)值,即:

(4)

式中,

式中,x0+vri不可行有兩種原因,一是搜索點超出了邊界,二是搜索點不滿足約束條件。

邊際值為

Δ=[f(x0)-f(x0+vr1),f(x0)-f(x0+vr2),…,
f(x0)-f(x0+vr(2n))]

(5)

步驟 4選擇新的搜索點。如果邊際值Δ中均為負數(shù),根據(jù)定理1,證明該搜索點為一個局部極小點,輸出該極小值點xmin=x0,Fmin=f(x0),同時執(zhí)行變異操作,轉到步驟5,開始新一輪的搜索。否則,邊際值Δ中至少存在1個正數(shù),選擇Δ中最大的正數(shù),不妨假設Δk=maxΔ,判斷如果x0+vrk?Ψ,則選擇點x0+vrk作為下一次搜索的初始點,同時將該點加入禁忌搜索的已搜索點集合Ψ,令x0=x0+vrk,j=j+1,轉到步驟2;否則,如果x0+vrk∈Ψ,證明該新搜索點在之前的搜索中出現(xiàn)過,根據(jù)禁忌搜索原理,執(zhí)行變異操作,轉到步驟5。

步驟 5變異操作。按照第2.3節(jié),根據(jù)問題的維數(shù)(即變量的個數(shù)),可選擇需要進行變異的變量數(shù)量,比如單點變異或多點變異。根據(jù)定義1,將變異得到的點xm0進行可行性判斷,若可行,且xm0?Ψ,則將其作為新的初始點,令x0=xm0,轉到步驟3;否則,重新執(zhí)行變異操作步驟5,直到得到可行的新初始點。

3 實例分析

例1考慮以下二維離散變量優(yōu)化問題:

(6)

式中,x1是0.25的整數(shù)倍,x2是0.1的整數(shù)倍,且x1∈[-50, 50],x2∈[3, 20]。

假設隨機生成的可行初始點A1為x0=[3, 6],則g1(X)=-14,g2(X)=0,因此為可行解。搜索過程如表1所示,其中*表示邊際值最大的變量。搜索路徑如圖5所示。從圖5可以看出,該問題如果以A1點作為初始點,只需要14次迭代,按照圖5中的路徑A1-C-B就可以找到最優(yōu)解B點:Xmin=(4, 5),f(Xmin)=-57。完成一次搜索后,算法將執(zhí)行變異,經(jīng)過單點變異得到A2點作為第2次搜索的初始點xA2=[4, 6.4],則算法將按照圖5中路徑A2-D,找到D點,xD=[4, 5.7],此時再進行1次邊際搜索,將會與第1次搜索路徑上的C點重復(xC=[4, 5.6]),若繼續(xù)搜索則余下的搜索將按照路徑C-B執(zhí)行,顯然發(fā)生了重復搜索(重復次數(shù)達7次)。因此,根據(jù)第2.4節(jié)中步驟4的禁忌搜索策略,搜索到D點時將不再繼續(xù)搜索,而是執(zhí)行變異,開始另一次尋優(yōu)。

表1 改進邊際搜索算法的逐步搜索過程

圖5 改進邊際優(yōu)化的尋優(yōu)路徑Fig.5 Optimization path for improved marginal optimization

對于該問題,如果按照傳統(tǒng)邊際優(yōu)化,從變量的下界開始搜索,即x0=[-50, 3],該初始點為不可行點,式(3)中兩個約束不等式均不滿足。初始點不可行,則無法計算邊際值,算法將無法繼續(xù)執(zhí)行。

例 2考慮以下減速器體積優(yōu)化設計問題[2,4-5,22],該問題為一個6維的離散變量優(yōu)化問題:

(7)

式中,x1表示齒輪的寬度,x1∈[10, 20],取整數(shù);x2表示小齒輪的齒數(shù),x2∈[17, 30],取整數(shù);x3表示齒輪的模數(shù),x3∈[0.2, 1],要求精確到小數(shù)點后1位;x4表示減速器箱體的寬度,x4∈[20, 25],要求精確到小數(shù)點后2位;x5和x6表示軸的直徑,x5∈[10, 15],x6∈[13, 20],均取整數(shù)。

改進邊際搜索在運行100次的情況下,目標函數(shù)值的變化如圖6所示。從圖6可以看出,對于離散變量優(yōu)化問題,改進邊際優(yōu)化算法可以持續(xù)降低目標函數(shù)值,當達到某個局部極小點(對應目標函數(shù)值為30 622),此時無法繼續(xù)減小,算法執(zhí)行變異操作,跳出局部極小,開始新一輪的尋優(yōu)。本例中,發(fā)生了一次變異,從圖6也可看出,變異后目標函數(shù)值發(fā)生跳躍式增大。經(jīng)過多次試驗,算法不僅找到了全局最優(yōu)方案,也找到了幾個相對滿意的局部最優(yōu)方案,如表2所示。

圖6 改進邊際優(yōu)化的目標函數(shù)值變化趨勢圖Fig.6 Change trend chart of objective function value for improved marginal optimization

表2 所提方法找到的局部極小與文獻的對比

文獻[4]找到局部極小為:xm1=[13, 24, 0.6, 23.75, 10, 13],f(xm1)=30 675。對其進行檢驗，在其周圍單位步長空間內,容易找到點xa=[13, 24, 0.6, 23.74, 10, 13],f(xa)=30 673,由于f(xa)

文獻[5]找到局部極小為xm2=[14, 23, 0.6, 29.33, 12, 13],f(xm2)=33 540。對其進行檢驗,發(fā)現(xiàn)其周圍單位步長空間內無更小的點,因此,該點為一個局部極小點。但顯然該點的目標函數(shù)值過大,不能視為滿意解。文獻[22]的局部極小為xm3=[13, 19, 0.9, 23.6, 10, 13],f(xm3)=40 459,經(jīng)驗證,該點實際為不可行點,因為約束條件g2(X)不滿足,如表2所示。文獻[2]找到了全局最小點xm4,與本文方法得到的最優(yōu)解一致。但是,本文還找到了幾個次優(yōu)的局部極小解,可作為備選優(yōu)化方案。由于局部極小的搜索路徑上的點都可作為初始點,故初始點不唯一,實驗中5組解的初始點分別為xa1的初始點為[13, 24, 0.6, 24.61, 14, 13],經(jīng)過116次搜索得到;xa2的初始點為[14, 23, 0.7, 24.86, 10, 13],經(jīng)過38次搜索得到;xa3的初始點為[12, 27, 0.6, 23.63, 14, 13],經(jīng)過119次搜索得到;xa4的初始點為[12, 30, 0.6, 24.53, 12, 16],經(jīng)過312次搜索得到;xa5的初始點為[13, 22, 0.7, 24.93, 10, 14],經(jīng)過246次搜索得到。

如果按照連續(xù)變量優(yōu)化問題求解,利用Matlab自帶的fmincon函數(shù)可以很快找到最優(yōu)解,即最優(yōu)目標函數(shù)值為29 476,最優(yōu)解為(10.577, 23.858, 0.661 1, 21.077, 10, 13)。該連續(xù)解若經(jīng)過四舍五入法圓整處理,得到鄰近的離散解為(11, 24, 0.7, 21.08, 10, 13),代入約束式g1(X)～g10(X),得到該點為可行點,同時對應的目標函數(shù)值為32 622,可見明顯大于本文找到的最優(yōu)解,故用圓整法往往只能得到非最優(yōu)解或不可行解。通過與文獻的對比可見,本文算法具有以下優(yōu)點。

(1) 能夠保證算法的收斂性。通過對比文獻[4]發(fā)現(xiàn),遺傳算法往往能夠找到滿意解,但是不一定是局部極小,即使找到的解在局部極小附近,也難以發(fā)現(xiàn)局部極小。這是由于遺傳算法的搜索原理決定的,而根據(jù)定理1,本文算法一定能夠得到局部極小。

(2) 目標函數(shù)測算次數(shù)盡可能少。相比各種啟發(fā)式算法,改進邊際搜索算法所需的目標函數(shù)測算次數(shù)相對較少,且根據(jù)推論2,每個初始點的邊際搜索路徑唯一,因此在算法中引入了禁忌搜索策略。一旦出現(xiàn)已搜索路徑上的點,即執(zhí)行變異操作,避免了大量的重復路徑搜索過程。

(3) 本文算法原理簡單,容易實現(xiàn),且專門針對離散變量優(yōu)化問題設計,適用性強。對于非整數(shù)的離散變量優(yōu)化問題無需轉化為整數(shù)優(yōu)化,可直接用離散步長進行搜索實現(xiàn)。

例 3考慮以下齒輪減速器的可靠性優(yōu)化設計問題[2,17],為一個4維離散變量優(yōu)化問題:

(8)

式中,x1表示法向模數(shù),x1∈[2, 20],取整數(shù);x2表示小齒輪數(shù),x2∈[17, 50],取整數(shù);x3表示螺旋角,x3∈[0.6, 1.2],要求精確到小數(shù)點后2位;x4表示齒寬系數(shù),x4∈[6, 20],取整數(shù);r表示傳動比,本文取5。

如表3所示,文獻[2]利用改進遺傳算法、文獻[17]利用圓整法,找到局部極小分別為xm1=xm2=[2, 17, 0.96, 6],f(xm1)=106.231。應用定理1對其進行檢驗,該點為一個局部極小點。而本文算法則找到了更好的最優(yōu)解[2, 17, 0.97, 19],目標函數(shù)值為103.165。與例2類似,算法還找到了幾個全局最優(yōu)解(見表3)。實驗中4組解的初始點(不唯一)分別為:xa1的初始點為[2, 28, 0.97, 18],經(jīng)過13次搜索得到;xa2的初始點為[3, 41, 1.12, 19],經(jīng)過26次搜索得到;xa3的初始點為[2, 48, 0.95, 20],經(jīng)過33次搜索得到;xa4的初始點為[19, 29, 1.02, 20],經(jīng)過31次搜索得到。

表3 例3實驗結果對比

由于目標函數(shù)中不包含x3,因此改變x3能夠帶來的邊際增量始終為0,算法將始終不會對其進行改變。故當最優(yōu)解中x3取其他值時,必然還可找到更多解,其余解不再一一列舉。

例 4考慮以下離散變量優(yōu)化問題[23-24],其維度n可根據(jù)需要設定:

minf(X)=(x1-1)2+(xn-1)2+

s.t. -5≤xk≤5,k=1,2,…,n

(9)

式中,xk取整數(shù)。

該問題是一個無約束的非線性整數(shù)規(guī)劃問題,常用于測試優(yōu)化算法在高維度情況下的運行效果。其有11n個可行點和許多局部極小值[24],但只有一個全局極小值解:xmin=[1, 1, …, 1],對應目標函數(shù)值為f(xmin)=0。

本文采取隨機初始值的方法,分別在n為25, 50, 100的情況下進行了10次試驗,均找到了全局最優(yōu)解,結果如表4所示。其中,FN表示算法找到最優(yōu)解時目標函數(shù)的計算次數(shù),分別給出了最少、最多和平均次數(shù);T表示算法找到最優(yōu)解時的CPU用時(為與文獻比較,僅給出了最長的一次用時)。

表4 例4實驗結果對比

通過對比發(fā)現(xiàn),本文算法找到最優(yōu)解時所需的FN和T的最大值均明顯少于文獻[24]。對于n=50的情形,文獻[24]以更少的FN得出了最優(yōu)解,甚至比n=25的情況下還少。這是因為n=50時,所選擇的初始點剛好能夠很快收斂到全局最優(yōu),而如果隨機選擇初始點時,文獻[24]可能需要更多的迭代次數(shù)才能收斂到全局最優(yōu)。另外,文獻[24]是在指定初始點的情況下得到的結果,本文則是在隨機初始點情況下的結果。通過反復實驗發(fā)現(xiàn),對于高維度問題,除非初始點剛好能夠一次收斂到全局最優(yōu),本文算法對于初始點的選擇以及變異點數(shù)(采取單點變異或多點變異)的影響不大。

這里給出一次實驗的運行結果:當n=100時,采取3點變異,在2 000次迭代的情況下,目標函數(shù)值的變化如圖7(a)所示,整個過程共發(fā)生143次變異,實際進行了1 857步搜索。如圖7(b)所示,第1次搜索在第423次迭代時,找到局部極值點,x1=[0, 0, …, 0],對應f(x1)=2;在第797次迭代時,找到第2個局部極值點,x2=[1, 1, …, 1],對應f(x2)=0,為本問題的全局最優(yōu)解;在第1 212次迭代時,找到第3個局部極值點,x3=[-1, 1, 1, …, 1],對應f(x3)=4。除以上2次有效變異,其余的141次變異均因禁忌搜索策略而中止搜索。

圖7 目標函數(shù)值變化趨勢圖Fig.7 Change trend chart of objective function value

4 結 論

本文針對離散變量優(yōu)化問題的特點,設計了基于改進邊際優(yōu)化的搜索算法,為保證搜索效率,設置了變異操作和禁忌搜索策略,以實現(xiàn)通過最少的迭代次數(shù)得到更多的局部最優(yōu)解,從而找到問題的最優(yōu)解或滿意解。算法借鑒了傳統(tǒng)邊際優(yōu)化和模式搜索算法的原理,相比傳統(tǒng)邊際優(yōu)化,本文算法選擇初始點更為靈活,不需要從所有變量的下界開始搜索,且搜索方向不僅是邊際增量方向,也包括邊際減量方向,從而保證最快速度落入局部極小點。相比模式搜索算法,由于選取的步長為離散變量的單位步長,可避免出現(xiàn)模式搜索因搜索步長過大而漏掉搜索區(qū)域內的局部極小點,以及搜索到假的局部極小點的問題。

對于離散變量優(yōu)化問題,本文證明了改進邊際搜索具有收斂性和路徑唯一性的特點,對于保證解的質量、提高求解效率具有重要意義。因此,本文算法特別適用于目標函數(shù)為黑箱模型、仿真模型以及高維離散變量優(yōu)化問題。下一步,考慮研究邊際優(yōu)化算法與其他算法的混合使用,主要從初始點的選擇策略、變異調整策略、禁忌搜索策略等角度開展深入研究,以進一步提高復雜高維離散變量優(yōu)化問題的求解效率。