劉作軍， 張 曉， 陳玲玲， 張 燕

(1.河北工業(yè)大學(xué) 控制科學(xué)與工程學(xué)院 天津 300130； 2.智能康復(fù)裝置與檢測技術(shù)教育部工程研究中心 天津 300130)

0 引言

遺傳算法(genetic algorithm，GA)由美國Holland教授于1975年提出，是一種智能優(yōu)化算法．由于遺傳算法不依賴于問題具體的信息，且具有很強(qiáng)的全局搜索能力，所以廣泛應(yīng)用于函數(shù)優(yōu)化、故障診斷、車間調(diào)度、旅行商問題等眾多領(lǐng)域[1-7]，但其具有易陷入局部最優(yōu)解的缺陷.針對傳統(tǒng)遺傳算法的不足，各種改進(jìn)算法相繼被提出，其中文獻(xiàn)[2-10]通過結(jié)合聚類、量子理論、生物免疫概念、小生境技術(shù)或其他進(jìn)化算法等思想對遺傳算法進(jìn)行了改進(jìn).例如，文獻(xiàn)[9]提出了基于聚類劃分子種群的多種群遺傳算法，將滿足約束條件的個體根據(jù)其特征劃分到不同種群中，避免所有子群陷入局部最優(yōu)；文獻(xiàn)[10]通過帶精英策略的快速非支配排序遺傳算法在多目標(biāo)無功優(yōu)化中的應(yīng)用，保留了父代中的優(yōu)良個體.而文獻(xiàn)[11-14]通過設(shè)計交叉、變異操作對遺傳算法進(jìn)行改進(jìn).例如，文獻(xiàn)[14]采用自適應(yīng)交叉變異，最大限度地保留了父代的優(yōu)良特性，增強(qiáng)了算法的尋優(yōu)能力．

本文提出了程序性細(xì)胞死亡進(jìn)化算法(programmed cell death evolutionary algorithm，PCDA).首先，程序性細(xì)胞算子ced-3和ced-4協(xié)同完成選擇操作，程序性細(xì)胞算子ced-9執(zhí)行精英策略，目的是引導(dǎo)種群中的個體朝著最優(yōu)解方向進(jìn)化；其次，經(jīng)過自適應(yīng)交叉、變異操作[14]，算法運(yùn)行到一定代數(shù)后，結(jié)合聚類思想將種群劃分為多個子種群；最后，求解多峰值函數(shù)優(yōu)化問題及經(jīng)典TSP問題，結(jié)果表明了該算法的有效性．

1 程序性細(xì)胞死亡進(jìn)化算法

1.1 程序性細(xì)胞死亡原理

文獻(xiàn)[15]描述了程序性細(xì)胞死亡原理：程序性細(xì)胞死亡是一個具有遺傳性和程序性特征的過程，在生物體中能保持細(xì)胞的生死動態(tài)平衡．目前最新的研究進(jìn)展是ced-4激活ced-3的機(jī)制，該機(jī)制是清華大學(xué)施一公實(shí)驗(yàn)室發(fā)現(xiàn)的，即ced-4以八聚體的形式存在，與兩個ced-3結(jié)合激活ced-4的功能，而ced-4的功能又和ced-9有關(guān)聯(lián)，這樣就形成一個精確的調(diào)控系統(tǒng)[16]．

在發(fā)育過程中，細(xì)胞只有在正確的時間發(fā)生正確的分化，才能產(chǎn)生正確的細(xì)胞類型．人體內(nèi)的所有細(xì)胞根據(jù)特征的區(qū)別形成各種各樣的組織和器官，如肌肉、血液、心臟和神經(jīng)系統(tǒng)．細(xì)胞在正確的時間才發(fā)生分化對遺傳算法的啟發(fā)是：在進(jìn)化過程中，個體只有到特定的代數(shù)才能正確地對種群進(jìn)行劃分，產(chǎn)生具有相同特征的子種群．本文結(jié)合程序性細(xì)胞死亡原理改進(jìn)遺傳算法，設(shè)計了程序性細(xì)胞死亡進(jìn)化算法．該算法在遺傳算法操作的基礎(chǔ)上添加3個算子參加運(yùn)算：算子ced-3和ced-4參與遺傳算法的選擇過程，而算子ced-9參與精英策略．

