48.2. 基因算法

基因算法(GA)是一種啟發式的優化法(heuristic optimization method), 它是通過既定的隨機搜索進行操作。優化問題的可能的解的集合被認為是個體(individuals)組成的人群(population)。 一個個體對它的環境的適應程度由它的健康度(fitness)表示。

一個個體在搜索空間裡的參照物是用染色體(chromosomes)表示的, 實際上那是一套字符串。 一個基因 (gene)是染色體的一個片段,基因是被優化的單個參數的編碼。 對一個基因的典型的編碼可以是二進制(binary)整數(integer)

通過仿真進化過程的重組(recombination)突變(mutation)選擇(selection)找到新一代的搜索點,它們的平均健康度要比它們的祖先好。

根據 comp.ai.genetic FAQ,我們不論怎麼強調 GA 在解決一個問題時不是純隨機搜索都不過份。 GA 使用隨機處理,但是結果明顯不是隨機的(比隨機更好)。

Figure 48-1. 基因算法的結構化框圖

P(t)t 時刻的父代
P''(t)t 時刻的子代

+=========================================+
|>>>>>>>>>>>  Algorithm GA  <<<<<<<<<<<<<<|
+=========================================+
| INITIALIZE t := 0                       |
+=========================================+
| INITIALIZE P(t)                         |
+=========================================+
| evalute FITNESS of P(t)                 |
+=========================================+
| while not STOPPING CRITERION do         |
|   +-------------------------------------+
|   | P'(t)  := RECOMBINATION{P(t)}       |
|   +-------------------------------------+
|   | P''(t) := MUTATION{P'(t)}           |
|   +-------------------------------------+
|   | P(t+1) := SELECTION{P''(t) + P(t)}  |
|   +-------------------------------------+
|   | evalute FITNESS of P''(t)           |
|   +-------------------------------------+
|   | t := t + 1                          |
+===+=====================================+