DNAPSO算法在連續(xù)空間優(yōu)化問題中的應(yīng)用

馬　翠，周先東（第三軍醫(yī)大學(xué)數(shù)學(xué)與生物數(shù)學(xué)教研室，重慶400038）

DNAPSO算法在連續(xù)空間優(yōu)化問題中的應(yīng)用

馬翠，周先東
（第三軍醫(yī)大學(xué)數(shù)學(xué)與生物數(shù)學(xué)教研室，重慶400038）

針對DNA計算方法中的個體在進(jìn)化過程中具有多樣性、容易導(dǎo)致局部最優(yōu)的問題，提出了一種新的DNAPSO算法。該算法利用PSO算法中個體依據(jù)全局最優(yōu)解和局部最優(yōu)解決定的進(jìn)化方向原理，設(shè)計了向特定方向變異的多點變異算子，同時保留了DNA計算中復(fù)制、交叉重組等算子，使新算法既具有了個體多樣性特點，又具備了向最優(yōu)解快速收斂的能力。多維連續(xù)空間優(yōu)化問題中4個典型函數(shù)的仿真測試結(jié)果表明：所提出的DNAPSO算法在收斂精度、收斂速度和魯棒性方面較之DNA計算方法和標(biāo)準(zhǔn)PSO算法都有明顯提高，豐富了連續(xù)空間優(yōu)化問題的求解方法。

DNAPSO算法；粒子群優(yōu)化算法；連續(xù)空間優(yōu)化問題

DNA計算的產(chǎn)生，源于1994年美國加州大學(xué)Adleman教授在Science上發(fā)表的關(guān)于DNA計算的開創(chuàng)性文章，他運用生化實驗的方法解決了一個七節(jié)點的Hamilton路徑問題［1］。1995年，R. lipton進(jìn)一步論證了采用DNA計算能夠解決NP完全性問題［2］。隨后，許多學(xué)者對DNA計算做了大量的研究，這些研究在搜索問題最優(yōu)解的過程中都是通過對染色體的位串個體采用交叉和變異操作并不斷產(chǎn)生新個體而獲得。DNA計算方法在各個領(lǐng)域都得到廣泛的應(yīng)用［2-7］。然而，DNA計算方法中的個體在進(jìn)化過程中具有多樣性，很容易導(dǎo)致局部最優(yōu)的問題出現(xiàn)，且多樣性的進(jìn)化過程也使得收斂速度受到影響。為改變這一現(xiàn)狀，張雷等［6］將DNA計算與遺傳算法進(jìn)行有效結(jié)合，提出了DNA遺傳算法，使得算法繼承了遺傳算法全局搜索的能力，提高了算法的有效性和收斂速度，避免了經(jīng)典的遺傳算法容易出現(xiàn)的“早熟收斂”和“收斂速度慢”的難題。實驗表明［4］，粒子群優(yōu)化算法（particle swarm optimization，PSO）隨著變量維數(shù)的增加，能夠比遺傳算法取得更好的效果?；诖?，本文引入PSO算法進(jìn)化原理對DNA計算的進(jìn)化算子加以改進(jìn)，提出DNAPSO混合算法，以期得到一種簡單、容易實現(xiàn)、穩(wěn)定性和效率較高的新算法。

粒子群優(yōu)化算法最早由Eberhart和Kennedy于1995年提出，是基于群體的演化算法，其思想來源于對鳥群捕食行為的研究。一群鳥在隨機(jī)搜尋食物，如果這個區(qū)域里只有一塊食物，那么找到食物的最簡單有效的策略就是搜尋目前距離食物最近的鳥的周圍區(qū)域。PSO算法就是從這種模型中得到啟示而產(chǎn)生的，并用于解決優(yōu)化問題。PSO求解優(yōu)化問題時，問題的解對應(yīng)于搜索空間中一只鳥的位置，稱這些鳥為“粒子”或“主體”。每個粒子都有自己的位置和速度（決定飛行的方向和距離），還有一個由被優(yōu)化函數(shù)決定的適應(yīng)值。各個粒子記憶、追隨當(dāng)前的最優(yōu)粒子，在解空間中搜索。每次迭代的過程不是完全隨機(jī)的，如果找到較好解，將會以此為依據(jù)來尋找下一個解。

