A Compounded Genetic and Simulated Annealing Algorithm for the Closest String Problem
The closest string problem is an NP-hard problem, which arises in computational molecular biology and coding theory. Its task is to find a string that minimizes maximum Hamming distance to a given set of strings. In this paper, a compounded genetic and simulated annealing algorithm (CGSA) which combines the merits of genetic algorithms and simulated annealing is presented to solve CSP. An adapting two-point crossover operator and a heuristic gene mutation operator designed by us are used in CGSA. In addition, by analyzing the optimal solutions structural features some rules are designed to pretreat the data, which reduces the problem size. We report computational results which show that the CGSA is capable of finding good solutions in a reasonable amount of time.
Closest String Problem Genetic Algorithm Simulated Annealing Computational Biology Hybrid Methods
Xiaolan LIU Mauch Holger Zhifeng HAO Guangchao WU
School of Computer Science & Engineering South China University of Technology Guangzhou, China Schoo Natural Sciences Collegium Eckerd College Florida, USA School of Mathematical Sciences South China University of Technology
国际会议
上海
英文
702-705
2008-05-16（万方平台首次上网日期，不代表论文的发表时间）