三、遺傳算法
遺傳算法（Genetic Algorithm，簡稱GA）是一類模擬生物界自然選擇和遺傳的啟發式
隨機搜索算法。標準遺傳算法的步驟包括編碼、初始群體的生成、適應度評估和檢測、選擇、
交叉操作和變異操作。它是一種具有“生成+檢測”的迭代過程的搜索算法，如圖11.5 所示。
編 碼
初始群體的生成
群體中個體適應度函數的評估
交 叉
終止？
結束
選 擇
變 異
是
否
圖11.5 標準遺傳算法的流程圖
（一）編碼
編碼的作用是將設計變量表示成遺傳空間的基因型串結構數據。通常采用一定長度的二
進制碼代表設計變量的各種取值。對于連續變量，如果設計變量的精度指定為Z，下限為XL，
上限為XU，那么二進制碼的長度K為：
2K ≥ [(XU – XL)/ Z + 1 ]
對于離散變量，如果離散變量可能取值數為M，那么二進制碼的長度K 為：
2K ≥ M
將各個變量的二進制碼連成一串，得到一個二進制代碼串，它代表了設計空間的一個點。二
進制碼所有可能的結構代表了整個設計空間。因此，GA 中的編碼技術可統一地將含連續/離
散變量的設計空間用一系列二進制代碼來表示。
（二）初始群體的生成
遺傳算法是一種群體操作算法，必須為遺傳操作準備一個由若干初始解組成的初始群體。
通常采用隨機方法來產生初始群體。群體規模的確定對遺傳算法的效果有影響。群體規模越
· 171 ·
大，GA 陷入局部最優解的危險性越小，但計算量會增加；群體規模太小，會使GA 在搜索空
間中分布范圍有限，會引起未成熟收斂現象。
（三）適應度函數的評估
遺傳算法在進化搜索中基本上不用外部信息，僅用目標函數即適應度函數為依據。適應
度函數評估是選擇操作的依據。由于適應度函數應為非負值。一般需將目標函數以一定的方
式映射成適應度函數。適應度函數的設計直接影響到算法的性能。
（四）選擇算子
選擇算子的目的是把優化的個體(或設計點)直接遺傳到下一代或通過配對交叉產生新的
個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的，適應度越大的
個體，被選中的概率越大，也就是說適應度越高的個體，有更多的機會繁殖后代，使其優良
特性得以遺傳和保留。常用的選擇方法有適應度比例方法、最佳個體保留方法、期望值方法、
排序選擇和聯賽選擇方法。
（五）交叉操作
在自然界生物進化過程中起核心作用的是生物遺傳基因的重組。遺傳算法中起核心作用
的遺傳操作的交叉算子。所謂交叉是指把兩個父代個體的部份結構加以替換重組而生成新的
個體，通過交叉，遺傳算法的搜索能力得以飛躍提高。最簡單的交叉算子是一點交叉
(one-point crossover)：隨機地選取一個截斷點，將雙親的基因碼串在截斷點切開，然后交
換其尾部：
雙親 后代
1000┆10011110 ——→ 1000┆11000110
0010┆11000110 ——→ 0010┆10011110
另一種常用的交叉算子是一致交叉(uniform crossover)，它是通過設定屏蔽字(mask)來決定
新個體的基因繼承兩個舊個體中哪個個體的對應基因。一致交叉的操作過程是：當屏蔽字中
的位為0 時，新個體A′繼承舊個體A 中對應的基因，當屏蔽字位為1 時，新個體A′繼承舊
個位B 中對應的基因，由此生成一個完整的新個體A′，反之，可生成新個體B′。例如：
舊個體A 0 0 1 1 1 1
舊個體B 1 1 1 1 0 0
屏蔽字 0 1 0 1 0 1
新個體A′ 0 1 1 1 1 0
新個體B′ 1 0 1 1 0 1
（六）變異算子
變異算子的目的是模擬生物在自然的遺傳環境中由于各種偶然因素引起的基因突變。其
方法是以一定的概率選取群體中若干個體，對已選取的每個個體，隨機選取某一位，將該位
的數碼翻轉。變異算子增加了群體基因材料的多樣性，增加了自然選擇的余地，有利的變異
將由于選擇操作的作用，得以遺傳與保留，而有害的變異則將在逐代遺傳中被淘汰。
通過用選擇、交叉、變異得到的新一代群體代替其上一代群體，再進行評估、選擇、交
叉、變異。如此迭代下去，各代群體的優良基因成份逐漸積累，群體的平均適應度和最優個
體適應度不斷上升，直到迭代過程趨于收斂，適應度趨于穩定，不再上升時，就找到了所需
· 172 ·
的最優解。
與傳統的優化算法相比，遺傳算法的優點主要有以下三方面：
(1) GA 處理的對象廣
GA 處理的是計算對象編碼，因此它對處理對象的性質幾乎沒有限制，對象可以是連續變
量、離散變量、各種數據結構和樹等。
(2) GA 是一種搜索全局最優解的算法
許多傳統的搜索方法都是單點搜索算法，即通過一些變動規則，問題的解從搜索空間中
的當前解(點)移動到另一解(點)。這種單點搜索方法對于多峰分布的設計空間常常會陷于局
中國航空網 m.k6050.com
航空翻譯 www.aviation.cn
本文鏈接地址：飛機總體設計(55)
