智能計(jì)算及應(yīng)用遺傳算法培訓(xùn)課件

智能計(jì)算及應(yīng)用遺傳算法3遺傳算法的改進(jìn)CHC算法

自適應(yīng)遺傳算法基于小生境技術(shù)的遺傳算法4遺傳算法的應(yīng)用解決帶約束的函數(shù)優(yōu)化問(wèn)題解決多目標(biāo)優(yōu)化問(wèn)題

解決組合優(yōu)化問(wèn)題遺傳算法在模式識(shí)別中的應(yīng)用2智能計(jì)算及應(yīng)用遺傳算法3遺傳算法的改進(jìn)

改進(jìn)的途徑改變遺傳算法的組成成分；采用混合遺傳算法；采用動(dòng)態(tài)自適應(yīng)技術(shù)；采用非標(biāo)準(zhǔn)的遺傳操作算子；采用并行遺傳算法等。

3智能計(jì)算及應(yīng)用遺傳算法遺傳算法的改進(jìn)

改進(jìn)思路1991年Eshelman提出的一種改進(jìn)遺傳算法；C：跨代精英選擇（Crossgenerationalelitistselection）策略；H：異物種重組（Heterogeneousrecombination）；C：大變異（Cataclysmicmutation）。1.CHC算法

4智能計(jì)算及應(yīng)用遺傳算法遺傳算法的改進(jìn)

選擇上一代種群與通過(guò)新的交叉方法產(chǎn)生的個(gè)體群混合起來(lái)，從中按一定概率選擇較優(yōu)的個(gè)體；即使交叉操作產(chǎn)生較劣個(gè)體偏多，由于原種群大多數(shù)個(gè)體殘留，不會(huì)引起個(gè)體的評(píng)價(jià)值降低；可以更好地保持遺傳多樣性；排序方法，克服比例適應(yīng)度計(jì)算的尺度問(wèn)題。CHC算法

5智能計(jì)算及應(yīng)用遺傳算法遺傳算法的改進(jìn)

交叉均勻交叉的改進(jìn)：當(dāng)兩個(gè)父?jìng)€(gè)體位值相異的位數(shù)為m時(shí)，從中隨機(jī)選取m/2個(gè)位置，實(shí)行父?jìng)€(gè)體位值的交換；顯然，這樣的操作對(duì)模式具有很強(qiáng)的破壞性。確定一閾值，當(dāng)個(gè)體間距離低于該閾值時(shí)，不進(jìn)行交叉操作。進(jìn)化收斂的同時(shí)，逐漸地減小該閾值。CHC算法

6智能計(jì)算及應(yīng)用遺傳算法遺傳算法的改進(jìn)

變異在進(jìn)化前期不采取變異操作，當(dāng)種群進(jìn)化到一定收斂時(shí)期，從最優(yōu)個(gè)體中選擇一部分個(gè)體進(jìn)行初始化；初始化：選擇一定比例（擴(kuò)散率，一般0.35）的基因座，隨機(jī)地決定它們的位值。CHC算法

7智能計(jì)算及應(yīng)用遺傳算法遺傳算法的改進(jìn)

參數(shù)分析交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵，直接影響算法的收斂性；Pc越大，新個(gè)體產(chǎn)生的速度就越快，但過(guò)大會(huì)使優(yōu)秀個(gè)體的結(jié)構(gòu)很快被破壞；Pc過(guò)小，搜索過(guò)程緩慢，以至停止不前；Pm過(guò)小，不易產(chǎn)生新個(gè)體結(jié)構(gòu)，Pm過(guò)大，變成純粹的隨機(jī)搜索；2自適應(yīng)遺傳算法

8智能計(jì)算及應(yīng)用遺傳算法遺傳算法的改進(jìn)

自適應(yīng)策略Srinvivas等提出一種自適應(yīng)遺傳算法，Pc和Pm能夠隨適應(yīng)度自動(dòng)改變：當(dāng)種群各個(gè)體適應(yīng)度趨于一致或趨于局部最優(yōu)時(shí)，使Pc和Pm增加；而當(dāng)群體適應(yīng)度比較分散時(shí)，使Pc和Pm減少；對(duì)于適應(yīng)度較高的個(gè)體，對(duì)應(yīng)于較低的Pc和Pm

；而較低適應(yīng)度的個(gè)體，對(duì)應(yīng)于較高的Pc和Pm

。自適應(yīng)遺傳算法

9智能計(jì)算及應(yīng)用遺傳算法遺傳算法的改進(jìn)

自適應(yīng)方法

fmax——群體中最大的適應(yīng)度值；

favg——每代群體的平均適應(yīng)度值；

f’——要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值；

f——要交叉或變異的個(gè)體適應(yīng)度值；自適應(yīng)遺傳算法

