遺傳算法-3課件

確定問題的編碼方案確定適配值函數(shù)遺傳算子的設(shè)計(jì)算法參數(shù)的選取算法終止準(zhǔn)則從算法流程看，GA算法按照以下步驟進(jìn)行第四節(jié)算法關(guān)鍵參數(shù)與操作的設(shè)計(jì)一、編碼目的：將問題的解用一種碼表示，將問題的狀態(tài)空間與GA的碼空間相對(duì)應(yīng)。碼長(zhǎng)碼制1、問題空間與GA空間遺傳算法不能直接處理問題空間的參數(shù)，必須把它們轉(zhuǎn)換成遺傳空間的、由基因按一定結(jié)構(gòu)組成的染色體或個(gè)體。這一轉(zhuǎn)換過程實(shí)際上是將問題空間轉(zhuǎn)換為GA空間，它們的對(duì)應(yīng)關(guān)系如下圖表示。圖GA空間與問題空間的對(duì)應(yīng)關(guān)系P2P1CP1P2C交叉GA空間問題空間編碼譯碼2、編碼評(píng)估規(guī)范評(píng)估編碼策略常采用以下3個(gè)規(guī)范：完備性（Completeness）：?jiǎn)栴}空間中的所有點(diǎn)（后選解）都能作為GA空間中的點(diǎn)（染色體）表現(xiàn)。問題空間的所有解都能表示為所設(shè)計(jì)的基因型。健全性（Soundness）：GA空間中的染色體能對(duì)應(yīng)所有問題空間中的解。任何一個(gè)基因型都對(duì)應(yīng)于一個(gè)可能解。非冗余性（Non-redundancy）：染色體和后選解一一對(duì)應(yīng)。問題空間和表達(dá)空間一一對(duì)應(yīng)。3、編碼技術(shù)遺傳算法用到的一般編碼技術(shù)有：一維染色體編碼多參數(shù)映射編碼可變?nèi)旧w長(zhǎng)度編碼二維染色體編碼樹結(jié)構(gòu)編碼多種編碼方式二進(jìn)制編碼；浮點(diǎn)數(shù)編碼；格雷碼編碼；符號(hào)編碼；復(fù)數(shù)編碼；DNA編碼等。二進(jìn)制編碼與浮點(diǎn)數(shù)編碼的比較在交叉操作時(shí)，二進(jìn)制編碼比浮點(diǎn)數(shù)編碼產(chǎn)生新個(gè)體的可能性多；在變異操作時(shí)，二進(jìn)制編碼的種群穩(wěn)定性比浮點(diǎn)數(shù)編碼差。二、群體設(shè)定1、初始群體的設(shè)定

一般來講，初始群體的設(shè)定可采取如下的策略：根據(jù)問題固有知識(shí)，設(shè)法把握最優(yōu)解所占空間在整個(gè)問題空間中的分布范圍，然后，在此分布范圍內(nèi)設(shè)定初始群體。先隨機(jī)生成一定數(shù)目的個(gè)體，然后從中挑出最好的個(gè)體加到初始群體中。這個(gè)過程不斷迭代，直到初始群體中個(gè)體個(gè)數(shù)達(dá)到要求。一般情況下，遺傳算法在群體初始化階段采用的是隨機(jī)數(shù)初始化方法。采用生成隨機(jī)數(shù)的方法，對(duì)染色體的每一維變量進(jìn)行初始化賦值。初始化染色體時(shí)必須注意染色體是否滿足優(yōu)化問題對(duì)有效解的定義。如果在進(jìn)化開始時(shí)保證初始群體已經(jīng)是一定程度上的優(yōu)良群體的話，將能夠有效提高算法找到全局最優(yōu)解的能力。2、群體多樣性根據(jù)模式定理，在二進(jìn)制編碼的前提下，為了滿足GA的隱并行性，群體個(gè)體數(shù)只要設(shè)定為即可，其中為染色體長(zhǎng)度?；蚍Q適應(yīng)度函數(shù)。目的：對(duì)個(gè)體進(jìn)行評(píng)價(jià)，是優(yōu)化過程的依據(jù)。三、適配值函數(shù)1、目標(biāo)函數(shù)映射成適應(yīng)度函數(shù)2、適應(yīng)度函數(shù)的設(shè)計(jì)對(duì)GA的影響評(píng)估函數(shù)用于評(píng)估各個(gè)染色體的適應(yīng)值，進(jìn)而區(qū)分優(yōu)劣。影響算法對(duì)種群的選擇，恰當(dāng)?shù)脑u(píng)估函數(shù)應(yīng)該能夠?qū)θ旧w的優(yōu)劣做出合適的區(qū)分，保證選擇機(jī)制的有效性，從而提高群體的進(jìn)化能力。評(píng)估函數(shù)的設(shè)置同優(yōu)化問題的求解目標(biāo)有關(guān)。比如在求解函數(shù)優(yōu)化問題時(shí)，問題定義的目標(biāo)函數(shù)可以作為評(píng)估函數(shù)的原型。評(píng)估函數(shù)應(yīng)滿足較優(yōu)染色體的適應(yīng)值較大的規(guī)定。因此對(duì)于一些求解最大值的數(shù)值優(yōu)化問題，我們可以直接套用問題定義的函數(shù)表達(dá)式。為了更好地提高選擇的效能，可以對(duì)評(píng)估函數(shù)做出一定的修正。目前主要的評(píng)估函數(shù)修正方法有：線性變換；乘冪變換；指數(shù)變換等。適應(yīng)度函數(shù)的重要性

