智能計算及應(yīng)用3-遺傳算法-2.ppt

1、遺傳算法(續(xù))，3遺傳算法的改良基于CHC算法適應(yīng)遺傳算法小學(xué)生環(huán)境技術(shù)的遺傳算法4遺傳算法的應(yīng)用制約函數(shù)最優(yōu)化問題解決多目標(biāo)優(yōu)化問題解決組合優(yōu)化問題遺傳算法在模式識別上的應(yīng)用， 3采用遺傳算法的改良混合遺傳算法的動態(tài)適應(yīng)技術(shù)的非標(biāo)準(zhǔn)遺傳操作算子的并聯(lián)遺傳算法等。 遺傳算法的改良、改良構(gòu)想1991年Eshelman提出的改良遺傳算法c :世代間精英階層選擇(crossgenerationalelitistselection )策略h :異物種類重組(Heterogeneous recombination )； c :大變異(Cataclysmic mutation )。 1. CHC算法，遺傳

2、算法的改良，將上一代的個體群和用新的交叉方法產(chǎn)生的個體群混合，從其中以一定的概率選擇優(yōu)秀個體的交叉操作造成的劣化個體即使很多，由于原個體群的很多個體殘留，所以能夠更好地保持不會引起個體的評估價值降低的遺傳多樣性的排序方法是、CHC算法、遺傳算法的改良、交叉均勻交叉的改良： 2個母個體的二進(jìn)制位值不同的二進(jìn)制位數(shù)為m時，從其中隨機(jī)選擇m/2個位置，執(zhí)行母個體的二進(jìn)制位值的交換，這種操作對模式具有很強(qiáng)的破壞性。 如果個體間距低于該閾值，則確定不進(jìn)行交叉操作的閾值。 進(jìn)化收斂后，在云同步上，逐漸減小該閾值。 CHC算法、遺傳算法的改良、變異在進(jìn)化前期不采取變異操作，當(dāng)種群在一定收斂時期進(jìn)化時，從最佳

3、個體中選擇一部分個體進(jìn)行初始化的初始化：選擇一定比例(擴(kuò)散速率，一般為0.35 )的基因座，隨機(jī)決定它們的二進(jìn)制位值。CHC算法、遺傳算法的改進(jìn)、殘奧儀分析交叉概率Pc和突變概率Pm的選擇在影響遺傳算法行為和性能的關(guān)鍵方面，直接影響算法的收斂性。 Pc越大，新個體的發(fā)生速度越快，但一過大會，優(yōu)秀個體的結(jié)構(gòu)就會立即被破壞。 Pc太小，搜索過程太慢，不能停止的Pm太小，難以產(chǎn)生新的個體結(jié)構(gòu)，Pm太大，成為純粹的隨機(jī)搜索的2適應(yīng)遺傳算法，遺傳算法的改良，適應(yīng)策略Srinvivas等Pc和Pm可以根據(jù)適應(yīng)度自動變化的適應(yīng)遺傳對于適應(yīng)度高的個體，與低Pc和Pm對應(yīng)的低適應(yīng)度的個體與高Pc和Pm對應(yīng)。 自

4、適應(yīng)遺傳算法、遺傳算法的改良、自適應(yīng)方法fmax群中最大的每個自適應(yīng)度值favg世代的平均自適應(yīng)度值f交叉的2個個體中大的自適應(yīng)度值f交叉或變異的個體自適應(yīng)度的值、自適應(yīng)遺傳算法、k1、k2、k3、k4取(0，1 )的值，遺傳算法的改良、自適應(yīng)前期優(yōu)秀個體可能是局部最有利的，因此采用了將最大適應(yīng)度個體的交叉概率和變異概率從0提高到Pc2和Pm2的精英階層選擇策略，遺傳算法的改良，適應(yīng)方法的進(jìn)一步改良，適應(yīng)遺傳算法，遺傳算法的改良， 小學(xué)生環(huán)境概念小學(xué)生環(huán)境(niche ) :在生物科學(xué)特定環(huán)境下的組織機(jī)能自然段中，通常聚集特征性性狀相似的物種，在同類中使子孫后代交配繁衍生息。 在SGA中，“近