PSO算法采用的是基于種群的全局搜索策略，它所運用的簡單速度-位移搜索模型避免了復(fù)雜的遺傳操作，同時其特有的記憶功能使其可以動態(tài)地跟蹤前面的搜索情況以調(diào)整其搜索策略，具有較強(qiáng)的快速收斂能力和魯棒性，且不需要借助問題的特征信息［3，8-9］。該算法在解空間的進(jìn)化過程與遺傳算法有所不同，其進(jìn)化方向是由當(dāng)前的最優(yōu)解所決定的，因此，在提高收斂速度方面比遺傳算法更具有優(yōu)勢。

1　DNAPSO算法的設(shè)計

DNAPSO算法主要基于DNA計算原理，利用構(gòu)成DNA的4元素能天然地形成數(shù)學(xué)上的一種良好的代數(shù)結(jié)構(gòu)的特點，對種群中的DNA鏈按照既定的規(guī)則（算子）進(jìn)行進(jìn)化運算（如復(fù)制、交叉、變異等算子），從而模擬實現(xiàn)在解空間隨機(jī)搜索最優(yōu)解的過程。DNAPSO算法的核心是在DNA計算的基礎(chǔ)上將PSO算法的進(jìn)化思想融入到了變異算子當(dāng)中，構(gòu)造了具有方向性的多點變異算子，從而提高了算法的收斂速度。

1.1進(jìn)化算子設(shè)計

DNAPSO算法主要設(shè)計以下3種進(jìn)化算子：

1）復(fù)制選擇算子。按適應(yīng)度比例法和精華保存法對DNA鏈進(jìn)行復(fù)制和選擇，使適應(yīng)度大的有更多繁殖后代的機(jī)會［6］。

2）具有方向性的多點變異算子。將PSO算法的進(jìn)化思想與DNA計算中的變異算子結(jié)合，形成的以最優(yōu)解為目標(biāo)方向的多點變異算子，這是本算法中最重要的算子。它充分繼承了PSO算法進(jìn)化算子快速向最優(yōu)解收斂的優(yōu)點，具體設(shè)計如下：

在DNA單鏈形成的可行解種群中，根據(jù)適應(yīng)度函數(shù)選擇出適應(yīng)度最好的個體作為最優(yōu)DNA鏈，種群中的其他個體則以此最優(yōu)DNA鏈為目標(biāo)，沿著目標(biāo)方向進(jìn)行步長隨機(jī)的搜索。具體移動的過程是使用特定變異酶對每個DNA鏈的各個堿基進(jìn)行有方向性的變異操作。為此，首先令堿基T，C，G，A按照圖1的2個方向搜索。

由于T，C，G，A對應(yīng)的二進(jìn)制編碼的十進(jìn)制整數(shù)依次增大，按照此方式設(shè)計能夠保證進(jìn)化過程中所有DNA鏈沿最優(yōu)DNA鏈的方向移動。設(shè)T，C，G，A每相鄰兩個堿基間的距離為1，每次搜索DNA鏈中堿基的步長為一隨機(jī)的整數(shù)。

圖1　堿基進(jìn)化的2個方向

例如：對某DNA鏈中的一個堿基T，如果該堿基的搜索步長為+1，則將其變異為C，以此類推，若搜索步長為+2，+3，則分別變異為G，A；相應(yīng)的如果步長為-1，-2，-3，則分別變異為A，G，C；若堿基的搜索步長為0，+4，-4時，則該堿基不進(jìn)行變異。

由于堿基只有4種，故當(dāng)步長的絕對值大于3時則要對步長進(jìn)行模4運算來求得滿足要求的步長。進(jìn)化過程中，將每條DNA鏈的所有變量對應(yīng)的DNA片段都按照上述方式進(jìn)行隨機(jī)的有方向性的變異。

3）交叉重組算子。交叉重組算子就是把來自初始種群的DNA鏈個體中的部分內(nèi)容進(jìn)行互換，通過改變基因的組合方式來產(chǎn)生新的DNA鏈，可獲得比原來更好的個體。交叉重組算子繼承了DNA計算中交叉算子的優(yōu)點，是本算法的主要算子之一，它能使算法避免陷入局部最優(yōu)。雜交生成的后代應(yīng)盡量保留雙親的優(yōu)良基因成分，個體必須滿足解空間的約束條件。使用限制酶切割兩條DNA鏈的同一位置，交換兩條DNA鏈的后半部分。雜交具體實現(xiàn)如下：

