一種基于排序的LDF改進遺傳算法

An Improved Genetic Algorithm for LDF Based on Sorting

李榮雨　陳　鑫

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

?

一種基于排序的LDF改進遺傳算法

An Improved Genetic Algorithm for LDF Based on Sorting

李榮雨陳鑫

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

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

關鍵詞：高維數(shù)據(jù)算法收斂問題遺傳算法拉普拉斯分布函數(shù)(LDF)適應度函數(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引言

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

1遺傳算法簡介

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

2基于排序的LDF改進遺傳算法

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

2.1適應度函數(shù)

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

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

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

(1)

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

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

2.2交叉算子

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

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

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

(2)

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

(3)

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

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

(4)

(5)

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

(6)

拉普拉斯分布函數(shù)與交叉算子結(jié)合的好處在于:可以通過改變a的取值來適應不同的具體實例，具有一定的校正作用。通過改變b的取值可以影響在解空間內(nèi)搜索的整體傾向性：b值越大則搜索的結(jié)果越集中，b值越小則搜索的結(jié)果越松散。因此，需要調(diào)整適當?shù)腷值使算法在前期相對松散，以保持種群的多樣性，并在后期相對集中以加快算法的收斂速度并保持收斂的穩(wěn)定性。該算子也具有自適應性和一定的跳出性。根據(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ù)為：

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

(7)

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

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

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

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

算法名稱F1F2F3F4F5F6F7J標準遺傳算法235772619823816125798544964469742.3216只改進交叉算子的LDF遺傳算法2180124224220221574012077945498622.0145基于排序的LDF遺傳算法2219124656224151399211441857691611.6462PCCOs遺傳算法20251225012045617455110911069493811.9730

圖1為各算法的收斂曲線，本文采取的模型中共有7個機架。實驗表明，編號越靠后的機架，收斂速度相對越慢。為使結(jié)果具有代表性，該收斂曲線是取第7個機架的變動值。

從仿真結(jié)果可以看出，圖1(a)中的標準遺傳算法幾乎很快就陷入了局部最優(yōu)解，收斂速度非常快，且不能跳出搜索到的局部最優(yōu)解；而圖1(b)中的只改進交叉算子的LDF遺傳算法，搜索的范圍明顯大于標準遺傳算法，并有明顯的跳出局部最優(yōu)解，但可以看出，其后期穩(wěn)定性并不是很好；圖1(c)中，改進了適應度函數(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)解以及后期收斂速度較慢等問題。

圖1　各算法收斂曲線

4結(jié)束語

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

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

參考文獻

[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]何新貴,梁久禎.利用目標函數(shù)梯度的遺傳算法[J].軟件學報,2001,12(7):981-985.

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

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

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

中圖分類號：TP18;TH6

文獻標志碼：A

DOI:10.16086/j.cnki.issn1000-0380.201602001

江蘇省高校自然科學基金資助項目(編號：12KJB510007)。

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

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