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

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

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

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

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

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