1.2算法步驟

步驟1初始化，生成n條DNA鏈，計算每條DNA鏈對應(yīng)的適應(yīng)度函數(shù)值。

步驟2根據(jù)適應(yīng)度函數(shù)值大小和比例，復(fù)制選擇出t條DNA鏈中的最優(yōu)個體，并保留適應(yīng)度值最優(yōu)的DNA鏈。

步驟3將步驟2中選擇出的t條DNA鏈，以適應(yīng)度值最優(yōu)DNA鏈為目標(biāo)，按照如下公式確定每個DNA片段的變異步長，產(chǎn)生新的DNA鏈。

步驟4按照步驟1初始化方法產(chǎn)生一部分新的DNA鏈加入新種群中，同時在上一代種群中按照一定比例隨機(jī)選擇成對的DNA鏈進(jìn)行交叉重組操作，但保持DNA鏈的總數(shù)為n不變。

步驟5計算新種群中各DNA鏈的適應(yīng)值，選擇全局最優(yōu)DNA鏈和局部最優(yōu)DNA鏈，用其替換前一次進(jìn)化的全局最優(yōu)DNA鏈和局部最優(yōu)DNA鏈。

步驟6若全局最優(yōu)DNA鏈滿足終止條件或進(jìn)化次數(shù)達(dá)到最大進(jìn)化次數(shù)則終止運行，否則轉(zhuǎn)步驟7。

步驟7用新的種群替換上一次進(jìn)化前的種群，轉(zhuǎn)步驟2。

2　DNAPSO算法求解連續(xù)空間優(yōu)化問題

對于一般的連續(xù)空間多維優(yōu)化問題，無論是否有約束條件，引入懲罰函數(shù)都可以在適當(dāng)條件下轉(zhuǎn)化為如下的上下限約束問題：

2.1初始種群產(chǎn)生

DNAPSO算法和DNA計算一樣是基于實數(shù)編碼的算法，最初的群體是隨機(jī)均勻產(chǎn)生的，每一條DNA鏈就是優(yōu)化問題解空間的一個解。對上述連續(xù)空間優(yōu)化問題，按照如下方式對各變量進(jìn)行DNA編碼和解碼以實現(xiàn)用DNAPSO算法求解［4，10］：

將函數(shù)的各個變量用一定長度的單鏈DNA片段表示（即用一定數(shù)量的A，T，C，G 4種堿基組成的序列），再由這些片段按一定順序組成一個DNA單鏈，這個DNA單鏈也就是函數(shù)優(yōu)化問題的一個可行解。例如：對于問題的一個可行解（x1，x2，…，xn），將每個變量用10個堿基表示，若x1對應(yīng)的DNA片段為：AGCTAAGT，x2對應(yīng)的DNA片段為：TCAGAGCT，…，xn對應(yīng)的DNA片段為：GCTTAGTA。則由這些片段可以構(gòu)成一個DNA單鏈：

由此就可以表示出問題中的一個可行解。

對于上述編碼，令T≡00，A≡11，C≡01，G≡10，由此則將每個變量由堿基組成的單鏈DNA片段轉(zhuǎn)換為二進(jìn)制字符串（b0b1b2…bn-1），其中bi∈｛0，1｝，i=0，1，…，n-1，b0為最高位，bn-1為最低位，變量xi的下界為，上界為。則該二進(jìn)制編碼對應(yīng)的十進(jìn)制整數(shù)為R，可以用如下公式對該變量進(jìn)行解碼：

2.2適應(yīng)度函數(shù)設(shè)計

為了衡量DNA鏈的優(yōu)劣，按照通常的方法設(shè)計一個適應(yīng)度函數(shù)。對于連續(xù)空間優(yōu)化問題，可直接采用原目標(biāo)函數(shù)或其他形式作為其適應(yīng)度函數(shù)。由此來計算各個DNA鏈的適應(yīng)值，從而判斷DNA鏈的優(yōu)劣。

