基于雙字符搜索的GRASP-CSP算法改進(jìn)

李珊珊　鄭　晨　朱　平

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

?

基于雙字符搜索的GRASP-CSP算法改進(jìn)

李珊珊鄭晨朱平*

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

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

關(guān)鍵詞CSPGRASPPareto優(yōu)化強(qiáng)化策略雙字符

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

1算法的準(zhǔn)備

1.1基本的記號(hào)

1.2CSP的定義

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

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

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

1.3GRASP-CSP算法的簡介

GRASP-CSP是建立在GRASP的基礎(chǔ)上的，GRASP是一個(gè)啟發(fā)式隨機(jī)迭代過程，主要包括貪婪函數(shù)、隨機(jī)組成、自適應(yīng)過程和局部搜索四個(gè)方面的內(nèi)容[7]。GRASP算法最初是由Feo和Resende在1989年提出來的。GRASP的每次迭代過程包含兩個(gè)階段：構(gòu)造階段和局部搜索階段。構(gòu)造階段產(chǎn)生一個(gè)初始可行解；局部搜索階段將初始可行解進(jìn)行局部優(yōu)化，得到局部最優(yōu)。文獻(xiàn)[5,8-11]中GRASP因?yàn)樵诔跏嫉臉?gòu)造階段采取了適當(dāng)?shù)膯l(fā)式策略，隨著問題的規(guī)模擴(kuò)大，能夠大大提高時(shí)間效率。

1.3.1GRASP-CSP的構(gòu)造階段

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

1.3.2GRASP-CSP的局部搜索階段

由于在構(gòu)造階段所產(chǎn)生的初始可行解并不能保證已經(jīng)達(dá)到最優(yōu)，因此需要進(jìn)入到第二階段——局部搜索階段。局部搜索階段能夠在一定的領(lǐng)域內(nèi)搜尋局部優(yōu)解。GRASP-CSP是通過逐一位置的搜索進(jìn)行優(yōu)化，嘗試改變字符，判斷能否進(jìn)一步縮小漢明距離。

1.3.3GRASP-CSP的更新當(dāng)前最優(yōu)解階段

依據(jù)基于概率啟發(fā)式貪婪函數(shù)值，判斷當(dāng)前優(yōu)化解與此前最優(yōu)解的優(yōu)劣，更新得出了當(dāng)前最優(yōu)解。

1.3.4GRASP-CSP的創(chuàng)新點(diǎn)

2改進(jìn)的IGRASP-CSP算法

2.1擴(kuò)大局部搜索范圍

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

引理1設(shè)xR為一個(gè)隨機(jī)整體解，則：

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

對(duì)于情況(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設(shè)xR為一個(gè)隨機(jī)整體解，則

文獻(xiàn)[1]中定理3證明了對(duì)于字符串x1、x2，當(dāng)f(x1)

表1 可行的方案驗(yàn)證cost*函數(shù)的優(yōu)越性

cost*函數(shù)只考慮了xR為隨機(jī)整體解而并未考慮隨機(jī)局部解的情形，因?yàn)槎xcost*函數(shù)主要是為了在局部搜索階段擴(kuò)展局部搜索的廣度，所以重新定義的cost*函數(shù)只應(yīng)用于局部搜索階段和更新當(dāng)前最優(yōu)解階段，在構(gòu)造階段仍利用cost函數(shù)形成受限候選目錄。

2.2強(qiáng)化策略

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

2.3Pareto優(yōu)化

為解決在更新當(dāng)前最優(yōu)解階段判斷指標(biāo)過于單一的問題，受到Pareto優(yōu)化的啟發(fā)，引入強(qiáng)Pareto優(yōu)化的概念，使得判斷指標(biāo)多元化。Pareto優(yōu)化分為強(qiáng)Pareto優(yōu)化和弱Pareto優(yōu)化兩種，區(qū)別強(qiáng)弱的本質(zhì)是對(duì)應(yīng)的Pareto優(yōu)化種類不同。首先給出兩種不同種類Pareto優(yōu)化的概念。

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

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

2.4改進(jìn)的IGRASP-CSP算法的偽代碼

