全局最優解演算法

① 請大神解釋一下在醫學圖像配准中，什麼叫做局部優化演算法，什麼叫做全局優化演算法

演算法GA把問題的解表示成「染色體」，在演算法中也即是以二進制編碼的串。並且，在執行遺傳演算法之前，給出一群「染色體」，也即是假設解。然後，把這些假設解置於問題的「環境」中，並按適者生存的原則，從中選擇出較適應環境的「染色體」進行復制，再通過交叉，變異過程產生更適應環境的新一代「染色體」群。這樣，一代一代地進化，最後就會收斂到最適應環境的一個「染色體」上，它就是問題的最優解。
一、遺傳演算法的目的
典型的遺傳演算法CGA(Canonical Genetic Algorithm)通常用於解決下面這一類的靜態最優化問題：
考慮對於一群長度為L的二進制編碼bi，i＝1，2，…，n；有
bi∈{0,1}L (3-84)
給定目標函數f，有f(bi)，並且
0<f(bi)<∞
同時
f(bi)≠f(bi+1)
求滿足下式
max{f(bi)|bi∈{0,1}L} (3-85)
的bi。
很明顯，遺傳演算法是一種最優化方法，它通過進化和遺傳機理，從給出的原始解群中，不斷進化產生新的解，最後收斂到一個特定的串bi處，即求出最優解。
二、遺傳演算法的基本原理
長度為L的n個二進制串bi(i＝1，2，…，n)組成了遺傳演算法的初解群，也稱為初始群體。在每個串中，每個二進制位就是個體染色體的基因。根據進化術語，對群體執行的操作有三種：
1．選擇(Selection)
這是從群體中選擇出較適應環境的個體。這些選中的個體用於繁殖下一代。故有時也稱這一操作為再生(Reproction)。由於在選擇用於繁殖下一代的個體時，是根據個體對環境的適應度而決定其繁殖量的，故而有時也稱為非均勻再生(differential reproction)。
2．交叉(Crossover)
這是在選中用於繁殖下一代的個體中，對兩個不同的個體的相同位置的基因進行交換，從而產生新的個體。
3．變異(Mutation)
這是在選中的個體中，對個體中的某些基因執行異向轉化。在串bi中，如果某位基因為1，產生變異時就是把它變成0；反亦反之。
遺傳演算法的原理可以簡要給出如下：
choose an intial population
determine the fitness of each indivial
perform selection
repeat
perform crossover
perform mutation
determine the fitness of each indivial
perform selection
until some stopping criterion applies
這里所指的某種結束准則一般是指個體的適應度達到給定的閥值；或者個體的適應度的變化率為零。
三、遺傳演算法的步驟和意義
1．初始化
選擇一個群體，即選擇一個串或個體的集合bi，i=1，2，...n。這個初始的群體也就是問題假設解的集合。一般取n＝30-160。
通常以隨機方法產生串或個體的集合bi,i＝1，2，...n。問題的最優解將通過這些初始假設解進化而求出。
2．選擇
根據適者生存原則選擇下一代的個體。在選擇時，以適應度為選擇原則。適應度准則體現了適者生存，不適應者淘汰的自然法則。
給出目標函數f，則f(bi)稱為個體bi的適應度。以

