改进的蚁群算法在2D HP模型中的应用

改进的蚁群算法在2D HP模型中的应用 Application of Improved Ant Colony Optimization Algorithm to the 2D HP Model 何莲莲 HE Lian-lian~1 1 2 first-author 石峰 SHI Feng~1 1 2 周怀北 ZHOU Huai-bei~2 1 2 武汉大学数学与统计学院 武汉大学数学与统计学院 School of Mathematics and Statistics, Wuhan University School of Mathematics and Statistics, Wuhan University 武汉大学计算机科学学院,湖北,武汉,430072 武汉大学计算机科学学院,湖北,武汉,430072 School of Computer , Wuhan University School of Computer , Wuhan University 针对蛋白质二维格模型（2D HP）折叠问题提出了一种改进的蚁群算法（Ant Colony Optimization Al gorithm）,在算法的搜索阶段采用了牵引移动（pull moves）的方法:首先按照一定规则移动一个或两个顶点的位置,然后将其他顶点沿着链依次向前移动两个位置,一旦达到一个新的有效构象则停止该移动.该方法的优点是大多数移动只需改变很少的顶点位置,使得改进后的蚁群算法具有较快的收敛速度.求解基准实例的结果表明,该算法在保证解的质量的前提下能大大缩短计算时间. An improved Ant Colony Optimization （ACO） is proposed for the 2-dimensional hydrophobic-polar （2D HP） protein folding problem, we modified the local search mechanism by using pull moves: First one or two vertices was moved by rule, then, pull the other vertices two spaces up the chain until a new valid configuration is reached. The advantage is that most moves displace few vertices. It can quicken the convergence rate. Our experiments show that our algorithm can observably decrease computing time with the same result of previous ACO algorithm. 蛋白质折叠 格模型 蚁群算法 生物信息学 protein folding lattice model ant colony optimization （ACO） algorithm bioinformatics O241 国家自然科学基金资助项目（30170214） 2005-01-01 2021-04-01 1