本文關鍵詞：基于進化計算的行為模型自動精化和排序?qū)W習方法的研究，，由筆耕文化傳播整理發(fā)布。

《山東大學》 2009年

基于進化計算的行為模型自動精化和排序?qū)W習方法的研究

王帥強  

【摘要】： 進化計算是研究仿照生物進化自然選擇過程中所表現(xiàn)出來的優(yōu)化規(guī)律和方法,以解決復雜的工程技術領域或其他領域的優(yōu)化問題的一種計算方法。隨著進化計算自身的發(fā)展,一些新的進化計算方法在不斷的提出,而一些舊的方法也在煥發(fā)著新的活力。 近些年,在一些領域中的某些問題的研究中,傳統(tǒng)的方法遇到了很大的困難,例如在軟件工程領域中的模型精化問題;而在一些領域中,某些問題利用傳統(tǒng)的人工智能方法不能得到很理想的結(jié)果,例如信息檢索領域中的排序?qū)W習問題。這些問題都促使我們從進化計算的角度重新審視,以期利用自然進化的思想對他們進一步處理,從而得到理想的結(jié)果。 基于以上的應用背景和需求,本文重點研究了利用進化計算相關算法解決傳統(tǒng)方法難以處理的某些問題:并以此為基礎,開發(fā)了一系列的原型系統(tǒng)對研究成果進行了驗證。本文主要的研究內(nèi)容和創(chuàng)新點包括以下方面: 1對軟件系統(tǒng)中行為的建模和精化理論的研究。本論文根據(jù)自動精化方法必須的條件,提出了一套描述行為模型的形式化符號體系,并據(jù)此提出了行為模型的形式化建模方法和行為精化理論。行為建模方法和行為模型的自動精化方法的提出,為推動模型驅(qū)動開發(fā)理論,尤其是UML和形式化方法集成建模技術的發(fā)展和應用,將會起到巨大的推動作用。 在模型驅(qū)動開發(fā)中,行為的建模和精化是一個關鍵問題,它需要考慮對象的一系列的動作語義,包括動作在何時觸發(fā),系統(tǒng)狀態(tài)如何變化,以及行為執(zhí)行結(jié)束后最終狀態(tài)如何描述等等。由于UML在模型語義等方面的缺失,以及形式化方法和UML混合建模研究的廣泛開展,使得我們不得不采用以集合論和謂詞邏輯為基礎的形式化建模方法,對行為進行精確的建模并逐步精化至代碼。近幾十年中,盡管有很多精化理論和精化工具相繼提出,但總體而言,傳統(tǒng)的關于精化方面的研究主要考慮的是整個軟件系統(tǒng)模型的精化定義和驗證問題。隨著UML和形式化方法集成建模的研究的廣泛開展,形式化建模方法所關注的領域轉(zhuǎn)變?yōu)檐浖到y(tǒng)的對象行為的細節(jié)。在這方面,國內(nèi)外并沒有相關的專門用于描述行為精化的思想提出,而傳統(tǒng)的基于整個系統(tǒng)的精化顯得過于龐大,對于我們的問題并不十分合適。因此,行為精化理論的提出,是一個亟待解決的重要問題。 根據(jù)自動精化方法必須的條件,參照前人的工作,我們提出了一套描述行為模型的形式化符號體系,并據(jù)此提出了行為模型的形式化建模方法和行為精化理論。本文根據(jù)行為精化理論,從問題求解的角度上,提出了一種實現(xiàn)行為精化的一般性的指導思想,即通過搜索狀態(tài)空間,從而找到一個可以滿足特定條件的狀態(tài),進而得到精化結(jié)果。通過估計狀態(tài)空間可以證明,遍歷式的窮盡搜索辦法是不可行的,必須引入啟發(fā)式的智能搜索機制。 2對基于遺傳規(guī)劃的行為模型自動精化方法的研究。本論文提出了一種基于遺傳規(guī)劃的自動精化方法,它為形式化模型的自動精化方法提供了一個新的思路,同時為UML和形式化方法集成建模方法的推廣和應用提供了更加有效的工具支持。 軟件開發(fā)的模型化和自動化是軟件技術的發(fā)展趨勢,而缺乏自動精化方法是阻礙形式化方法在業(yè)界應用的一個重要原因。在本文中我們提出了一種基于遺傳規(guī)劃的自動精化方法。 由于遺傳規(guī)劃算法源自于遺傳算法,它也有其自身的弱點,最突出的問題就是它最適合線性結(jié)構(gòu)的問題求解邏輯,而不能有效地處理顯式的循環(huán)結(jié)構(gòu)和選擇結(jié)構(gòu)。為了解決上述問題,我們提出了一種基于謂詞邏輯的遺傳規(guī)劃方法。首先,對抽象模型的后置條件進行自下而上的歸約精化,以生成顯式的循環(huán)結(jié)構(gòu)并將問題簡化和分解;然后將生成的子問題采用基于遺傳規(guī)劃的精化方法進一步精化,將行為模型的精化看作一個問題求解最終得到實現(xiàn)模型,通過基于遺傳規(guī)劃的方法最終得到一個由若干基本操作組合而成的具體行為。我們還提出了一種在遺傳規(guī)劃中采用組合終止條件的方法,用以生成選擇結(jié)構(gòu);最后,我們提出一種對實現(xiàn)模型的優(yōu)化方法,以減少實現(xiàn)模型中操作邏輯的冗余。根據(jù)我們提出的方法,成功的演化出了冒泡排序算法。 事實上,本方法具有一定的通用性,它適用于任何由若干基本操作組合以完成復雜操作的問題求解過程。 3對基于進化計算的排序?qū)W習的研究。本論文提出了基于進化計算的排序函數(shù)發(fā)現(xiàn)算法的框架;并根據(jù)該框架,提出一種基于免疫規(guī)劃的排序?qū)W習方法RankIP,并得到了很好的性能,有力的證明了我們提出的基于排序?qū)W習算法框架的有效性。本論文的研究將有力的促進進化計算方法在排序?qū)W習問題的應用。 網(wǎng)頁排序問題是Web信息檢索領域的一個中心問題,一個好的排序算法能夠明顯的提高檢索質(zhì)量。傳統(tǒng)的網(wǎng)頁排序算法分為三類:基于鏈接的方法、基于內(nèi)容的方法和混合方法。此外,基于機器學習技術的網(wǎng)頁排序算法,即“排序?qū)W習”,越來越廣泛的用來解決信息檢索排序問題。這一問題作為信息檢索和機器學習的交叉領域,已經(jīng)成為非常活躍的一個研究熱點,并引起廣泛關注。目前提出的各種排序?qū)W習算法,其結(jié)果都不甚理想。 一些學者依據(jù)進化計算的思想,提出了基于遺傳規(guī)劃的排序?qū)W習方法;而最近包括群智能算法,免疫算法等一系列性能更為優(yōu)異的進化計算方法的提出,也為基于進化計算的排序?qū)W習方法提供了更加有力的工具。在這個基礎上,我們介紹了一系列的定義,精確的表達了基于進化計算的排序函數(shù)發(fā)現(xiàn)算法的一般原理;并且描述了基于進化計算的排序函數(shù)發(fā)現(xiàn)算法的框架,使得任何的進化計算方法都可以靈活的嵌入算法框架中。算法框架的提出,將有力的促進進化計算方法在信息檢索領域,尤其是排序?qū)W習問題的應用。 根據(jù)我們提出的基于進化計算的排序函數(shù)發(fā)現(xiàn)的算法框架,在本文中我們還提出一種基于免疫規(guī)劃的排序?qū)W習方法RanklP。我們采用微軟亞洲研究院提供的LETOR 2.0數(shù)據(jù)集合作為訓練和驗證數(shù)據(jù)集合,實驗證明RankIP較之其他排序?qū)W習方法在P@n,MAP和NDCG等評價標準上均優(yōu)于目前提出的著名的排序?qū)W習方法,如RankingSVM和RankBoost等。在實驗中我們還對比了免疫規(guī)劃和遺傳規(guī)劃在排序?qū)W習中的應用,結(jié)果表明,由于免疫規(guī)劃在多樣性方面優(yōu)于遺傳規(guī)劃,因此在幾乎相同的條件下,基于免疫規(guī)劃的排序?qū)W習算法的性能更為優(yōu)越。