(3-86)
為選中bi為下一代個體的次數。
顯然．從式(3—86)可知：
(1)適應度較高的個體，繁殖下一代的數目較多。
(2)適應度較小的個體，繁殖下一代的數目較少；甚至被淘汰。
這樣，就產生了對環境適應能力較強的後代。對於問題求解角度來講，就是選擇出和最優解較接近的中間解。
3．交叉
對於選中用於繁殖下一代的個體，隨機地選擇兩個個體的相同位置，按交叉概率P。在選中的位置實行交換。這個過程反映了隨機信息交換；目的在於產生新的基因組合，也即產生新的個體。交叉時，可實行單點交叉或多點交叉。
例如有個體
S1=100101
S2=010111
選擇它們的左邊3位進行交叉操作，則有
S1=010101
S2=100111
一般而言，交叉幌宰P。取值為0.25—0.75。
4．變異
根據生物遺傳中基因變異的原理，以變異概率Pm對某些個體的某些位執行變異。在變異時，對執行變異的串的對應位求反，即把1變為0，把0變為1。變異概率Pm與生物變異極小的情況一致，所以，Pm的取值較小，一般取0.01-0.2。
例如有個體S＝101011。
對其的第1，4位置的基因進行變異，則有
S'=001111
單靠變異不能在求解中得到好處。但是，它能保證演算法過程不會產生無法進化的單一群體。因為在所有的個體一樣時，交叉是無法產生新的個體的，這時只能靠變異產生新的個體。也就是說，變異增加了全局優化的特質。
5．全局最優收斂(Convergence to the global optimum)
當最優個體的適應度達到給定的閥值，或者最優個體的適應度和群體適應度不再上升時，則演算法的迭代過程收斂、演算法結束。否則，用經過選擇、交叉、變異所得到的新一代群體取代上一代群體，並返回到第2步即選擇操作處繼續循環執行。
圖3—7中表示了遺傳演算法的執行過程。

② 線性規劃(LP)基本概念和搜索演算法

可以用一個符號描述一系列類似的數量值

一個方程，如果他是關於決策變數的常熟加權求和形式，則該方程式 線性方程(liner) ，佛則該方程為 非線性方程(non-linear)

目標函數 以及約束方程 中均為關於決策變數的線性方程，則該優化模型為 線性規劃(linear program, LP) ，其中目標函數可以為滿足約束的任意整數或者分數

目標函數 以及約束方程 中存在關於決策變數的線性方程，則該優化模型為 非線性規劃(nonlinear program, LP) ，其中目標函數可以為滿足約束的任意整數或者分數

一個優化模型，如果他的決策變數中存在離散變數，則該優化模型位 整數規劃(integer program, IP) ，如果整數規劃的所有決策變數均為離散變數，則該整數規劃為 純整數規劃(pure integer program) ；否則為 混合整數規劃(mixed integer program) 。

搜索演算法(improving search) 通過檢查鄰域來尋找比當前更好地解，若有改進則替換當前解，繼續迭代，直到鄰域中沒有更好的解為止。搜索演算法又稱為 局部改進(local improvement) ， 爬山演算法(hillclimbing) ， 局部搜索(local search) 或 鄰域搜索(neighborhood search)

倘若一組可行解周圍足夠小的的鄰域內沒有優於該解的可行點，則稱為 局部最優解(local optimum) ，最小化(最大化)問題存在 局部最小(最大)解 。

如果在全局范圍內不存在目標值優於某可行解的其他可行點，則稱為 全局最優解(global optimum) ，最小化(最大化)問題存在 全局最小(最大)解

搜索演算法沿 由當前點 向下一個搜索點 移動，其中 是當前點 處的 搜索方向(move direction) ， 是沿該方向前進的 步長 ， 。

對於所有足夠小的 都有 ,則稱 是當前解的一個 改進方向(improving direction) ,如果滿足所有約束條件，則為 可行改進方向 。

如果優化模型的目標函數 是光滑的(所有決策變數都是可微的)，那麼，當 是一個n維向量的函數，當它有一個一階片倒數，這些導數組成的n維向量稱為 梯度

導數(derivative) ，描述函數隨參數的變化率，可以看做斜率。 偏導數(partial derivative) ，是保持其他變數恆定時，關於其中一個變數的導數

對於最大化目標函數 ,若 ，搜索方向 是 處的可改進方向，若 ，搜索方向 不是 處的可改進方向。

對於最小化目標函數 ,若 ，搜索方向 是 處的可改進方向，若 ，搜索方向 不是 處的可改進方向。

當目標函數梯度 ，是最大化目標 的一個改進方向， 是最小化目標函數 的一個改進方向

如果可行域內任意兩點的連線都在可行域內，則稱該可行域為 凸集 。

離散的可行集總是非凸集

若優化模型的可行集是凸集，那麼對任意可行解始終存在指向另一個解的可行方向，意味著，只要存在最優解，可能性不會阻礙局部最優解發展為全局最優解。

線性約束的可行集又稱為多面體集。

如果優化模型的所有約束都是線性的，那麼該模型的可行域是凸集

