An Improved Genetic Algorithm for LDF Based on Sorting

李榮雨　陳　鑫

(南京工業(yè)大學(xué)電子與信息工程學(xué)院，江蘇 南京　211816)

?

一種基于排序的LDF改進(jìn)遺傳算法

An Improved Genetic Algorithm for LDF Based on Sorting

李榮雨陳鑫

(南京工業(yè)大學(xué)電子與信息工程學(xué)院，江蘇 南京211816)

摘要：針對(duì)高維數(shù)據(jù)建模過(guò)程中常見(jiàn)的非線性復(fù)雜問(wèn)題，使用遺傳算法進(jìn)行全局尋優(yōu)?？紤]到標(biāo)準(zhǔn)遺傳算法在搜索過(guò)程中存在的多種收斂性問(wèn)題，提出基于排序的拉普拉斯分布函數(shù)(LDF)改進(jìn)遺傳算法。該算法針對(duì)性地改進(jìn)了遺傳算法的多種收斂性問(wèn)題，解決了遺傳算法過(guò)快收斂至局部最優(yōu)解以及后期收斂速度過(guò)慢等問(wèn)題。根據(jù)實(shí)際生產(chǎn)數(shù)據(jù)，對(duì)軋鋼精軋機(jī)組進(jìn)行了仿真模擬，仿真實(shí)驗(yàn)結(jié)果表明了該算法切實(shí)可行，在保證了優(yōu)化效果的同時(shí)，也保證了算法的總體收斂速度和穩(wěn)定性，具有良好的應(yīng)用前景。

關(guān)鍵詞：高維數(shù)據(jù)算法收斂問(wèn)題遺傳算法拉普拉斯分布函數(shù)(LDF)適應(yīng)度函數(shù)交叉算子優(yōu)化算法

Abstract：In high dimensional data modeling process,the complex nonlinear problem is commonly seen,thus global optimization is conducted by using genetic algorithm.Considering the multiple convergence problems existing in standard genetic algorithm,the improved genetic algorithm for Laplace distribution function (LDF) based on sorting is proposed.The algorithm improves the multiple convergence problems,solves the problems of premature convergence of local optimum solution,and the slow convergence in late phase.The simulation based on practical productive data from the steel rolling finishing mill group is conducted,the results of simulation indicate that this algorithm is feasible,it ensures the optimization effect,overall convergence speed and stability,and possesses excellent applicable prospects.

Keywords:High dimensional dataConvergence problemGenetic algorithmLaplace distribution function (LDF)Fitness functionCrossover operatorOptimization algorithm

0引言

實(shí)際生產(chǎn)過(guò)程大多具有高維度、強(qiáng)關(guān)聯(lián)和非線性等特點(diǎn)，一般的傳統(tǒng)優(yōu)化算法難以對(duì)其進(jìn)行優(yōu)化。而遺傳算法因?yàn)榫邆渲悄苄?、并行性，并不依賴?wèn)題的內(nèi)部機(jī)理，能在多數(shù)可行解中根據(jù)特定要求搜索最優(yōu)解，非常適合解決復(fù)雜的非結(jié)構(gòu)化、非線性、非規(guī)律性的問(wèn)題[1]。但算法本身也存在一定的問(wèn)題，針對(duì)這些問(wèn)題，國(guó)內(nèi)外學(xué)者對(duì)此進(jìn)行了探索，提出了很多改進(jìn)方法，大致包括：編碼方式的改進(jìn)[2-3]、適應(yīng)度函數(shù)的改進(jìn)[4]、算子的自適應(yīng)改進(jìn)[5-6]以及與不同分布函數(shù)的結(jié)合應(yīng)用[7-8]等。本文根據(jù)前人提出的研究與改進(jìn)方法，著重研究了算法收斂問(wèn)題方面的改進(jìn)，并在仿真實(shí)驗(yàn)部分測(cè)試了改進(jìn)的效果，對(duì)比算法為PCCOs (parent-centric crossover operators)遺傳算法[9]。實(shí)驗(yàn)結(jié)果表明，該算法切實(shí)可行，仿真結(jié)果達(dá)到了預(yù)期要求。

