Jialin

一、簡介

基因演算法（Genetic Algorithm），又稱為遺傳演算法。1975年，由美國J.Holland教授提出。

二、精神

「適者生存，不適者淘汰」。經由初始母體的演化、迭代的過程，保留較優秀的子代。

三、流程

基因演算法流程圖如下：

(a)  編碼( Encoding )

每一條染色體（chromosome）即為一組解，而每一條染色體是由許多基因所組成。在編碼的過程（為基因命名），有許多種方式，可以以二元（0，1）方式進行編碼，或是以實數（1，2，3……）的方式進行。

(b)  產生初始母體( Initial population )

以下，以實數方式進行編碼來說明。

下面有三條染色體，每條染色體上有8個基因，分別為1~8。產生初始母體是以隨機的方式，將編號為1~8的基因隨機排列成為一條染色體。可以依問題的大小，來決定要產出多少條初始母體。也可以實際coding，改變初始母體的數目，增加母體的多樣性，來觀察是否能獲得較佳的解。

(c)  計算合適度函數( Fitness function )

針對每一條染色體，計算合適度函數（Fitness function）。目的為評估每一條染色體對於待解決問題的合適度，評估每一個解（染色體）的好壞程度（是否要保留的依據）。

合適度函數：

（被放進箱子的積木體積總和／箱子的體積）*100％

（vi=第i個積木之體積，L=箱子之長度，W=箱子之寬度，H=箱子之高度）

(d)  選擇與複製

由合適度函數的數值，把每一條染色體由數值大至小（優至劣）進行排列，選擇最優秀的一定百分比的染色體進行複製。

(e)  交配( Crossover )

由選擇與複製所留下的染色體，選出兩條染色體，進行交配。

選擇A、B兩條染色體，隨機選擇1~T兩相異正整數最為交配點，如下圖為 [2] ~ [4]。

把位置 [2] ~ [4] 之基因進行交換，產生新的染色體a、b。

把重複之基因標示出來（我們只有編號1~8的基因）。

染色體a，第一個重複之基因為1，位置在5，第二個重複之基因為7，位置在6。

染色體b，第一個重複之基因為3，位置在3，第二個重複之基因為2，位置在7。

把相對位置之基因值互換。

互換完成，藉由交配產生新的染色體a與b。

(f)  突變( Mutation )

設定一突變率，只有小部分的染色體進行內部基因互換的行為。目的為避免掉入「區域最佳解」（local optimum）。

採用雙點互換的方式，利用隨機產生一介於0~1 之間的值，當此值小於設定之突變率時，隨機選擇1~T兩相異正整數做為突變點，把位置上之基因值互換。

編號3之染色體，隨機突變點為2、6，把位置2、6上之基因值互換，完成編號3之染色體突變。

感謝收看，還請不吝指教 =)