淺析基于排序的LDF改進遺傳算法
相關(guān)鏈接： 中國安全網(wǎng) 中國質(zhì)量網(wǎng) 中國論文網(wǎng) 中國資訊網(wǎng)
作者：徐一凡
遺傳算法因為具備智能性、并行性，并不依賴問題的內(nèi)部機理，能在多數(shù)可行解中根據(jù)特定要求搜索最優(yōu)解，非常適合解決復(fù)雜的非結(jié)構(gòu)化、非線性、非規(guī)律性的問題。但算法本身也存在一定的問題，針對這些問題，國內(nèi)外學(xué)者對此進行了探索，提出了很多改進方法，大致包括：編碼方式的改進、適應(yīng)度函數(shù)的改進、算子的自適應(yīng)改進以及與不同分布函數(shù)的結(jié)合應(yīng)用等。本文根據(jù)前人提出的研究與改進方法，著重研究了算法收斂問題方面的改進，并在仿真實驗部分測試了改進的效果，對比算法為PCCOs（parent - centric crossover operators）遺傳算法。實驗結(jié)果表明，該算法切實可行，仿真結(jié)果達到了預(yù)期要求。
1遺傳算法簡介
遺傳算法是一種隨機性的全局優(yōu)化算法，它不但具有較強的全局搜索功能和求解問題的能力，還具有簡單通用、魯棒性強、適于并行處理等特點，是一種較好的全局優(yōu)化搜索算法。其核心內(nèi)容按操作順序一般分為以下5點。①參數(shù)編碼。根據(jù)問題的復(fù)雜程度或者適應(yīng)度選擇合適的編碼，常用的編碼方式有二進制編碼、格雷編碼、實數(shù)編碼等。②適應(yīng)度函數(shù)。適應(yīng)度是由目標函數(shù)變換而來，適應(yīng)度的尺度變換是對目標函數(shù)域的某種映射變換，具有評價個體適應(yīng)環(huán)境能力的作用，是選擇操作的依據(jù)。③選擇操作。遺傳算法中的選擇操作是在對個體的適應(yīng)度評價的基礎(chǔ)上，確定選取適當?shù)膫�體復(fù)制到下一代中的方法，可以提高全局的收斂性，縮短整體搜索時間。常用的選擇操作有輪盤賭選擇法、排序選擇法、聯(lián)賽選擇法等。④交叉操作。交叉操作是遺傳算法中產(chǎn)生新個體的主要方式，也是區(qū)別于其他智能算法的重要特點，其作用是組合出新的個體，在解空間內(nèi)進行有效搜索。常用的交叉算子有單點交叉、雙點交叉、一致交叉、均勻交叉、算術(shù)交叉、順序交叉和周期交叉等。⑤變異操作。變異是指將根據(jù)變異算子來替代個體編碼中的某些基因值，以此產(chǎn)生一個新的個體。遺傳算法中的變異運算是產(chǎn)生新個體的輔助方法，其目的是使遺傳算法具有局部的隨機搜索能力和保持群體的多樣性。常用的變異算子有基本位變異、均勻變異、高斯變異等。這5部分對算法的優(yōu)劣起著關(guān)鍵性的作用，正確的改進可以大大提升搜索到最優(yōu)解的概率，并縮短搜索的時間；而不恰當?shù)母倪M則會阻撓搜索到最優(yōu)解的概率和效率。
2基于排序的LDF改進遺傳算法
如同大多數(shù)智能算法，遺傳算法具有兩個較為明顯的收斂性問題：一是容易出現(xiàn)早熟，過快收斂于局部最優(yōu)解；二是后期收斂速度過慢以及收斂結(jié)果不穩(wěn)定的問題。針對這些問題，本文在采用實數(shù)編碼的前提下，對標準遺傳算法中的適應(yīng)度函數(shù)以及交叉算子兩部分進行了改進。
2.1適應(yīng)度函數(shù)
個體通過適應(yīng)度函數(shù)可以得出其在種群中的地位，這將直接影響在下一代種群中出現(xiàn)的概率。傳統(tǒng)的遺傳算法中的適應(yīng)度函數(shù)與目標函數(shù)呈線性關(guān)系，甚至一些簡單的模型可以直接用目標函數(shù)作為適應(yīng)度函數(shù)。但這種做法存在一些缺點，一是在算法的前期最大適應(yīng)值與最小適應(yīng)值很可能相差很大，很容易淘汰掉很多含有優(yōu)秀基因片段的個體，而使得前期種群多樣性遭到破壞；二是在算法后期個體間適應(yīng)值的差異已經(jīng)很小，使得遺傳算法搜索全局最優(yōu)解的能力下降。
針對這些問題，前人也提出了各種改進方法，典型的有梯度改進遺傳算法、基于約束區(qū)域的動態(tài)遺傳算法等。梯度改進遺傳算法考慮了函數(shù)在搜索點的函數(shù)值及其變化率，并將該信息加入適應(yīng)度函數(shù)；基于約束區(qū)域的動態(tài)遺傳算法將遺傳算法的全局搜索和約束區(qū)域神經(jīng)網(wǎng)絡(luò)模型的局部搜索結(jié)合起來，使用神經(jīng)網(wǎng)絡(luò)確定動態(tài)遺傳算法的適應(yīng)度函數(shù)。但以上算法只考慮了局部最優(yōu)解問題以及整體收斂速度問題，未考慮到不同時間段算法的選擇壓力變化問題。針對這一問題，在兩者的基礎(chǔ)上，引入了一種基于排序的適應(yīng)度函數(shù)。
首先，將目標函數(shù)作為中間函數(shù)，把個體代入目標函數(shù)中fi=J（xi），i =1，2…，，m，其中m為種群規(guī)模，再將工按照從大到小進行排列得到一個序列{f}．，其中f i=max{f,}，以此類推；然后，作映射fi_x；，i =1，2…．，m，得到一個基于適應(yīng)值大小排列的{xi}，i =1，2…，，m；最后代人公式，得到每個個體的基于排序的適應(yīng)值。
式中：SP為選擇壓力，本文取2；m為種群規(guī)模。
這樣改進的好處在于可以在算法前期極大地減小個體之間適應(yīng)度的差異，以減小選擇壓力，確保前期種群的多樣性，從而避免過早陷入局部最優(yōu)解；同時，在算法后期相對于標準遺傳算法增大了選擇壓力，間接加快了算法整體收斂速度。
2.2交叉算子
遺傳算法中的交叉運算，是指將兩個進行配對的染色體按交叉算子互相交換其部分基因，形成兩個新的個體。交叉運算在遺傳算法中起著關(guān)鍵的作用，也是遺傳算法區(qū)別于其他智能算法的重要特征。常用的交叉算子有單點交叉、雙點交叉、一致交叉、均勻交叉、算術(shù)交叉、順序交叉和周期交叉等。對于交叉算子的改進，典型的有多親遺傳算法、自適應(yīng)雜交算子遺傳算法等。多親遺傳算法是一種利用了群體中心交叉方法來改進算子的遺傳算法，并能將其應(yīng)用到數(shù)據(jù)聚類等相關(guān)問題；自適應(yīng)雜交算子遺傳算法則是提出一種基于進化代數(shù)和個體適應(yīng)值的交叉算子，使交叉操作向有利于算法收斂的方向進行。多親遺傳算法雖然涉及到與函數(shù)分布有關(guān)的指數(shù)型增長或是減少問題，但它的前提是必須滿足一定的假設(shè)條件；而自適應(yīng)雜交算子遺傳算法是根據(jù)進化代數(shù)來直接修改適應(yīng)度較小的個體，雖然結(jié)論表明自適應(yīng)性良好，但修改后的個體有可能超出可行域。
針對以上問題，本文采用了將拉普拉斯函數(shù)與交叉算子相結(jié)合的拉普拉斯交叉算子。經(jīng)改進后，該算子綜合了兩者的優(yōu)點，既能利用函數(shù)分布特性來滿足算法自適應(yīng)性，同時產(chǎn)生的后代也仍然在其可行域內(nèi)，回避了大多數(shù)情況下算子與函數(shù)結(jié)合后可行域變化的問題。
拉普拉斯的密度函數(shù)：
拉普拉斯的分布函數(shù)：
式中：a為位置參數(shù)；b為尺度參數(shù)。
當a=0時，如b越接近0，中心附近的父代產(chǎn)生后代的概率較高；如b越接近1，則離中心較遠處的父代產(chǎn)生后代的概率增大。
拉普拉斯算子交叉后的后代：
其思想來源于中間重組交叉算子和拉普拉斯分布函數(shù)。B由以下公式得出：
式中：p通過反轉(zhuǎn)拉普拉斯分布函數(shù)得到；M為服從0~1之間的均勻分布的隨機數(shù)。同時，為了使結(jié)果不超出仿真實驗中軋鋼精軋機組的實際可行域，需要規(guī)定u的取值必須大于
拉普拉斯分布函數(shù)與交叉算子結(jié)合的好處在于：可以通過改變a的取值來適應(yīng)不同的具體實例，具有一定的校正作用。通過改變b的取值可以影響在解空間內(nèi)搜索的整體傾向性：b值越大則搜索的結(jié)果越集中，b值越小則搜索的結(jié)果越松散。因此，需要調(diào)整適當?shù)腷值使算法在前期相對松散，以保持種群的多樣性，并在后期相對集中以加快算法的收斂速度并保持收斂的穩(wěn)定性。該算子也具有自適應(yīng)性和一定的跳出性。根據(jù)拉普拉斯分布函數(shù)的特性，彼此接近的父代更傾向于產(chǎn)生彼此接近的子代，相互遠離的父代更傾向于產(chǎn)生彼此較遠的子代，產(chǎn)生的子代也更傾向于在父代附近，大大減少了收斂過快或者過早陷入局部最優(yōu)解的情況。在陷入局部最優(yōu)解的情況下，改進后的算子在不超出整體可行域的前提下具有一定的概率跳出該局部極值，重新在解空間內(nèi)搜索全局最優(yōu)解。為證明該算子的可行性，下文將對軋鋼熱連軋精軋機組進行仿真模擬。
3仿真實驗
本文使用了從現(xiàn)場采集的數(shù)據(jù)，用基于排序的LDF改進遺傳算法對熱連軋精軋機組負荷分配進行優(yōu)化計算。同時，為了對比其效果，本文將比較標準遺傳算法、只改進交叉算子的LDF遺傳算法、基于排序的LDF改進遺傳算法以及PCCOs遺傳算法。
精軋機組仿真模型中的目標函數(shù)為：
實驗鋼種為Q235，來料寬度Bo =1 535 mm，來料厚度Ho =36.7 mm，成品厚度為5.7 mm，粗軋出口溫度TRC =10 670 cC，精軋機組出口溫度TFC =8 911℃，目標凸度CR。=0.016 mm，機架數(shù)n=7。實驗中，算法的結(jié)構(gòu)參數(shù)為：種群數(shù)大小M= 500，最大遺傳代數(shù)T= 200，交叉概率P。=0.9，變異概率Pm =0.01，改進交叉算子中a=0，6=0.1。
表1是各遺傳算法優(yōu)化負荷分配的結(jié)果，包括各機架的軋制力F．—F，以及目標函數(shù)值．，。在符合軋制規(guī)程的情況下，目標函數(shù)值-，越小，表明總體負荷分配就越合理。
圖1為各算法的收斂曲線，本文采取的模型中共有7個機架。實驗表明，編號越靠后的機架，收斂速度相對越慢。為使結(jié)果具有代表性，該收斂曲線是取第7個機架的變動值。
從仿真結(jié)果可以看出，圖1(a)中的標準遺傳算法幾乎很快就陷入了局部最優(yōu)解，收斂速度非�？欤也荒芴鏊阉鞯降木植孔顑�(yōu)解；而圖1(b)中的只改進交叉算子的LDF遺傳算法，搜索的范圍明顯大于標準遺傳算法，并有明顯的跳出局部最優(yōu)解，但可以看出，其后期穩(wěn)定性并不是很好；圖1(c)中，改進了適應(yīng)度函數(shù)，大大提高了前期種群的多樣性，搜索范圍再次增大，且有多次跳出局部最優(yōu)解的過程，但可以看出，即使在接近收斂時，仍會有小范圍的跳出最優(yōu)解，只是其很快又收斂到最優(yōu)解的過程，直至最后完全收斂；圖1(d)采用PCCOs遺傳算法，可以看出算法前期多樣性很好，但卻陷入局部最優(yōu)解而無法跳出，收斂速度則適中。由以上分析可以看出，基于排序的LDF改進遺傳算法得出的結(jié)果優(yōu)于其他3種遺傳算法：在符合實際生產(chǎn)要求的前提下，保證了算法前期的多樣性，以及后期的收斂速度與穩(wěn)定性，避免了出現(xiàn)前期陷入局部最優(yōu)解以及后期收斂速度較慢等問題。
4結(jié)束語
本文針對傳統(tǒng)優(yōu)化算法和標準遺傳算法不能有效解決高維數(shù)據(jù)建模的問題，通過將適應(yīng)度函數(shù)進行基于排序的自適應(yīng)改進，并將拉普拉斯分布函數(shù)與交叉算子相結(jié)合，提出了基于排序的LDF改進遺傳算法�；谂判虻腖DF改進遺傳算法針對遺傳算法的多種收斂性問題，既保證了算法前期的多樣性，又保證了算法后期的收斂速度與穩(wěn)定性，解決了大多數(shù)遺傳算法過快收斂至局部最優(yōu)解，以及后期收斂速度過慢與不穩(wěn)定等問題。該算法成功應(yīng)用于軋鋼熱連軋精軋機組的負荷分配模型。通過仿真實驗的對比結(jié)果可知，該算法切實可行，在遺傳算法的收斂性問題方面有了很大的改善。
5摘要：針對高維數(shù)據(jù)建模過程中常見的非線性復(fù)雜問題，使用遺傳算法進行全局尋優(yōu)�？紤]到標準遺傳算法在搜索過程中存在的多種收斂性問題，提出基于排序的拉普拉斯分布函數(shù)( LDF)改進遺傳算法。該算法針對性地改進了遺傳算法的多種收斂性問題，解決了遺傳算法過快收斂至局部最優(yōu)解以及后期收斂速度過慢等問題。根據(jù)實際生產(chǎn)數(shù)據(jù)，對軋鋼精軋機組進行了仿真模擬，仿真實驗結(jié)果表明了該算法切實可行，在保證了優(yōu)化效果的同時，也保證了算法的總體收斂速度和穩(wěn)定性，具有良好的應(yīng)用前景。
