本文關(guān)鍵詞：胞映射算法的開發(fā)和在動力學、控制和優(yōu)化中的應用　出處：《天津大學》2015年博士論文　論文類型：學位論文

  更多相關(guān)文章： 胞映射 多目標優(yōu)化 控制器設計 非線性動力學分析 非線性求零問題 穩(wěn)定邊界搜索 并行計算

【摘要】：胞映射方法最早由著名力學家徐皆蘇先生于上世紀八十年代提出。該方法最初被用來解決非線性動力學的全局問題。胞映射方法的基本思想是通過離散動力學系統(tǒng)的狀態(tài)空間,將原有連續(xù)的動力學軌跡轉(zhuǎn)化成離散的胞對胞映射。一步胞映射的構(gòu)造實際是通過短時積分動力學系統(tǒng)而得到的。通過構(gòu)造狀態(tài)空間中所有胞的一步映射,可以近似得到以任何胞作為初始條件的胞空間軌跡。進而可以通過分析某條軌跡的走向來判斷該軌跡上所有胞的動力學行為和性質(zhì)。該方法的優(yōu)勢在于,一旦確立了所有的胞的短時映射關(guān)系,系統(tǒng)的分析就無需再進行方程的積分。也就是說,相比于通常的點空間的分析,胞映射保留了積分軌跡上的所有時刻的信息。因此,和連續(xù)點空間的分析相比,胞映射能夠節(jié)省大量的計算時間。傳統(tǒng)的胞映射分為簡單胞映射和廣義胞映射。簡單胞映射在構(gòu)造短時映射時,通過從原像胞的中心點積分動力學方程,得到像點的位置,進而得到像點所在像胞的位置,從而構(gòu)造短時一步胞映射。簡單胞映射的特點是構(gòu)造方法簡單,分析思路清晰,容易編程實現(xiàn)。其分析的流程類似圖論算法里的深度最優(yōu)搜索策略,即對某一個正在處理的胞進行遍歷,直到該軌跡遇到自循環(huán)結(jié)構(gòu)或合并到其他已處理過的胞中。通過對胞進行分類,簡單胞映射可得到諸如吸引子和吸引域等動力學信息。雖然簡單胞映射在算法實現(xiàn)和深層邏輯上具有很強的優(yōu)勢性,但是其計算精度和計算量和胞的大小有著緊密的關(guān)系。鑒于簡單胞映射僅接受一個像胞,為保證胞軌跡和真實連續(xù)軌跡的較小誤差,胞的尺寸要盡可能的小。這樣就增加的計算的復雜度和計算量。為了避免簡單胞映射的缺陷,能夠接受多個像胞的廣義胞映射被發(fā)明出來。廣義胞映射在構(gòu)造一步映射時,在原像胞里采用多個初始點進行積分。其像胞為若干像點落入的胞中。換句話說,廣義胞映射收集了若干條短時積分軌跡的信息,其像胞的個數(shù)也不唯一。因此,廣義胞映射的儲存需要用到有向圖和稀疏矩陣的概念。廣義胞映射的分析方法可以借助馬爾科夫鏈和圖論分析。這兩個學科在離散數(shù)學和計算機科學已經(jīng)有了成熟的發(fā)展和廣泛的應用。和簡單胞映射不同的是,在廣義胞映射框架下,一個胞可能能夠演化到不同的吸引域,演化到不同域的概率也可以通過簡單的采樣方法進行計算。這樣就為隨機系統(tǒng)的分析搭建了一個很好的框架。因此,除了分析確定性系統(tǒng)外,廣義胞映射還能夠有效分析隨機系統(tǒng)的動力學行為。特別是當結(jié)合了有著解析解的短時高斯解后,廣義胞映射能夠準確快速地給出具有強非線性的隨機系統(tǒng)穩(wěn)態(tài)響應的概率密度函數(shù)。針對低維系統(tǒng)的模擬已經(jīng)證明,廣義胞映射的結(jié)果和大量蒙特卡洛模擬的結(jié)果吻合度相當高。值得一提的是,對于非線性系統(tǒng),一旦通過廣義胞映射確定了其一步轉(zhuǎn)移矩陣,也就是廣義胞映射的稀疏矩陣表達,系統(tǒng)的所有動力學信息,包括吸引子、吸引域、吸引盆邊界乃至穩(wěn)態(tài)概率密度分布,都可以通過一次分析廣義胞映射矩陣而得到。這是其他現(xiàn)有方法無法達到的優(yōu)勢。隨著胞映射方法在動力學系統(tǒng)中的大量成功應用,針對胞映射方法的改進也逐步被提出來,其中值得一提的一個改進是插值胞映射。嚴格來說,插值胞映射已經(jīng)不屬于離散數(shù)學處理的范疇。其基本思想雖然仍是將動力學系統(tǒng)狀態(tài)空間離散成網(wǎng)格,但其分析的主要思路是通過每個胞網(wǎng)格角點的精確積分信息來插值擬合胞內(nèi)任意一點的映射像點。該做法和有限元方法中的插值函數(shù)思路非常接近。插值胞映射能夠在一定程度上克服傳統(tǒng)胞映射離散誤差的劣勢,在提高求解精度上有一定的優(yōu)勢。但由于其插值格式僅限于二維平面問題,且其插值格式難以推廣到更高維的問題,插值胞映射在八十年代后期到九十年代初逐步淡出研究者的視線。在本論文中,我們利用插值胞映射的思路,提出一種能適應任何維度的插值格式,并證明了所提插值格式的精度可以達到局部二階近似。我們利用插值胞映射的思想對所求結(jié)果進行進一步的細化和精度提升。值得注意的是,插值胞映射僅是作為后處理的方法。在求解過程中,我們還是應用簡單或者廣義胞映射進行全局搜索。另一個針對胞映射的改進是面向集合的細分算法。該思路針對全局不變集搜索。其基本思想是通過由低分辨率到高分辨率的胞空間迭代逐步提高解的精確性。非線性動力學問題的全局不變集合通常僅占狀態(tài)空間很小的一部分。因此,若僅要得到不變集,則沒有必要對所有胞進行計算和處理。面向集合的細分算法正是基于這點,提出在不同分辨率胞空間下搜索的策略。初始所搜在粗胞下進行,當找到覆蓋可能出現(xiàn)解的胞集合后,算法只處理這些覆蓋集胞,所有的暫態(tài)胞則被丟掉。針對這些覆蓋集合胞進行細分后,同樣的搜索策略被應用在分辨率更高的小胞上。該過程如此反復,直到胞空間足夠滿足收斂條件。為保證每次迭代覆蓋集能夠全部找到,細分算法采用了一步逆映射指導搜索。嚴格的數(shù)學證明顯示該策略能夠最終收斂到真實的不變集合解。從胞映射被發(fā)明以來,在相當長的一段時間里,胞映射能解決的問題都局限在低維動力學系統(tǒng)中。盡管胞映射和其各種改進能夠有效揭示低維動力學的復雜動力學行為,但隨著動力學領(lǐng)域研究的發(fā)展和深入,人們需要了解越來越多的高維系統(tǒng)。維度詛咒是導致針對高維問題一直沒有合適方法出現(xiàn)的重要瓶頸。在其他應用領(lǐng)域,例如優(yōu)化和機器學習,基于隨機搜索的啟發(fā)式算法盡管能夠在一定程度上避免維度詛咒,但其算法的適用性、收斂性、全局性都還處于一個未知的探索階段。如何利用現(xiàn)有算法解決更高維的問題成為了胞映射算法向前發(fā)展必須要解決的問題。在本論文中,我們嘗試通過并行計算的思路拓展胞映射的應用空間。由于胞映射在構(gòu)造一步映射時任意兩個胞的處理是相互獨立的,所以胞映射在構(gòu)造階段可以針對一大批胞進行批量處理,也就是平行運算�；谠撌聦�,我們應用顯示處理單元(gpu)對胞映射算法進行加速。gpu由于其多核的特性已經(jīng)被廣泛應用在多個行業(yè),如天氣預報、金融分析、有限元計算等的并行計算和模擬中。顯卡生產(chǎn)和制造的先驅(qū)企業(yè)英偉達公司于近些年開發(fā)了gpu編程的通用平臺cuda。cuda平臺能集成當今流行的計算機語言,通過將代碼轉(zhuǎn)化為在gpu上可執(zhí)行的命令,從而使得gpu編程變得靈活和方便。在本論文中,我們應用cudac/c++環(huán)境對平行胞映射算法進行編程實現(xiàn)。應該指出的是,論文中所報道的加速效果和所進行計算的顯卡非常相關(guān),同樣的代碼在更好更快的新一代顯卡上能夠獲得更多的加速。本論文基于胞映射的框架,提出了若干基于離散胞空間的算法來解決多目標優(yōu)化、非線性動力學、零點搜索和穩(wěn)定邊界搜索等問題。平行運算貫穿了所有所提胞映射算法中。針對具體的應用,所提胞映射的局部構(gòu)造和全局搜索策略也有所不同。在本文中,我們通過構(gòu)造驅(qū)動胞對胞映射的底層動力學來將不同的應用統(tǒng)一在胞空間意義下的框架下。下面對本論文中胞映射方法的具體應用做簡要介紹:多目標優(yōu)化廣泛存在于各種工程優(yōu)化問題中。多目標優(yōu)化通常考慮若干相互制約的優(yōu)化指標。和傳統(tǒng)的單目標優(yōu)化不同,多目標優(yōu)化的解不再在參數(shù)空間中的點,而是一個集合,稱為帕累托集合。帕累托集合里的任意兩個點滿足非劣性,也就是無法找到一個解在多目標意義下比另一個解更優(yōu)。多目標優(yōu)化往往能給出一個較寬的設計范圍,因此在實際工程中,多目標優(yōu)化設計具有很強的優(yōu)勢。解決多目標優(yōu)化問題的關(guān)鍵在于能否找到全局的帕累托集合。傳統(tǒng)的目標加權(quán)雖然能將多目標問題轉(zhuǎn)為單目標,但其權(quán)重參數(shù)的選擇往往基于經(jīng)驗。隨著演化算法的逐步興起,基于生物種群演化的多目標優(yōu)化啟發(fā)式算法逐漸得到重視。演化算法的優(yōu)勢在于通過模擬生物種群的演化過程,能夠用較少的計算量得到盡可能覆蓋全局的非劣解集。其缺點是無法保證算法的收斂性和全局性。此外,演化算法是一種基于隨機搜索的算法,在應用中通常需要多次運行,通過統(tǒng)計的辦法確認多目標優(yōu)化解集在參數(shù)空間的位置。基于胞映射的全局搜索能力,我們提出了一種簡單胞映射混合算法來有效解決多目標優(yōu)化的全局問題。我們混合了有梯度和無梯度的局部搜索策略。通過面向集合細分算法逐步提高解的精確性。其中,無梯度算法首先應用在較粗的胞中,通過比較某一個胞的相鄰胞確定胞映射的像胞。注意該搜索策略僅為零階精度,因此僅限于在精度要求較低的前提下進行計算。但該搜索策略速度較快,計算代價低,所以我們用它來初步確認覆蓋集合的位置。一旦覆蓋集確認,我們應用細分的胞空間,通過有梯度的搜索策略構(gòu)造一步簡單胞映射,進而對解集的更細結(jié)構(gòu)進行捕捉。前期的研究通過一系列的標準問題證明了該算法的有效性和準確性。在本論文中,我們應用這種算法來解決多目標全狀態(tài)反饋和含時滯pid控制器的優(yōu)化設計。我們針對線性和非線性系統(tǒng)分別進行了控制器設計。將若干時域指標,諸如追蹤控制中的超調(diào)、響應時間、積分誤差等,設為多目標優(yōu)化指標。對于含時滯的非線性系統(tǒng),將局部線性化的閉環(huán)系統(tǒng)穩(wěn)定性作為優(yōu)化約束。應用所提混合算法,求得不同控制任務下控制器的多目標優(yōu)化設計。數(shù)值模擬顯示,所提多目標優(yōu)化算法能夠?qū)刂破鬟M行時域定量的優(yōu)化設計。閉環(huán)系統(tǒng)的時域信號顯示,多目標優(yōu)化策略所得追蹤響應呈一個緊湊的帶狀分布。胞映射算法搜索出的帕累托前沿,即帕累托集合的像,有著精細的內(nèi)部結(jié)構(gòu)。帕累托前沿能夠很好的反映優(yōu)化指標之間矛盾的本質(zhì)。作為胞映射應用最廣泛的領(lǐng)域,非線性動力學的全局分析一直是一個熱門話題。在本文中,作者嘗試使用并行計算、插值胞映射和面向集合細分算法將原有的簡單胞映射和廣義胞映射算法進行推廣。針對不同分析,我們提出了兩種基于胞空間的分析思路:其一,搜索狀態(tài)空間中全局不變集合。不變集一般包括穩(wěn)定平衡點、極限環(huán)、概周期解及混沌吸引子。所搜全局不變集,特別是有共存現(xiàn)象的非線性系統(tǒng),對于認識非線性系統(tǒng)長期演化狀態(tài)有著重要的意義。我們利用廣義胞映射和細分算法,對覆蓋集首先進行粗略估計。當細分進行到一定程度時,我們應用高維插值格式,將所求得的胞空間解作為已知數(shù)據(jù)庫,對不變集的更細結(jié)構(gòu)通過插值胞映射進行提取。所提插值格式的精度經(jīng)證明可達到局部二階精度。其二,針對非線性系統(tǒng)的全局分析,包括暫態(tài)胞的分類、吸引域標示和吸引邊界的搜索。這類分析需要構(gòu)造胞空間內(nèi)所有胞的廣義胞映射。由于我們對所有胞的性質(zhì)和動力學行為都要進行研究,細分算法將不再適用。所有動力學信息的提取都將在較高分辨率的胞空間下一步轉(zhuǎn)移矩陣確認后一次提取出來。顯而易見的是,構(gòu)造一步轉(zhuǎn)移矩陣將占據(jù)全局分析的絕大部分計算資源和計算時間,因此,并行計算在這個階段的引入將非常必要。針對所提出的胞映射分析框架,我們通過若干例子進行了驗證。通過一個低維的隱式動力學系統(tǒng)驗證了并行計算的顯著加速效果。在不同胞空間劃分下研究了不同計算量下并行計算的加速效果。通過中低維系統(tǒng)對胞映射全局分析的框架進行了驗證。通過高維洛倫茲系統(tǒng)的不變集搜索,提出了若干高維動力學系統(tǒng)分析的困難和解決方案。作為非線性系統(tǒng)分析的前處理部分,搜索非線性代數(shù)方程的全局零解問題是關(guān)鍵。很多非線性問題的分析,例如分叉分析、穩(wěn)定點搜索、穩(wěn)定邊界搜索等都可以轉(zhuǎn)化為代數(shù)方程找零的形式。應用胞映射和面向集合混合算法,我們提出了一種類似搜索不變集的搜索算法。和非線性動力學分析不同的是,找零問題沒有顯式的動力學系統(tǒng)可以構(gòu)造胞對胞映射。因此,我們需要根據(jù)找零問題的特點構(gòu)造新的底層動力學。本文通過牛頓梯度方法構(gòu)造找零問題胞映射的底層動力學,通過點對點映射將牛頓梯度法作用在胞空間中。應用簡單和廣義胞映射的混合算法,首先找到底層動力學的不變集,即零解的覆蓋集。進而通過在覆蓋集上的向前簡單胞映射搜索,細分所求解集,使之達到求解精度。針對胞映射引入的離散誤差,我們通過聚類分析,找出獨立的胞集合。在某一胞集合上再次應用點空間精確的搜索找出高精度的零解。通過不同維度的例子,我們驗證了算法的計算效率和精確性。通過計算我們發(fā)現(xiàn),高維代數(shù)方程的零解可能顯示出復雜的幾何形狀。通過分析方程的全局零解的穩(wěn)定性,可以了解非線性系統(tǒng)平衡點的局部拓撲性質(zhì)。由非線性系統(tǒng)理論可知,經(jīng)過鞍點的所有穩(wěn)定流行構(gòu)成劃分兩個穩(wěn)定平衡點的穩(wěn)定邊界�；诜蔷�性系統(tǒng)的這個性質(zhì),我們提出了一種基于簡單胞映射的穩(wěn)定邊界搜索算法。該算法從非線性系統(tǒng)的勢能函數(shù)出發(fā),首先利用找零算法求出非線性系統(tǒng)的全局平衡點并給出穩(wěn)定性分析,然后應用簡單胞映射,將各暫態(tài)胞進行歸類。這樣便求得穩(wěn)定平衡點的吸引盆。從鞍點出發(fā),通過辨識鞍點附近不同的吸引域,通過延拓的方法找出不同穩(wěn)定點之間的穩(wěn)定邊界。進而完成對非線性系統(tǒng)穩(wěn)定邊界的搜索。該算法最大的計算量發(fā)生在簡單胞映射構(gòu)造的階段,我們利用并行計算,顯著提高了求解速度。計算表明,一個具有百萬量級胞數(shù)的計算任務,僅需要五秒左右便可求解完畢。論文結(jié)尾給出了胞映射算法在其他領(lǐng)域的應用,其中包括滑�？刂频亩嗄繕藘�(yōu)化設計、參數(shù)不確定系統(tǒng)的魯棒性設計、結(jié)構(gòu)的多目標優(yōu)化設計、多目標路徑規(guī)劃等。這些應用也都適合平行運算。此外,給出了胞映射算法仍需要研究的問題,其中包括胞空間劃分策略、最優(yōu)采樣、胞映射與模式識別和機器學習的結(jié)合等。
[Abstract]:......
【學位授予單位】：天津大學
【學位級別】：博士
【學位授予年份】：2015
【分類號】：O19;O231

