胞映射算法的開發(fā)和在動力學(xué)、控制和優(yōu)化中的應(yīng)用.pdf

1、胞映射方法最早由著名力學(xué)家徐皆蘇先生于上世紀(jì)八十年代提出。該方法最初被用來解決非線性動力學(xué)的全局問題。胞映射方法的基本思想是通過離散動力學(xué)系統(tǒng)的狀態(tài)空間，將原有連續(xù)的動力學(xué)軌跡轉(zhuǎn)化成離散的胞對胞映射。一步胞映射的構(gòu)造實(shí)際是通過短時(shí)積分動力學(xué)系統(tǒng)而得到的。通過構(gòu)造狀態(tài)空間中所有胞的一步映射，可以近似得到以任何胞作為初始條件的胞空間軌跡。進(jìn)而可以通過分析某條軌跡的走向來判斷該軌跡上所有胞的動力學(xué)行為和性質(zhì)。該方法的優(yōu)勢在于，一旦確立了所有的

2、胞的短時(shí)映射關(guān)系，系統(tǒng)的分析就無需再進(jìn)行方程的積分。也就是說，相比于通常的點(diǎn)空間的分析，胞映射保留了積分軌跡上的所有時(shí)刻的信息。因此，和連續(xù)點(diǎn)空間的分析相比，胞映射能夠節(jié)省大量的計(jì)算時(shí)間。
　　隨著胞映射方法在動力學(xué)系統(tǒng)中的大量成功應(yīng)用，針對胞映射方法的改進(jìn)也逐步被提出來，其中值得一提的一個(gè)改進(jìn)是插值胞映射。嚴(yán)格來說，插值胞映射已經(jīng)不屬于離散數(shù)學(xué)處理的范疇。其基本思想雖然仍是將動力學(xué)系統(tǒng)狀態(tài)空間離散成網(wǎng)格，但其分析的主要思路是通過

3、每個(gè)胞網(wǎng)格角點(diǎn)的精確積分信息來插值擬合胞內(nèi)任意一點(diǎn)的映射像點(diǎn)。該做法和有限元方法中的插值函數(shù)思路非常接近。插值胞映射能夠在一定程度上克服傳統(tǒng)胞映射離散誤差的劣勢，在提高求解精度上有一定的優(yōu)勢。
　　從胞映射被發(fā)明以來，在相當(dāng)長的一段時(shí)間里，胞映射能解決的問題都局限在低維動力學(xué)系統(tǒng)中。盡管胞映射和其各種改進(jìn)能夠有效揭示低維動力學(xué)的復(fù)雜動力學(xué)行為，但隨著動力學(xué)領(lǐng)域研究的發(fā)展和深入，人們需要了解越來越多的高維系統(tǒng)。維度詛咒是導(dǎo)致針對高維

4、問題一直沒有合適方法出現(xiàn)的重要瓶頸。在其他應(yīng)用領(lǐng)域，例如優(yōu)化和機(jī)器學(xué)習(xí)，基于隨機(jī)搜索的啟發(fā)式算法盡管能夠在一定程度上避免維度詛咒，但其算法的適用性、收斂性、全局性都還處于一個(gè)未知的探索階段。如何利用現(xiàn)有算法解決更高維的問題成為了胞映射算法向前發(fā)展必須要解決的問題。
　　在本論文中，我們嘗試通過并行計(jì)算的思路拓展胞映射的應(yīng)用空間。由于胞映射在構(gòu)造一步映射時(shí)任意兩個(gè)胞的處理是相互獨(dú)立的，所以胞映射在構(gòu)造階段可以針對一大批胞進(jìn)行批量處理

