如果您无法下载资料,请参考说明:
1、部分资料下载需要金币,请确保您的账户上有足够的金币
2、已购买过的文档,再次下载不重复扣费
3、资料包下载后请先用软件解压,在使用对应软件打开
基因演算法(GeneticAlgorithms)也和記憶基礎理解及類神經網路相同,是建立在類比生物思考過程之上。數百萬年來物競天擇使生物不斷進化,也更適應環境,生存下來的適者會藉由繁衍,將自身的基因傳遞給下一代。增加個體對環境的適應性來解決問題。基因演算法常被應用在三個領域:訓練類神經網路生成記憶基礎理解的評分函數排程的最適化功能等。其中最普遍的,就是用來訓練類神經網路。目前許多類神經網路都將基因演算法列為訓練的選項之一。密西根大學的約翰.賀藍(JohnHolland)首創用了『基因演算法』,發展出這項技術有力的理論基礎。他在理論中描述了基因演算法是如何運作,以及基因如何巧妙地創造了適應生存的物種。資料採礦著重是分類,預測,而不是最適化,儘管許多資料採礦的問題可以視作最適化問題。一個典型的資料採礦問題,是根據某項產品前一週的銷售量及其特性等等,預測其存貨量。換成最適化的方式,問題就變:『哪一種函數與存貨曲線是最吻合,可用來預測。』使用統計迴歸是一種方式,類神經網路是另一方式,基因演算法則提供了另一種可能性。遺傳學概述:在比較高等的動物中,這些傳遞下來的DNA藉由雜交融合了其它適者的DNA,這種技術稱之為雜交(Crossover)。有時候傳遞基因給下一代的過程也會有出錯,稱之突變(mutation)。這所有的過程加起來,一代一代傳遞,使得生物高度適應其環境:這就是演化過程。一個簡單的例子來解釋基因演算法如何運作:在一個只有一個參數『p』簡單函數,p值為在0至31之間,該函數31p–p2見下圖。這個例子可視為一個基因組(genome),只含有一個5位元基因參數p。(需要5位元來表達0到31)這個函數的最大值出現在p為15與16時,分別以01111與10000代表。這個例子也顯示即使有數個最適狀態,基因演算法依然適用。電腦上的遺傳學我們必須選擇所謂的適配函數(fitnessfunction)來解決這個問題。在這個例子裡,適配函數就是31p–p2,然後進行以下一些步驟:定義基因組以及適配函數,創造第一代的基因組。2.藉由選擇,雜交,以及突變,來修訂起始群體。3.重複步驟2,直到這個群體不再進步為止。運用基因演算的第一個步驟就是設定問題。該基因組含有一個5位元基因參數p。如下表顯示,第一代有四個隨產生的基因組。平均適配值是117.75,已經相當不錯,不過基因演算法可以使其更為改善。基因p適配值101102217600011387000102581100125150如下圖所示,基本演算過程利用三個運算元來修訂起始群體-選擇(selection),雜交(crossover),及突變(mutation)。電腦上的遺傳學在我們的計算過程中,母群體的數量是保持恆定的,也就是說該群體不致滅種。基因組存活並繁衍的機率,與其適配值(fitnessvalue)成正比:值越高者,在下一代基因組中所佔比例就越高。按比例計算後,遺傳給下一代的數量通常是個分數,但是群體中基因組的數量卻絕對是整數。生存是建立在依照比例再任意選擇基因組的基準上。電腦上的遺傳學電腦上的遺傳學電腦上的遺傳學下一個運算元的因素則是雜交。雜交也發生在自然界中,將2組基因組原有的某一部分與另一組雜交,產生了新的2組基因組。如前圖所示,雜交發生在2組基因組之間,且發生的節點位置乃隨機決定。舉例來說:10110與00010這2組基因組在2與3之間的位置做雜交。過程如下:10∣11000∣010─────經過雜交後(加底線者為原本第2個基因組)10∣01000∣010新產生的基因組,稱為子嗣(children),皆繼承了來自雙親的某部份。雜交進行的過程就是選擇某一對基因後,再如擲銅板般隨機決定是否雜交基因。這個機率稱之為雜交機率(crossoverprobability),通常以pc表示。0.5的雜交機率(與擲銅板擲到人頭那一面的機率相同)通常會帶來好結果。在這個例子中,10110與00010這2個基因組被選擇在2與3位元之間的位進行雜交,如下表。經過選擇與雜交,母群體的平均適配值由117.75提高到178.5。這對僅僅經過一代是相當了不起的進步。基因p適配值100101823411001251500011061501011022176最後一種運算元的因素是突變。突變在自然界中極少發生,是因為親代在繁衍後代時,基因編碼產生了錯誤所致。在提高適應性上,選擇和雜交相當有助益,但與其原先的狀況有密切相關,隨機的特性也可能阻礙一些基因產生更好的組合。突變提供了另一種可能。自然界中,突變極少發生,在基因演算法裡其比例也很低,每一代的發生機率小於1為合理。假設接下來這一代第2個基因組第3個位元的位置發生了突變。下表顯示了經過突變後的基因組。如同