5、親繁殖”容易的NGA(Niche Generic Algorithm )將各世代的個體分為幾個等級，各等級選擇優(yōu)秀的個體構(gòu)成一個個體群的優(yōu)點(diǎn)：維持解的多樣性，提高全球搜索能力，最適合復(fù)雜的多峰函數(shù)的優(yōu)化3、基于小生環(huán)境技術(shù)的遺傳算法、遺傳算法的改進(jìn)、選擇策略預(yù)選反應(yīng)歷程、排斥反應(yīng)歷程、共享反應(yīng)歷程預(yù)選(preselection，1970 )當(dāng)反應(yīng)歷程子個體的適應(yīng)度超過母個體的適應(yīng)度時，子個體可以取代母個體，否則母個體可以有效地維持剩馀個體群的多樣性基于生境技術(shù)的遺傳算法、遺傳算法的改良、排除(crowding，1975 )反應(yīng)歷程設(shè)置排除因子CF(CF=2或3 )，隨機(jī)選擇1/CF的個體構(gòu)成排

6、除成員，排除與其相似的個體的個體間的相似性，可以通過個體查詢密碼列間的海明距離來測定。 基于小生環(huán)境技術(shù)的遺傳算法、遺傳算法的改進(jìn)、共享(sharing，1987 )反應(yīng)歷程是通過個體間相似程度的共享函數(shù)來調(diào)節(jié)各個體適應(yīng)度的共享函數(shù)的目的：地理區(qū)分搜索空間的多個峰，在各峰中接受一定比例的個體， 比例數(shù)表示與峰值高度相關(guān)的基于小學(xué)生環(huán)境技術(shù)的遺傳算法、遺傳算法的改良、共有(sharing，1987 )反應(yīng)歷程共有函數(shù)的值越大，個體間越類似，Sh(dij )，dij是兩個個體I和j之間的距離。 share是niche的半徑，由用戶指定。 基于棲息技術(shù)的遺傳算法、遺傳算法的改良、共享(sharing

7、，1987 )反應(yīng)歷程共享法降低了個體的適應(yīng)度，即適應(yīng)度值fi除以一個niche計數(shù)mi :在距離在share范圍內(nèi)的個體之間削減適應(yīng)度， 這些個個體包含在一個niche內(nèi)的基于小學(xué)生環(huán)境技術(shù)的遺傳算法，4遺傳算法的應(yīng)用，制約最優(yōu)化問題的表現(xiàn)，1制約函數(shù)最優(yōu)化問題的解決，遺傳算法的應(yīng)用，解決制約問題的無制約問題(罰函數(shù)法， peel無約束問題的方法已得到改進(jìn)，可以用于有約束的情況(梯度心理投射算法)，發(fā)展緩慢。 解決遺傳算法有制約的問題的關(guān)鍵是制約條件的處理(不能在沒有制約的問題上直接處理：隨機(jī)生成的初期點(diǎn)上有很多不可能解的遺傳算子作用于可行解的話，有可能產(chǎn)生不能執(zhí)行解)。 約束函數(shù)最優(yōu)化問題

8、、遺傳算法的應(yīng)用、一般方法罰函數(shù)法將罰函數(shù)納入適應(yīng)度評價：關(guān)鍵是如何設(shè)定罰函數(shù)、是否太輕、是否太重，應(yīng)慎重找出懲罰平衡，并對不同問題設(shè)定罰函數(shù)。 約束函數(shù)最優(yōu)化問題、遺傳算法的應(yīng)用、一般方法協(xié)同進(jìn)化遺傳算法(Coevolutionary Genetic Algorithm，1997 )食物鏈關(guān)系、基于內(nèi)共生等的生物進(jìn)化現(xiàn)象稱為協(xié)同進(jìn)化的一個種群由問題的解構(gòu)成，另一個種群由約束構(gòu)成，兩個種群協(xié)同進(jìn)化解決約束函數(shù)最優(yōu)化問題，罰函數(shù)法評價函數(shù)的構(gòu)造：加法乘法、遺傳算法的應(yīng)用、約束函數(shù)最優(yōu)化問題的解決、罰函數(shù)法罰函數(shù)分類：懲罰簡單約束問題變量的復(fù)雜約束問題，包括可變懲罰率和違反約束的懲罰量兩部分。 遺

9、傳算法的應(yīng)用解決了約束函數(shù)最優(yōu)化問題，約束違反的程度隨著約束違反的程度變得嚴(yán)重而增加懲罰壓力，靜態(tài)懲罰增加的進(jìn)化迭代次數(shù)隨著進(jìn)化過程的發(fā)展而增加懲罰壓力，動態(tài)懲罰。 尺罰函數(shù)交叉運(yùn)算：設(shè)母個體為x=x1，x2，xn和y=y1，y2，yn單純交叉單點(diǎn)算術(shù)交叉整體的算術(shù)交叉方向的交叉： x=r(x-y) x，r為(0)遺傳算法的應(yīng)用，限制函數(shù)最優(yōu)化問題的解決，罰函數(shù)法變異演算：將母體設(shè)為x=x1，x2，xn均勻變異(動態(tài)變異)邊界變異： x=x1，x2，xk，xn方向變異： x=x rd， d是目標(biāo)函數(shù)的近似梯度，遺傳算法的應(yīng)用，約束函數(shù)最優(yōu)化問題的解決，遺傳算法的應(yīng)用，求解線性約束最優(yōu)化問題的遺

10、傳算法線性約束最優(yōu)化問題一般形式是約束函數(shù)最優(yōu)化問題的解決，遺傳算法的應(yīng)用， 求解線性約束最優(yōu)化問題的遺傳算法線性約束最優(yōu)化問題：目標(biāo)函數(shù)是可線形函數(shù)還是不可線形函數(shù)可思維方法的變量，等式約束設(shè)置修正罰函數(shù)設(shè)置修正特殊遺傳操作，約束函數(shù)優(yōu)化問題的解決，遺傳算法的應(yīng)用，多目標(biāo)優(yōu)化問題解的存在性的解決，2多目標(biāo)優(yōu)化問題的解決，遺傳算法的應(yīng)用， Pareto最優(yōu)性理論是k個目標(biāo)函數(shù)最小化的問題中，如果不存在決定向量x*F為Pareto最佳的另一個決定向量xF，則對云同步滿意，多目標(biāo)最優(yōu)化問題、遺傳算法的應(yīng)用、Pareto最優(yōu)性理論多目標(biāo)最優(yōu)化問題的解通常是多個滿足解的集合，而Pareto 解決多目標(biāo)

11、最優(yōu)化問題、遺傳算法的應(yīng)用、傳統(tǒng)方法多目標(biāo)加權(quán)法層次優(yōu)化法目標(biāo)修正法等特征：將多目標(biāo)函數(shù)轉(zhuǎn)換為單目標(biāo)函數(shù)處理，只能得到特定條件下的帕累托解。 解決多目標(biāo)最優(yōu)化問題、遺傳算法的應(yīng)用、多目標(biāo)優(yōu)化遺傳算法的優(yōu)點(diǎn)：不僅可以并行處理可能解的定徑套的Pareto尖端的形狀和連續(xù)性，也容易處理不連續(xù)凹形的Pareto尖端。 現(xiàn)在基于Pareto的遺傳算法占了主要地位。 解決多目標(biāo)最優(yōu)化問題、遺傳算法的應(yīng)用、多目標(biāo)優(yōu)化的遺傳算法聚合函數(shù)方法：無需改變以多個目標(biāo)函數(shù)表示為一個目標(biāo)函數(shù)作為遺傳算法自適應(yīng)函數(shù)(聚合)的遺傳算法，但權(quán)重難以確定的改進(jìn)：自適應(yīng)字體粗細(xì)值。 多目標(biāo)最優(yōu)化問題、遺傳算法的應(yīng)用、多目標(biāo)優(yōu)化的

12、遺傳算法向量評價遺傳算法(非Pareto法): 子種群發(fā)生按目標(biāo)函數(shù)分別選擇。 基于多目標(biāo)最優(yōu)化問題、遺傳算法的應(yīng)用、多目標(biāo)優(yōu)化的遺傳算法排序的多目標(biāo)遺傳算法：根據(jù)“帕累托最優(yōu)個體”的概念對整個個體排序，并根據(jù)該排序?qū)M(jìn)化過程中的選擇運(yùn)算，使得上位帕累托最優(yōu)個體將更多的機(jī)會遺傳給下一代集團(tuán)。 多目標(biāo)最優(yōu)化問題、遺傳算法的應(yīng)用、多目標(biāo)優(yōu)化的遺傳算法小生環(huán)境Pareto遺傳算法：使種群向在Pareto頂端面均勻分布的方向進(jìn)化，通過共享函數(shù)定義小生環(huán)境來實(shí)現(xiàn)，以保證優(yōu)良的過程不收斂于具有可執(zhí)行區(qū)域的局部。 多用途最優(yōu)化問題、遺傳算法的應(yīng)用、解決TSP Benchmark問題41 94的37 84；

