遗传程式设计基因规划法课件.ppt
第 10 講 演化計算:演化策略 及遺傳程式設計,演化策略 遺傳程式設計 總結,另一個模擬自然演化的方法是20世紀60年代早期在德國提出的。和基因演算法不同，這種稱為演化策略的方法用於解決技術最佳化的問題。,演化策略,1963年，柏林技術大學的兩個學生Ingo Rechenberg和Hans-Paul Schwefel致力於研究流體的最佳化形狀。在工作中，他們使用了Institute of Flow Engineering的風洞。由於這是一個艱苦且需要依靠直覺的工作，他們決定按照自然突變的例子來隨機改變形狀的參數，結果便產生了演化策略。演化策略是可替代工程師直覺的一種方法。和基因演算法不同，演化策略僅用到突變運算。,演化策略,演化策略最簡單的形式是(1+1)演化策略，即使用常態分佈突變使每代一個雙親只產生一個後代。(1+1)演化策路的實現方法如下：,定義每個參數的標準差和需要最佳化的函數。,步驟 1:選擇表示問題的N個參數，然後確定每個參數的可行的範圍：,步驟 2:在每個參數各自的可行範圍內隨機選擇初始值。這些參數值的集合就是親代參數的初始種群：,x1,x2,.,xN,X=f(x1,x2,.,xN),步驟 3:計算親代參數的解決方案：,步驟 4:透過增加常態分佈的隨機變數a(其均值為0)及預先定義的變異數為每個親代參數建立新的參數(後代)：,均值為0的常態分佈的突變反映了演化的自然過程，即較小變化的發生的機率遠遠大於較大的變化發生的機率。步驟 5:計算後代參數的解決方案：,i=1,2,.,N,步驟 6:比較子代參數和親代參數的解決方案。如果子代的解決方案比較好，就用子代種群替代親代種群。否則，保留親代參數。步驟 7:回到步驟4，重複這個過程，直到得到滿意的解決方案，或者達到了指定的遺傳代數為止。,演化策略反映了染色體的本質。單個的基因可能會同時影響到生物體的幾個特徵。另一方面，生物體的單個特徵也可能由幾個基因同時確定。自然選擇作用在一組基因而不是單個基因上。,電腦科學的一個核心問題就是如何能讓電腦在沒有明確程式設計的情況下知道如何解決問題。遺傳程式設計提供了解決這個問題的方法，即透過自然選擇的方法來使電腦程式演化。實際上遺傳程式設計是傳統基因演算法的擴展，但遺傳程式設計的目的不僅僅是用位元字串來表示問題，而是要編寫解決問題的程式。,遺傳程式設計(基因規劃法)genetic programming,遺傳程式設計是演化計算領域最新發展成果。在20世紀90年代，John Koza對遺傳程式設計的發展產生了很大的作用。根據Koza的理論，遺傳程式設計為非常適合待解決的問題的程式搜尋電腦程式設計的可能空間。任何的電腦程式都是應用到值(參數)的一系列運算(函數)。但不同的程式語言包含有不同的描述、運算及語法限制。,由於遺傳程式設計是用遺傳運算來操作程式，因此，程式語言應該允許電腦程式可以像資料一樣運算，並且新建立的資料可以作為程式執行。由於上述的原因，通常選擇LISP作為遺傳程式設計的主要語言。,LISP具有高度符號導向的結構。其基本資料結構是原子和表。原子是LISP語法中不可分割的最小元素。數字 21，符號 X 和字串“This is a string”都是LISP原子的例子。表是由原子或其他表組成的物件。LISP表可以寫為圓括號中項目的有序集合。,LISP 結構,例如：此表要求呼叫減號函數(-)處理兩個引數，也就是表(*AB)和原子C。首先，LISP對原子A和B使用乘函數(*)，得到列表(*AB)的結果，然後用減函數(-)計算整個(-(*AB)C)的結果。,(-(*A B)C),LISP 結構,原子和表都稱作符號運算式或S運算式。在LISP中，所有的資料和程式都是S運算式。因此，LISP可以像運算元一樣運算程式。也就是說，LISP程式可以修改它們自己，甚至編寫出其他的LISP程式。LISP的這個重要的特點對於遺傳程式設計而言非常有吸引力。任何LISP的S運算式都可以表達成一棵用節點標記成有根的、具有有序分支的樹。,LISP S運算式的表示圖,LISP S運算式(-(*AB)C),如何使用遺傳程式設計來解決問題？在使用遺傳程式設計來解決問題前，必須先執行五個預備步驟：,(1)確定終端集合。(2)選擇基本函數集。(3)定義適應性函數。(4)確定控制執行的參數。(5)選擇指定執行結果的方法。,可以用畢氏定理來說明這些預備步驟，並證明遺傳程式設計的潛力。畢氏定理說明，直角三角形的斜邊c和兩個直角邊a、b有以下關係：,遺傳程式設計的目的是找到和這個函數匹配的程式。,為了測量至今還未發現的電腦程式的性能，我們在這裏使用不同的適應性案例。畢氏定理的適應性案例用表7-4所示的直角三角形表示。這些適應性案例是在變數a和b的範圍內隨機選擇的。,步驟 1:確定終端集合 找到與電腦程式的輸入相對應的終端。本例中有兩個輸入，a 和 b。步驟 2:選擇基本函數集 函數可以用標準算術運算、標準程式設計運算、標準數學函數、邏輯函數或特定領域的函數來表示。本例使用標準算術函數+、-、*、/和一個數學函數 sqrt。,步驟 3:定義適應性函數 適應性函數用來評估某個電腦程式解決問題的能力。適應性函數的選擇取決於要解決的問題。每個問題的適應性函數可能有很大不同。本例中，電腦程式的適應性可以透過程式產生的實際結果和適應性案例給出的結果之間的誤差來衡量。一般情況下，只有一個案例時不測量誤差，而是要計算一組適應性案例的絕對誤差的總和。總和越接近於0，電腦程式就越好。,步驟 4:確定控制執行的參數 為了控制執行，遺傳程式設計使用的主要參數和基因演算法一樣。它包含種群大小和最大遺傳代數。步驟 5:選擇指定執行結果的方法 通常在遺傳程式設計中指定目前最好的遺傳程式的結果作為執行結果。,一旦這五個步驟執行完畢，就可以開始執行 了。遺傳程式設計的執行從電腦程式的初始種 群的隨機選擇的一代開始。每個程式由+、-、*、/和 sqrt 以及終端節點 a、b 組成。在最初的種群中，所有電腦程式的適應性都很 差，但某些個體的適應性要比其他個體好。就 像適應性較強的染色體被選中進行繁殖的機率 更高一樣，適應性較好的電腦程式透過複製自 己進入下一代的機率也更高。,遺傳程式設計中的交配:,兩個親代的 S運算式,遺傳程式設計中的交配:,兩個子代的 S運算式,突變運算可以任意改變LISP的S運算式中的函數或終端。在突變中，函數僅能用函數取代，終端也僅能用終端取代。圖7-16解釋了遺傳程式設計中突變的基本概念。,遺傳程式設計中的突變,原始 S運算式,遺傳程式設計中的突變:,遺傳程式設計中的突變:,突變後的 S運算式,步驟 1:指定執行的最大遺傳代數以及複製、交配和突變的機率。注意，複製、交配和突變三者機率的和必須為1。步驟 2:產生長度為N、由隨機選擇的終端和函數組成的電腦程式的初始種群。,總之，遺傳程式設計透過執行下述步驟來建立電腦程式：,步驟 3:在種群中執行每個電腦程式，用合適的適應性函數計算其適應性，指定最好的個體作為執行的結果。步驟 4:用指定的機率選擇遺傳運算，以執行複製、交配和突變。,步驟 5:如果選擇的是複製運算，則從現有種群中選擇一個程式，複製該程式後將其放入下一代種群中。如果選擇的是交配運算，則從現有種群中選擇一對程式，建立一對後代程式放入下一代種群中。如果選擇的是突變運算，則從現有種群中選擇一個程式，執行突變運算並將其突變的結果放入下一代種群中。,步驟 6:重複執行步驟4，直到新種群的程式數量和初始種群一樣多(等於N)為止。步驟 7:用新的(子代)種群取代目前的(親代)種群。步驟 8:回到步驟3，重複執行，直到達到滿足終止條件為止。,最好的S運算式的適應性,遺傳程式設計和基因演算法使用相同的演化方法。但是遺傳程式設計不再用位元字串表示編碼方法，而是用完整的電腦程式解決具體的問題。基因演算法最基本的困難在於問題的表達，也就是固定長度的編碼，表達效果不佳限制了基因演算法的能力，甚至導致錯誤的結論。,和基因演算法相比，遺傳程式設計的優點是什麼？,固定長度的編碼相當的困難。由於不能提供長度的動態變化，這樣的編碼經常會導致相當大的冗餘，從而降低了遺傳搜尋的效率。相反，遺傳程式設計使用高層可變長度的元件，其大小和複雜性可以在繁殖中改變。遺傳程式設計在很多不同場合中都可以使用，它有很多有潛力的應用。,