5、，也就是平行運(yùn)算。基于該事實(shí)，我們應(yīng)用顯示處理單元(GPU)對胞映射算法進(jìn)行加速。GPU由于其多核的特性已經(jīng)被廣泛應(yīng)用在多個(gè)行業(yè)，如天氣預(yù)報(bào)、金融分析、有限元計(jì)算等的并行計(jì)算和模擬中。顯卡生產(chǎn)和制造的先驅(qū)企業(yè)英偉達(dá)公司于近些年開發(fā)了GPU編程的通用平臺CUDA。CUDA平臺能集成當(dāng)今流行的計(jì)算機(jī)語言，通過將代碼轉(zhuǎn)化為在GPU上可執(zhí)行的命令，從而使得GPU編程變得靈活和方便。在本論文中，我們應(yīng)用CUDA C/C++環(huán)境對平行胞映射算法進(jìn)行

6、編程實(shí)現(xiàn)。應(yīng)該指出的是，論文中所報(bào)道的加速效果和所進(jìn)行計(jì)算的顯卡非常相關(guān)，同樣的代碼在更好更快的新一代顯卡上能夠獲得更多的加速。
　　本論文基于胞映射的框架，提出了若干基于離散胞空間的算法來解決多目標(biāo)優(yōu)化、非線性動力學(xué)、零點(diǎn)搜索和穩(wěn)定邊界搜索等問題。平行運(yùn)算貫穿了所有所提胞映射算法中。針對具體的應(yīng)用，所提胞映射的局部構(gòu)造和全局搜索策略也有所不同。在本文中，我們通過構(gòu)造驅(qū)動胞對胞映射的底層動力學(xué)來將不同的應(yīng)用統(tǒng)一在胞空間意義下的框架

7、下。下面對本論文中胞映射方法的具體應(yīng)用做簡要介紹:
　　多目標(biāo)優(yōu)化廣泛存在于各種工程優(yōu)化問題中。多目標(biāo)優(yōu)化通?？紤]若干相互制約的優(yōu)化指標(biāo)。和傳統(tǒng)的單目標(biāo)優(yōu)化不同，多目標(biāo)優(yōu)化的解不再在參數(shù)空間中的點(diǎn)，而是一個(gè)集合，稱為帕累托集合。帕累托集合里的任意兩個(gè)點(diǎn)滿足非劣性，也就是無法找到一個(gè)解在多目標(biāo)意義下比另一個(gè)解更優(yōu)。多目標(biāo)優(yōu)化往往能給出一個(gè)較寬的設(shè)計(jì)范圍，因此在實(shí)際工程中，多目標(biāo)優(yōu)化設(shè)計(jì)具有很強(qiáng)的優(yōu)勢。
　　解決多目標(biāo)優(yōu)化問題的

8、關(guān)鍵在于能否找到全局的帕累托集合。傳統(tǒng)的目標(biāo)加權(quán)雖然能將多目標(biāo)問題轉(zhuǎn)為單目標(biāo)，但其權(quán)重參數(shù)的選擇往往基于經(jīng)驗(yàn)。隨著演化算法的逐步興起，基于生物種群演化的多目標(biāo)優(yōu)化啟發(fā)式算法逐漸得到重視。演化算法的優(yōu)勢在于通過模擬生物種群的演化過程，能夠用較少的計(jì)算量得到盡可能覆蓋全局的非劣解集。其缺點(diǎn)是無法保證算法的收斂性和全局性。此外，演化算法是一種基于隨機(jī)搜索的算法，在應(yīng)用中通常需要多次運(yùn)行，通過統(tǒng)計(jì)的辦法確認(rèn)多目標(biāo)優(yōu)化解集在參數(shù)空間的位置。

9、>　　基于胞映射的全局搜索能力，我們提出了一種簡單胞映射混合算法來有效解決多目標(biāo)優(yōu)化的全局問題。我們混合了有梯度和無梯度的局部搜索策略。通過面向集合細(xì)分算法逐步提高解的精確性。其中，無梯度算法首先應(yīng)用在較粗的胞中，通過比較某一個(gè)胞的相鄰胞確定胞映射的像胞。注意該搜索策略僅為零階精度，因此僅限于在精度要求較低的前提下進(jìn)行計(jì)算。但該搜索策略速度較快，計(jì)算代價(jià)低，所以我們用它來初步確認(rèn)覆蓋集合的位置。一旦覆蓋集確認(rèn)，我們應(yīng)用細(xì)分的胞空間，通過