k1、k2、k3、k4取(0,1)的值10智能計(jì)算及應(yīng)用遺傳算法遺傳算法的改進(jìn)

自適應(yīng)方法進(jìn)一步改進(jìn)適用于進(jìn)化后期，不適于進(jìn)化前期，因?yàn)榍捌诘膬?yōu)秀個(gè)體有可能是局部最優(yōu)點(diǎn)；使最大適應(yīng)度個(gè)體的交叉概率和變異概率由0提高到Pc2和Pm2

；采用精英選擇策略；自適應(yīng)遺傳算法

11智能計(jì)算及應(yīng)用遺傳算法遺傳算法的改進(jìn)

自適應(yīng)方法進(jìn)一步改進(jìn)自適應(yīng)遺傳算法

12智能計(jì)算及應(yīng)用遺傳算法遺傳算法的改進(jìn)

小生境概念小生境（niche）：生物學(xué)中，特定環(huán)境中的一種組織功能；在自然界中，往往特征、性狀相似的物種相聚在一起，并在同類中交配繁衍后代。在SGA中，容易“近親繁殖”；NGA（NicheGenericAlgorithm），將每一代個(gè)體劃分為若干類，每類選出優(yōu)秀個(gè)體組成一個(gè)種群；優(yōu)勢(shì)：保持解的多樣性，提高全局搜索能力，適合復(fù)雜多峰函數(shù)的優(yōu)化。3基于小生境技術(shù)的遺傳算法

13智能計(jì)算及應(yīng)用遺傳算法遺傳算法的改進(jìn)

選擇策略預(yù)選擇機(jī)制、排擠機(jī)制、分享機(jī)制；預(yù)選擇（preselection,1970）機(jī)制當(dāng)子個(gè)體的適應(yīng)度超過(guò)其父?jìng)€(gè)體適應(yīng)度時(shí)，子個(gè)體才可以替代父?jìng)€(gè)體，否則父?jìng)€(gè)體仍保留；有效維持種群多樣性，造就小生境進(jìn)化環(huán)境?；谛∩臣夹g(shù)的遺傳算法

14智能計(jì)算及應(yīng)用遺傳算法遺傳算法的改進(jìn)

排擠（crowding,1975）機(jī)制設(shè)置排擠因子CF（CF=2或3），隨機(jī)選取1/CF的個(gè)體組成排擠成員，排擠與其相似的個(gè)體；個(gè)體之間的相似性可用個(gè)體編碼串之間的海明距離來(lái)度量?；谛∩臣夹g(shù)的遺傳算法

15智能計(jì)算及應(yīng)用遺傳算法遺傳算法的改進(jìn)

共享（sharing,1987）機(jī)制通過(guò)個(gè)體之間的相似性程度的共享函數(shù)來(lái)調(diào)整各個(gè)體的適應(yīng)度；共享函數(shù)的目的：將搜索空間的多個(gè)峰值在地理上區(qū)分開(kāi)來(lái)，每一個(gè)峰值處接受一定比例數(shù)目的個(gè)體，比例數(shù)目與峰值高度有關(guān)；基于小生境技術(shù)的遺傳算法

16智能計(jì)算及應(yīng)用遺傳算法遺傳算法的改進(jìn)

共享（sharing,1987）機(jī)制共享函數(shù)的值越大，表明個(gè)體之間越相似，記為Sh(dij)，dij為兩個(gè)個(gè)體i和j之間的距離；

σshare是niche的半徑，由使用者給定。基于小生境技術(shù)的遺傳算法

17智能計(jì)算及應(yīng)用遺傳算法遺傳算法的改進(jìn)

共享（sharing,1987）機(jī)制共享法將個(gè)體的適應(yīng)度降低，即適應(yīng)度值fi除以一個(gè)niche計(jì)數(shù)mi：在距離為σshare的范圍內(nèi)的個(gè)體彼此削減適應(yīng)度，這些個(gè)體將收斂在一個(gè)niche內(nèi)，避免了整個(gè)種群的收斂?；谛∩臣夹g(shù)的遺傳算法

18智能計(jì)算及應(yīng)用遺傳算法4遺傳算法的應(yīng)用

約束最優(yōu)化問(wèn)題（ConstrainedOptimizationProblems）的表述

1解決帶約束的函數(shù)優(yōu)化問(wèn)題

19智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