1遺傳算法簡(jiǎn)介

遺傳算法是一種隨機(jī)性的全局優(yōu)化算法，它不但具有較強(qiáng)的全局搜索功能和求解問(wèn)題的能力，還具有簡(jiǎn)單通用、魯棒性強(qiáng)、適于并行處理等特點(diǎn)，是一種較好的全局優(yōu)化搜索算法。其核心內(nèi)容按操作順序一般分為以下5點(diǎn)。① 參數(shù)編碼。根據(jù)問(wèn)題的復(fù)雜程度或者適應(yīng)度選擇合適的編碼，常用的編碼方式有二進(jìn)制編碼、格雷編碼、實(shí)數(shù)編碼等。② 適應(yīng)度函數(shù)。適應(yīng)度是由目標(biāo)函數(shù)變換而來(lái)，適應(yīng)度的尺度變換是對(duì)目標(biāo)函數(shù)域的某種映射變換，具有評(píng)價(jià)個(gè)體適應(yīng)環(huán)境能力的作用，是選擇操作的依據(jù)。③ 選擇操作。遺傳算法中的選擇操作是在對(duì)個(gè)體的適應(yīng)度評(píng)價(jià)的基礎(chǔ)上，確定選取適當(dāng)?shù)膫€(gè)體復(fù)制到下一代中的方法，可以提高全局的收斂性，縮短整體搜索時(shí)間。常用的選擇操作有輪盤賭選擇法、排序選擇法、聯(lián)賽選擇法等。④ 交叉操作。交叉操作是遺傳算法中產(chǎn)生新個(gè)體的主要方式，也是區(qū)別于其他智能算法的重要特點(diǎn)，其作用是組合出新的個(gè)體，在解空間內(nèi)進(jìn)行有效搜索。常用的交叉算子有單點(diǎn)交叉、雙點(diǎn)交叉、一致交叉、均勻交叉、算術(shù)交叉、順序交叉和周期交叉等。⑤ 變異操作。變異是指將根據(jù)變異算子來(lái)替代個(gè)體編碼中的某些基因值，以此產(chǎn)生一個(gè)新的個(gè)體。遺傳算法中的變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法，其目的是使遺傳算法具有局部的隨機(jī)搜索能力和保持群體的多樣性。常用的變異算子有基本位變異、均勻變異、高斯變異等。這5部分對(duì)算法的優(yōu)劣起著關(guān)鍵性的作用，正確的改進(jìn)可以大大提升搜索到最優(yōu)解的概率，并縮短搜索的時(shí)間；而不恰當(dāng)?shù)母倪M(jìn)則會(huì)阻撓搜索到最優(yōu)解的概率和效率。

2基于排序的LDF改進(jìn)遺傳算法

如同大多數(shù)智能算法，遺傳算法具有兩個(gè)較為明顯的收斂性問(wèn)題：一是容易出現(xiàn)早熟，過(guò)快收斂于局部最優(yōu)解；二是后期收斂速度過(guò)慢以及收斂結(jié)果不穩(wěn)定的問(wèn)題。針對(duì)這些問(wèn)題，本文在采用實(shí)數(shù)編碼的前提下，對(duì)標(biāo)準(zhǔn)遺傳算法中的適應(yīng)度函數(shù)以及交叉算子兩部分進(jìn)行了改進(jìn)。

2.1適應(yīng)度函數(shù)