10、有梯度的搜索策略構(gòu)造一步簡單胞映射，進(jìn)而對解集的更細(xì)結(jié)構(gòu)進(jìn)行捕捉。
　　前期的研究通過一系列的標(biāo)準(zhǔn)問題證明了該算法的有效性和準(zhǔn)確性。在本論文中，我們應(yīng)用這種算法來解決多目標(biāo)全狀態(tài)反饋和含時(shí)滯PID控制器的優(yōu)化設(shè)計(jì)。我們針對線性和非線性系統(tǒng)分別進(jìn)行了控制器設(shè)計(jì)。將若干時(shí)域指標(biāo)，諸如追蹤控制中的超調(diào)、響應(yīng)時(shí)間、積分誤差等，設(shè)為多目標(biāo)優(yōu)化指標(biāo)。對于含時(shí)滯的非線性系統(tǒng)，將局部線性化的閉環(huán)系統(tǒng)穩(wěn)定性作為優(yōu)化約束。應(yīng)用所提混合算法，求得不同控

11、制任務(wù)下控制器的多目標(biāo)優(yōu)化設(shè)計(jì)。數(shù)值模擬顯示，所提多目標(biāo)優(yōu)化算法能夠?qū)刂破鬟M(jìn)行時(shí)域定量的優(yōu)化設(shè)計(jì)。閉環(huán)系統(tǒng)的時(shí)域信號顯示，多目標(biāo)優(yōu)化策略所得追蹤響應(yīng)呈一個(gè)緊湊的帶狀分布。胞映射算法搜索出的帕累托前沿，即帕累托集合的像，有著精細(xì)的內(nèi)部結(jié)構(gòu)。帕累托前沿能夠很好的反映優(yōu)化指標(biāo)之間矛盾的本質(zhì)。
　　作為胞映射應(yīng)用最廣泛的領(lǐng)域，非線性動力學(xué)的全局分析一直是一個(gè)熱門話題。在本文中，作者嘗試使用并行計(jì)算、插值胞映射和面向集合細(xì)分算法將原有的簡

12、單胞映射和廣義胞映射算法進(jìn)行推廣。針對不同分析，我們提出了兩種基于胞空間的分析思路:
　　其一，搜索狀態(tài)空間中全局不變集合。不變集一般包括穩(wěn)定平衡點(diǎn)、極限環(huán)、概周期解及混沌吸引子。所搜全局不變集，特別是有共存現(xiàn)象的非線性系統(tǒng)，對于認(rèn)識非線性系統(tǒng)長期演化狀態(tài)有著重要的意義。我們利用廣義胞映射和細(xì)分算法，對覆蓋集首先進(jìn)行粗略估計(jì)。當(dāng)細(xì)分進(jìn)行到一定程度時(shí)，我們應(yīng)用高維插值格式，將所求得的胞空間解作為已知數(shù)據(jù)庫，對不變集的更細(xì)結(jié)構(gòu)通過插值

13、胞映射進(jìn)行提取。所提插值格式的精度經(jīng)證明可達(dá)到局部二階精度。
　　其二，針對非線性系統(tǒng)的全局分析，包括暫態(tài)胞的分類、吸引域標(biāo)示和吸引邊界的搜索。這類分析需要構(gòu)造胞空間內(nèi)所有胞的廣義胞映射。由于我們對所有胞的性質(zhì)和動力學(xué)行為都要進(jìn)行研究，細(xì)分算法將不再適用。所有動力學(xué)信息的提取都將在較高分辨率的胞空間下一步轉(zhuǎn)移矩陣確認(rèn)后一次提取出來。顯而易見的是，構(gòu)造一步轉(zhuǎn)移矩陣將占據(jù)全局分析的絕大部分計(jì)算資源和計(jì)算時(shí)間，因此，并行計(jì)算在這個(gè)階段的

