基于雙字符搜索的GRASP-CSP算法改進

李珊珊　鄭　晨　朱　平

(江南大學理學院　江蘇 無錫 214122)

?

基于雙字符搜索的GRASP-CSP算法改進

李珊珊鄭晨朱平*

(江南大學理學院江蘇 無錫 214122)

摘要距離最近字符串問題CSP(The Closest String Problem)是一個組合優化問題，在生物信息學和編碼理論中有著很重要的應用。關于CSP問題采用一種基于概率啟發式的算法，即GRASP-CSP算法。針對GRASP-CSP算法存在的每次迭代過程相對獨立、搜索范圍狹窄、判斷指標過于單一這三大問題，提出通過強化策略，引入強Pareto優化的概念，特別是擴展局部搜索范圍，對GRASP-CSP進行進一步的優化。最后，給出基于GRASP-CSP改進之后的新算法，即IGRASP-CSP。實驗結果表明，改進之后的新算法能夠進一步縮小字符解與給定字符串集的漢明距離，從而得到關于CSP問題的進一步優化解，獲得滿意的優化效果，并從一維的應用擴展至多維。

關鍵詞CSPGRASPPareto優化強化策略雙字符

IMPROVEMENT OF GRASP-CSP ALGORITHM BASED ON DOUBLE CHARACTER SEARCH

Li ShanshanZheng ChenZhu Ping*

(School of Science, Jiangnan University, Wuxi 214122, Jiangsu，China)

AbstractThe closest string problem (CSP) is a combinatorial optimisation problem. It has very important applications in bioinformatics and coding theory. For this problem, we use a probability heuristic-based algorithm, i.e. GRASP-CSP. It has three problems: relatively independent in every iteration process, narrow search range, and single judgment indicator. In light of these, we propose to further optimise GRASP-CSP by enforcing strategy and introducing strong Pareto optimisation concept, in particular, expanding the local search scope. Finally, we give an improved GRASP-CSP-based new algorithm, namely IGRASP-CSP. Experimental results indicate that the improved algorithm is able to further shorten the Hamming distance between character solution and given string set, so that obtains further optimised solution in regard to CSP problem, achieves satisfactory optimisation results, and expands from one dimension to multi-dimension.

KeywordsCSPGRASPPareto optimisationEnforcing strategyDouble character

0引言

CSP就是找到一個字符串，使其與給定字符串集的漢明距離最大值盡可能的小。該問題屬于一個更為普遍的問題——序列一致性問題，它在許多方面有著重要的應用。在生物信息學中的應用，如設計藥物和創建細菌感染診斷探頭；在編碼理論中也有應用，如數據壓縮、錯誤解碼和語音編碼等[1]。關于CSP已經提出了若干算法，例如，Mauch提出的CGSA算法是最初元啟發式算法中的一種，它將模擬退火算法和遺傳算法進行了有效的融合；Faro在2010年提出的蟻群優化算法，稱為Ant-CSP[1]；以及在文獻[3，6]中提出的一種基于數據編碼技術的遺傳算法等。本文提及的GRASP-CSP算法是Esfahan在2011年提出來的，在此之前由于缺少充分的數據比照，很難判斷以上的這些算法哪個是最優的，因此Sayyed和Navid將GRASP-CSP算法和CGSA算法、Ant-CSP算法、DBCGA算法進行了充分的數據對比，結果表明GRASP-CSP算法能夠在一個合理的時間內獲得更優的解決方案。但該算法還存在若干缺陷：在構造階段，每次迭代優化過程都是相對獨立的，導致其不能從現有的優化解中學習改進，從而在下一次的迭代過程中獲得更優的初始解；在局部搜索階段，搜索范圍有待拓展；在更新當前最優解階段，作為判斷的指標過于單一，有時很難結合實際判斷取優。針對這主要的三大問題，本文在Sayyed Rasoul Mousavi等人提出的GRASP-CSP算法的基礎上，受到文獻[7]中優化集ε和文獻[2，4]中Pareto優化的啟發，對GRASP-CSP算法進行了進一步的優化。