按照上述DNA編碼方法，運用DNAPSO算法的復(fù)制、具有方向性的多點變異和交叉重組算子實現(xiàn)搜索最優(yōu)解的進(jìn)化過程即可求解連續(xù)空間的優(yōu)化問題。

3　DNAPSO算法求解連續(xù)空間優(yōu)化問題實例測試

本文實驗采用DNAPSO算法求解實例的過程是在C++平臺上編程實現(xiàn)的。實驗中，每個變量的堿基序列長度為20，種群規(guī)模為50。

為驗證DNAPSO算法的收斂速度、尋優(yōu)精度等性能優(yōu)于DNA計算和PSO算法，本文采用4個不同維數(shù)的標(biāo)準(zhǔn)測試函數(shù)［4，11］進(jìn)行對比測試，測試結(jié)果如下：

測試函數(shù)1：Sphere函數(shù)

其中-15≤xi≤15。函數(shù)在（0，0，…，0）處有最小值0，應(yīng)用DNAPSO（n=3，最大進(jìn)化次數(shù)設(shè)為3 000）得到最優(yōu)解的情況見表1。

表1　測試函數(shù)1的結(jié)果

測試函數(shù)2：Rosenbrock函數(shù)

其中-30≤xi≤30。函數(shù)在（1，1，…，1）處有最小值0。雖然在求極小值時它是單峰函數(shù)，但它是非凸、病態(tài)的，難以進(jìn)行全局優(yōu)化，應(yīng)用DNAPSO（n=1，最大進(jìn)化次數(shù)設(shè)為3 000）得到最優(yōu)解的情況見表2。

表2　測試函數(shù)2的結(jié)果

測試函數(shù)3：Rastrigin函數(shù)

其中-30≤xi≤30，該函數(shù)有很多正弦凸起的局部極小點，在（0，0，…，0）處取得全局最優(yōu)值0，應(yīng)用DNAPSO算法（n=3，最大進(jìn)化次數(shù)設(shè)為3 000）得到最優(yōu)解的情況見表3。

表3　測試函數(shù)3的結(jié)果

測試函數(shù)4：Schaffer F6函數(shù)

其中-100≤xi≤100。函數(shù)在（0，0）處取得全局最優(yōu)值-1，應(yīng)用DNAPSO算法（n=2，最大進(jìn)化次數(shù)設(shè)為3 000）得到最優(yōu)解的情況見表4。

表4　測試函數(shù)4的結(jié)果

需要說明的是，文獻(xiàn)［4］運用DNA計算方法對上述部分函數(shù)做了測試，其編碼長度為40，是本文編碼長度的2倍，而且其結(jié)果精度并不理想。其原因在于DNA計算進(jìn)化過程有交叉、倒位、變異、復(fù)制等復(fù)雜的算子，必然影響其執(zhí)行效率，而DNAPSO算法卻只有簡單的變異和交叉算子。通過比較來看，無論是從精度方面還是從效率方面，DNAPSO算法效果均明顯優(yōu)于DNA計算方法。同時，DNAPSO算法還繼承了PSO算法隨著編碼長度的增加其效率受影響較小的特點，因此，其優(yōu)越性相比其他智能算法更為明顯。表5、圖2表明：DNAPSO算法的收斂率和收斂速度確實優(yōu)于DNA計算方法和標(biāo)準(zhǔn)PSO算法，具有一定的應(yīng)用價值。

表5　DNAPSO算法與DNA計算方法、標(biāo)準(zhǔn)PSO算法的比較

圖2　DNAPSO算法與DNA計算方法、標(biāo)準(zhǔn)PSO算法的收斂性比較

4　結(jié)束語

本文設(shè)計的DNAPSO算法將個體依據(jù)全局最優(yōu)解和局部最優(yōu)解決定的進(jìn)化方向的原理應(yīng)用到了DNA計算算子設(shè)計中，有效避免了DNA計算易陷入的局部最優(yōu)問題，同時提高了算法求解多維優(yōu)化問題的能力，是繼DNA遺傳算法之后的又一種新算法。實驗結(jié)果表明：該算法能夠很好地解決連續(xù)空間優(yōu)化問題；與DNA計算和DNA遺傳算法比較而言，其算子設(shè)計單一簡單，更容易實現(xiàn)，并降低了算法的復(fù)雜度，提高了計算機(jī)的求解能力和DNA計算、標(biāo)準(zhǔn)的PSO算法比較，DNAPSO算法的全局收斂性和收斂速度都有明顯優(yōu)勢。