圖1 子種群和優(yōu)良種群的關(guān)系Fig.1 The relationship between sub populations and good populations

1.2 多種群協(xié)同進(jìn)化

構(gòu)建了一個多種群協(xié)同進(jìn)化模型.首先采用隨機(jī)法產(chǎn)生初始群體P，進(jìn)行遺傳操作，直到特定的代數(shù)；然后將種群通過對所有個體聚類的方法分解為n個子種群(P1，P2，…，Pn)，在進(jìn)化過程中所有子種群協(xié)同進(jìn)化，在各自種群的內(nèi)部單獨(dú)完成選擇、交叉和變異操作，在各個子種群中選擇有限的優(yōu)良個體作為精英個體組成優(yōu)良種群PP，子種群可以從優(yōu)良種群中獲取其他種群的精英個體，以改善本種群的品質(zhì)，子種群和優(yōu)良種群的關(guān)系如圖1所示，這種種群結(jié)構(gòu)既增加了種群多樣性，又提高了算法的收斂速度．

1.3 算子操作

1.3.1選擇 模擬2個ced-3結(jié)合激活ced-4功能的生理過程，在PCDA算法的選擇過程中，ced-3算子根據(jù)輪盤賭選擇分別對子種群中的個體進(jìn)行2次標(biāo)記，每次標(biāo)記的結(jié)果都是將適應(yīng)度高的個體標(biāo)記為“1”，適應(yīng)度低的個體標(biāo)記為“0”．2次ced-3算子標(biāo)記過后，ced-4算子將標(biāo)記為“00”的個體淘汰，標(biāo)記為“11”的優(yōu)秀個體采用ced-9算子保存，標(biāo)記為“01”或“10”的大部分個體保留在原子種群中便于后續(xù)的進(jìn)化操作，ced-4共有3種狀態(tài)：

(1)

式中：Ri是子種群中的第i個個體；ced-3-1(Ri)是對Ri執(zhí)行第1次選擇；ced-3-2(Ri)是對Ri執(zhí)行第2次選擇；ced-4=0時，不對個體進(jìn)行任何操作；ced-4=1時，ced-9被激活執(zhí)行精英保留操作；ced-4=-1時，刪除個體Ri．

1.3.2交叉 遺傳算法中起核心作用的是遺傳操作的交叉算子．標(biāo)準(zhǔn)遺傳算法采用的是一個恒定的交叉概率，而恒定不變的交叉概率存在自身缺陷，即經(jīng)過幾代的進(jìn)化后，在算法運(yùn)行后期種群內(nèi)部的個體絕大多數(shù)是適應(yīng)度高的個體，所以適應(yīng)度高的個體作為父代的概率要大，從而被破壞的概率變大．針對恒定的交叉概率帶來的不足，本文采用自適應(yīng)交叉概率[17]，即在進(jìn)化的過程中使交叉概率隨著適應(yīng)度值的變動自動調(diào)整，在進(jìn)化后期避免了破壞種群中的優(yōu)秀個體．自適應(yīng)交叉概率的調(diào)整公式[18]為

(2)

式中：fmax為群體中最大的適應(yīng)度值；favg為每代群體的平均適應(yīng)度值；f表示交叉的兩個個體中較大的適應(yīng)度值．本文將Pc1設(shè)置為0.9．

1.3.3變異 變異操作使遺傳算法具有局部的隨機(jī)搜索能力．如果變異概率很大，那么整個搜索過程就退化為一個隨機(jī)搜索過程．本文采用的自適應(yīng)變異可以提供一個適度的變異概率，自適應(yīng)變異概率的調(diào)整公式[18]為

(3)

式中：fmax為群體中最大的適應(yīng)度值；favg為每代群體的平均適應(yīng)度值；f′是即將變異的個體的適應(yīng)度值.本文將Pm1設(shè)置為0.1．

引入的自適應(yīng)交叉和自適應(yīng)變異策略都與適應(yīng)度值有關(guān)，兩者的結(jié)合能夠解決進(jìn)化過程中因交叉和變異概率固定不變所導(dǎo)致的收斂速度緩慢的問題，克服種群早熟化的固有弊端，改善算法的收斂速度[18]．

