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

• 作者: 朱平 李珊珊 郑晨
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: CSP GRASP Pareto 优化 强化策略 双字符
• 年，卷（期）: 2016,（2）
• 所属期刊栏目: 算 法
• 页码范围: 203-207,258
• 页数: 6页
• 分类号: TP301.6|TP311
• 字数: 6223字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386x.2016.02.048

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	朱平	江南大学理学院	60	186	7.0	12.0
2	李珊珊	江南大学理学院	8	3	1.0	1.0
3	郑晨	江南大学理学院	2	2	1.0	1.0