1算法的準備

1.1基本的記號

1.2CSP的定義

目標是找到一個字符串，使其與給定字符串集的漢明距離最大值盡可能的小。

舉例：給定一個字符串集S={s1,s2,…,sn}n>1

限制條件：min{max{dH(x,si),i=1,2,…,n}}

1.3GRASP-CSP算法的簡介

GRASP-CSP是建立在GRASP的基礎上的，GRASP是一個啟發式隨機迭代過程，主要包括貪婪函數、隨機組成、自適應過程和局部搜索四個方面的內容[7]。GRASP算法最初是由Feo和Resende在1989年提出來的。GRASP的每次迭代過程包含兩個階段：構造階段和局部搜索階段。構造階段產生一個初始可行解；局部搜索階段將初始可行解進行局部優化，得到局部最優。文獻[5,8-11]中GRASP因為在初始的構造階段采取了適當的啟發式策略，隨著問題的規模擴大，能夠大大提高時間效率。

1.3.1GRASP-CSP的構造階段

構造階段是循環迭代產生一個初始可行解的過程，循環迭代終止的條件是直至未指定位置集U(x)=?為止。每次迭代過程中根據基于概率啟發式的貪婪函數形成受限候選目錄，即RCL。

1.3.2GRASP-CSP的局部搜索階段

由于在構造階段所產生的初始可行解并不能保證已經達到最優，因此需要進入到第二階段——局部搜索階段。局部搜索階段能夠在一定的領域內搜尋局部優解。GRASP-CSP是通過逐一位置的搜索進行優化，嘗試改變字符，判斷能否進一步縮小漢明距離。

1.3.3GRASP-CSP的更新當前最優解階段

依據基于概率啟發式貪婪函數值，判斷當前優化解與此前最優解的優劣，更新得出了當前最優解。

1.3.4GRASP-CSP的創新點

2改進的IGRASP-CSP算法

2.1擴大局部搜索范圍

為解決在局部搜索階段搜索范圍過于狹窄的問題，將搜索位置由原來的一個字符擴展為兩個字符一起搜索，擴展了局部搜索的廣度。事實上，單一字符搜索是包含于兩個字符一起搜索的，相當于固定了其中一個字符，所以兩個字符一起搜索更廣更優。下面需重新定義擴展之后的cost*函數。

引理1設xR為一個隨機整體解，則：

顯然,分為以下四種情況：

對于情況(1)而言：

=P-2nf(xR) (xR)·(P-1+ P-2)nf(xR)-1 (xR)·

(P0+P-1+P-2)nf(xR)-2(xR)·(1-P2)nf(xR)-3(xR)

定理1設xR為一個隨機整體解，則

文獻[1]中定理3證明了對于字符串x1、x2，當f(x1)

表1 可行的方案驗證cost*函數的優越性

cost*函數只考慮了xR為隨機整體解而并未考慮隨機局部解的情形，因為定義cost*函數主要是為了在局部搜索階段擴展局部搜索的廣度，所以重新定義的cost*函數只應用于局部搜索階段和更新當前最優解階段，在構造階段仍利用cost函數形成受限候選目錄。

2.2強化策略