解決途徑將有約束問(wèn)題轉(zhuǎn)化為無(wú)約束問(wèn)題（罰函數(shù)法，penaltyfunctionmethod），歷史較長(zhǎng)；改進(jìn)無(wú)約束問(wèn)題的方法，使之能用于有約束的情況（梯度投影算法），發(fā)展較晚。遺傳算法解決有約束問(wèn)題的關(guān)鍵是對(duì)約束條件的處理（直接按無(wú)約束問(wèn)題處理是行不通的：隨機(jī)生成的初始點(diǎn)中可能有大量不可行解；遺傳算子作用于可行解后可能產(chǎn)生不可行解）。解決帶約束的函數(shù)優(yōu)化問(wèn)題

20智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

一般方法罰函數(shù)法將罰函數(shù)包含到適應(yīng)度評(píng)價(jià)中：關(guān)鍵是如何設(shè)計(jì)罰函數(shù)，需要謹(jǐn)慎地在過(guò)輕或過(guò)重懲罰之間找到平衡，針對(duì)不同問(wèn)題設(shè)計(jì)罰函數(shù)。解決帶約束的函數(shù)優(yōu)化問(wèn)題

21智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

一般方法協(xié)同進(jìn)化遺傳算法（CoevolutionaryGeneticAlgorithm,1997）以食物鏈關(guān)系、共生關(guān)系等為基礎(chǔ)的生物進(jìn)化現(xiàn)象稱為協(xié)同進(jìn)化；一個(gè)種群由問(wèn)題的解組成，另一個(gè)種群由約束組成，兩個(gè)種群協(xié)同進(jìn)化，較好的解應(yīng)滿足更好的約束，較優(yōu)的約束則被更多的解所違背。解決帶約束的函數(shù)優(yōu)化問(wèn)題

22智能計(jì)算及應(yīng)用遺傳算法罰函數(shù)法評(píng)價(jià)函數(shù)的構(gòu)造：加法

乘法遺傳算法的應(yīng)用

解決帶約束的函數(shù)優(yōu)化問(wèn)題

23智能計(jì)算及應(yīng)用遺傳算法罰函數(shù)法罰函數(shù)分類：定量懲罰——簡(jiǎn)單約束問(wèn)題變量懲罰——復(fù)雜約束問(wèn)題，包含兩個(gè)部分：可變懲罰率和違反約束的懲罰量。遺傳算法的應(yīng)用

解決帶約束的函數(shù)優(yōu)化問(wèn)題

違反約束程度——隨違反約束程度變得嚴(yán)重而增加懲罰壓力，靜態(tài)懲罰；進(jìn)化迭代次數(shù)——隨著進(jìn)化過(guò)程的進(jìn)展而增加懲罰壓力，動(dòng)態(tài)懲罰。24智能計(jì)算及應(yīng)用遺傳算法罰函數(shù)法交叉運(yùn)算：設(shè)父?jìng)€(gè)體為x=[x1,x2,…,xn]和y=[y1,y2,…,yn]

簡(jiǎn)單交叉單點(diǎn)算術(shù)交叉整體算術(shù)交叉基于方向的交叉：x’=r(x-y)+x，r為(0,1)之間的隨機(jī)數(shù)，并假設(shè)f(x)≥f(y)。遺傳算法的應(yīng)用

解決帶約束的函數(shù)優(yōu)化問(wèn)題

25智能計(jì)算及應(yīng)用遺傳算法罰函數(shù)法變異運(yùn)算：設(shè)父?jìng)€(gè)體為x=[x1,x2,…,xn]

均勻變異非均勻變異（動(dòng)態(tài)變異）邊界變異：x’=[x1,x2,…,xk’,…,xn]，xk’等概率地取用變異量的上界或下界，當(dāng)最優(yōu)解在可行域邊界上或附近時(shí)，邊界變異算子較為有效；基于方向的變異：x’=x+r?d，d為目標(biāo)函數(shù)的近似梯度。遺傳算法的應(yīng)用

解決帶約束的函數(shù)優(yōu)化問(wèn)題

26智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

求解線性約束優(yōu)化問(wèn)題的遺傳算法線性約束優(yōu)化問(wèn)題一般形式為：解決帶約束的函數(shù)優(yōu)化問(wèn)題

27智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

求解線性約束優(yōu)化問(wèn)題的遺傳算法線性約束優(yōu)化問(wèn)題：目標(biāo)函數(shù)可以是線性函數(shù)或非線性函數(shù)；思路——消除可能的變量，消除等式約束設(shè)計(jì)罰函數(shù)設(shè)計(jì)特別的遺傳操作解決帶約束的函數(shù)優(yōu)化問(wèn)題

28智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

多目標(biāo)優(yōu)化問(wèn)題

解的存在性怎樣求解2解決多目標(biāo)優(yōu)化問(wèn)題

29智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

Pareto最優(yōu)性理論在一個(gè)有k個(gè)目標(biāo)函數(shù)最小化的問(wèn)題中，稱決策向量x*∈F是Pareto最優(yōu)的，當(dāng)不存在另外一個(gè)決策向量x∈F同時(shí)滿足解決多目標(biāo)優(yōu)化問(wèn)題