本節(jié)給出改進(jìn)之后基于雙字符搜索的IGRASP-CSP算法，它需要執(zhí)行若干次的啟發(fā)式隨機(jī)迭代過程，而每次啟發(fā)式隨機(jī)迭代過程都包含以下三個(gè)階段。

(1) 初始解的構(gòu)造階段

通過循環(huán)迭代產(chǎn)生一個(gè)初始可行解，其中受限候選目錄仍然根據(jù)cost函數(shù)生成。不同的是每次迭代過程不再獨(dú)立，按照強(qiáng)化策略獲得學(xué)習(xí)改進(jìn)之后可以進(jìn)入下一階段的可行解。

(2) 雙字符搜索階段

同時(shí)搜索相鄰的兩個(gè)位置，嘗試變換不同組合的雙字符，根據(jù)cost*函數(shù)判別能否進(jìn)一步優(yōu)化，循環(huán)迭代直至局部最優(yōu)。

(3) 更新當(dāng)前最優(yōu)解階段

采用貪婪函數(shù)值和強(qiáng)Pareto優(yōu)化的雙判斷指標(biāo)，更新得出當(dāng)前最優(yōu)解。

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算法對(duì)比實(shí)驗(yàn)

本節(jié)對(duì)改進(jìn)之后的IGRASP-CSP算法和文獻(xiàn)[1]中所提出的GRASP-CSP算法進(jìn)行比較，如表2所示。

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

續(xù)表2

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

4結(jié)語

本文對(duì)經(jīng)典的CSP問題采用了一種概率啟發(fā)式的GRASP算法，以此為基礎(chǔ)，對(duì)現(xiàn)有的算法進(jìn)行了優(yōu)化。在構(gòu)造階段，通過強(qiáng)化策略對(duì)初始解的構(gòu)造進(jìn)行了學(xué)習(xí)改進(jìn)；在更新當(dāng)前最優(yōu)解階段，判斷指標(biāo)不再單一，引入強(qiáng)Pareto優(yōu)化使指標(biāo)多元化；特別在局部搜索階段，將搜索位置由原來的一個(gè)字符擴(kuò)展為兩個(gè)字符一起，意義不僅僅只在于一維擴(kuò)展為二維，能夠進(jìn)一步縮小漢明距離，更在于它是一維至多維的擴(kuò)展。因?yàn)樽鳛榻?jīng)典的CSP問題，如果對(duì)于它的研究只局限于問題本身而未能運(yùn)用到實(shí)際中，這是遠(yuǎn)遠(yuǎn)不夠的。比如三個(gè)堿基對(duì)對(duì)應(yīng)一個(gè)氨基酸，這便可以提取為一個(gè)CSP問題。在局部搜索階段就必須三個(gè)字符一起，因?yàn)槿齻€(gè)字符一起才對(duì)應(yīng)到相應(yīng)的生物信息。故搜索范圍由一維擴(kuò)展為二維，本文提供了一維至多維擴(kuò)展的思路，賦予了CSP問題的實(shí)際運(yùn)用，具有重要意義。

參考文獻(xiàn)

[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] 馮麗娟,嚴(yán)洪森,朱莉莉.基于改進(jìn)貪婪隨機(jī)自適應(yīng)算法的車間調(diào)度優(yōu)化[J].計(jì)算機(jī)技術(shù)與發(fā)展,2009,19(10):44-50.

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

[9] 樂美龍,王婷婷,吳聰聰.基于改進(jìn)的GRASP算法的飛機(jī)優(yōu)化恢復(fù)研究[J].江蘇科技大學(xué)學(xué)報(bào),2013,27(2):166-171.

[10] 李軍,郭玉華,王鈞,等.基于貪婪隨機(jī)自適應(yīng)過程的多類型衛(wèi)星聯(lián)合任務(wù)規(guī)劃技術(shù)[J].系統(tǒng)工程與電子技術(shù),2010,32(10):2162-2166.

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

中圖分類號(hào)TP301.6TP311

文獻(xiàn)標(biāo)識(shí)碼A

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

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