【關鍵詞】：
【學位授予單位】：山東大學
【學位級別】：博士
【學位授予年份】：2009
【分類號】：TP181
【目錄】：

下載全文 更多同類文獻

CAJ全文下載

(如何獲取全文？ 歡迎：購買知網(wǎng)充值卡、在線充值、在線咨詢)

CAJViewer閱讀器支持CAJ、PDF文件格式

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 何加浪;張琨;張宏;;進化計算在軟件智能修復中的應用[J];計算機工程;2011年16期

2 張宇山;郝志峰;黃翰;;二元進化策略的收斂性分析[J];計算機科學;2011年07期

3 蔡昭權;羅偉;張宇山;黃翰;羅勇為;;Lévy變異進化規(guī)劃算法的計算時間分析[J];計算機科學;2011年09期

4 王麗芳;曾建潮;洪毅;;利用Copula函數(shù)估計概率模型并采樣的分布估計算法[J];控制與決策;2011年09期

5 吳延科;;隨機因素對PSO算法的性能影響分析[J];文山學院學報;2011年03期

6 周傳華;謝安世;;一種基于動態(tài)小生境的自組織學習算法[J];軟件學報;2011年08期

7 陳皓;崔杜武;;基于族群進化計算的多項式回歸電力負荷預測[J];軟件;2011年05期