兩階段法

大M法

③ 混沌優化演算法可以求解全局最優解嗎

非線性最優化問題的一種混合解法

摘 要：把BFGS方法與混沌優化方法相結合，基於混沌變數提出一種求解具有變數邊界約束非線性最優化問題的混合優化方法。混合演算法兼顧了混沌優化全局搜索能力強和BFGS方法收斂速度快的優點，成為一種求解非凸優化問題全局最優的有效方法。算例表明，當混沌搜索的次數達到一定數量時，混合優化方法可以保證演算法收斂到全局最優解，且計算效率比混沌優化方法有很大提高。

關鍵詞：混合法；BFGS方法；混沌優化方法；全局最優

1 引言
在系統工程、控制工程、統計學、反問題優化求解等領域中，很多問題是具有非凸性的。對此普通的優化技術只能求出局部最優解，因為這些確定性演算法總是解得最近的一個極值點[1]，只有能夠給出很好的初始點才有可能得出所需要的全局最優解。為此，實際應用中通過在多個初始點上使用傳統數值優化方法來求取全局解的方法仍然被人們所採用，但是這種處理方法求得全局解的概率不高，可靠性低，建立盡可能大概率的求解全局解演算法仍然是一個重要問題。近年來基於梯度法的全局最優化方法已經有所研究[2]，基於隨機搜索技術的遺傳演算法和模擬退火演算法等在全局優化問題中的應用也得到越來越大的重視[3-4]。本文則基於混沌優化和BFGS方法，提出一種求解具有簡單界約束最優化問題(1)的混合演算法。
混沌是存在於非線性系統中的一種較為普遍的現象。混沌運動宏觀上無序無律，具有內隨機性、非周期性和局部不穩定性，微觀上有序有律，並不是完全的隨機運動，具有無窮嵌套的自相似幾何結構、存在普適性規律，並不是雜亂無章的。利用混沌變數的隨機性、遍歷性和規律性特點可以進行優化搜索[5]，且混沌優化方法容易跳出局部最優點。但是某些狀態需要很長時間才能達到，如果最優值在這些狀態時，計算時間勢必很長[5]。可以說混沌優化具有全局搜索能力，其局部搜索能力稍顯不足，文[5]採用二次載波技術，文[6]考慮逐漸縮小尋優變數的搜索空間都是為了彌補這一弱點。而本文則採用混沌搜索與BFGS方法進行優化求解，一方面採用混沌搜索幫助BFGS方法跳出局部最優，另一方面利用BFGS增強解附近的超線性收斂速度和搜索能力，以提高搜索最優的效率。
2 混沌－BFGS混合優化方法
2.1 BFGS方法
作為求解無約束最優化問題的擬牛頓方法類最有代表性的演算法之一，BFGS方法處理凸非線性規劃問題，以其完善的數學理論基礎、採用不精確線性搜索時的超線性收斂性和處理實際問題有效性，受到人們的重視[7-9]。擬牛頓方法使用了二階導數信息，但是並不直接計算函數的Hesse矩陣，而是採用一階梯度信息來構造一系列的正定矩陣來逼近Hesse矩陣。BFGS方法求解無約束優化問題min()的主要步驟如下：
(1) 給變數賦初值x0，變數維數n和BFGS方法收斂精度ε，令B0=I（單位陣），k=0，計算在點x0的梯度g0。
(2) 取sk=-Bk-1gk，沿sk作一維搜索，確定最優步長αk，，得新點xk+1=xk+αksk，計算xk+1點的梯度gk+1。
(3) 若||gk+1||≤ε，則令，，BFGS搜索結束，轉步驟3；否則執行(4)。
(4) 計算Bk+1：
(2)
(3)
(5) k=k+1，轉(2)。
2.2 混沌優化方法
利用混沌搜索求解問題(1)時，先建立待求變數與混沌變數的一一對應關系，本文採用。然後,由Logistic映射式(4)產生個軌跡不同的混沌變數（）進行優化搜索，式(4)中=4。已經證明，=4是「單片」混沌，在[0,1]之間歷遍。
(4)
(1)給定最大混沌變數運動次數M；給賦初值，計算和；置，。
(2) 。
(3) 。
(4) 若k<M，
若，令，；
若，和保持不變；
然後令k=k+1，，轉(2)。
若k>M，則，，混沌搜索結束。
2.3 混合優化方法
混沌方法和BFGS方法混合求解連續對象的全局極小值優化問題(1)的步驟如下：
step1 設置混沌搜索的最大次數M，迭代步數iter=0，變數賦初值x0，。
step2 以為始點BFGS搜索，得當前BFGS方法最優解及=。
step3 若，取=；若，取；若，取，是相對於,較小的數。
step 4 以為始點進行混沌搜索M次，得混沌搜索後的最優解及=。
step5 若<，iter=iter+1，，轉step2；否則執行step6。
step6 改變混沌搜索軌跡，再次進行混沌搜索，即給加微小擾動，執行step 4，得搜索結果和。若<，iter=iter+1，，轉step2；否則計算結束，輸出、。
對全局極大值問題，max ，可以轉化為求解全局極小問題min 。
混合演算法中混沌搜索的作用是大范圍宏觀搜索，使得演算法具有全局尋優性能。而BFGS搜索的作用是局部地、細致地進行優化搜索，處理的是小范圍搜索問題和搜索加速問題。
3 算例

