求解DNA杂交测序的改进最大最小蚂蚁算法

An Improved Max-Min Ant Algorithm for DNA Sequencing by Hybridization

根据DNA杂交测序的特点,设计了一个改进的最大最小蚂蚁算法.首先,对问题进行预处理,将其转化为有约束的非对称旅行商问题;然后,对状态转移规则和全局更新规则进行改进,并运用变量邻域搜索思想,设计了一种简单高效的局部搜索技术.最后,采用后处理技术来解决长度约束问题.实验结果表明:该算法提高了DNA杂交测序的求解精度.

An improved Max-Min Ant algorithm is designed based on the characteristics of DNA sequencing by hybridization.First,apreparatory treatment is done to transform the problem into a non-symmetrical traveling salesman problem with constraints.Second,after improving the state transition rule and the global update policy,a simple and efficient local search technique is designed by applying the idea of variable neighborhood search.Finally,the post-processing technology is adopted to solve the problem of length restraint.The result shows that our algorithm is significantly better than other algorithms in raising the accuracy and stability of solving DNA sequencing by hybridization.