1.4 算法流程

算法具體流程如下：

Step 1 初始化.采用二進(jìn)制編碼得到的初始種群P包含N個個體，個體染色體的長度設(shè)置為L；對初始種群進(jìn)行遺傳操作，直到特定的代數(shù)G，才將種群分解為n個子種群，每個子種群含有的個體數(shù)沒有必要一定相同；

Step 2 根據(jù)目標(biāo)函數(shù)計算適應(yīng)值函數(shù)f；

Step 3 執(zhí)行選擇操作.兩次輪盤賭操作的結(jié)果由ced-3算子標(biāo)記，由ced-4算子執(zhí)行，由ced-9算子精英保留到優(yōu)良種群中；

Step 4 執(zhí)行自適應(yīng)交叉、變異操作；

Step 5 為了實(shí)現(xiàn)子種群之間的共享，從優(yōu)良種群中獲取優(yōu)良個體；

Step 6 判斷是否到達(dá)最大遺傳代數(shù).如滿足，算法運(yùn)行結(jié)束，輸出結(jié)果；如不滿足，則返回Step 2．

2 實(shí)例驗(yàn)證

2.1 測試函數(shù)實(shí)驗(yàn)分析

用文獻(xiàn)[19]中Rosenbrock函數(shù)和文獻(xiàn)[20-21]中的三維Shubert函數(shù)測試算法性能，并與其他算法進(jìn)行了對比．

2.1.1Rosenbrock函數(shù) Rosenbrock函數(shù)為

(4)

圖2 Rosenbrock函數(shù)的圖形Fig.2 The figure of Rosenbrock function

函數(shù)的描述如式(4)所示，該函數(shù)是求解Rosenbrock函數(shù)的全局最大值．它有兩個局部極大點(diǎn)，分別是：f(2.048，-2.048)=3 897.734 227和f(-2.048，-2.048)=3 905.926 227，其中Rosenbrock函數(shù)的圖形如圖2所示.

采用標(biāo)準(zhǔn)遺傳算法(SGA)和本文的PCDA算法對Rosenbrock函數(shù)求解最優(yōu)，結(jié)果如圖3所示．由圖3(a)可知，SGA算法在140代左右穩(wěn)定在得到的最優(yōu)解處，此時得到的最優(yōu)解為3 897.725，即算法陷入了局部最優(yōu)解；由圖3(b)可知，大概進(jìn)化到4代時，種群根據(jù)個體的特征劃分為多種群，使大概在54代時PCDA算法得到了兩個穩(wěn)定的解，實(shí)線是PCDA算法得到的最優(yōu)解(3 905.926)，虛線是PCDA算法得到的次優(yōu)解(3 897.731)．由此可得：PCDA算法收斂速度快，能同時得到全局最優(yōu)解和次優(yōu)解，有利于全局分析．

圖3 2種算法對Rosenbrock函數(shù)的進(jìn)化過程Fig.3 The evolution process of two algorithms to Rosenbrock function

2.1.2Shubert函數(shù) Shubert函數(shù)為

(5)

圖4 Shubert函數(shù)的圖形Fig.4 The figure of Shubert function

Shubert函數(shù)是多峰值函數(shù)，用(5)式求解該多峰值函數(shù)的全局最小點(diǎn)，全局最小點(diǎn)共有18個，全局最小點(diǎn)為fmin=-186.731，其中Shubert函數(shù)的圖形如圖4所示．

為了證明程序性細(xì)胞死亡進(jìn)化算法的優(yōu)越性，將它與改進(jìn)的小生境算法(INGA)[20]、自適應(yīng)遺傳算法(AGA)、改進(jìn)的自適應(yīng)遺傳算法(IAGA)[21]和標(biāo)準(zhǔn)遺傳算法(SGA)進(jìn)行了對比．涉及到的實(shí)驗(yàn)部分參數(shù)為：種群規(guī)模N=40，最大進(jìn)化代數(shù)為50，共進(jìn)行500次實(shí)驗(yàn)．表1是5種算法進(jìn)程中3個算子操作的設(shè)計．

