現(xiàn)代智能優(yōu)化算法遺傳算法

現(xiàn)代智能優(yōu)化算法—

遺傳算法2008年2月1簡介1995畢業(yè)于東北電力學(xué)院，獲學(xué)士學(xué)位2000年畢業(yè)于東北電力學(xué)院，獲碩士學(xué)位2005年畢業(yè)于天津大學(xué)，獲博士學(xué)位2007年UniveristyofStrathclyde博士后2現(xiàn)代智能優(yōu)化算法遺傳算法禁忌算法蟻群算法粒子群算法細(xì)菌算法混沌算法TSGAACOPSOBCCOA混沌算法DE3遺傳算法（GeneticAlgorithm,GA），是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計算模型。它是由美國Michigan大學(xué)的J.Holland教授于1975年首先提出的。其主要特點是群體搜索策略和群體中個體之間的信息交換，搜索不依賴于梯度信息，尤其適用于處理傳統(tǒng)搜索方法難于解決的復(fù)雜和非線性問題，可廣泛用于組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制等領(lǐng)域，是21世界有關(guān)智能計算中的關(guān)鍵技術(shù)之一。4GA四個基本條件1.存在由多個生物個體組成的種群2.生物個體之間存在著差異，或全體具有

多樣性3.生物能夠自我繁殖4.不同個體具有不同的環(huán)境生存能力，具有優(yōu)良基因結(jié)構(gòu)的個體繁殖能力強(qiáng)，反之則弱5GA--特點遺傳算法以決策變量的編碼作為運算對象。傳統(tǒng)的優(yōu)化算法往往直接利用決策變量的實際值本身進(jìn)行優(yōu)化計算，但遺傳算法不是直接以決策變量的值，而是以決策變量的某種形式的編碼為運算對象，從而可以很方便地引入和應(yīng)用遺傳操作算子遺傳算法直接以目標(biāo)函數(shù)值作為搜索信息。傳統(tǒng)的優(yōu)化算法往往不只需要目標(biāo)函數(shù)值，還需要目標(biāo)函數(shù)的導(dǎo)數(shù)等其它信息。這樣對許多目標(biāo)函數(shù)無法求導(dǎo)或很難求導(dǎo)的函數(shù)，遺傳算法就比較方便。6GA--特點遺傳算法同時進(jìn)行解空間的多點搜索。傳統(tǒng)的優(yōu)化算法往往從解空間的一個初始點開始搜索，這樣容易陷入局部極值點。遺傳算法進(jìn)行群體搜索，而且在搜索的過程中引入遺傳運算，使群體又可以不斷進(jìn)化。這些是遺傳算法所特有的一種隱含并行性。遺傳算法使用概率搜索技術(shù)。遺傳算法屬于一種自適應(yīng)概率搜索技術(shù)，其選擇、交叉、變異等運算都是以一種概率的方式來進(jìn)行的，從而增加了其搜索過程的靈活性。實踐和理論都已證明了在一定條件下遺傳算法總是以概率1收斂于問題的最優(yōu)解。7達(dá)爾文1858年用自然選擇來解釋物種起源和生物的進(jìn)化，其自然選擇學(xué)說包括以下三個方面1遺傳種瓜得瓜，種豆得豆。生物有了這個特征，物種才能穩(wěn)定存在；2變異一母生九子，九子各不同。變異的選擇和積累是生物多樣性的根源；3適者生存具有適應(yīng)性變異的個體被保留下來，通過一代代生存環(huán)境的選擇作用，物種一代代進(jìn)化，演變?yōu)樾碌奈锓N8GA的基礎(chǔ)術(shù)語染色體（Chromosome）生物細(xì)胞中含有的一種微小的絲狀化合物。是遺傳物質(zhì)的主要載體，由多個遺傳基因組成DNA&RNAinthechromosome基因（gene）也稱遺傳因子，DNA或RNA長鏈中占有一定位置的基本單位。生物的基因數(shù)量根據(jù)物種不同多少不一，從幾個（病毒）到幾萬個（動物）。9GA的基礎(chǔ)術(shù)語基因座（locus）染色體中基因的位置表現(xiàn)型（phenotype）由染色體決定性狀的外部表現(xiàn)基因型（genetype）與表現(xiàn)型密切相關(guān)的基因組成個體（individual）指染色體帶有特征的實體種群（population）一定數(shù)量個體的集合10GA的基礎(chǔ)術(shù)語適應(yīng)度（fitness）個體對環(huán)境的適應(yīng)程度進(jìn)化（evolution）生物逐漸適應(yīng)其生存環(huán)境，使得其品質(zhì)不斷提高選擇（selection）指決定以一定概率從種群中選擇若干個體的操作。一般而言，選擇的過程是一種基于適應(yīng)度的優(yōu)勝劣汰的過程復(fù)制（reproduction）細(xì)胞分裂時，遺傳物質(zhì)DNA通過復(fù)制轉(zhuǎn)移到新的細(xì)胞中，新的細(xì)胞就繼承了舊細(xì)胞的基因11GA的基礎(chǔ)術(shù)語交叉（crossover）兩個染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個新的染色體變異（mutation）在細(xì)胞復(fù)制時，基因的某個位發(fā)生某種突變，產(chǎn)生新的染色體編碼（coding）DNA中遺傳信息按一定的方式排列，也可看作從表現(xiàn)型到遺傳型的映射解碼（decoding）從遺傳型到表現(xiàn)型的映射12GA的三個基本算子復(fù)制／選擇(Reproduction/Selection)

