基因演算法之基本概念、方法與國內相關研究概況〈都市與設計運算方法專題〉期末報告學生：黃衍明N78901010國立成功大學建築研究所博士班指導：林峰田教授壹、基因演算法之基本概念基因演算法（geneticalgorithms，GAs）與「演化策略」（evolutionstrategies，ESs）、「演化程式」（evolutionaryprogramming，EP）並稱為「演化演算法」（evolutionaryalgorithms，EAs）的三個主要分支研究，但近年來以基因演算法最受研究者所重視（B?ck,1996）。早於1960年代生物學家FraserA.S.便提出人為交換染色體DNA以刺激生物演化的方法，此便成為發展基因演算法之靈感來源（B?ck,1996）。成熟的基因演算法概念則首次出現於1975年JohnH.Holland大作AdaptationinNaturalandArtificialSystems（Holland,1975）1。Holland由自然界生物基因中DNA編碼與繁殖的原理中得到靈感，提出了基因演算的方法，用以模擬自然環境與人造環境中的一些現象。Holland認為，無論自然或人造環境，可以將事物依其屬性進行如基因DNA一樣的編碼（codingandrepresentation），並在物群之間藉由編碼的運算繁衍出「下一代」。透過函數設計可以遴選適合環境的「下一代」繼續參與繁衍，以此獲得較適合環境的物種。Holland在該書中認為，除了自然界生物基因學研究之外，經濟學、遊戲理論、模式辨識（Pattern-Recognition）、控制與函數最佳化（Optimization）等等領域當中，均有近似基因工程之現象。換言之，無論自然環境或人造環境，均可以運用基因演算法描述一些現象，或甚至預測某些未知現象之發生。Holland在該書所提示領域，幾乎指引出後來基因演算法所應用的範疇。貳、基因演算法之方法Holland在該書中除說明基因演算法的基本概念之外，亦奠定了基因演算法的方法原型。Holland指出基因演算法的三項基本操作（Geneticoperators），即「交配」（Cross-over）、「反轉」（inversion）與「突變」（Mutation）。這三個基本操作一直沿用至今，成為運算的核心部分。而後續的研究則提出比較周全的操作程序，詳述如下（Man,et.al.,1999）：1.染色體編碼：根據問題的屬性予以編碼，稱為「染色體」（chromosomeRepresentation），建立資料結構。較傳統的染色體編碼方法為位元串列（bitstring）。但也可以有不同的染色體編碼法，例如「圖」（graphs）。染色體11975版本原為UniversityofMichiganPress出版，1992年版本為MITPress出版基因演算法之基本概念、方法與國內相關研究黃衍明10-2編碼可以是目的導向的，可根據資料處理的目的而進行編碼；也可以是問題導向的，根據面臨問題的屬性選擇適合的染色體編碼法。2.目標函數與適應函數：目標函數（objectivefunctions，或稱評量函數evaluationfunctions）是度量各組染色體的機制，可對應到「適應函數」（fitnessfunctions）。這個對應關係可以使一組染色體的目標值對應到一個適應值，觀察其適應值的高低可以獲知其對目標的適應程度。3.選擇：選擇優良的雙親（parents）對產生高適應性的結果（offsprings）。根據前一步驟的「適應值」進行產生結果之挑選：「適應值」越高的染色體將獲選比較多，「適應值」較低的染色體獲選數量便相對較少。而此步驟便是決定「適應值」與獲選分配比例的關係。4.基因操作（Geneticoperations）4.1交配：將獲選的染色體組進行交配（crossover）。交配法可以有「單點法」（one-pointcrossovermethod）、「雙點法」（two-pointcrossovermethod），以及「套選法」（uniformcrossovermethods）等等。「單點法」指選擇染色體中的固定一個位置將串列截斷，進行雙親前後段編碼的對換，產生結果。如下圖1所示：「雙點法」指選擇染色體中的固定二個位置將串列截斷，將截出之中段編碼進行對換，產生結果（見圖2）。由雙點法原理可以繼續發展出出「多點法」（multi-pointcrossovermethod）。「套選法」乃由亂數產生