複製鏈接
請複製以下鏈接發送給好友

遺傳程序

鎖定
遺傳程序是John Koza與遺傳算法相關的一個技術,在遺傳程序中,並不是參數優化,而是計算機程序優化。
中文名
遺傳程序
領    域
最優化理論

遺傳程序簡介

遺傳程序是John Koza與遺傳算法相關的一個技術,在遺傳程序中,並不是參數優化,而是計算機程序優化。遺傳程序一般採用樹型結構表示計算機程序用於進化,而不是遺傳算法中的列表或者數組。一般來説,遺傳程序比遺傳算法慢,但同時也可以解決一些遺傳算法解決不了的問題。 [1] 

遺傳程序遺傳算法

遺傳算法(英語:genetic algorithm (GA))是計算數學中用於解決最優化的搜索算法,是進化算法的一種。進化算法最初是借鑑了進化生物學中的一些現象而發展起來的,這些現象包括遺傳突變自然選擇以及雜交等。
遺傳算法通常實現方式為一種計算機模擬。對於一個最優化問題,一定數量的候選解(稱為個體)可抽象表示為染色體,使種羣向更好的解進化。傳統上,解用二進制表示(即0和1的串),但也可以用其他表示方法。進化從完全隨機個體的種羣開始,之後一代一代發生。在每一代中評價整個種羣的適應度,從當前種羣中隨機地選擇多個個體(基於它們的適應度),通過自然選擇和突變產生新的生命種羣,該種羣在算法的下一次迭代中成為當前種羣。 [1] 

遺傳程序遺傳編程

遺傳編程或稱基因編程,簡稱GP,是一種從生物演化過程得到靈感的自動化生成和選擇計算機程序來完成用户定義的任務的技術。從理論上講,人類用遺傳編程只需要告訴計算機“需要完成什麼”,而不用告訴它“如何去完成”,最終可能實現真正意義上的人工智能:自動化的發明機器。
遺傳編程是一種特殊的利用進化算法機器學習技術,它開始於一羣由隨機生成的千百萬個計算機程序組成的“人羣”,然後根據一個程序完成給定的任務的能力來確定某個程序的適合度,應用達爾文自然選擇(適者生存)確定勝出的程序,計算機程序間也模擬兩性組合,變異基因複製,基因刪除等代代進化,直到達到預先確定的某個中止條件為止。
遺傳編程的首批試驗由斯蒂芬·史密斯(1980年)和Nichael·克拉姆(1985年)發表。約翰·Koza(1992年)也寫了一本著名的書,《遺傳編程:用自然選擇讓計算機編程》(ISBN 9780262111706),來介紹遺傳編程。
使用遺傳編程的計算機程序可以用很多種編程語言來寫成。早期(或者説傳統)的GP實現中,程序的指令和數據的值使用樹狀結構的組織方式,所以那些本來就提供樹狀組織形式的編程語言最適合與GP,例如Koza使用的Lisp語言。其他形式的GP也被提倡和實現,例如相對簡單的適合傳統編程語言(例如Fortran、BASIC和C語言)的線性遺傳編程。有商業化的GP軟件把線性遺傳編程和彙編語言結合來獲得更好的性能,也有的實現方法直接生成彙編程序。
遺傳編程所需的計算量非常之大(處理大量候選的計算機程序),以至於在90年代的時候它只能用來解決一些簡單的問題。近年來,隨着遺傳編程技術自身的發展和中央處理器計算能力的指數級提升,GP開始產生了一大批顯著的結果。例如在2004年左右,GP在多個領域獲取近40項成果:量子計算、電子設計、遊戲比賽、排序搜索等等。這些計算機自動生成的程序(算法)中有些與2000年後人工產生的發明十分類似,甚至有兩項結果產生了可以申請專利的新發明。
在90年代,人們普遍認為為遺傳編程發展一個理論十分困難,GP在各種搜索技術中也處於劣勢。2000年後,GP的理論獲取重大發展,創建確切的GP概率模型和馬爾可夫鏈模型已成為可能。遺傳編程比遺傳算法適用的範圍更廣(實際上包含了遺傳算法)
除了生成計算機程序,遺傳編程也被用與產生可發展的硬件。Juergen Schmidhuber進一步提出了宏遺傳編程,一種使用遺傳編程來生成一個遺傳編程系統的技術。一些評論認為宏遺傳編程在理論上不可行,但是需要更多的研究來確認。 [1] 

遺傳程序參見

參考資料
  • 1.    Poli, R., Langdon, W. B., McPhee, N. F. A Field Guide to Genetic Programming. Lulu.com, freely available from the internet. 2008. ISBN 978-1-4092-0073-4.