個(gè)體通過(guò)適應(yīng)度函數(shù)可以得出其在種群中的地位，這將直接影響在下一代種群中出現(xiàn)的概率。傳統(tǒng)的遺傳算法中的適應(yīng)度函數(shù)與目標(biāo)函數(shù)呈線性關(guān)系，甚至一些簡(jiǎn)單的模型可以直接用目標(biāo)函數(shù)作為適應(yīng)度函數(shù)。但這種做法存在一些缺點(diǎn)，一是在算法的前期最大適應(yīng)值與最小適應(yīng)值很可能相差很大，很容易淘汰掉很多含有優(yōu)秀基因片段的個(gè)體，而使得前期種群多樣性遭到破壞;二是在算法后期個(gè)體間適應(yīng)值的差異已經(jīng)很小，使得遺傳算法搜索全局最優(yōu)解的能力下降。

針對(duì)這些問(wèn)題，前人也提出了各種改進(jìn)方法，典型的有梯度改進(jìn)遺傳算法[10]、基于約束區(qū)域的動(dòng)態(tài)遺傳算法[11]等。梯度改進(jìn)遺傳算法考慮了函數(shù)在搜索點(diǎn)的函數(shù)值及其變化率，并將該信息加入適應(yīng)度函數(shù)；基于約束區(qū)域的動(dòng)態(tài)遺傳算法將遺傳算法的全局搜索和約束區(qū)域神經(jīng)網(wǎng)絡(luò)模型的局部搜索結(jié)合起來(lái)，使用神經(jīng)網(wǎng)絡(luò)確定動(dòng)態(tài)遺傳算法的適應(yīng)度函數(shù)。但以上算法只考慮了局部最優(yōu)解問(wèn)題以及整體收斂速度問(wèn)題，未考慮到不同時(shí)間段算法的選擇壓力變化問(wèn)題。針對(duì)這一問(wèn)題，在兩者的基礎(chǔ)上，引入了一種基于排序的適應(yīng)度函數(shù)。

由圖1～圖5可知：本文設(shè)計(jì)的航向控制器使無(wú)人艇能夠很好地沿著給定的航向航行，跟蹤誤差幾乎為零。但是，僅采用動(dòng)態(tài)面技術(shù)所設(shè)計(jì)的控制器，對(duì)環(huán)境擾動(dòng)引起的不確定項(xiàng)處理效果不理想(如圖5所示)。因此，引入RBF神經(jīng)網(wǎng)絡(luò)逼近器，對(duì)系統(tǒng)不確定項(xiàng)進(jìn)行全局逼近處理。采用單一的在線神經(jīng)網(wǎng)絡(luò)逼近不確定項(xiàng)，不僅解決不確定項(xiàng)的逼近問(wèn)題，在航向控制過(guò)程中有良好的效果，也簡(jiǎn)化了動(dòng)態(tài)面控制器結(jié)構(gòu)，減小計(jì)算負(fù)擔(dān)。

(1)

式中：SP為選擇壓力，本文取2；m為種群規(guī)模。

這樣改進(jìn)的好處在于可以在算法前期極大地減小個(gè)體之間適應(yīng)度的差異，以減小選擇壓力，確保前期種群的多樣性，從而避免過(guò)早陷入局部最優(yōu)解；同時(shí)，在算法后期相對(duì)于標(biāo)準(zhǔn)遺傳算法增大了選擇壓力，間接加快了算法整體收斂速度。

2.2交叉算子

