研究主軸 > 基因演算法(Genetic Algorithms)
   
   
簡介  
         
 

基因演算法(Genetic Algorithms,簡稱GA,有人稱之遺傳演算法或者基因遺傳演算法)可以追溯到1950年代,生物學

   
 

者和電腦學家合作,嘗試在電腦上模擬出基因的運作。緊接著在1960年代初期,密西根大學的約翰.賀藍(John

   
 

Holland)和他的同事們將電腦化的遺傳學-染色體、基因、配對基因、適配函數等-應用到其到許多領域。

   
       
 

1967年,一位賀藍的學生貝格力(J.D. Bagley)在其畢業論文中首度創用了「基因演算法」這個名詞,來描述這種最

   
 

適化的技術。然而,許多學者質疑,因為基因演算法相當倚賴隨機選擇,而這些選擇是任意且不可預測的。開啟

   
 

遺傳演算法大門的賀藍博士(Dr. John Holland),於1975年在密西根大學發表了闡述自然與人工系統的適應問題著作

   
 

(Holland, 1975),該書總結了賀藍博士二十年來對於學習、演化與創造的研究心得,此文奠定了遺傳演算法的發展

   
 

基礎與思考架構。

   
       
 

在基因演算法中我們稱每一個體稱為染色體(Chromosome),每一染色體的基因的值是由亂數產生,而每一世代

   
 

的染色體所成的集合稱做群體(Population)。在每一世代中的每一個染色體互相競爭,較適合生存環境的有較高

   
   

的適存值(Fitness value),而有較高的適存值的染色體可以複製出較多的子代,然後從其中選擇配對來交配(

   
   

Crossover )產生下一代,以期可以產生適存度更高的下一代。再者,為了避免錯過某些有用的資訊,乃加入突變

   
   

(Mutation)的處裡,以產生出有用的資訊,不過一般而言,突變率(Mutation Rate )通常是很低的。

   
         
 

如此一代一代的演化下去,將產生適存值較高的染色體,而該染色體即是我們需要的解。遺傳演算法的限制為在

   
   

搜尋解答時不保證找到真正的最佳解,而是找出近似解,但此近似最佳解是經過廣大解答空間演化到某種程度的

   
   

可能最適解。對於若干無法預知最佳解的狀況下,遺傳演算法可以快速求得某種程度之滿意解。因此適合非線性

   
   

等多變數複雜問題之求解。

   
         
   

遺傳演算法的基本運算為選擇、交配和突變等機制,而這些機制之操作狀態通常是根據隨機值而改變的,因此即

   
 

使在環境參數完全固定不變下,每一次運算求解所得之答案可能並不相同。

   
       
回研究主軸