［1］Adleman L.Molecular computation of solutions to combinatorial problems［J］.Science，1994（5187）：1021 -1024.

［2］Lipton R J.DNA solution of hard computational problems［J］.Science，1995（28）：542-545.

［3］Shi Y，Eberhart R C.AModified Particle Swarm Optimization［C］//Proceedings of the 1999 Congress on Evolutionary Computation.Piscataway，N J：IEEE Press，1998：69-73.

［4］魏平，熊偉清，王小勸.DNA計算求解連續(xù)空間優(yōu)化問題［J］.計算機(jī)應(yīng)用研究，2006（1）：151-153.

［5］張勛才，趙海蘭，崔光照，等.DNA計算的研究進(jìn)展及展望［J］.計算機(jī)工程與應(yīng)用，2007，43（10）：44-47，51.

［6］張雷，楊大地，冉戎.基于DNA遺傳算法的曲面最短路徑問題［J］.計算機(jī)工程，2007（16）：181-185.

［7］支凌迎，殷志祥，黃曉慧，等.DNA計算研究概述與分析［J］.系統(tǒng)工程與電子技術(shù)，2009，31（6）：1462 -1466.

［8］Nasir M，Das S，Maity D，et al.A dynamic neighborhood learning based particle swarm optimizer for global numerical optimization［J］.Information Sciences，2012（209）：16-36.

［9］Satapathy S，Naik A，Parvathi K.A teaching learning based optimization based on orthogonal design for solving global optimization problems［J］.Springer Plus，2013，130（2）：1-12.

［10］郭穩(wěn)濤，何怡岡.基于混合蟻群算法的DNA編碼序列設(shè)計方法［J］.數(shù)值計算與計算機(jī)應(yīng)用，2013，34（2）：105-116.

［11］VESTERSTRAM J，THOMSEN R.A Comparative Study of Differential Evolution，Particle Swarm Optimization，and Evolutionary Algorithms on Numerical Benchmark Problems［C］//Proceedings of the 2004 Congress on Evolutionary Computation.Piscataway，N J：IEEE Press，2004：1980-897.

（責(zé)任編輯何杰玲）

Application of DNAPSO Algorithm for Continuous Space Optim ization

MA Cui，ZHOU Xian-dong
（Departmentof Mathematics and Biomathematics，Third Military Medical University，Chongqing 400038，China）

In order to overcome the defects of local optimum which are generated by the individual diversity in the evolutionary process，a new DNAPSO algorithm based on DNA structure and the evolution process of particle swarm optimization was proposed.The DNAPSO algorithm used the evolutionary principle of the individual's gradually flying to the optimal solution in the PSO.The new algorithm retained the advantages of DNA algorithm，multipointmutation operatorwhich can mutate to the particular direction wasdesigned.Therefore，the proposed algorithm both had the feature of individual diversity and the ability of fast convergence to the optimal solution.And then，results of four typical functions in the continuous space optimization show that the DNAPSO algorithm has better stability and convergence compared with DNA algorithm and standard PSO algorithm，and a new way is found to solve the continuous space optimization.

DNAPSO algorithm；particle swarm optimization；continuous space optimization

TP301.6

A

1674-8425（2015）05-0087-06

10.3969/j.issn.1674-8425（z）.2015.05.016

2015-02-16

重慶市自然科學(xué)基金資助項目（CSTC2013jcyjA10041）

馬翠（1982—），女，江蘇徐州人，講師，主要從事智能算法及生物數(shù)學(xué)建模研究。

馬翠，周先東.DNAPSO算法在連續(xù)空間優(yōu)化問題中的應(yīng)用［J］.重慶理工大學(xué)學(xué)報：自然科學(xué)版，2015（5）：87-92.

format：MA Cui，ZHOU Xian-dong.Application of DNAPSO Algorithm for Continuous Space Optim ization［J］.Journal of Chongqing University of Technology：Natural Science，2015（5）：87-92.