查询结果:   李珊珊,郑晨,朱平.基于双字符搜索的GRASP-CSP算法改进[J].计算机应用与软件,2016,33(2):203 - 207,258.
中文标题
基于双字符搜索的GRASP-CSP算法改进
发表栏目
算法
摘要点击数
619
英文标题
[JP2]IMPROVEMENT OF GRASP-CSP ALGORITHM BASED ON DOUBLE CHARACTER SEARCH
作 者
李珊珊 郑晨 朱平 Li Shanshan Zheng Chen Zhu Ping
作者单位
江南大学理学院 江苏 无锡 214122     
英文单位
School of Science, Jiangnan University, Wuxi 214122, Jiangsu,China     
关键词
CSP GRASP Pareto优化 强化策略 双字符
Keywords
CSP GRASP Pareto optimisation Enforcing strategy Double character
基金项目
国家自然科学基金项目(11271163)
作者资料
李珊珊,硕士生,主研领域:智能计算与生物统计。郑晨,硕士生。朱平,教授。 。
文章摘要
距离最近字符串问题CSP(The Closest String Problem)是一个组合优化问题,在生物信息学和编码理论中有着很重要的应用。关于CSP问题采用一种基于概率启发式的算法,即GRASP-CSP算法。针对GRASP-CSP算法存在的每次迭代过程相对独立、搜索范围狭窄、判断指标过于单一这三大问题,提出通过强化策略,引入强Pareto优化的概念,特别是扩展局部搜索范围,对GRASP-CSP进行进一步的优化。最后,给出基于GRASP-CSP改进之后的新算法,即IGRASP-CSP。实验结果表明,改进之后的新算法能够进一步缩小字符解与给定字符串集的汉明距离,从而得到关于CSP问题的进一步优化解,获得满意的优化效果,并从一维的应用扩展至多维。
Abstract
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.
下载PDF全文