8 張超群;鄭建國;王翔;;蜂群算法研究綜述[J];計算機應用研究;2011年09期

9 劉寧;劉雪瑞;;GPS軟件接收機精確載波頻率捕獲算法分析與實現(xiàn)[J];全球定位系統(tǒng);2011年02期

10 楊治秋;;基于遺傳算法的功能可重構(gòu)數(shù)字體系研究[J];微計算機信息;2011年08期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 黎明;周琳霞;楊小芹;;圖像的進化計算分割法[A];中國圖象圖形學會第十屆全國圖像圖形學術會議（CIG’2001）和第一屆全國虛擬現(xiàn)實技術研討會（CVR’2001）論文集[C];2001年

2 褚德欣;;進化計算及其在智能控制中的應用[A];山西省科學技術情報學會學術年會論文集[C];2004年

3 楊光;林鴻;方鋒;;廣州市似大地水準面精化及成果應用[A];現(xiàn)代空間定位技術應用研討交流會論文集（第5卷 第3集）[C];2007年

4 甄登春;;初探重慶主城區(qū)的似大地水準面精化[A];重慶市測繪學會第三屆優(yōu)秀論文評選獲獎論文暨2005-2006年度學術交流會論文選編[C];2008年

5 趙清杰;楊波;;基于進化計算的BP網(wǎng)權值訓練算法及其應用探討[A];1998年中國智能自動化學術會議論文集（下冊）[C];1998年

6 呂崗;趙鶴鳴;;一種優(yōu)化前向神經(jīng)網(wǎng)絡權值的免疫算法[A];2003年中國智能自動化會議論文集（上冊）[C];2003年

7 范新云;;GPS水準法擬合似大地水準面精化的研究[A];第二十一屆海洋測繪綜合性學術研討會論文集[C];2009年