適應(yīng)度函數(shù)的選取直接影響遺傳算法的收斂速度以及能否找到最優(yōu)解。一般而言，適應(yīng)度函數(shù)是由目標(biāo)函數(shù)變換而成的，對(duì)目標(biāo)函數(shù)值域的某種映射變換稱為適應(yīng)度的尺度變換（fitnessscaling）。幾種常見的適應(yīng)度函數(shù)直接轉(zhuǎn)換若目標(biāo)函數(shù)為最大化問題：Fit(f(x))=f(x)

若目標(biāo)函數(shù)為最小化問題：Fit(f(x))=-f(x)幾種常見的適應(yīng)度函數(shù)界限構(gòu)造法1

若目標(biāo)函數(shù)為最大化問題：若目標(biāo)函數(shù)為最小化問題：幾種常見的適應(yīng)度函數(shù)界限構(gòu)造法2

若目標(biāo)函數(shù)為最大化問題：若目標(biāo)函數(shù)為最小化問題：

c為目標(biāo)函數(shù)的保守估計(jì)值。適應(yīng)度函數(shù)的作用

適應(yīng)度函數(shù)設(shè)計(jì)不當(dāng)有可能出現(xiàn)欺騙問題：（1）進(jìn)化初期，個(gè)別超常個(gè)體控制選擇過程；（2）進(jìn)化末期，個(gè)體差異太小導(dǎo)致陷入局部極值。適應(yīng)度函數(shù)的設(shè)計(jì)單值、連續(xù)、非負(fù)、最大化合理、一致性計(jì)算量小通用性強(qiáng)適應(yīng)度函數(shù)的線性變換法

f’=α*f+β系數(shù)的確定滿足以下條件：①f’avg=favg②f’max=cmultf’avg

cmult=1.0~2.0適應(yīng)度函數(shù)的冪函數(shù)變換法

f’=fk

k與所求優(yōu)化相關(guān)k適應(yīng)度函數(shù)的指數(shù)變換法

f’=e-af

a決定了復(fù)制的強(qiáng)制性，其值越小，復(fù)制的強(qiáng)制性就越趨向于那些具有最大適應(yīng)性的個(gè)體。α理論上還沒有完全解決，影響算法的性能！種群數(shù)目交叉概率變異概率四、算法參數(shù)群體規(guī)模N

染色體長(zhǎng)度L

影響算法的搜索能力和運(yùn)行效率。若N設(shè)置較大，一次進(jìn)化所覆蓋的模式較多，可以保證群體的多樣性，從而提高算法的搜索能力，但是由于群體中染色體的個(gè)數(shù)較多，勢(shì)必增加算法的計(jì)算量，降低了算法的運(yùn)行效率。若N設(shè)置較小，雖然降低了計(jì)算量，但是同時(shí)降低了每次進(jìn)化中群體包含更多較好染色體的能力。N的設(shè)置一般為20~100。影響算法的計(jì)算量和交配變異操作的效果。L的設(shè)置跟優(yōu)化問題密切相關(guān)，一般由問題定義的解的形式和選擇的編碼方法決定。對(duì)于二進(jìn)制編碼方法，染色體的長(zhǎng)度L根據(jù)解的取值范圍和規(guī)定精度要求選擇大小。對(duì)于浮點(diǎn)數(shù)編碼方法，染色體的長(zhǎng)度L

