控制課件037神經網絡

15-4

遺傳算法的發(fā)展

GA的發(fā)展主要圍繞著提高求得全局最優(yōu)解的概率和效率進行。

多年來，從各種不同的方面，作了種種努力，在SGA基礎上，取得了相當?shù)倪M展；同時針對不同的應用領域，研究了相應的解決特定問題的算法。本節(jié)介紹以下算法。5-4-1交叉、變異率的自適應調整5-4-2高級算子5-4-3并行GA5-4-4可變長個體與MessyGA5-4-5基于小生境技術的GA5-4-6

混合GA5-4-7導入年齡結構的GA5-4-8基于基因分布評價的適應度調整25-4-1交叉、變異率的自適應調整

35-4-2高級算子

在SGA基礎上，為提高GA有效性進行了有益的探索，介紹幾例高級算子。

1.逆算子逆（倒位）算子操作：在個體的長度方向上，選兩個切斷點，兩點間基因倒位，再接起來，成為新個體。經常是逆算子與交叉相結合進行操作。例5-4-1

見圖，在4567基因座上倒位。

逆算子舊個體新個體12345678123456781001010110001011圖5-4-1逆算子例4

3.靜態(tài)繁殖

SGA是用子代取代父代，靜態(tài)繁殖是在迭代過程中，用部分優(yōu)質子串來更新部分父串，這需要合理確定更新的數(shù)量。

4.本地算子自然界中相距遙遠的、種類相似的生物并非一道繁殖，本地的才有機會。為了維持多樣性，本地算子采取了兩項措施：（1）造一種共享機制，限制一些個體快速擴張；（2）為了維持一些個體的存在，應有選擇的進行交配，即交叉受限。

2.對等交叉法兩個體上的基因完全對等時，才可進行交叉。例5-4-2

有3個個體A、B、C：

A=11001

B=00110

C=10011A、B的基因完全對等，可進行交叉，A、C和B、C都不能。55-4-3并行GA

介紹兩種并行GA模型。

1.島模型把種群分成多個子群，在多計算機上進行并行且獨立的GA操作，同時，不同部分的子群間，進行個體交換，稱遷移。若任意子群之間均可有個體遷移，稱飛石模型。關于遷移，需確定如下幾個問題：

（1）哪些子群間可以遷移；

（2）遷移個體的選擇，遷移的個體數(shù)；

（3）經幾代可遷移。圖5-4-2（a），為分成四個子群，并進行遷移的島模型示意圖。此模型由于并行計算，使運算時間縮短，且因局域性搜索，對于整個群體，可維持個體多樣性，抑制了早期收斂。6

2.近旁模型

（1）在種群內的個體，僅與限定近旁的個體進行GA操作。故操作是并行、局域的。

（2）每一個體定義其近旁，每一個體，既是其近旁的核心，又是限定的其他個體的近旁。因近旁定義不同，有多種形式，圖5-4-2（b）為一例。

（3）由于GA操作的局域性，既使某個體的f很高，其影響，只能通過近旁間，漸漸地波及到整個群體中，因此高f個體的急劇增加被抑制，起到了抑制早期收斂的作用。7

用SGA，2進位串長度L是不變的，定義長的模式，被破壞的可能性大，故探索用可變長個體改善GA搜索能力。

1.可變長個體個體長度L不變，個體可用2元組（基因座與其值）表示：5-4-4可變長個體與MessyGA

82.算子

代替SGA中交叉算子的是如下兩個算子：（1）切斷以某概率在個體長度上，隨機選擇位置，將基因鏈切斷，圖5-4-3（a）。

（2）接合

以某概率，將兩個基因鏈接合，圖5-4-3（b）。

(a)(b)9105-4-5基于小生境技術的GA

在SGA的基礎上，Goldberg提出了：適應度共享模型的選擇策略是基于小生境技術的GA算法中的一種。使種群在進化過程中，能依據(jù)調整后的適應度進行選擇，以維護種群的多樣性，構造出小生境的進化環(huán)境。它是一種用于

多峰搜索問題的優(yōu)化算法使之能（盡可能）搜索到多個全局最優(yōu)解。1112135-4-6混合GA

SGA的不足之一：局部搜索（微調）能力差。

將有很強局部搜索能力的算法與GA結合，構成混合GA，是彌補其不足的手段：

梯度法與GA結合的混合GA適用于連續(xù)可微函數(shù)的全局尋優(yōu)。

模擬退火算法與GA結合的混合GA是一種求解大規(guī)模組合優(yōu)化問題的有效近似算法。

145-4-7導入年齡結構的GA

是模擬自然界中，多年生生物具有年齡所建立的模型。算法有兩種：AGA－AgedGA、

ASGA－AgeStructuredGA。共同點：把離散的一個單元作為一代，每一個體，設整數(shù)年齡參數(shù)；在第t代年齡為x的個體，在第t+1代，年齡為x+1，并設置死亡年齡。

1.AGA

（1）是導入年齡和死亡年齡的模型；（2）算法中，除了由選擇而淘汰一部分個體外，達到死亡年齡的個體，也被淘汰；（3）交叉后的雙親不存留，新生的子輩年齡=0；（4）算法中，親子不共存；（5）增加的計算：年齡的更新和到齡個體的死亡。15

2.ASGA

（1）在AGA基礎上，增設了死亡率參數(shù)；（2）模擬了多年生生物，在每一年令都可能有死亡這一現(xiàn)象；

（3）死亡率：與適應度無關的死亡概率，是0～1間的隨機數(shù)；

（4）每代，選擇及達到死亡年齡的個體被淘汰外，每一年齡的個體，按死亡率被淘汰；

（5）交叉后的雙親，仍可生存，在群體中，親子共存；（6）ASGA與AGA比較：相同情況下，求解過程中，前者比后者，個體適應度的變化，出現(xiàn)較少的振蕩，趨向于最終收斂。

可見：

ASGA與AGA模型，是通過抑制種群中適應度f高個體的增殖，使f低和個體數(shù)少的個體生存概率增加，降低了選擇壓，維持個體的多樣性，緩和了早期收斂。165-4-8基于基因分布評價的適應度調整

多變量優(yōu)化問題，用十進制整數(shù)編碼，評價個體多樣性的方法及適應度調整。要點：

（1）用基因分布直方圖，評價種群中基因分布的多樣性；

（2）用基因分布直方圖，計算個體的稀少度；

（3）通過調整變異的幅度，產生稀少的個體。175-4-9GA理論研究

GA的理論研究有兩種理論：

基于模式理論的分析

基于隨機模型理論的研究

（1）Holland提出的模式及模式定理，指出了在三個GA算子的作用下，較優(yōu)的模式數(shù)目呈指數(shù)增長，為解釋SGA的尋優(yōu)機理提供了數(shù)學方法。

不足：僅適用于二進編碼、沒有涉及SGA的五項參數(shù)的選取等問題。

（2）Bethke提出用Walsh函數(shù)、離散Walsh變換，計算模式平均適應度的方法，對GA的尋優(yōu)過程進行分析。

（3）

基于隨機模型理論的GA分析，建立馬爾科夫鏈的GA模型，分析GA的收斂問題。1819（3）GA欺騙問題

欺騙問題定義：在GA搜索過程中，將妨礙適應值高的個體生成而影響

GA的工作，使搜索方向偏離全局最優(yōu)解的問題。欺騙問題分類：完全欺騙、一致欺騙、序列欺騙、基本欺騙問題欺騙問題搜索難度：欺騙性依次由高降低，搜索難度也隨之由高降低依欺騙性定義和相關定理：單調和單峰函數(shù)無模式欺騙性