8 范新云;;GPS水準法擬合似大地水準面精化的研究[A];中國航海學會航標專業(yè)委員會測繪學組學術研討會學術交流論文集[C];2009年

9 柯益華;胡學姝;;油氣田產(chǎn)量預報Г模型參數(shù)估計的進化計算[A];2001年中國智能自動化會議論文集（下冊）[C];2001年

10 張全德;;精化區(qū)域似大地水準面技術方法與設計[A];中國測繪學會2006年學術年會論文集[C];2006年

中國重要報紙全文數(shù)據(jù)庫 前10條

1 ;[N];國際商報;2000年

2 記者 翟敏;[N];上海證券報;2011年

3 記者 翟敏;[N];上海證券報;2011年

4 記者 翟敏;[N];上海證券報;2011年

5 記者 楊勇;“烏龍合同”涉嫌虛假信披 彩虹精化復牌地量跌停[N];第一財經(jīng)日報;2011年

6 梅雪榮;[N];中國經(jīng)濟時報;2011年

7 記者 施浩;產(chǎn)能釋放+毛利提升 天馬精化今年業(yè)績或超預期[N];上海證券報;2011年

8 記者 魏夢杰;[N];上海證券報;2011年

9 記者 吳正懿;[N];上海證券報;2011年

10 記者 翟敏;[N];上海證券報;2011年

中國博士學位論文全文數(shù)據(jù)庫 前10條

1 王帥強;基于進化計算的行為模型自動精化和排序?qū)W習方法的研究[D];山東大學;2009年

2 尹文君;面向不確定制造過程調(diào)度問題的進化計算方法及其應用[D];清華大學;2004年

3 王志春;基于進化計算的復雜分類算法研究及應用[D];天津大學;2010年

4 楊海軍;進化計算中的模式理論、涌現(xiàn)及應用研究[D];天津大學;2004年

5 李智歡;無功優(yōu)化進化計算的局部搜索策略及多目標處理方法[D];華中科技大學;2010年

6 呂崗;免疫算法及其應用研究[D];中國礦業(yè)大學（北京）;2003年

7 薛明志;進化計算與小波分析若干問題研究[D];西安電子科技大學;2004年

8 石振國;資源網(wǎng)絡的精化學習及應用研究[D];上海大學;2011年

9 楊開兵;基于進化計算的多目標流水車間批組調(diào)度問題研究[D];大連理工大學;2011年

10 陳昊;動態(tài)環(huán)境下進化計算的研究[D];南京航空航天大學;2011年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 龐巍;進化計算算法在路徑優(yōu)化問題應用的研究[D];吉林大學;2004年

2 安磊;一種基于遺傳算法的數(shù)據(jù)挖掘技術的研究與應用[D];河海大學;2001年

3 彭軒;遺傳算法及其在圖像分割中的應用[D];吉林大學;2006年

4 費璐璐;進化計算在作物生長模型優(yōu)化中的應用研究[D];華東師范大學;2004年

5 華潔;函數(shù)聚類及其進化計算知識獲取研究[D];西安理工大學;2010年

6 汪晗;基于進化計算的多目標優(yōu)化與決策方法研究[D];中國人民解放軍國防科學技術大學;2002年

7 彭偉民;基于線性變換的適應度函數(shù)及機器人進化計算研究[D];廣東工業(yè)大學;2006年

8 于曉輝;進化計算和人工神經(jīng)網(wǎng)絡在多目標優(yōu)化問題中的應用[D];山東師范大學;2004年

9 藍海;CIMS環(huán)境下的數(shù)據(jù)倉庫與數(shù)據(jù)挖掘應用研究[D];清華大學;2002年

10 王麗愛;研究思維進化計算的多峰優(yōu)化性能及研究算法參數(shù)對效率的影響[D];太原理工大學;2004年

  本文關鍵詞：基于進化計算的行為模型自動精化和排序?qū)W習方法的研究，由筆耕文化傳播整理發(fā)布。