為解決在構造階段，由于每次迭代優化過程都是相對獨立的，導致其不能從現有的優化解中學習改進的問題。受到文獻[7]中強化策略的啟發，從歷史優化解中獲取信息來影響下一次初始解的構造，這便是一個學習改進的過程。強化策略的具體實施過程為：建立一個長度為q的優化集ε(本文q一般選為m的整數倍)，初始的優化集隨機產生，只有當迭代產生初始解的cost值小于ε中的最差個體，才能被接受進入到下一階段的局部搜索階段。由于每次迭代產生初始解都經過強化策略，只有優于原優化集ε中的最差個體才能夠被接受，這樣會影響初始解的多樣性，造成算法的早熟[7]?；谝陨峡紤]，優化集ε的學習改進從兩方面入手。一方面，若迭代產生的初始解優于原優化集ε中的最差個體，則刪除ε中的最差個體，以迭代產生的解代之；另一方面，若迭代產生的初始解與原優化集ε中的個體差別很大，鼓勵其也進入到下一階段，刪除ε中的最差個體，以迭代產生的可行解代之。設t*、t分別表示迭代產生的初始解以及優化集ε中的最差個體，若max{dH(t*,si)}>max{dH(t,si)}+Δ(其中si為給定字符串集中的任意字符串，Δ為1到m之間的一個整數，大小根據具體情況而定，用來調控字符串t*和t的差別程度)，則可以說t*和t差別很大，足夠達到可接受的程度進入到下一階段。

2.3Pareto優化

為解決在更新當前最優解階段判斷指標過于單一的問題，受到Pareto優化的啟發，引入強Pareto優化的概念，使得判斷指標多元化。Pareto優化分為強Pareto優化和弱Pareto優化兩種，區別強弱的本質是對應的Pareto優化種類不同。首先給出兩種不同種類Pareto優化的概念。

假設現在有若干項特定一組人員分配產品或者收入的分配方案，那么在不使任何其他組員情況變差的前提下，使至少一個人情況變好的分配方案的變化，則稱為Pareto優化I；某一項分配方案的變化，無需“都不使其他人情況變差”，至少使一個人情況變好，則稱為Pareto優化II。有了Pareto優化I和Pareto優化II的概念之后，進一步給出強Pareto優化和弱Pareto優化的概念。無法有進一步的Pareto優化I，則稱為強Pareto優化；無法有進一步的Pareto優化II，則稱為弱Pareto優化。

假設S1和S2分別為局部搜索階段之后弱Pareto優化、強Pareto優化字符串解集，顯然S2?S1，且原來GRASP-CSP算法中局部搜索階段之后得到的字符串解集為S1。此時，若t1,t2∈S1，且t1,t2對應的貪婪函數值相等(cost*(t1)=cost*(t2))，但t1∈S1S2，t2∈S2，則選擇t2，刪除t1。

2.4改進的IGRASP-CSP算法的偽代碼

本節給出改進之后基于雙字符搜索的IGRASP-CSP算法，它需要執行若干次的啟發式隨機迭代過程，而每次啟發式隨機迭代過程都包含以下三個階段。

(1) 初始解的構造階段

通過循環迭代產生一個初始可行解，其中受限候選目錄仍然根據cost函數生成。不同的是每次迭代過程不再獨立，按照強化策略獲得學習改進之后可以進入下一階段的可行解。

(2) 雙字符搜索階段

同時搜索相鄰的兩個位置，嘗試變換不同組合的雙字符，根據cost*函數判別能否進一步優化，循環迭代直至局部最優。

(3) 更新當前最優解階段

采用貪婪函數值和強Pareto優化的雙判斷指標，更新得出當前最優解。

IGRASP-CSP算法的偽代碼如下：

Output:astringoflengthm

bestsofarX←arandomcompletesolution

{constructionphase:}

forl=1toitr-numdo

x←″″

whileU(x)≠?do

forallk∈U(x)do

forallalphabetcharactercdo

updataRCL((k,c),cost(x))

endfor

endfor

(ks,cs)←arandommemberofRCL

endwhile

accordingtotheenforcestrategyupdateε

x←arandommemberofε

{localsearchphase:}

improved←true

whileimproveddo

improved←false

fork=1tomdo

forallalphabetcharacterc∈∑-{xk}

ifcost*(tempX)

x←tempX

improved←true

endif

endfor

endfor

endwhile

{updatebestsofarX:}

ifcost*(x)

bestsofarX←x

elseifcost*(x)=cost*(tempX)andxisastrongParetooptimalsolutionthen

bestsofarX←x

endif

endfor