跟問題定義的解的維數(shù)D相同。除了染色體長(zhǎng)度一定的編碼方法，Goldberg等人還提出了一種變長(zhǎng)度染色體遺傳算法MessyGA，其染色體的長(zhǎng)度并不是固定的。參數(shù)設(shè)計(jì)交配概率Pc

變異概率Pm

決定了進(jìn)化過程種群參加交配的染色體平均數(shù)目。取值一般為0.4至0.99。也可采用自適應(yīng)方法調(diào)整算法運(yùn)行過程中的交配概率。增加群體進(jìn)化的多樣性，決定了進(jìn)化過程中群體發(fā)生變異的基因平均個(gè)數(shù)。Pm的值不宜過大。因?yàn)樽儺悓?duì)已找到的較優(yōu)解具有一定的破壞作用，如果Pm的值太大，可能會(huì)導(dǎo)致算法目前處于的較好的搜索狀態(tài)倒退回原來較差的情況。Pm的取值一般為0.001至0.1之間。也可采用自適應(yīng)方法調(diào)整算法運(yùn)行過程中的Pm值。參數(shù)設(shè)計(jì)復(fù)制交叉變異為了避免有效基因的損失用于組合新的個(gè)體，降低對(duì)有效模式的破壞增加種群的有效性五、遺傳算子確定性采樣排擠模型最佳個(gè)體保存模型適應(yīng)值比例模型排序模型隨機(jī)錦標(biāo)賽模型無回放余數(shù)隨機(jī)采樣期望值模型選擇算子交配算子單性孢子交配算子邊重組交配算子循環(huán)交配算子順序交配算子部分匹配交配算子多點(diǎn)交配算子算術(shù)交配算子均勻交配算子兩點(diǎn)交配算子邊集合交配算子變異算子非均勻變異算子高斯變異算子邊界變異算子算子選擇1、選擇算子設(shè)群體大小為，其中個(gè)體

的適應(yīng)度為

，則被選擇的概率

為:

遺傳操作（1）適應(yīng)度比例方法(fitnessproportionmodel)適應(yīng)度比例方法是目前遺傳算法中最基本也是最常用的選擇方法。它也叫賭輪或蒙特卡羅（MonteCarlo）選擇。在該方法中，各個(gè)個(gè)體的選擇概率和其適應(yīng)度值成比例。14.4%49.2%30.9%5.5%1234使用賭輪方法的選擇（2）最佳個(gè)體保存方法（elitistmodel）該方法的思想是把群體中適應(yīng)度最高的個(gè)體不進(jìn)行配對(duì)交叉而直接復(fù)制到下一代中，此種選擇操作又稱復(fù)制。DeJong對(duì)此方法作了如下定義：設(shè)到時(shí)刻t（第t代）時(shí)，群體中a*(t)為最佳個(gè)體。又設(shè)A(t+1)為新一代群體，若A(t+1)中不存在a*(t)，則把a(bǔ)*(t)作為A(t+1)中的第n+1個(gè)個(gè)體。選擇

適應(yīng)度計(jì)算：按比例的適應(yīng)度函數(shù)（proportionalfitnessassignment）基于排序的適應(yīng)度計(jì)算（Rank-basedfitnessassignment）

選擇算法：輪盤賭選擇（roulettewheelselection）選擇

選擇算法：隨機(jī)遍歷抽樣（stochasticuniversalselection）局部選擇（localselection）截?cái)噙x擇（truncationselection）錦標(biāo)賽選擇（tournamentselection）除了上述選擇算子外，還有期望值方法(expectedvaluemodel)排序選擇方法(rank-basedmodel)聯(lián)賽選擇方法(tournamentselectionmodel)排擠方法(crowdingmodel)等幾個(gè)概念選擇壓力(selectionpressure):最佳個(gè)體選中的概率與平均個(gè)體選中概率的比值；偏差(bias)：個(gè)體正規(guī)化適應(yīng)度與其期望再生概率的絕對(duì)差值；個(gè)體擴(kuò)展(spread)：?jiǎn)蝹€(gè)個(gè)體子代個(gè)數(shù)的范圍；多樣化損失(lossofdiversity)：在選擇階段未選中個(gè)體數(shù)目占種群的比例；幾個(gè)概念選擇強(qiáng)度(selectionintensity):