【相似文獻】

相關(guān)期刊論文 前10條

1 徐紅波;;空間填充曲線映射算法研究[J];科技信息(科學教研);2007年35期

2 周向東;;一種改進的無參數(shù)自組織映射算法[J];安徽大學學報(自然科學版);2009年03期

3 許向陽;朱元泓;桑鳳仙;;與圖像內(nèi)容相關(guān)的色域映射算法研究[J];武漢大學學報(信息科學版);2012年05期

4 譚英杰,孫建剛,高玉久,龍真;板彈塑性問題的返回映射算法[J];大慶石油學院學報;1997年04期

5 楊先娣;彭智勇;吳黎兵;劉君強;;基于樹結(jié)構(gòu)的多策略本體映射算法[J];武漢大學學報(理學版);2008年03期

6 蘭美輝;高煒;;基于k-部排序?qū)W習方法的本體映射算法[J];蘇州科技學院學報(自然科學版);2012年02期

7 高煒;梁立;;基于概念匹配的本體映射算法[J];安徽大學學報(自然科學版);2010年06期

8 高煒;高云;梁立;;基于ε-鄰域方法的本體映射算法[J];云南師范大學學報(自然科學版);2011年03期

9 周莉;;基于DTD元素樹的XML與RDB的雙向映射算法研究[J];江西師范大學學報(自然科學版);2011年05期

10 徐天偉;甘健侯;高麗金;高煒;;基于降維理論的本體映射算法[J];西北師范大學學報(自然科學版);2011年04期

相關(guān)會議論文 前6條

1 潘泉;張洪才;戴冠中;杜宏偉;;并行映射及啟發(fā)式映射算法[A];1995年中國控制會議論文集（下）[C];1995年

2 李選如;何潔月;;一種新的自動本體映射算法(英文)[A];全國語域web與本體能研討會論文集[C];2006年

3 林琪;謝連寶;;支持動態(tài)校驗的概念模型映射算法[A];2013年中國智能自動化學術(shù)會議論文集（第五分冊）[C];2013年

4 劉真;許向陽;盧亮;;一種新的色彩信號跨媒體轉(zhuǎn)換再現(xiàn)分區(qū)映射算法[A];2008中國儀器儀表與測控技術(shù)進展大會論文集（Ⅰ）[C];2008年

5 朱雙鶴;馬凌;;用改進的自組織映射算法求解TSP問題[A];1999年中國神經(jīng)網(wǎng)絡與信號處理學術(shù)會議論文集[C];1999年

6 郜盛魁;劉凱;朱衍波;張s，

本文編號：1400415