遺傳算法中的交叉運(yùn)算，是指將兩個(gè)進(jìn)行配對(duì)的染色體按交叉算子互相交換其部分基因，形成兩個(gè)新的個(gè)體。交叉運(yùn)算在遺傳算法中起著關(guān)鍵的作用，也是遺傳算法區(qū)別于其他智能算法的重要特征。常用的交叉算子有單點(diǎn)交叉、雙點(diǎn)交叉、一致交叉、均勻交叉、算術(shù)交叉、順序交叉和周期交叉等。對(duì)于交叉算子的改進(jìn)，典型的有多親遺傳算法[12]、自適應(yīng)雜交算子遺傳算法[13]等。多親遺傳算法是一種利用了群體中心交叉方法來(lái)改進(jìn)算子的遺傳算法，并能將其應(yīng)用到數(shù)據(jù)聚類等相關(guān)問(wèn)題；自適應(yīng)雜交算子遺傳算法則是提出一種基于進(jìn)化代數(shù)和個(gè)體適應(yīng)值的交叉算子，使交叉操作向有利于算法收斂的方向進(jìn)行。多親遺傳算法雖然涉及到與函數(shù)分布有關(guān)的指數(shù)型增長(zhǎng)或是減少問(wèn)題，但它的前提是必須滿足一定的假設(shè)條件；而自適應(yīng)雜交算子遺傳算法是根據(jù)進(jìn)化代數(shù)來(lái)直接修改適應(yīng)度較小的個(gè)體，雖然結(jié)論表明自適應(yīng)性良好，但修改后的個(gè)體有可能超出可行域。

針對(duì)以上問(wèn)題，本文采用了將拉普拉斯函數(shù)與交叉算子相結(jié)合的拉普拉斯交叉算子。經(jīng)改進(jìn)后，該算子綜合了兩者的優(yōu)點(diǎn)，既能利用函數(shù)分布特性來(lái)滿足算法自適應(yīng)性，同時(shí)產(chǎn)生的后代也仍然在其可行域內(nèi)，回避了大多數(shù)情況下算子與函數(shù)結(jié)合后可行域變化的問(wèn)題。

拉普拉斯的密度函數(shù)：

(2)

拉普拉斯的分布函數(shù)：

(3)

當(dāng)a=0時(shí)，如b越接近0，中心附近的父代產(chǎn)生后代的概率較高;如b越接近1，則離中心較遠(yuǎn)處的父代產(chǎn)生后代的概率增大。

拉普拉斯算子交叉后的后代：

(4)

(5)

其思想來(lái)源于中間重組交叉算子和拉普拉斯分布函數(shù)。β由以下公式得出：

(6)

拉普拉斯分布函數(shù)與交叉算子結(jié)合的好處在于:可以通過(guò)改變a的取值來(lái)適應(yīng)不同的具體實(shí)例，具有一定的校正作用。通過(guò)改變b的取值可以影響在解空間內(nèi)搜索的整體傾向性：b值越大則搜索的結(jié)果越集中，b值越小則搜索的結(jié)果越松散。因此，需要調(diào)整適當(dāng)?shù)腷值使算法在前期相對(duì)松散，以保持種群的多樣性，并在后期相對(duì)集中以加快算法的收斂速度并保持收斂的穩(wěn)定性。該算子也具有自適應(yīng)性和一定的跳出性。根據(jù)拉普拉斯分布函數(shù)的特性，彼此接近的父代更傾向于產(chǎn)生彼此接近的子代，相互遠(yuǎn)離的父代更傾向于產(chǎn)生彼此較遠(yuǎn)的子代，產(chǎn)生的子代也更傾向于在父代附近，大大減少了收斂過(guò)快或者過(guò)早陷入局部最優(yōu)解的情況。在陷入局部最優(yōu)解的情況下，改進(jìn)后的算子在不超出整體可行域的前提下具有一定的概率跳出該局部極值，重新在解空間內(nèi)搜索全局最優(yōu)解。為證明該算子的可行性，下文將對(duì)軋鋼熱連軋精軋機(jī)組進(jìn)行仿真模擬。

3仿真實(shí)驗(yàn)

本文使用了從現(xiàn)場(chǎng)采集的數(shù)據(jù)，用基于排序的LDF改進(jìn)遺傳算法對(duì)熱連軋精軋機(jī)組負(fù)荷分配進(jìn)行優(yōu)化計(jì)算。同時(shí)，為了對(duì)比其效果，本文將比較標(biāo)準(zhǔn)遺傳算法、只改進(jìn)交叉算子的LDF遺傳算法、基于排序的LDF改進(jìn)遺傳算法以及PCCOs遺傳算法。

