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

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

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

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

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

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

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

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

9、數(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習”，越

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

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