14、引入將非常必要。
　　針對所提出的胞映射分析框架，我們通過若干例子進(jìn)行了驗(yàn)證。通過一個(gè)低維的隱式動力學(xué)系統(tǒng)驗(yàn)證了并行計(jì)算的顯著加速效果。在不同胞空間劃分下研究了不同計(jì)算量下并行計(jì)算的加速效果。通過中低維系統(tǒng)對胞映射全局分析的框架進(jìn)行了驗(yàn)證。通過高維洛倫茲系統(tǒng)的不變集搜索，提出了若干高維動力學(xué)系統(tǒng)分析的困難和解決方案。
　　作為非線性系統(tǒng)分析的前處理部分，搜索非線性代數(shù)方程的全局零解問題是關(guān)鍵。很多非線性問題的分析，例如分叉分

15、析、穩(wěn)定點(diǎn)搜索、穩(wěn)定邊界搜索等都可以轉(zhuǎn)化為代數(shù)方程找零的形式。應(yīng)用胞映射和面向集合混合算法，我們提出了一種類似搜索不變集的搜索算法。和非線性動力學(xué)分析不同的是，找零問題沒有顯式的動力學(xué)系統(tǒng)可以構(gòu)造胞對胞映射。因此，我們需要根據(jù)找零問題的特點(diǎn)構(gòu)造新的底層動力學(xué)。
　　本文通過牛頓梯度方法構(gòu)造找零問題胞映射的底層動力學(xué)，通過點(diǎn)對點(diǎn)映射將牛頓梯度法作用在胞空間中。應(yīng)用簡單和廣義胞映射的混合算法，首先找到底層動力學(xué)的不變集，即零解的覆蓋集

16、。進(jìn)而通過在覆蓋集上的向前簡單胞映射搜索，細(xì)分所求解集，使之達(dá)到求解精度。針對胞映射引入的離散誤差，我們通過聚類分析，找出獨(dú)立的胞集合。在某一胞集合上再次應(yīng)用點(diǎn)空間精確的搜索找出高精度的零解。通過不同維度的例子，我們驗(yàn)證了算法的計(jì)算效率和精確性。通過計(jì)算我們發(fā)現(xiàn)，高維代數(shù)方程的零解可能顯示出復(fù)雜的幾何形狀。
　　通過分析方程的全局零解的穩(wěn)定性，可以了解非線性系統(tǒng)平衡點(diǎn)的局部拓?fù)湫再|(zhì)。由非線性系統(tǒng)理論可知，經(jīng)過鞍點(diǎn)的所有穩(wěn)定流行構(gòu)成

17、劃分兩個(gè)穩(wěn)定平衡點(diǎn)的穩(wěn)定邊界?；诜蔷€性系統(tǒng)的這個(gè)性質(zhì)，我們提出了一種基于簡單胞映射的穩(wěn)定邊界搜索算法。該算法從非線性系統(tǒng)的勢能函數(shù)出發(fā)，首先利用找零算法求出非線性系統(tǒng)的全局平衡點(diǎn)并給出穩(wěn)定性分析，然后應(yīng)用簡單胞映射，將各暫態(tài)胞進(jìn)行歸類。這樣便求得穩(wěn)定平衡點(diǎn)的吸引盆。從鞍點(diǎn)出發(fā)，通過辨識鞍點(diǎn)附近不同的吸引域，通過延拓的方法找出不同穩(wěn)定點(diǎn)之間的穩(wěn)定邊界。進(jìn)而完成對非線性系統(tǒng)穩(wěn)定邊界的搜索。該算法最大的計(jì)算量發(fā)生在簡單胞映射構(gòu)造的階段，我們