精軋機(jī)組仿真模型中的目標(biāo)函數(shù)為：

J=min{(P1-K1P2)2+(P2-K2P3)2+

(7)

實(shí)驗(yàn)鋼種為Q235，來(lái)料寬度B0=1 535 mm，來(lái)料厚度H0=36.7 mm，成品厚度為5.7 mm，粗軋出口溫度 TRC=10 670 ℃，精軋機(jī)組出口溫度TFC=8 911 ℃,目標(biāo)凸度CRn=0.016 mm，機(jī)架數(shù)n=7。實(shí)驗(yàn)中，算法的結(jié)構(gòu)參數(shù)為：種群數(shù)大小M=500，最大遺傳代數(shù)T=200，交叉概率Pc=0.9，變異概率Pm=0.01，改進(jìn)交叉算子中a=0，b=0.1。

表1是各遺傳算法優(yōu)化負(fù)荷分配的結(jié)果，包括各機(jī)架的軋制力F1～F7以及目標(biāo)函數(shù)值J。在符合軋制規(guī)程的情況下，目標(biāo)函數(shù)值J越小，表明總體負(fù)荷分配就越合理。

表1各算法的軋制力負(fù)荷分配結(jié)果

Tab.1The results of the rolling force load distribution of different algorithmskN

算法名稱F1F2F3F4F5F6F7J標(biāo)準(zhǔn)遺傳算法235772619823816125798544964469742.3216只改進(jìn)交叉算子的LDF遺傳算法2180124224220221574012077945498622.0145基于排序的LDF遺傳算法2219124656224151399211441857691611.6462PCCOs遺傳算法20251225012045617455110911069493811.9730

圖1為各算法的收斂曲線，本文采取的模型中共有7個(gè)機(jī)架。實(shí)驗(yàn)表明，編號(hào)越靠后的機(jī)架，收斂速度相對(duì)越慢。為使結(jié)果具有代表性，該收斂曲線是取第7個(gè)機(jī)架的變動(dòng)值。

從仿真結(jié)果可以看出，圖1(a)中的標(biāo)準(zhǔn)遺傳算法幾乎很快就陷入了局部最優(yōu)解，收斂速度非?？?，且不能跳出搜索到的局部最優(yōu)解；而圖1(b)中的只改進(jìn)交叉算子的LDF遺傳算法，搜索的范圍明顯大于標(biāo)準(zhǔn)遺傳算法，并有明顯的跳出局部最優(yōu)解，但可以看出，其后期穩(wěn)定性并不是很好；圖1(c)中，改進(jìn)了適應(yīng)度函數(shù)，大大提高了前期種群的多樣性，搜索范圍再次增大，且有多次跳出局部最優(yōu)解的過(guò)程，但可以看出，即使在接近收斂時(shí)，仍會(huì)有小范圍的跳出最優(yōu)解，只是其很快又收斂到最優(yōu)解的過(guò)程，直至最后完全收斂；圖1(d)采用PCCOs遺傳算法，可以看出算法前期多樣性很好，但卻陷入局部最優(yōu)解而無(wú)法跳出，收斂速度則適中。由以上分析可以看出，基于排序的LDF改進(jìn)遺傳算法得出的結(jié)果優(yōu)于其他3種遺傳算法：在符合實(shí)際生產(chǎn)要求的前提下，保證了算法前期的多樣性，以及后期的收斂速度與穩(wěn)定性，避免了出現(xiàn)前期陷入局部最優(yōu)解以及后期收斂速度較慢等問(wèn)題。

圖1　各算法收斂曲線

4結(jié)束語(yǔ)

本文針對(duì)傳統(tǒng)優(yōu)化算法和標(biāo)準(zhǔn)遺傳算法不能有效解決高維數(shù)據(jù)建模的問(wèn)題，通過(guò)將適應(yīng)度函數(shù)進(jìn)行基于排序的自適應(yīng)改進(jìn)，并將拉普拉斯分布函數(shù)與交叉算子相結(jié)合，提出了基于排序的LDF改進(jìn)遺傳算法。

基于排序的LDF改進(jìn)遺傳算法針對(duì)遺傳算法的多種收斂性問(wèn)題，既保證了算法前期的多樣性，又保證了算法后期的收斂速度與穩(wěn)定性，解決了大多數(shù)遺傳算法過(guò)快收斂至局部最優(yōu)解，以及后期收斂速度過(guò)慢與不穩(wěn)定等問(wèn)題。該算法成功應(yīng)用于軋鋼熱連軋精軋機(jī)組的負(fù)荷分配模型。通過(guò)仿真實(shí)驗(yàn)的對(duì)比結(jié)果可知，該算法切實(shí)可行，在遺傳算法的收斂性問(wèn)題方面有了很大的改善。

參考文獻(xiàn)

[1] Holland J H.Building blocks,cohort genetic algorithms,and hyperplane-defined functions[J].Evolutionary Computation,2008,8(4):373-391.

[2] Chen Z Q,Wang R L.Two efficient real-coded genetic algorithms for real parameter optimization[J].International Journal of Innovative Computing Information and Control,2011,7(8):4871-4883.

[3] Fang N,Zhou J Z,Zhang R,et al.A hybrid of real coded genetic algorithm and artificial fish swarm algorithm for short-term optimal hydrothermal scheduling[J].International Journal of Electrical Power & Energy Systems,2014,62(11):617-629.

[4] Liu H B,Wu C L,Cheng Y C,et al.Sensor placement on bridge structure based on genetic algorithms with different fitness functions[J]. Journal of Jilin University: Engineering and Technology Edition,2012,42(1):51-56.

[5] Zhu Y G,Xu Y P,Zhou X,et al.Research on adaptive genetic algorithm injected learning mechanism[J].Computer Engineering and Application,2010,46(36):34-36.

[6] Li K,Li J H,Yang X Q,et al.An adaptive genetic algorithm based on parameters cooperated with evolution[J].Computer Simulation,2010,27(11):204-208.

[7] Deep K,Thakur M.A new crossover operator for real coded genetic algorithms[J].Applied Mathematics and Computation,2007,188(1):895-911.

[8] Deep K,Thakur M.A new mutation operator for real coded genetic algorithms[J].Applied Mathematics and Computation,2007,193(1):211-230.

[9] Garcia-Martinez C,Lozano M,Herrera F,et al.Global and local real-coded genetic algorithms based on parent-centric crossover operators[J].European Journal of Operational Research,2008,185(3):1088-1113.

[10]何新貴,梁久禎.利用目標(biāo)函數(shù)梯度的遺傳算法[J].軟件學(xué)報(bào),2001,12(7):981-985.

[11]陶卿,曹進(jìn)德,孫德敏,等.基于約束區(qū)域神經(jīng)網(wǎng)絡(luò)的動(dòng)態(tài)遺傳算法[J].軟件學(xué)報(bào),2001,12(3):462-467.

[12]李平,吳佳英,鄭金華,等.多親遺傳算法的理論分析及其應(yīng)用研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2006,27(4):581-583.

[13]都偉,韓正之.一種自適應(yīng)雜交算子的浮點(diǎn)遺傳算法[J].系統(tǒng)仿真學(xué)報(bào),2006,18(6):1711-1713.

中圖分類號(hào)：TP18;TH6

文獻(xiàn)標(biāo)志碼：A

DOI:10.16086/j.cnki.issn1000-0380.201602001

江蘇省高校自然科學(xué)基金資助項(xiàng)目(編號(hào)：12KJB510007)。

修改稿收到日期：2015-05-02。

第一作者李榮雨(1977-)，男，2007年畢業(yè)于浙江大學(xué)控制系，獲博士學(xué)位，副教授；主要從事工業(yè)過(guò)程的監(jiān)控、優(yōu)化與控制方面的研究。