基于双字符搜索的 GRASP-CSP 算法改进

摘要

距离最近字符串问题 CSP（The Closest String Problem）是一个组合优化问题，在生物信息学和编码理论中有着很重要的应用。关于 CSP 问题采用一种基于概率启发式的算法，即 GRASP-CSP 算法。针对 GRASP-CSP 算法存在的每次迭代过程相对独立、搜索范围狭窄、判断指标过于单一这三大问题，提出通过强化策略，引入强 Pareto 优化的概念，特别是扩展局部搜索范围，对 GRASP-CSP 进行进一步的优化。最后，给出基于 GRASP-CSP 改进之后的新算法，即 IGRASP-CSP。实验结果表明，改进之后的新算法能够进一步缩小字符解与给定字符串集的汉明距离，从而得到关于 CSP 问题的进一步优化解，获得满意的优化效果，并从一维的应用扩展至多维。%The 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.