實(shí)現(xiàn)全局優(yōu)化的支撐區(qū)域水平集算法.pdf

1、在科學(xué)，工程，管理，經(jīng)濟(jì)，軍事等領(lǐng)域存在著大量的優(yōu)化問(wèn)題，許多科學(xué)與工程中的實(shí)際問(wèn)題，也可以轉(zhuǎn)化為優(yōu)化問(wèn)題．這些問(wèn)題用傳統(tǒng)的確定性方法難以有效地求全局最優(yōu)解．近一、二十年來(lái)，全局優(yōu)化的研究成為熱點(diǎn)領(lǐng)域之一，很多研究者提出了各類方法，其中一些隨機(jī)性方法具有對(duì)目標(biāo)函數(shù)性質(zhì)要求低，簡(jiǎn)單直觀，計(jì)算穩(wěn)定性好的特點(diǎn)，從而得到了廣泛的關(guān)注． 本文提出了一個(gè)新的基于水平集的全局優(yōu)化算法—支撐區(qū)域水平集方法（SupportArea Level S

2、et Algorithm，SALSA），并給出了一個(gè)新的概念算法及其收斂性證明，同時(shí)在實(shí)現(xiàn)算法中針對(duì)求解全局優(yōu)化問(wèn)題的一類水平集方法實(shí)現(xiàn)困難、容易遺漏全局極值點(diǎn)等問(wèn)題提出了一套行之有效的解決方案．首先本文就一類水平集方法的研究現(xiàn)狀進(jìn)行了歸納，分析，列舉了一些主要的方法，其中包括鄭權(quán)的積分水平集算法，張連生等的離散均值水平集算法等．由于該類方法需要得到水平集，并且對(duì)目標(biāo)函數(shù)在水平集上進(jìn)行積分，但在實(shí)現(xiàn)過(guò)程中，水平集往往難以得到，積分更是困

3、難．很多學(xué)者就此進(jìn)行了研究，提出了很多替代水平集的方法，并取得了不錯(cuò)的效果，這些方法包括閉箱法，變側(cè)度子箱法等，它們都是利用規(guī)則的區(qū)域來(lái)逼近不規(guī)則分布的真實(shí)水平集，故在逼近程度上難以提高．本文采用了不同的思路，基于統(tǒng)計(jì)學(xué)習(xí)的方法，借助支持向量機(jī)可以對(duì)不規(guī)則分布區(qū)域進(jìn)行有效估計(jì)的特點(diǎn)，將水平集估計(jì)問(wèn)題轉(zhuǎn)化為單一的一類樣本集的識(shí)別問(wèn)題．具體來(lái)說(shuō)就是，將隨機(jī)采樣得到的位于水平集內(nèi)的樣本點(diǎn)視為單一的一類樣本集，利用它們訓(xùn)練支持向量機(jī)得到的判別函

4、數(shù)來(lái)獲得對(duì)真實(shí)水平集的近似估計(jì)． 由于訓(xùn)練支持向量機(jī)的過(guò)程實(shí)際上是一個(gè)求解帶線性約束的二次規(guī)劃問(wèn)題，該問(wèn)題的變量與訓(xùn)練樣本的數(shù)目相等，這樣本文提出的算法便將復(fù)雜的水平集估計(jì)問(wèn)題轉(zhuǎn)化為求解一個(gè)二次規(guī)劃問(wèn)題，通常只需較小的計(jì)算代價(jià)． 然而由于單純利用判別函數(shù)估計(jì)水平集仍存在以下兩點(diǎn)不足：一，估計(jì)水平集（支撐區(qū)域）邊界分明，若其無(wú)法完全覆蓋真實(shí)水平集將導(dǎo)致全局極值點(diǎn)的遺漏，最終算法將無(wú)法收斂到全局最優(yōu)解；二，利用判別函數(shù)進(jìn)行判

5、斷同樣需要計(jì)算時(shí)間和空間．基于以上分析，本文通過(guò)利用支撐區(qū)域內(nèi)的支持向量（Support Vector，SV）創(chuàng)造性地提出了區(qū)別于前人方法的隨機(jī)投點(diǎn)策略．該方法具有以下兩個(gè)優(yōu)點(diǎn)：一，有效結(jié)合了支撐區(qū)域?qū)φ鎸?shí)水平集的估計(jì)結(jié)果，保證了為下一步迭代所投放的采樣點(diǎn)能夠有效集中于估計(jì)水平集內(nèi)，提高了有效采樣點(diǎn)的比重，同時(shí)該方法對(duì)于一些特殊的不規(guī)則水平集分布具有自適應(yīng)的特點(diǎn)；二，按照特定分布隨機(jī)投點(diǎn)，允許跨越支撐區(qū)域邊界投放采樣點(diǎn)，使得遺漏全局極值