將正規(guī)高斯分布應(yīng)用于選擇方法，期望平均適應(yīng)度；選擇方差(selectionvariance):將正規(guī)高斯分布應(yīng)用于選擇方法，期望種群適應(yīng)度的方差。個(gè)體選擇概率的常用分配方法按比例的適應(yīng)度分配（proportionalfitnessassignment）

某個(gè)體i，其適應(yīng)度為fi，則其被選取的概率Pi為：

個(gè)體ff2P12.56.250.1821.01.000.0333.09.000.2641.21.440.0452.14.410.1360.80.640.0272.56.250.1881.31.690.0590.90.810.02101.83.240.09個(gè)體選擇概率的常用分配方法基于排序的適應(yīng)度分配（rank-basedfitnessassignment）

線性排序（byBaker）

μ為種群大小，i為個(gè)體序號(hào)，ηmax代表選擇壓力。個(gè)體選擇概率的常用分配方法基于排序的適應(yīng)度分配（rank-basedfitnessassignment）

非線性排序（byMichalewicz）

i為個(gè)體序號(hào)，c為排序第一的個(gè)體的選擇概率。常用選擇方法輪盤賭選擇法（roulettewheelselection）

個(gè)體1234567891011適應(yīng)度2.01.81.61.41.21.00.80.60.40.20.1選擇概率0.180.160.150.130.110.090.070.060.030.020.0累計(jì)概率0.180.340.490.620.730.820.890.950.981.001.00常用選擇方法隨機(jī)遍歷抽樣法（stochasticuniversalsampling）

個(gè)體1234567891011適應(yīng)度2.01.81.61.41.21.00.80.60.40.20.1選擇概率0.180.160.150.130.110.090.070.060.030.020.0累計(jì)概率0.180.340.490.620.730.820.890.950.981.001.00設(shè)定n為需要選擇的個(gè)體數(shù)目，等距離選擇個(gè)體，選擇指針的距離為1／n。第一個(gè)指針的位置由[0，l／n]區(qū)間的均勻隨機(jī)數(shù)決定。如圖所示，需要選擇6個(gè)個(gè)體，指針間的距離為l／6＝o.167，第一個(gè)指針的隨機(jī)位置為0.1，按這種選擇方法被選中作為交配集個(gè)體為：1．2，3．4，6，8。常用選擇方法局部選擇法（localselection）

(1)線形鄰集在局部選擇法中，每個(gè)個(gè)體處于一個(gè)約束環(huán)境中，稱為局部鄰域(而其他選擇方法中視整個(gè)種群為個(gè)體之鄰域)，個(gè)體僅與其鄰近個(gè)體產(chǎn)生交互，該鄰域的定義由種群的分布結(jié)構(gòu)給出。鄰域可被當(dāng)作潛在的交配伙伴。首先均勻隨機(jī)地選擇一半交配種群，選擇方法可以是隨機(jī)遍歷方法也可以是截?cái)噙x擇方法，然后對(duì)每個(gè)被選個(gè)體定義其局部鄰域，在鄰域內(nèi)部選擇交配伙伴。常用選擇方法局部選擇法（localselection）

(2)

兩對(duì)角鄰集常用選擇方法局部選擇法（localselection）

(2)

兩對(duì)角鄰集常用選擇方法截?cái)噙x擇法（truncationselection）

個(gè)體按適應(yīng)度排列，只有優(yōu)秀個(gè)體能夠稱為父?jìng)€(gè)體，參數(shù)為截?cái)嚅y值（被選作父?jìng)€(gè)體的百分比）。截?cái)嚅y值1％10％20％40％50％80％選擇強(qiáng)度2.661.761.20.970.80.34常用選擇方法錦標(biāo)賽選擇法（tournamentselection）隨機(jī)從種群中挑選一定數(shù)目個(gè)體，其中最好的個(gè)體作為父?jìng)€(gè)體，此過程重復(fù)進(jìn)行完成個(gè)體的選擇。競(jìng)賽規(guī)模12351030選擇強(qiáng)度00.560.851.151.532.04交叉點(diǎn)（1）一點(diǎn)交叉（one-pointcrossover）具體操作是：在個(gè)體串中隨機(jī)設(shè)定一個(gè)交叉點(diǎn)，實(shí)行交叉時(shí)，該點(diǎn)前或后的兩個(gè)個(gè)體的部分結(jié)構(gòu)進(jìn)行互換，并生成兩個(gè)新個(gè)體。如：個(gè)體A10011111001000新個(gè)體A

