Make your own free website on Tripod.com


什麼是基因演算法? 林豐澤

詳細原稿


近年來演化計算 ( Evolutionary Computation)逐漸盛行,已吸引全世界許多學者投入這個研究的行列。簡單的說,演化計算是利用自然界演化的過程而形成的一種計算模式,藉以求解各種組合性最佳化問題。所謂自然演化過程就是指達爾文的進化論-”適者生存,不適者淘汰”的道理。在演化計算中以基因演算法 ( Genetic Algorithms)為最重要,它也是橫跨資訊工程與應用數學之領域。本文僅就基因演算法向同學們做一簡扼的背景介紹。

1.簡介

    基因演算法是於1970年左右由密西根大學John Holland教授及其學生所共同研發出來的。Holland本來在研究細胞自動機(Cellular automata),由此他探討自然與人工系統之適應調整問題而奠定出基因演算法之雛型。經過將近二十年的研究發展,基因演算法已被廣泛的應用於求解最佳化問題及人工智慧機器學習的領域上。最近幾年,基因演算法也被應用到模糊控制之領域,在模糊控制的規則設計中,設計者常用三角形或梯形來作為規則中模糊集合之隸屬函數;但是這些模糊集合的底集區間大小及函數的某些係數是否適當,常常需要靠try-and-error的方式來調整。基因演算法可來求得這些參數的最佳值,因而能改進控制的效率。到目前為止,似乎基因演算法是一個極有效且強健的搜尋最佳解技術,在自然科學與工程應用上有不錯的成績,但是基因演算法仍不能保證能夠得到全體最佳解,只能保證局部最佳解。儘管如此,此法已經被學術界公認是一種具有威力且可信賴的佳化方法之一。

2.基本觀念

    自然界的演化是發生在生物染色體(chromosome)的基因中,每一種生物之特徵係來自於該種生物上一代的基因排列,演化是指每一代之間基因所發生之變化。所謂適者生存是指這一代的基因排列係於上一代的基因排列而產生比上一代更優良更適應環境的世代。進化論就是因此有自然淘汰觀念而逐漸發展出來愈優秀的品種。基因演算法就是採用這種”survival-of-the-fitness”的觀念,把欲找尋的解答經過編碼,使用運算之程序而搜尋到問題所要求的”次最佳解”。而這些運算正是生物演化之程序:重生(reproduction)、交配(crossover)與突變(mutation)。於生物界實際的演化需要經過數百或數千年,可是在基因演算法使用Computer執行只要數秒內就完成了。

3.演算法則

一個基因演算法是由四個部分所構成的:

(1).編碼 (coding)

(2).適合函數 (fitness function)

(3).選擇方式 (selection mechanism)

(4).重生交配與突變。