嵌套分割算法：一種新的并行隨機優化算法

摘 要：嵌套分割算法是一種新的系統優化計算方法，它可以應用于確定型和隨機型、離散系統和連續系統的優化問題。綜述了嵌套分割算法的概念原理、方法步驟，介紹了算法的應用情況，并探討了算法未來的研究方向。

關鍵詞：嵌套分割算法； 系統優化； 算法綜述

中圖分類號：N945.15文獻標志碼：A

文章編號：1001-3695(2007)06-0079-03

0 引言

實際的工程應用中有一類復雜的離散時間動態系統優化問題。由于其狀態變量和控制參數通常受隨機因素影響，不能得到具體的函數解析表達式，從而很難對實際系統進行優化分析。為了解決這類問題，人們設計了很多求解方法［1－3］，但效果都不理想［4］。嵌套分割算法（Nested Partitions Method， NP算法）是由L. Shi和S. lafsson提出的一種新的全局優化算法［5－7］。這種方法對于離散時間動態系統以及組合優化問題具有很高的求解效率。它把全局搜索與局部尋優結合在一起，具有開放性、并行性、全局性和易操作性等突出優點；能夠解決許多復雜系統的確定性和隨機性優化問題，并且具有很高的計算效率。NP算法具有廣闊的應用前景，但國內外對這種方法的研究才剛剛起步。尤其是國內只有路曉偉、蔣馥的少數幾篇研究論文［8－10］，所以有必要對這種方法作出全面介紹，以便進行深入研究。

1 算法描述

1．1 算法的概念原理

定義1 一個通過固定分割策略得到的區域稱為該策略下的可行域(Valid Region)。對于離散系統，只含有一個單解的細分區域稱為單解域( Singleton Region) 。所有可行域的集合表示為∑。單解域具有特別的意義，可以將單解域的集合表示為∑0。

嵌套分割算法的實質是針對可行解的集合，而不是針對單個可行點。在這點上它是與遺傳算法、模擬退火等算法不同的。嵌套分割算法是對可行域進行反復細分的過程。從整個可行域Θ開始，將整個可行域逐漸細分，直到分為單解域或達到精度要求為止。

設定效果函數I:∑ → R，用來選擇最有希望包含最優解的區域(最可能域)，因此稱之為品質指標(Promising Index)。當系統具有確定的目標函數時，效果函數（或品質指標函數）通常就是取目標函數。另外，由于嵌套分割算法具有很大的開放性，可以根據需要設定品質指標函數的形式，唯一的要求就是它要與單解域上的效果函數相一致。

假設經過第k次重復分割，得到了最可能域σ(k)Θ；然后把該可行域分割成Mσ(k)個子域，并將σ(k)以外的整個區域看成一個區域。在每次重復分割時，都只是考慮Mσ(k)+1個不相交的可行域的子集（初次分割除外），在得到的每個區域上利用抽樣方法計算該區域的品質指標，用以比較確定哪個區域是最可能域。依此重復進行分割，直到得到不再變化的單解域為止。如果Mσ(k)以外的整個區域被認為是最可能域，則要回溯到包含當前最可能域的較大區域，并將其作為下一步繼續分割的最可能域。由于所得到的分割區域是一層一層嵌套的，該優化方法被稱為嵌套分割(Nested Partitions)算法。

1．2 算法的方法步驟

嵌套分割算法包括四個基本算子，即分割(Partition)、抽樣(Sampling)、選區(Selection)、回溯(Backtrack)。其尋優過程也是反復使用這四個算子的重復過程。

（1）分割

（2）抽樣

（3）計算索引值，選擇最可能區域

由于從不同區域中進行抽樣，并計算每個區域的品質索引值的步驟可以同時進行，該算法在本質上具有并行計算的特點，可以很方便地使用并行計算方法來大大提高其計算效率。

（4）回溯

