基于進(jìn)化計(jì)算的行為模型自動(dòng)精化和排序?qū)W習(xí)方法的研究.pdf

1、進(jìn)化計(jì)算是研究仿照生物進(jìn)化自然選擇過程中所表現(xiàn)出來的優(yōu)化規(guī)律和方法，以解決復(fù)雜的工程技術(shù)領(lǐng)域或其他領(lǐng)域的優(yōu)化問題的一種計(jì)算方法。隨著進(jìn)化計(jì)算自身的發(fā)展，一些新的進(jìn)化計(jì)算方法在不斷的提出，而一些舊的方法也在煥發(fā)著新的活力。
　　 近些年，在一些領(lǐng)域中的某些問題的研究中，傳統(tǒng)的方法遇到了很大的困難，例如在軟件工程領(lǐng)域中的模型精化問題；而在一些領(lǐng)域中，某些問題利用傳統(tǒng)的人工智能方法不能得到很理想的結(jié)果，例如信息檢索領(lǐng)域中的排序?qū)W習(xí)問題

2、。這些問題都促使我們從進(jìn)化計(jì)算的角度重新審視，以期利用自然進(jìn)化的思想對(duì)他們進(jìn)一步處理，從而得到理想的結(jié)果。
　　 基于以上的應(yīng)用背景和需求，本文重點(diǎn)研究了利用進(jìn)化計(jì)算相關(guān)算法解決傳統(tǒng)方法難以處理的某些問題；并以此為基礎(chǔ)，開發(fā)了一系列的原型系統(tǒng)對(duì)研究成果進(jìn)行了驗(yàn)證。本文主要的研究?jī)?nèi)容和創(chuàng)新點(diǎn)包括以下方面：
　　 1對(duì)軟件系統(tǒng)中行為的建模和精化理論的研究。本論文根據(jù)自動(dòng)精化方法必須的條件，提出了一套描述行為模型的形式化符號(hào)體

3、系，并據(jù)此提出了行為模型的形式化建模方法和行為精化理論。行為建模方法和行為模型的自動(dòng)精化方法的提出，為推動(dòng)模型驅(qū)動(dòng)開發(fā)理論，尤其是UML和形式化方法集成建模技術(shù)的發(fā)展和應(yīng)用，將會(huì)起到巨大的推動(dòng)作用。
　　 在模型驅(qū)動(dòng)開發(fā)中，行為的建模和精化是一個(gè)關(guān)鍵問題，它需要考慮對(duì)象的一系列的動(dòng)作語(yǔ)義，包括動(dòng)作在何時(shí)觸發(fā)，系統(tǒng)狀態(tài)如何變化，以及行為執(zhí)行結(jié)束后最終狀態(tài)如何描述等等。由于UML在模型語(yǔ)義等方面的缺失，以及形式化方法和UML混合建模

4、研究的廣泛開展，使得我們不得不采用以集合論和謂詞邏輯為基礎(chǔ)的形式化建模方法，對(duì)行為進(jìn)行精確的建模并逐步精化至代碼。近幾十年中，盡管有很多精化理論和精化工具相繼提出，但總體而言，傳統(tǒng)的關(guān)于精化方面的研究主要考慮的是整個(gè)軟件系統(tǒng)模型的精化定義和驗(yàn)證問題。隨著UML和形式化方法集成建模的研究的廣泛開展，形式化建模方法所關(guān)注的領(lǐng)域轉(zhuǎn)變?yōu)檐浖到y(tǒng)的對(duì)象行為的細(xì)節(jié)。在這方面，國(guó)內(nèi)外并沒有相關(guān)的專門用于描述行為精化的思想提出，而傳統(tǒng)的基于整個(gè)系統(tǒng)的精

5、化顯得過于龐大，對(duì)于我們的問題并不十分合適。因此，行為精化理論的提出，是一個(gè)亟待解決的重要問題。
　　 根據(jù)自動(dòng)精化方法必須的條件，參照前人的工作，我們提出了一套描述行為模型的形式化符號(hào)體系，并據(jù)此提出了行為模型的形式化建模方法和行為精化理論。本文根據(jù)行為精化理論，從問題求解的角度上，提出了一種實(shí)現(xiàn)行為精化的一般性的指導(dǎo)思想，即通過搜索狀態(tài)空間，從而找到一個(gè)可以滿足特定條件的狀態(tài)，進(jìn)而得到精化結(jié)果。通過估計(jì)狀態(tài)空間可以證明，遍歷

6、式的窮盡搜索辦法是不可行的，必須引入啟發(fā)式的智能搜索機(jī)制。
　　 2對(duì)基于遺傳規(guī)劃的行為模型自動(dòng)精化方法的研究。本論文提出了一種基于遺傳規(guī)劃的自動(dòng)精化方法，它為形式化模型的自動(dòng)精化方法提供了一個(gè)新的思路，同時(shí)為UML和形式化方法集成建模方法的推廣和應(yīng)用提供了更加有效的工具支持。
　　 軟件開發(fā)的模型化和自動(dòng)化是軟件技術(shù)的發(fā)展趨勢(shì)，而缺乏自動(dòng)精化方法是阻礙形式化方法在業(yè)界應(yīng)用的一個(gè)重要原因。在本文中我們提出了一種基于遺傳規(guī)