圖 1 函數-特性示意圖 圖 2 函數特性示意圖
採用如下兩個非常復雜的、常用於測試遺傳演算法性能的函數測試本文演算法：

函數稱為Camel 函數，該函數有6個局部極小點(1.607105, 0.568651)、(-1.607105, -0.568651)、(1.703607, -0.796084)、(-1.703607, 0.796084)、(-0.0898,0.7126)和(0.0898,-0.7126)，其中(-0.0898,0.7126)和(0.0898,-0.7126)為兩個全局最小點，最小值為-1.031628。函數稱為 Schaffer's函數，該函數有無數個極大值，其中只有（0，0）為全局最大點，最大值為1。此函數的最大峰值周圍有一圈脊，它們的取值均為0.990283，因此很容易停留在此局部極大點。文獻[10]採用該函數對該文提出的基於移動和人工選擇的改進遺傳演算法（GAMAS）其性能進行了考察，運行50次，40％的情況下該函數的唯一全局最優點能夠找到。而採用本文混合演算法，由計算機內部隨機函數自動隨機生產100個不同的初始點，由這些初始點出發，一般混合演算法迭代2－4次即能夠收斂。M取不同數值時對函數、的計算結果分別如表1和表2所示，表中計算時間是指在奔騰133微機上計算時間。
由表2可見，當M=1500時，本文方法搜索到最優解的概率即達到40％，而此時計算量比文獻[10]小。同樣由混合演算法的100個起始點，採用文獻[5]的演算法對函數優化計算100次，以作為收斂標准，混沌搜索50000次，計算結果為67次搜索到最優解，概率為67%，平均計算時間為1.2369s。而即使保證混合演算法100次全收斂到最優解所花費的平均計算時間也只為0.2142s（表1），可見混合演算法優於文獻[5]的方法。
表1 M取不同數值時函數的計算結果
_____________________________________________________________________
M 搜索到全局最優點的次數 搜索到最優的概率 平均計算時間
(-0.0898,0.7126) (0.0898,-0.7126)
_____________________________________________________________________________________________
1000 44 39 83% 0.1214s
3000 53 45 98% 0.1955s
5000 53 47 100% 0.2142s
________________________________________________________________________________________________

表2 M取不同數值時函數的計算結果
___________________________________________________________
M 搜索到全局最優點的次數 搜索到最優的概率 平均計算時間
____________________________________________________________________________________
1500 40 40% 0.1406s
5000 73 73% 0.2505s
10000 88 88% 0.4197s
50000 100 100% 1.6856s
____________________________________________________________________________________