個(gè)體B00110000011111新個(gè)體B

2、交叉算子此外還有多點(diǎn)交叉和一致交叉（uniformcrossover）等交叉算子。設(shè)置兩個(gè)交叉點(diǎn)，如：個(gè)體A10011111011111新個(gè)體A

個(gè)體B00110000001000新個(gè)體B

（2）兩點(diǎn)交叉（two-pointcrossover）在染色體交配階段，每個(gè)染色體能否進(jìn)行交配由交配概率Pc（一般取值為0.4到0.99之間）決定，其具體過程為：對(duì)于每個(gè)染色體，如果Random(0,1)小于Pc則表示該染色體可進(jìn)行交配操作（其中Random(0,1)為[0,1]間均勻分布的隨機(jī)數(shù)），否則染色體不參與交配直接復(fù)制到新種群中。每?jī)蓚€(gè)按照Pc交配概率選擇出來的染色體進(jìn)行交配，經(jīng)過交換各自部分基因，產(chǎn)生兩個(gè)新的子代染色體。具體操作是隨機(jī)產(chǎn)生一個(gè)有效的交配位置，染色體交換位于該交配位置后的所有基因。交叉或基因重組

實(shí)值重組（realvaluedrecombination）：離散重組（discreterecombination）中間重組（intermediaterecombination）線性重組（linearrecombination）擴(kuò)展線性重組（extendedlinearrecombination）交叉或基因重組

二進(jìn)制交叉（binaryvaluedcrossover）：?jiǎn)吸c(diǎn)交叉(single-pointcrossover)多點(diǎn)交叉(multiple-pointcrossover)均勻交叉(uniformcrossover)洗牌交叉(shufflecrossover)縮小代理交叉(crossoverwithreducedsurrogate)實(shí)值重組離散重組

子個(gè)體的每個(gè)變量可以按等概率隨機(jī)地挑選父?jìng)€(gè)體。父?jìng)€(gè)體112

25

5父?jìng)€(gè)體2123

4

34子個(gè)體1123

4

5子個(gè)體212

4

34實(shí)值重組中間重組

子個(gè)體＝父?jìng)€(gè)體1＋α×（父?jìng)€(gè)體2－父?jìng)€(gè)體1）

α是比例因子，由[-d,1+d]上均勻分布地隨機(jī)數(shù)產(chǎn)生。

d=0時(shí)為中間重組，一般取d=0.25。子代的每個(gè)變量均產(chǎn)生一個(gè)α。實(shí)值重組中間重組

父?jìng)€(gè)體1

12255父?jìng)€(gè)體2

123434子個(gè)體1子個(gè)體2α值樣本1

0.51.1-0.1α值樣本2

0.10.80.512＋0.5×（123－12）=67.567.525＋1.1×（4－25）=1.91.92.112＋0.1×（123－12）=23.123.18.219.5實(shí)值重組中間重組

實(shí)值重組線性重組

父?jìng)€(gè)體1

12255父?jìng)€(gè)體2

123434子個(gè)體1子個(gè)體2α值樣本10.5α值樣本20.112＋0.5×（123－12）=67.567.525＋0.5×（4－25）=14.514.519.512＋0.1×（123－12）=23.123.122.97.9實(shí)值重組線性重組

二進(jìn)制交叉單點(diǎn)交叉

二進(jìn)制交叉多點(diǎn)交叉

二進(jìn)制交叉均勻交叉

父?jìng)€(gè)體1

01110011010

父?jìng)€(gè)體210101100101子個(gè)體1

1

11

011

11

1

1

1子個(gè)體2

0

01

100

00

0

0

0

樣本101100011010樣本210011100101變異點(diǎn)（1）基本變異算子對(duì)群體個(gè)體串隨機(jī)挑選一個(gè)或多個(gè)基因，并對(duì)這些基因做變動(dòng)。如：個(gè)體A10011111101011新個(gè)體A

3、變異算子逆轉(zhuǎn)點(diǎn)個(gè)體A1001011110101011新個(gè)體A

