基于双字符搜索的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)。李珊珊，硕士生，主研领域：智能计算与生物统计。郑晨，硕士生。朱平，教授。