7、劃的自動(dòng)精化方法。
　　 由于遺傳規(guī)劃算法源自于遺傳算法，它也有其自身的弱點(diǎn)，最突出的問題就是它最適合線性結(jié)構(gòu)的問題求解邏輯，而不能有效地處理顯式的循環(huán)結(jié)構(gòu)和選擇結(jié)構(gòu)。為了解決上述問題，我們提出了一種基于謂詞邏輯的遺傳規(guī)劃方法。首先，對(duì)抽象模型的后置條件進(jìn)行自下而上的歸約精化，以生成顯式的循環(huán)結(jié)構(gòu)并將問題簡(jiǎn)化和分解；然后將生成的子問題采用基于遺傳規(guī)劃的精化方法進(jìn)一步精化，將行為模型的精化看作一個(gè)問題求解最終得到實(shí)現(xiàn)模型，通過基于

8、遺傳規(guī)劃的方法最終得到一個(gè)由若干基本操作組合而成的具體行為。我們還提出了一種在遺傳規(guī)劃中采用組合終止條件的方法，用以生成選擇結(jié)構(gòu)；最后，我們提出一種對(duì)實(shí)現(xiàn)模型的優(yōu)化方法，以減少實(shí)現(xiàn)模型中操作邏輯的冗余。根據(jù)我們提出的方法，成功的演化出了冒泡排序算法。
　　 事實(shí)上，本方法具有一定的通用性，它適用于任何由若干基本操作組合以完成復(fù)雜操作的問題求解過程。
　　 3對(duì)基于進(jìn)化計(jì)算的排序?qū)W習(xí)的研究。本論文提出了基于進(jìn)化計(jì)算的排序函

9、數(shù)發(fā)現(xiàn)算法的框架；并根據(jù)該框架，提出一種基于免疫規(guī)劃的排序?qū)W習(xí)方法RankIP，并得到了很好的性能，有力的證明了我們提出的基于排序?qū)W習(xí)算法框架的有效性。本論文的研究將有力的促進(jìn)進(jìn)化計(jì)算方法在排序?qū)W習(xí)問題的應(yīng)用。
　　 網(wǎng)頁(yè)排序問題是Web信息檢索領(lǐng)域的一個(gè)中心問題，一個(gè)好的排序算法能夠明顯的提高檢索質(zhì)量。傳統(tǒng)的網(wǎng)頁(yè)排序算法分為三類：基于鏈接的方法、基于內(nèi)容的方法和混合方法。此外，基于機(jī)器學(xué)習(xí)技術(shù)的網(wǎng)頁(yè)排序算法，即“排序?qū)W習(xí)”，越

10、來越廣泛的用來解決信息檢索排序問題。這一問題作為信息檢索和機(jī)器學(xué)習(xí)的交叉領(lǐng)域，已經(jīng)成為非?；钴S的一個(gè)研究熱點(diǎn)，并引起廣泛關(guān)注。目前提出的各種排序?qū)W習(xí)算法，其結(jié)果都不甚理想。
　　 一些學(xué)者依據(jù)進(jìn)化計(jì)算的思想，提出了基于遺傳規(guī)劃的排序?qū)W習(xí)方法；而最近包括群智能算法，免疫算法等一系列性能更為優(yōu)異的進(jìn)化計(jì)算方法的提出，也為基于進(jìn)化計(jì)算的排序?qū)W習(xí)方法提供了更加有力的工具。在這個(gè)基礎(chǔ)上，我們介紹了一系列的定義，精確的表達(dá)了基于進(jìn)化計(jì)算的排

11、序函數(shù)發(fā)現(xiàn)算法的一般原理；并且描述了基于進(jìn)化計(jì)算的排序函數(shù)發(fā)現(xiàn)算法的框架，使得任何的進(jìn)化計(jì)算方法都可以靈活的嵌入算法框架中。算法框架的提出，將有力的促進(jìn)進(jìn)化計(jì)算方法在信息檢索領(lǐng)域，尤其是排序?qū)W習(xí)問題的應(yīng)用。
　　 根據(jù)我們提出的基于進(jìn)化計(jì)算的排序函數(shù)發(fā)現(xiàn)的算法框架，在本文中我們還提出一種基于免疫規(guī)劃的排序?qū)W習(xí)方法RankIP。我們采用微軟亞洲研究院提供的LETOR2.0數(shù)據(jù)集合作為訓(xùn)練和驗(yàn)證數(shù)據(jù)集合，實(shí)驗(yàn)證明RankIP較之其他