（2）逆轉(zhuǎn)算子（inversionoperator）染色體的變異作用于基因之上，對(duì)于交配后新種群中染色體的每一位基因，根據(jù)變異概率Pm判斷該基因是否進(jìn)行變異。如果Random(0,1)小于Pm，則改變?cè)摶虻娜≈担ㄆ渲蠷andom(0,1)為[0,1]間均勻分布的隨機(jī)數(shù)）。否則該基因不發(fā)生變異，保持不變。實(shí)值變異一般采用：二進(jìn)制變異

事先給定最大進(jìn)化步數(shù)，或者判斷最優(yōu)值在連續(xù)若干步?jīng)]有變化。六、算法終止條件編碼表示:初始化:適配值:二進(jìn)制選擇策略:遺傳算子:雜交變異停止準(zhǔn)則:已經(jīng)找到能接受的解;迭代了預(yù)置的次數(shù).研究重點(diǎn)主要集中在以下幾方面：算法的數(shù)學(xué)基礎(chǔ)：包括算法的收斂性理論，早熟現(xiàn)象與欺騙問題，交叉算子的數(shù)學(xué)意義與統(tǒng)計(jì)解釋，參數(shù)設(shè)置對(duì)算法的影響等。算法與其他優(yōu)化技術(shù)的比較和融合：充分利用遺傳算法的大范圍群體搜索性能，與快速收斂的局部?jī)?yōu)化方法混合產(chǎn)生有效的全局優(yōu)化方法，從根本上提高遺傳算法計(jì)算性能。算法的改進(jìn)和深化：據(jù)實(shí)際應(yīng)用不斷改進(jìn)和完善算法的編碼策略、基因操作方法、參數(shù)選擇等。算法的并行化研究：并行遺傳算法(PGA)正成為一個(gè)重要的研究方向。第五節(jié)遺傳算法的改進(jìn)及其并行性算法改進(jìn)遺傳算法本質(zhì)上依賴于問題的編碼以及遺傳操作算子，要發(fā)展遺傳算法也要以這幾個(gè)方面作為突破口解決實(shí)際問題，經(jīng)驗(yàn)往往要起到?jīng)Q定性作用，不要期望能很快很好的解決問題多親和單親遺傳算法多目標(biāo)優(yōu)化問題和其他優(yōu)化算法整合，取長(zhǎng)補(bǔ)短

遺傳算法的改進(jìn)

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

遺傳算法的改進(jìn)

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

1、CHC算法

遺傳算法的改進(jìn)

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

1、CHC算法

遺傳算法的改進(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í)，逐漸地減小該閾值。

1、CHC算法

遺傳算法的改進(jìn)

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

1、CHC算法

遺傳算法的改進(jìn)

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