當σ(k)之外的整個區域被認為是最可能域時，需要從當前最可能域σ(k)出發，按照事先確定好的回溯原則，回溯到一個包含當前最可能域的較大區域，并將其作為下一步的最可能域。回溯原則可以按照需要確定，如可以將當前最可能域的母域s(σ(k))作為回溯對象。此時最可能域的選擇可以表示為

當然也可以將整個有限可行域Θ作為回溯對象，即σ(k+1)=Θ。

由新的最可能域σ(k+1)出發，繼續進行上述分割、抽樣、選區和回溯四個算子，就得到了一個分割區域的序列。這樣可以一直進行到所有可行域中的點都與單解域相對應，可以將被認為是最可能域的次數最多的單解域中的點看做是全局最優解。

2 算法收斂的理論分析

在嵌套分割過程中，算法關心的區域從∑空間中的一個區域轉移到另一個區域。轉移所依據的只是當前對各區域的抽樣信息。因此該算法的分割尋優過程就產生了一個以∑作為狀態空間的馬爾可夫鏈{σ(k)}∞k=1。不難證明，該馬爾可夫鏈具有唯一的平衡分布。

如果馬爾可夫鏈的起始狀態不是最大深度域，它或者會轉移到當前最可能域的一個子域，或是回溯到一個更大的區域，而轉移到同一個狀態的概率為0。所以吸收態必定是最大深度域。

因此η不是一個吸收態，而只是一個過渡態。由于全局最優解所處的最大深度域是馬爾可夫鏈{σ(k)}∞k=1的吸收態，當馬爾可夫鏈一經到達這種狀態，它就再也不會轉移到其他狀態。馬爾可夫鏈中存在很多過渡態，所以要經過有限次的轉移，才能由過渡態到達吸收態［7］。

這就說明，嵌套分割算法具有堅實的數學基礎。用它來解決一些復雜的優化問題一定能得到理想的最優解；而且上述理論分析并沒有限制嵌套分割算法的分割策略、抽樣策略、品質索引函數選擇以及回溯策略。因此嵌套分割算法具有其他算法無法比擬的開發性。

3 一個算例

有這樣一個組合優化問題：它的可行域為η0=Θ={1，2，3，4，5，6，7，8}。利用嵌套分割算法求解，分割策略是：每次迭代將當前最可能域分割成兩等份（圖1）。

4 算法應用及研究前景

嵌套分割算法是一種新型的優化算法，它在處理組合優化問題時具有很高的計算效率。Shi等人將嵌套分割算法應用于解決TSP問題、供應鏈管理、產品設計以及機器分配等領域，取得了顯著效果［11－13］。另外嵌套分割算法有比其他算法更廣泛的開放性，能夠方便地與其他算法結合在一起，提高計算效率。Shi等人將嵌套分割算法與遺傳算法結合起來，得到了比遺傳算法更好的結果［6］。路曉偉、蔣馥將嵌套分割算法與模擬退火算法相結合，提高了算法的計算效率［8，9］。嵌套分割算法還具有并行計算的特點，可以使用并行計算技術提高優化效率。它經過拓展還可以應用于有限區域上的連續系統優化問題［10］。

嵌套分割算法為解決系統全局優化問題提供了新的選擇，具有廣泛的應用前景，但對其研究才剛剛開始，還有許多該算法的未知領域值得進行深入的探索。①算法的應用。雖然NP算法已經有了一些應用研究，但范圍還很小，深度還不夠，有關嵌套分割算法的更廣泛深入的應用研究是一項很有意義的工作。②是NP算法的改進研究。嵌套分割算法具有很強的全局尋優能力，結合一些具有優良局部尋優能力的算法，可以對算法進行有效改良。③由于嵌套分割算法的分割算子和抽樣算子對算法的有效性起重要作用，所以分割策略和抽樣策略的研究也是一個有趣的研究方向。④雖然嵌套分割算法建立在一定的數學理論基礎之上，但對理論的進一步完善是一項不會終止的工作。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。