30智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

Pareto最優(yōu)性理論多目標(biāo)優(yōu)化問(wèn)題的解通常是多個(gè)滿意解的集合，稱為Pareto最優(yōu)集，解集中的決策向量稱為非劣的。解決多目標(biāo)優(yōu)化問(wèn)題

31智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

傳統(tǒng)方法多目標(biāo)加權(quán)法層次優(yōu)化法目標(biāo)規(guī)劃法等特點(diǎn)：將多目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)函數(shù)處理，只能得到特定條件下的某一Pareto解。解決多目標(biāo)優(yōu)化問(wèn)題

32智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

多目標(biāo)優(yōu)化的遺傳算法優(yōu)勢(shì)：并行地處理一組可能的解；不局限于Pareto前沿的形狀和連續(xù)性，易于處理不連續(xù)的、凹形的Pareto前沿。目前基于Pareto的遺傳算法占據(jù)主要地位。解決多目標(biāo)優(yōu)化問(wèn)題

33智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

多目標(biāo)優(yōu)化的遺傳算法

聚合函數(shù)法：把多個(gè)目標(biāo)函數(shù)表示成一個(gè)目標(biāo)函數(shù)作為遺傳算法的適應(yīng)函數(shù)（聚合）；無(wú)需改動(dòng)遺傳算法，但權(quán)值難以確定；改進(jìn)：自適應(yīng)權(quán)值。解決多目標(biāo)優(yōu)化問(wèn)題

34智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

多目標(biāo)優(yōu)化的遺傳算法

基于排序的多目標(biāo)遺傳算法：根據(jù)“Pareto最優(yōu)個(gè)體”的概念對(duì)所有個(gè)體進(jìn)行排序，依據(jù)這個(gè)排列次序來(lái)進(jìn)行進(jìn)化過(guò)程中的選擇運(yùn)算，從而使得排在前面的Pareto最優(yōu)個(gè)體將有更多的機(jī)會(huì)遺傳到下一代群體。解決多目標(biāo)優(yōu)化問(wèn)題

36智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

多目標(biāo)優(yōu)化的遺傳算法

小生境Pareto遺傳算法：為了保證尋優(yōu)過(guò)程不收斂于可行域的某一局部，使種群向均勻分布于Pareto前沿面的方向進(jìn)化，通過(guò)共享函數(shù)定義一小生境加以實(shí)現(xiàn)。解決多目標(biāo)優(yōu)化問(wèn)題

37智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

TSPBenchmark問(wèn)題

4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;4503解決組合優(yōu)化問(wèn)題

38智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

TSPBenchmark問(wèn)題編碼：直接采用解的表示形式，30位（30個(gè)城市）長(zhǎng)，每位代表所經(jīng)過(guò)的城市序號(hào)（無(wú)重復(fù)）；

適應(yīng)度函數(shù)：個(gè)體所代表的路徑距離的倒數(shù)；

選擇：輪盤(pán)賭方法

解決組合優(yōu)化問(wèn)題

39智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

TSPBenchmark問(wèn)題交叉：有序交叉法

1）隨機(jī)選取兩個(gè)交叉點(diǎn)；

2）兩個(gè)父?jìng)€(gè)體交換中間部分；

3）替換交換后重復(fù)的城市序號(hào)。解決組合優(yōu)化問(wèn)題

X1:98|45671|320X2:87|14032|965X1’:98|14032|320X2’:87|45671|965X1’:98|14032|756X2’:83|45671|90240智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

TSPBenchmark問(wèn)題變異：隨機(jī)選擇同一個(gè)個(gè)體的兩個(gè)點(diǎn)進(jìn)行交換；初始參數(shù)：種群規(guī)模100

交叉概率0.8

變異概率0.8

終止代數(shù)2000解決組合優(yōu)化問(wèn)題

41智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

TSPBenchmark問(wèn)題運(yùn)行結(jié)果：解決組合優(yōu)化問(wèn)題

42智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

TSPBenchmark問(wèn)題運(yùn)行結(jié)果：解決組合優(yōu)化問(wèn)題

43智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

TSPBenchmark問(wèn)題運(yùn)行結(jié)果：解決組合優(yōu)化問(wèn)題

44智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

TSPBenchmark問(wèn)題運(yùn)行結(jié)果：解決組合優(yōu)化問(wèn)題

45智能計(jì)算及應(yīng)用遺傳算法遺傳算法的應(yīng)用

TSPBenchmark問(wèn)題運(yùn)行結(jié)果：解決組合優(yōu)化問(wèn)題

46智能計(jì)算及應(yīng)用遺傳算法遺傳