李珊珊　郑　晨　朱　平

(江南大学理学院　江苏 无锡 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年提出……