returnbestsofarX

3算法對比實驗

本節對改進之后的IGRASP-CSP算法和文獻[1]中所提出的GRASP-CSP算法進行比較，如表2所示。

表2　IGRASP-CSP與GRASP-CSP算法的比較

續表2

取Σ={A,T,G,C}和n=10為例，每個算法單獨運行20次以上，記錄下最優值。表2是這兩種算法所得最后結果的統計(GRASP-CSP算法的測試結果源于文獻[1])。在全部的15組實驗中，就最優解而言，IGRASP-CSP算法所得到的最優解全部優于或至少等同于GRASP-CSP算法的最優解，而且除了第2組，其余各組都得到了確實的優化。另外，隨著m不斷變大尤其達到500時，優化效果愈加明顯。

4結語

本文對經典的CSP問題采用了一種概率啟發式的GRASP算法，以此為基礎，對現有的算法進行了優化。在構造階段，通過強化策略對初始解的構造進行了學習改進；在更新當前最優解階段，判斷指標不再單一，引入強Pareto優化使指標多元化；特別在局部搜索階段，將搜索位置由原來的一個字符擴展為兩個字符一起，意義不僅僅只在于一維擴展為二維，能夠進一步縮小漢明距離，更在于它是一維至多維的擴展。因為作為經典的CSP問題，如果對于它的研究只局限于問題本身而未能運用到實際中，這是遠遠不夠的。比如三個堿基對對應一個氨基酸，這便可以提取為一個CSP問題。在局部搜索階段就必須三個字符一起，因為三個字符一起才對應到相應的生物信息。故搜索范圍由一維擴展為二維，本文提供了一維至多維擴展的思路，賦予了CSP問題的實際運用，具有重要意義。

參考文獻

[1] Sayyed R M, Navid N E. A GRASP algorithm for the Closest String Problem using a probability-based heuristic[J]. Computers & Operations Research,2012,39(2):238-248.

[2] Soleimani-damaneh M. An optimization modeling for string selection in the molecular biology using Pareto optimality[J]. Applied Mathematical Modeling,2011,35(8):3887-3892.

[3] Sayyed R M, Farzaneh T. An improved algorithm for the longest common subsequence problem[J].Computers & Operations Research,2012,39(3):512-520.

[4] Li-Yeh Chuang, Chih-Jen Hsibo, Cheng-Hong Yang. Chaotic particle swarm optimization for data clustering[J].Expert Systems with Applications, 2011,38(12):14555-14563.

[5] Feo, Resende. A probabilistic heuristic for a computationally difficult set covering problem[J].Operations Research Letters, 1989,8(2):67-71.

[6] Julstrom B A. A data-based coding of candidate strings in the closest string problem[C]//GECCO: proceedings of the 11th annual conference companion on genetic and evolutionary computation conference, 2009.

[7] 馮麗娟,嚴洪森,朱莉莉.基于改進貪婪隨機自適應算法的車間調度優化[J].計算機技術與發展,2009,19(10):44-50.

[8] 孫立勇,張焰,蔣傳文.求解機組組合問題的嵌入貪婪搜索機制的改進粒子群優化算法[J].電網技術,2006,30(13):44-48.

[9] 樂美龍,王婷婷,吳聰聰.基于改進的GRASP算法的飛機優化恢復研究[J].江蘇科技大學學報,2013,27(2):166-171.

[10] 李軍,郭玉華,王鈞,等.基于貪婪隨機自適應過程的多類型衛星聯合任務規劃技術[J].系統工程與電子技術,2010,32(10):2162-2166.

[11] 黎靜華,韋化.適合于機組組合問題的貪婪隨機自適應搜索模型[J].電網技術,2010,34(4):119-124.

中圖分類號TP301.6TP311

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.048

收稿日期：2014-09-10。國家自然科學基金項目(11271163)。李珊珊，碩士生，主研領域：智能計算與生物統計。鄭晨，碩士生。朱平，教授。