演算法原理 – 基因演算法(GA).pdfVIP

演算法原理–基因演算法(GA)

基因演算法(GeneticAlgorithm)是由Holland在1975年時提出，Holland將達爾文進

化論中的「物競天擇」的想法抽象化；用來生物演化的過程。有趣的是，基因演算法在

發明的最初，並非運用在搜尋最佳解，而是應用於人工智慧的領域，直到1980年代，

方有學者將基因演算法應用於搜尋最佳解等其他的研究領域。

基因演算法的求解過程並非如同貪婪演算法般一步一步往最佳解的方向前進，基因

演算法在一開始會視問題的特性，使用不同的方式將問題的求解區域編碼成染色體，也

就是映射到另一個求解區域，接著散佈一個「族群」的染色體在函數的多處，如下圖

之後開始計算每個個體─染色體─的適應能力決定是否要在此區域繼續找尋最佳

解，此行為就像自然界在挑選較為優良、適此環境的個體存活下來繼續繁衍後代，此步

驟我們稱為「複製」(Reproduction)或「選擇」(Selection)。在求解過程中，每個染色體

會彼此交換基因找尋最佳解，此步驟我們稱之為「交配」(Crossover)。想當然爾，每個

染色體找到的解也有可能是區域最佳解，因此基因演算法也有跳脫區域最佳解的機制─

突變(Mutation)，此機制是隨機改變染色體中的基因，使其跳脫區域最佳解。以下是基

因演算法的流程圖

基因的編碼方式

將每一個染色體編碼，是我們的首要任務！此動作可以將問題轉至基因演算法的求

解空間，在演算的最後，則透過反向運算，將答案從求解空間取出，轉回問題所在的空

間並化為我們所需要的解的形式。如何將一個問題所需處理的資料編碼(Encode)，使之

成為染色體，是一個關鍵議題，至於要將資料編碼成何種類完全依據問題的特性與目的

而定。編碼方式有許多種，最常見的有四種：二元編碼(BinaryEncoding)、排列編碼

(PermutationEncoding)、實數編碼(ValueEncoding)、樹狀編碼(TreeEncoding)。

二元編碼，即將資料轉為二進位的字元所構成的字串，例如：100110111100110

、……等。二元編碼是較容易實行與適合絕大多數的最佳化問題，因此傳統上多使用二

元編碼。排列編碼，即將資料轉為一組有序的數字，例如：136549、2741389、……等。

排列編碼較適於有序或序列的問題，像是銷售員的問題。實數編碼，即將資料轉為一組

數字或是其它型態─像是字元、整數、浮點數、實數、任何物件等等─的資料，例如：

1.25632.65893.05994.12505.3698、HDSOAKFAOJKIDOLDMDKWSAKLMFIEK、

(down),(left),(upward),(forward)、……等等，實數編碼能夠應用在具有較複雜數值的

問題。樹狀編碼，即將資料使用樹狀結構表示資料，我們可以使用它來表示函數、規則

或是程式的一些指令等等。繞射光學元件設計多使用二元編碼與實數編碼，本文是使用

實數編碼，直接將相位當成基因的編碼。

選擇\複製

選擇機制是模擬大自然中，對環境適應度較佳的個體將存活下來，並繁衍後代。所

以，基因演算法中的選擇機制，將依據每一個個體的適應值高低，決定其繁衍子代的多

寡。適應值高的個體，其染色體在下一個世代中將被大量複製，反之，適應值低的染色

體，將被淘汰掉。常用的有輪盤式隨機選擇(roulettewheelselection)、競賽選擇

(tournamentselection)與精英制(elitismselection)。

輪盤式隨機選擇，是指每個個體被挑選到的機率與其適應值高低成正比；每個個體

被挑選到的機率為

f

Pi

in

f

i

i1

n

Piff

其中，為第個個體