基于改進邊際優化的離散變量優化設計算法

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

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

0 引 言

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

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

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

1 基本原理

離散變量優化問題可描述為

(1)

式中,XD為離散空間。

定義 1對于離散變量優化問題,稱點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為半徑的圓上。由于單位步長空間每次僅改變單個元素,通過增加或減少單位步長得到,因此單位步長空間包含點的個數為2n,n表示維數。

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

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

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

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

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

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

根據定義3,即可得出定理1。

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

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

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

證畢

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

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

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

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

證畢

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

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

2 基于邊際優化的離散變量優化算法設計

2.1 傳統邊際優化

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

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

2.2 改進邊際搜索算法

借鑒傳統邊際優化的思想,針對離散變量優化問題,做以下改進。

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

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

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

2.3 變異操作

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

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

圖3 變異操作Fig.3 Mutation operation

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

(2)

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

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

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

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

2.4 算法步驟

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

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

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

(3)

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

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

(4)

式中,

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

邊際值為

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

(5)

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

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

3 實例分析

例1考慮以下二維離散變量優化問題:

(6)

式中,x1是0.25的整數倍,x2是0.1的整數倍,且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就可以找到最優解B點:Xmin=(4, 5),f(Xmin)=-57。完成一次搜索后,算法將執行變異,經過單點變異得到A2點作為第2次搜索的初始點xA2=[4, 6.4],則算法將按照圖5中路徑A2-D,找到D點,xD=[4, 5.7],此時再進行1次邊際搜索,將會與第1次搜索路徑上的C點重復(xC=[4, 5.6]),若繼續搜索則余下的搜索將按照路徑C-B執行,顯然發生了重復搜索(重復次數達7次)。因此,根據第2.4節中步驟4的禁忌搜索策略,搜索到D點時將不再繼續搜索,而是執行變異,開始另一次尋優。

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

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

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

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

(7)

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

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

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

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

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

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

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

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

(8)

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

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

表3 例3實驗結果對比

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

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

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

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

(9)

式中,xk取整數。

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

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

表4 例4實驗結果對比

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

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

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

4 結 論

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

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