吳詩(shī)輝, 李正欣, 劉曉東, 周 宇, 賀 波

(空軍工程大學(xué)裝備管理與無(wú)人機(jī)工程學(xué)院, 陜西 西安 710051)

0 引 言

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

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

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

1 基本原理

離散變量?jī)?yōu)化問(wèn)題可描述為

(1)

式中,XD為離散空間。

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

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

圖1 邊際搜索與單位步長(zhǎng)Fig.1 Marginal search and unit step

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

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

定義 3對(duì)于離散變量?jī)?yōu)化問(wèn)題,稱點(diǎn)A為一個(gè)局部極小點(diǎn),當(dāng)且僅當(dāng)A在其周圍單位步長(zhǎng)空間Ω(A)內(nèi)目標(biāo)函數(shù)值最小時(shí)。

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

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

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

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

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

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

證畢

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

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

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

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

證畢

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

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

2 基于邊際優(yōu)化的離散變量?jī)?yōu)化算法設(shè)計(jì)

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

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

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

2.2 改進(jìn)邊際搜索算法

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

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

二是邊際增量不是每次增加1,而是增加或減少1個(gè)單位步長(zhǎng)(取決于離散變量的步長(zhǎng)間隔)。這是由初始點(diǎn)選擇的隨機(jī)性決定的,因?yàn)榫植孔顑?yōu)點(diǎn)可能位于初始點(diǎn)的增量方向,也可能位于減量方向。

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

2.3 變異操作

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

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

圖3 變異操作Fig.3 Mutation operation

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

(2)

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

該問(wèn)題是一個(gè)二維的無(wú)約束離散變量?jī)?yōu)化問(wèn)題,搜索過(guò)程如圖4所示。

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

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

2.4 算法步驟

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

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

步驟 3計(jì)算邊際值。令離散步長(zhǎng)矩陣v為

(3)

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

以初始點(diǎn)x0為中心,分別計(jì)算其周邊單位步長(zhǎng)各點(diǎn)的目標(biāo)函數(shù)值,即:

(4)

式中,

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

邊際值為

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

(5)

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

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

3 實(shí)例分析

例1考慮以下二維離散變量?jī)?yōu)化問(wèn)題:

(6)

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

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

表1 改進(jìn)邊際搜索算法的逐步搜索過(guò)程

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

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

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

(7)

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

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

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

表2 所提方法找到的局部極小與文獻(xiàn)的對(duì)比

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

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

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

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

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

(3) 本文算法原理簡(jiǎn)單,容易實(shí)現(xiàn),且專門針對(duì)離散變量?jī)?yōu)化問(wèn)題設(shè)計(jì),適用性強(qiáng)。對(duì)于非整數(shù)的離散變量?jī)?yōu)化問(wèn)題無(wú)需轉(zhuǎn)化為整數(shù)優(yōu)化,可直接用離散步長(zhǎng)進(jìn)行搜索實(shí)現(xiàn)。

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

(8)

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

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

表3 例3實(shí)驗(yàn)結(jié)果對(duì)比

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

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

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

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

(9)

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

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

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

表4 例4實(shí)驗(yàn)結(jié)果對(duì)比

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

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

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

4 結(jié) 論

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

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