4 計算結果分析
由表1和表2可見，混合演算法全局尋優能力隨M的增加而增大，當M達到某一足夠大的數值Mu後，搜索到全局最優的概率可以達到100％。
從理論上說，Mu趨向無窮大時，才能使混沌變數遍歷所有狀態，才能真正以概率1搜索到最優點。但是，本文混沌運動M次的作用是幫助BFGS方法跳出局部最優點，達到比當前局部最優函數值更小的另一局部最優附近的某一點處，並不是要混沌變數遍歷所有狀態。由混沌運動遍歷特性可知，對於某一具體問題，Mu達到某一具體有限數值時，混沌變數的遍歷性可以得到較好模擬，這一點是可以滿足的，實際算例也證實了這一點。
由於函數性態、復雜性不同，對於不同函數，如這里的測試函數、，數值Mu的大小是有差別的。對於同一函數，搜索區間增大，在相同混沌運動次數下，即使始點相同，總體而言會降低其搜索到全局最優的概率,要保證演算法仍然以概率1收斂到全局最優，必然引起Mu 增大。跟蹤計算中間結果證實，當M足夠大時，混合演算法的確具有跳出局部最優點，繼續向全局最優進行搜索的能力；並且混合演算法的計算時間主要花費在為使混合演算法具有全局搜索能力而進行混沌搜索上。
5 結語
利用混沌變數的運動特點進行優化，具有非常強的跳出局部最優解的能力，該方法與BFGS方法結合使用，在可以接受的計算量下能夠計算得到問題的最優解。實際上，混沌優化可以和一般的下降類演算法結合使用，並非局限於本文採用的BFGS方法。採用的Logistic映射產生混沌變數序列，只是產生混沌變數的有效方式之一。
混沌運動與隨機運動是不同的。混沌是確定性系統中由於內稟隨機性而產生的一種復雜的、貌似無規的運動。混沌並不是無序和紊亂，更像是沒有周期的秩序。與隨機運動相比較，混沌運動可以在各態歷經的假設下，應用統計的數字特徵來描述。並且，混沌運動不重復地經過同一狀態，採用混沌變數進行優化比採用隨機變數進行優化具有優勢。
混沌優化與下降類方法結合使用是有潛力的一種全局優化途徑，是求解具有變數界約束優化問題的可靠方法。如何進一步提高搜索效率，以及如何把混沌優化有效應用於復雜約束優化問題是值得進一步研究的課題。
本文演算法全局收斂性的嚴格數學證明正在進行之中。
參考文獻
[1]胡山鷹，陳丙珍，何小榮，沈靜珠．非線性規劃問題全局優化的模擬退火法[J]．清華大學學報，37(6)，1997，5-9．
[2]C A Floudas, A Aggarwal, A R Ciric． Global optimum search for nonconvex NLP and MINLP problems[J]. Comput Chem Engng． 1989， 13(10)， 1117~1132．
[3]康立山，謝雲，尤矢勇等．非數值並行演算法（第一冊）――模擬退火演算法[M]．北京：科學出版社，1998．
[4]劉勇，康立山，陳琉屏．非數值並行演算法（第二冊）――遺傳演算法[M]．北京：科學出版社，1998．
[5]李兵，蔣慰孫．混沌優化方法及其應用[J]．控制理論與應用，14(4)，1997，613-615．
[6]張彤，王宏偉，王子才．變尺度混沌優化方法及其應用[J]．控制與決策，14(3)，1999，285-287．
[7]席少霖．非線性最優化方法[M]．北京：高等教育出版社，1992．
[8]席少霖，趙鳳志．最優化計算方法[M]．上海：上海科學技術出版社，1983．
[9]Press W H, Tenkolsky S A, Vetterling W T, Flannery B P．Numerical Recipes in C, The Art of Scientific Computing[M]． Second edition， Cambridge University Press， 1992．
[10]J C Ports．The development and evaluation of an improved genetic algorithm based on migration and artificial selection[J]．IEEE Trans. Syst. Man and Cybern.．1994, 24(1)，73-85．
A Hybrid Approach for Nonlinear Optimization
Abstract：Combined BFGS method with chaos optimization method, a hybrid approach was proposed to solve nonlinear optimization problems with boundary restraints of variables. The hybrid method is an effective approach to solve nonconvex optimization problems, as it given both attentions to the inherent virtue to locate global optimum of chaos optimization method and the advantage of high convergence speed of BFGS method. Numerical examples illustrate that the present method possesses both good capability to search global optima and far higher convergence speed than that of chaos optimization method.