《文法演化的模型理論》是依託長沙理工大學，由何錇擔任項目負責人的面上項目。
基本介紹
- 中文名：文法演化的模型理論
- 項目類別：面上項目
- 項目負責人：何錇
- 依託單位：長沙理工大學
項目摘要,結題摘要,
項目摘要
文法演化（GE）是十分重要的遺傳程式設計方法，套用面很廣，特別適合類型、領域知識的刻畫，被視為解決多目標決策問題、軟體復用工程、CASE等複雜問題分析和設計的強有力的工具。研究旨在建立具有明顯性能優勢的文法演化理論，即文法演化的模型理論（MGE）。內容包括演化框架、基因模組性、個體的抽象表示、解釋器、複雜性等方面的理論、技術和方法。研究貢獻在於率先以文法為手段獲得模組描述的創新方法和關鍵技術的突破；以有窮自動機為工具系統地、可視地揭示文法形式概念、解的推導和演化的不確定性之間的關係。為此，開展MGE研究非常重要，它為利用形式化方法探究高性能GE的設計開闢了新途徑。
結題摘要
遺傳程式設計（Grnrtic Programming, GP）是Koza借鑑遺傳算法（Genetic Algorithm，GA）思想設計的自動程式設計方法。本課題就套用十分廣泛的一類GP變體，即文法演化（Grammatical Evolution，GE），進行了深入探討,涉及演化框架，基因的模組性，個體表示等。所以選用GE進行研究,是因為它有很強描述力,還可對接嵌入其他GP變體、智慧型計算方法。 文法演化（Grammatical Evolution, GE）最早由Ryan、O’Neill等共同提出，爾後經由許多研究者不斷完善。由於引入了文法，GE在諸多方面優於GP，如易於描述類型和領域知識，在研究、實踐者中贏得廣泛關注。 給定一個2型文法，GE算法可由GP算法結構修正如下： (a) 創建由若干密碼子序列（即個體）構成的初始種群； (b) 依據所謂基因型到表現型（genotype-to-phenotype, g2p）的轉換法則將個體譯為程式。 (c) 評估個體的適應值； (d) 用遺傳運算元產生新個體和種群；如果終止條件成立，則結束演化過程，否則繼續執行步驟b。 表示是GP（包括這裡的GE）研究領域的公開性難題，與GP高性能實現有著密切關係。理想的表示方法一般宜滿足以下要求，而這正是現有GE所欠缺的。 (a) 可理解性要好； (b) 功能描述的重用性要好，並且便於開展塊意義上的結構分析和語義重用； (c) 有助評估性能的提升。 為解決GE的以上缺陷，我們從模型角度對它進行了深入研究，提出基於模型的文法演化（Model-based Grammatical Evolution，MGE）方法. 新方法中，個體由產生式序列表示，因而它們可以表示為具有語義承載能力的正規式，既方便塊結構、模式的定義與描述，又便於利用形式語言學有關成就、結論進行系統化的科學處理。在此基礎上，我們可以看到：MGE沒有散失精準性和描述力，但較GE有效率性能的明顯提升；確立深度優先解碼原則下，不僅GE，而且GEP（Gene Expression Programming）等都能統一到具有語義承載能力的正規式表示基礎上。這為統一GP變體的統一性研究奠定了基礎。MGE是一個高性能GE平台，也可以嵌入其他GP變體，智慧型計算方法。為此，還開展了相關計算智慧型方法研究，為日後融合、深化套用做了鋪墊。