依據(jù)每一物種的適應(yīng)程度來決定其在下一代中應(yīng)被復(fù)制或淘汰個數(shù)的多少輪盤式選擇競爭式選擇13GA三個基本算子—交叉

交叉式一種提供個體間彼此交換信息的機(jī)制，交叉過程主要是母代中較優(yōu)良的染色體作某些基因的交換，預(yù)期產(chǎn)生更優(yōu)良的后代。一般常見的交叉方式有：

（1）單點交叉(One-pointcrossover)

（2）雙點交叉(Tail-tailcrossover)

（3）均勻交叉14GA三個基本算子—變異

通過突變的方式，使得解可以跳脫單純的交叉產(chǎn)生的區(qū)域，進(jìn)而產(chǎn)生新的染色體，變異的過程主要以隨機(jī)的方式，將染色體的基因位由0變成1或由1變成0，主要的變異方式有：（1）等位基因突變(SimpleMutation)（2）均勻突變(UniformMutation)（3）非均勻突變(Non-UniformMutation)15GA的基本流程根據(jù)問題編碼，并初始化種群計算群體適應(yīng)度選擇操作交叉操作變異操作滿足收斂條件否N輸出計算結(jié)果Y16算例說明—編碼求解問題maxf(x)=x2

[0,31]x取正整數(shù)第一步：編碼采用二進(jìn)制形式我們把變量x編碼為5位長的二進(jìn)制無符號整數(shù)表示形式0000003111111700111120110017算例說明—種群生成第二步初始種群的生成由于遺傳算法的群體型操作需要，所以為遺傳操作準(zhǔn)備了一個由若干初始解組成的初始群體。這里我們?nèi)∪后w大小為4，即群體由4個個體組成，每個個體通過隨機(jī)初始化產(chǎn)生初始群體也稱為進(jìn)化的初始代，即第一代（firstgeneration），初始化后，群體為

01101110000100010011

18算例說明—適應(yīng)度評價遺傳算法用評價函數(shù)（適應(yīng)度函數(shù)值）來評估個體（解）的優(yōu)劣，并作為以后遺傳操作的依據(jù)。這里我們根據(jù)f(x)=x2

在評價個體適應(yīng)度值大小時，首先要解碼，即把基因型個體變成表現(xiàn)型個體（即搜索空間的解）這里就是二進(jìn)制到十進(jìn)制的轉(zhuǎn)換基因型01101110000100010011表現(xiàn)型x

1324819f(x)=x2169

57664361