13、54、67； 25、62； 七六四二九六八； 71 44； 54、62； 83、69； 64 60； 18 54 22 60； 83、46； 91 38 25 38 24 42； 58 69 71 71； 74、78； 87 76； 18 40； 13 40； 82七六二三二； 58 35 45 21； 41二六四三五； 解決450、3組合最優(yōu)化問題，遺傳算法的應(yīng)用，TSP Benchmark問題查詢密碼：采用直接解的表達(dá)形式，30二進(jìn)制位(30個城市)長，各代表通過的城市號碼(無重復(fù))； 適應(yīng)度函數(shù)：個體表示的路徑距離的倒數(shù)選擇：輪盤賭方法、組合最優(yōu)化問題的解決、遺傳算法的應(yīng)用、TSP Be

14、nchmark問題交叉：有序交叉法1 )隨機(jī)選擇兩個道路交叉口2 )兩個母個體交換中間部分3 )交換后交換重復(fù)的城市號碼。解決組合關(guān)最優(yōu)化問題字，x 133609|4561|32 x 2336087|1432|95、x 133609|1403|32x 233608|457|965 x 133609|14032|756 x 2336083|4561|902，遺傳算法初始?xì)垔W表：種群規(guī)模100交叉概率0.8變異概率0.8代數(shù)2000結(jié)束，組合最優(yōu)化問題解決，遺傳算法的應(yīng)用，TSP Benchmark問題執(zhí)行結(jié)果：組合最優(yōu)化問題解決，遺傳算法TSP Benchmark問題執(zhí)行結(jié)果：組合最優(yōu)化問題解決，遺傳算法的應(yīng)用， TSP Benchmark問題執(zhí)行結(jié)果：組合最優(yōu)化問題解析，遺傳算法的應(yīng)用，TSP Benchmark問題執(zhí)行結(jié)果：組合最優(yōu)化問題解析，遺傳算法的應(yīng)用，tsp組合最優(yōu)化問題的解析，遺傳算法的應(yīng)用， TSP Benchmark問題的執(zhí)行結(jié)果：組合最優(yōu)化問題的解決、遺傳算法的應(yīng)用、遺傳算法的特征提取目的：從可能的m個特征中根據(jù)某個評價標(biāo)準(zhǔn)選擇d個特征(md )。 4遺傳算法在模式識別中的應(yīng)用，遺傳算法的應(yīng)用，遺傳算法對特征提取個體的表達(dá)方法：長度為l的個體對應(yīng)于l維的二進(jìn)制特征向量，其各二進(jìn)制位表示是包含還是排除對應(yīng)的特征。 一個個體是