DNAPSO算法在連續空間優化問題中的應用

馬　翠，周先東（第三軍醫大學數學與生物數學教研室，重慶400038）

DNAPSO算法在連續空間優化問題中的應用

馬翠，周先東
（第三軍醫大學數學與生物數學教研室，重慶400038）

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

DNAPSO算法；粒子群優化算法；連續空間優化問題

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

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

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

1　DNAPSO算法的設計

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

1.1進化算子設計

DNAPSO算法主要設計以下3種進化算子：

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

2）具有方向性的多點變異算子。將PSO算法的進化思想與DNA計算中的變異算子結合，形成的以最優解為目標方向的多點變異算子，這是本算法中最重要的算子。它充分繼承了PSO算法進化算子快速向最優解收斂的優點，具體設計如下：

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

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

圖1　堿基進化的2個方向

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

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

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

1.2算法步驟

步驟1初始化，生成n條DNA鏈，計算每條DNA鏈對應的適應度函數值。

步驟2根據適應度函數值大小和比例，復制選擇出t條DNA鏈中的最優個體，并保留適應度值最優的DNA鏈。

步驟3將步驟2中選擇出的t條DNA鏈，以適應度值最優DNA鏈為目標，按照如下公式確定每個DNA片段的變異步長，產生新的DNA鏈。

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

步驟5計算新種群中各DNA鏈的適應值，選擇全局最優DNA鏈和局部最優DNA鏈，用其替換前一次進化的全局最優DNA鏈和局部最優DNA鏈。

步驟6若全局最優DNA鏈滿足終止條件或進化次數達到最大進化次數則終止運行，否則轉步驟7。

步驟7用新的種群替換上一次進化前的種群，轉步驟2。

2　DNAPSO算法求解連續空間優化問題

對于一般的連續空間多維優化問題，無論是否有約束條件，引入懲罰函數都可以在適當條件下轉化為如下的上下限約束問題：

2.1初始種群產生

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

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

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

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

2.2適應度函數設計

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

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

3　DNAPSO算法求解連續空間優化問題實例測試

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

為驗證DNAPSO算法的收斂速度、尋優精度等性能優于DNA計算和PSO算法，本文采用4個不同維數的標準測試函數［4，11］進行對比測試，測試結果如下：

測試函數1：Sphere函數

其中-15≤xi≤15。函數在（0，0，…，0）處有最小值0，應用DNAPSO（n=3，最大進化次數設為3 000）得到最優解的情況見表1。

表1　測試函數1的結果

測試函數2：Rosenbrock函數

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

表2　測試函數2的結果

測試函數3：Rastrigin函數

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

表3　測試函數3的結果

測試函數4：Schaffer F6函數

其中-100≤xi≤100。函數在（0，0）處取得全局最優值-1，應用DNAPSO算法（n=2，最大進化次數設為3 000）得到最優解的情況見表4。

表4　測試函數4的結果

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

表5　DNAPSO算法與DNA計算方法、標準PSO算法的比較

圖2　DNAPSO算法與DNA計算方法、標準PSO算法的收斂性比較

4　結束語

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

［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計算求解連續空間優化問題［J］.計算機應用研究，2006（1）：151-153.

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

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

［7］支凌迎，殷志祥，黃曉慧，等.DNA計算研究概述與分析［J］.系統工程與電子技術，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］郭穩濤，何怡岡.基于混合蟻群算法的DNA編碼序列設計方法［J］.數值計算與計算機應用，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.

（責任編輯何杰玲）

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

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

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

馬翠，周先東.DNAPSO算法在連續空間優化問題中的應用［J］.重慶理工大學學報：自然科學版，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.