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

Application of Improved Ant Colony Optimization Algorithm to the 2D HP Model

针对蛋白质二维格模型(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.