表1 3個算子操作的設(shè)計

由于篇幅所限，各個算法的進(jìn)化圖不能全部展示．圖5(a)、(b)分別是SGA算法和PCDA算法對Shubert函數(shù)進(jìn)行全局尋優(yōu)的進(jìn)化圖，達(dá)到最大代數(shù)，進(jìn)化終止．由圖5可以看出，PCDA算法確實(shí)收斂速度快并且能夠搜索到最優(yōu)點(diǎn)．

圖5 2種算法對Shubert函數(shù)的進(jìn)化過程Fig.5 The evolution process of two algorithms to Shubert function

算法平均進(jìn)化代數(shù)搜索到最優(yōu)解的成功率/%PCDA10100INGA1599.8IAGA1599.8AGA2890SGA3172

表2列出了PCDA算法和其他4種算法的平均進(jìn)化代數(shù)以及5種算法搜索到最優(yōu)解的成功率．

由表2可知，在求解多峰值Shubert函數(shù)最優(yōu)解的進(jìn)程中，最差的SGA算法收斂到最小點(diǎn)處的成功率只有72%，而PCDA算法卻每次都能搜到全局最優(yōu)解，說明了PCDA算法在求解多峰值函數(shù)問題中的收斂率高于其他4種算法．

對比以上5種算法的數(shù)據(jù)可以看出，PCDA算法在求解復(fù)雜的多峰值尋優(yōu)問題時不僅搜索到全局最優(yōu)解，而且提高了算法的收斂率和收斂速度．

2.2 TSP問題的求解

為驗(yàn)證本文算法的有效性，將該算法應(yīng)用于典型的TSP問題.選用TSPLIB測試庫中的經(jīng)典案例eil51進(jìn)行了測試.

取種群數(shù)N=100，迭代次數(shù)為600，個體長度M=51，交叉率Pc=0.9，Pc1=0.9，Pc2=0.6，變異率Pm=0.05，Pm1=0.05，Pm2=0.001，隨機(jī)運(yùn)行10次.PCDA算法運(yùn)行結(jié)果的最優(yōu)解為429.118，次優(yōu)解為438.012，而文獻(xiàn)[22]中GA算法得到最優(yōu)解為433.443. PCDA算法運(yùn)行到222代就得到了最優(yōu)路徑(見圖6)，比GA算法的300代提前了很多. PCDA算法和GA算法的進(jìn)化過程如圖7所示.

圖6 最優(yōu)路徑Fig.6 The optimal path

圖7 進(jìn)化過程Fig.7 Evolutionary process

3 結(jié)論

針對遺傳算法易陷入早熟收斂的缺陷，提出了一種程序性細(xì)胞死亡進(jìn)化算法(PCDA)．為了驗(yàn)證該算法的可行性，分別在Rosenbrock函數(shù)和Shubert函數(shù)上進(jìn)行了性能測試，且與標(biāo)準(zhǔn)遺傳算法(SGA)和其他改進(jìn)的遺傳算法進(jìn)行了比較. 從實(shí)驗(yàn)結(jié)果可以看出，對于多峰值函數(shù)尋優(yōu)，PCDA算法表現(xiàn)出了良好的搜索性能，從而驗(yàn)證了PCDA算法的有效性和可行性．

在PCDA算法進(jìn)化過程中，得到的次優(yōu)解是潛在的最優(yōu)解．當(dāng)算法陷入到局部最優(yōu)時,有必要考慮新的可能解，使之跳出局部最優(yōu)，從而為決策者對實(shí)際問題的解決提供多種方案．該算法對于多峰值函數(shù)尋優(yōu)問題具有很好的優(yōu)勢，它能使多峰值函數(shù)得到全局最優(yōu)解．TSP問題的實(shí)驗(yàn)結(jié)果表明該算法可以解決工程中非線性、多極值的問題．

參考文獻(xiàn)：

[1] 馬超，鄧超，熊堯，等．一種基于混合遺傳和粒子群的智能優(yōu)化算法[J]．計算機(jī)研究與發(fā)展，2013，50(11)：2278-2286．

[2] 萬建臣，靳宗信．多峰值函數(shù)優(yōu)化問題的免疫遺傳算法求解[J]．電子科技大學(xué)學(xué)報，2013，42(5)：769-772．