2、自適應(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

。

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

自適應(yīng)方法fmax——群體中最大的適應(yīng)度值；favg——每代群體的平均適應(yīng)度值；f’——要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值；f——要交叉或變異的個(gè)體適應(yīng)度值；k1、k2、k3、k4取(0,1)的值

遺傳算法的改進(jìn)

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

自適應(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

；采用精英選擇策略；

遺傳算法的改進(jìn)

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

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

遺傳算法的改進(jìn)

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

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

遺傳算法的改進(jìn)

3、基于小生境技術(shù)的遺傳算法

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

遺傳算法的改進(jìn)

3、基于小生境技術(shù)的遺傳算法

排擠（crowding,1975）機(jī)制設(shè)置排擠因子CF（CF=2或3），隨機(jī)選取1/CF的個(gè)體組成排擠成員，排擠與其相似（用距離來度量）的個(gè)體；個(gè)體之間的相似性可用個(gè)體編碼串之間的海明距離來度量。

遺傳算法的改進(jìn)

3、基于小生境技術(shù)的遺傳算法

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

遺傳算法的改進(jìn)

3、基于小生境技術(shù)的遺傳算法

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

σshare是niche的半徑，由使用者給定。

遺傳算法的改進(jìn)

3、基于小生境技術(shù)的遺傳算法

共享（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è)種群的收斂。

遺傳算法的改進(jìn)

3、基于小生境技術(shù)的遺傳算法

是生命科學(xué)中免疫原理與傳統(tǒng)遺傳算法的結(jié)合。核心免疫算子接種疫苗免疫選擇理論上是概率1收斂的。免疫遺傳算法引言遺傳算法的迭代搜索過程：“產(chǎn)生----測(cè)試”一定程度上不可避免退化現(xiàn)象出現(xiàn)忽視特征信息，缺少靈活性深入挖掘和利用人類的智能資源，這是免疫遺傳算法的出發(fā)點(diǎn)。全免疫(fullimmunity)目標(biāo)免疫(targetimmunity)非特異性特異性全免疫指種群中每個(gè)個(gè)體在遺傳算子作用后，對(duì)其每一環(huán)節(jié)進(jìn)行一次免疫操作。目標(biāo)免疫指在進(jìn)行了遺傳操作后，經(jīng)過一定的判斷，個(gè)體僅在作用點(diǎn)處發(fā)生免疫操作。一、免疫遺傳算法首先，對(duì)所求解問題進(jìn)行具體分析，從中提取最基本的特征信息。其次，對(duì)特征信息進(jìn)行處理，將其轉(zhuǎn)化為求解問題的一種方案?？乖?antigen)疫苗(vaccine)抗體(antibody)最后，將此方案以適當(dāng)?shù)男问睫D(zhuǎn)化為免疫算子，以實(shí)現(xiàn)具體操作。實(shí)際操作過程1、接種疫苗方法與目的：按照先驗(yàn)知識(shí)來修改其某些基因位上的基因，使所得個(gè)體以較大概率具有更高的適應(yīng)值。其一、每一基因位上的信息都錯(cuò)誤，則轉(zhuǎn)移概率為0。其二、每一基因位都是正確的，則轉(zhuǎn)移概率為1。實(shí)現(xiàn)考慮以下兩種特殊情況：2、免疫選擇目的：改進(jìn)退化個(gè)體。第一步是免疫檢測(cè)，不如父代則被父代代替。否則進(jìn)行第二步。第二步是退火選擇。操作分兩步完成：算法步驟：Step1隨機(jī)產(chǎn)生初始父代群體A1;Step2根據(jù)先驗(yàn)知識(shí)提取疫苗;Step3若當(dāng)前種群包含了最佳個(gè)體，結(jié)束;否則進(jìn)行以下的步驟;Step4對(duì)種群Ak進(jìn)行交叉操作得到種群Bk;Step5對(duì)種群Bk進(jìn)行變異操作得到種群Ck;Step6對(duì)種群Ck進(jìn)行接種疫苗操作得到種群Dk;Step7對(duì)種群Dk進(jìn)行免疫操作得到下一代父代種群Ak+1，轉(zhuǎn)step3。算法收斂性分析：定理免疫遺傳算法是概率1收斂的，若算法中略去免疫算子，則該算法將不再保證收斂到全局最優(yōu)值。免疫疫苗的選取示例：1、分析待求問題，搜集特征信息最短距離法2、根據(jù)特征信息制作免疫疫苗在最終方案中，必然包括相鄰城市間最短距離。由此作為提取疫苗的依據(jù)。3接種疫苗并行計(jì)算單指令流多數(shù)據(jù)流計(jì)算機(jī)多指令流多數(shù)據(jù)流計(jì)算機(jī)并行計(jì)算網(wǎng)絡(luò)串行計(jì)算單指令流單數(shù)據(jù)流處理器并行遺傳算法并行遺傳算法標(biāo)準(zhǔn)型并行方法分解型并行方法標(biāo)準(zhǔn)型并行方法分解型并行方法子群體進(jìn)化信息交換問題分解型并行方法交換的時(shí)間交換的方式交換的內(nèi)容群體模型島嶼模型踏腳石模型鄰居模型0001100000010111100100000001011001110100101010101011100101101001011011110000000110011101000001010011

遺傳算法的基本操作

簡(jiǎn)單實(shí)例產(chǎn)生初始種群計(jì)算適應(yīng)度（8）（5）（2）（10）（7）（12）（5）（19）（10）（14）簡(jiǎn)單實(shí)例選擇個(gè)體染色體適應(yīng)度選擇概率累積概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111488＋5＋2＋10＋7＋12＋5＋19＋10＋140.08695758＋5＋2＋10＋7＋12＋5＋19＋10＋140.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174

遺傳算法的基本操作

簡(jiǎn)單實(shí)例選擇個(gè)體染色體適應(yīng)度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.