（適應(yīng)值）19算例說明—選擇選擇概率適應(yīng)度總和1170，平均值293運用輪盤賭選擇結(jié)果1201計算結(jié)果為0.140.490.060.3120算例說明—選擇初始族群適應(yīng)值E(i)複製個數(shù)011101960.180.711110005760.522.072100012890.261.04100111490.040.180初始族群01110110001000100111選擇后0111011000100011100021算例說明—交叉單點交叉為例兩個染色體1011100111001100假設(shè)交叉點在位置41011|10011100|1100101111001100100122算例說明—交叉01110110001100010001選擇后的結(jié)果配對情況1和2配對3和4配對

01110110001100010001交叉點選擇第一對位置3，第二對位置1交叉前01|1101100|011|0001000|1交叉后0100011001111101000023算例說明—交叉交配池配對交叉點交叉后xf(x)011102301000864110001311110309001100041110012562510001311000016256f=1845平均適應(yīng)度值f=46124算例說明—變異變異基因數(shù)的決定基因總數(shù)×變異概率=(4×5)×0.1=2

有兩個基因?qū)⒈煌蛔冸S機(jī)選取染色體進(jìn)行變異隨機(jī)選取要變異染色體的基因位變異目的在避免陷入局部最優(yōu)解25算例說明—變異01000110011111010000假設(shè)變異基因發(fā)生在第一個染色體的第3位和第四個染色體的第二位上變異就是把二進(jìn)制的0變成1把1變成0變異前01000110011111010000變異后0110011001111101001026算例說明—變異變異池是否有變異變異點變異后ff(x)01000是3011001010011001否3111103090011110否1110012562510000是11001018324f=1949

平均適應(yīng)度值f=48727算例說明—進(jìn)化過程進(jìn)化代數(shù)染色體xf(x)f平均值最佳值1011011100001000100111324819169576

6436111702921920110011001111101001012133018144169900324

15373843031010011001111101101022233024484529900576248962230410101111011111100010

29312

841961422475623128算例說明—終止準(zhǔn)則一般而言，遺傳算法終止條件有以下幾種：

（1）達(dá)到最大的進(jìn)化代數(shù)；

（2）所求的解達(dá)到可接受的范圍；

（3）連續(xù)幾代最佳解無變化或變化非常微??；

（4）達(dá)到最大的運算時間。29遺傳算法--參數(shù)配置種群數(shù)量視具體問題和解空間的維數(shù)問題越復(fù)雜，維數(shù)越高，種群數(shù)量要求越大遺傳運算的終止進(jìn)化代數(shù)根據(jù)問題的復(fù)雜程度，一般取為100~500交叉率一般選取范圍在0.4~0.99之間變異率一般選取范圍在0.001~0.1之間現(xiàn)代一般采用自適應(yīng)變化的交叉率和變異率30遺傳算法—應(yīng)用遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域，對問題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多學(xué)科。下面列舉一些遺傳算法的主要應(yīng)用領(lǐng)域。31遺傳算法—應(yīng)用組合優(yōu)化：遺傳算法是尋求組合優(yōu)化問題滿意解的最佳工具之一，實踐證明，遺傳算法對于組合優(yōu)化問題中的NP完全問題非常有效。32遺傳算法—應(yīng)用生產(chǎn)調(diào)度問題：生產(chǎn)調(diào)度問題在很多情況下所建立起來的數(shù)學(xué)模型難以精確求解，即使經(jīng)過一些簡化之后可以進(jìn)行求解也會因簡化得太多而使求解結(jié)果與實際相差太遠(yuǎn)。現(xiàn)在遺傳算法已經(jīng)成為解決復(fù)雜調(diào)度問題的有效工具。33遺傳算法—應(yīng)用自動控制：遺傳算法已經(jīng)在自動控制領(lǐng)域中得到了很好的應(yīng)用，例如基于遺傳算法的模糊控制器的優(yōu)化設(shè)計、基于遺傳算法的參數(shù)辨識、基于遺傳算法的模糊控制規(guī)則的學(xué)習(xí)、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)的結(jié)