[3] 劉占生，竇唯，王東華，等．基于遺傳算法的旋轉(zhuǎn)機(jī)械故障診斷方法融合[J]．機(jī)械工程學(xué)報，2007，43(10)：227-233．

[4] 劉曉冰，焦璇，寧濤，等．基于雙鏈量子遺傳算法的柔性作業(yè)車間調(diào)度[J]．計算機(jī)集成制造系統(tǒng)，2015，21(2)：495-502．

[5] 張鑫龍，陳秀萬，肖漢，等．一種求解旅行商問題的新型帝國競爭算法[J]．控制與決策，2016，31(4)：586-592．

[6] TOMINAGA Y，OKAMOTO Y，WAKAO S，et al．Binary-based topology optimization of magnetostatic shielding by a hybrid evolutionary algorithm combining genetic algorithm and extended compact genetic algorithm[J]．IEEE transactions on magnetics，2013，49(5)：2093-2096．

[7] HOU Y，WU N Q，ZHOU M C，et al．Pareto-optimization for scheduling of crude oil operations in refinery via genetic algorithm[J]．IEEE transactions on systems man and cybernetics，2017，47(3)：517-530．

[8] GUNTER R．Convergence analysis of canonical genetic algorithms[J]．IEEE transactions on neural networks，1994，5(1)：96-101．

[9] 丁若冰，鄒書蓉．基于聚類劃分子種群的多種群遺傳算法[J]．四川理工學(xué)院學(xué)報(自然科學(xué)版)，2014，27(3)：46-49．

[10] 馮士剛，艾芊．帶精英策略的快速非支配排序遺傳算法在多目標(biāo)無功優(yōu)化中的應(yīng)用[J]．電工技術(shù)學(xué)報，2007，22(12)：146-151．

[11] 蔡良偉，李霞．遺傳算法交叉操作的改進(jìn)[J]．系統(tǒng)工程與電子技術(shù)，2006，28(6)：925-928．

[12] 鐘國坤，曾碧，余永權(quán)．基于異位交叉的遺傳算法的研究[J]．控制與決策，2003，18(3)：361-363．

[13] 楊新武，楊麗軍．基于交叉模型的改進(jìn)遺傳算法[J]．控制與決策，2016，31(10)：1837-1844．

[14] 徐克林，朱偉，李艷冰．配裝-運(yùn)輸集成決策模型及其遺傳算法[J]．浙江大學(xué)學(xué)報(工學(xué)版)，2011，45(9)：1630-1635．

[15] ACEHAN D，JIANG X，MORGAN D G，et al．Three-dimensional structure of the apoptosome: implications for assembly，procaspase-9 binding，and activation[J]．Molecular cell, 2002，9(2)：423-432．

[16] 施一公，孫兵法．細(xì)胞凋亡的結(jié)構(gòu)生物學(xué)研究進(jìn)展[J]．生命科學(xué)，2010，22(3)：224-228．

[17] SRINIVAS M，PATNAIK L M．Adaptive probabilities of crossover and mutation in genetic algorithms[J]．IEEE transactions on systems man and cybernetics，2002，24(4)：656-667．

[18] 劉愛軍，楊育，程文明，等．復(fù)雜制造環(huán)境下的改進(jìn)非支配排序遺傳算法[J]．計算機(jī)集成制造系統(tǒng)，2012，18(11)：2446-2458．

[19] 李純蓮，王希誠，趙金城，等．一種基于信息熵的多種群遺傳算法[J]．大連理工大學(xué)學(xué)報，2004，44(4)：589-593．

[20] 黃聰明，陳湘秀．小生境遺傳算法的改進(jìn)[J]．北京理工大學(xué)學(xué)報，2004，24(8)：675-678．

[21] 陳明杰，劉勝．改進(jìn)自適應(yīng)遺傳算法在函數(shù)優(yōu)化中的應(yīng)用研究[J]．哈爾濱工程大學(xué)學(xué)報，2007，28(8)：875-879．

[22] 郁磊．MATLAB智能算法30個案例分析[M]．北京：北京航空航天大學(xué)出版社，2015．