Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (6): 92-95.

• 学术探讨 • Previous Articles     Next Articles

Oriented hill-climbing based genetic algorithm

LUO Biao,ZHENG Jin-hua,YANG Ping   

  1. Institute of Information Engineering,Xiangtan University,Xiangtan,Hunan 411105,China
  • Received:2007-06-12 Revised:2007-09-24 Online:2008-02-21 Published:2008-02-21
  • Contact: LUO Biao

基于定向爬山的遗传算法

罗 彪,郑金华,杨 平   

  1. 湘潭大学 信息工程学院,湖南 湘潭 411105
  • 通讯作者: 罗 彪

Abstract: The hill-climbing method is a local search algorithm,which has a good local search performance mainly because its search process is guided by information between individuals.In contrast,Traditional Genetic Algorithm(TGA) is a global search algorithm,which does not consider information between individuals in the search process.The convergence of TGA is limited because it only uses individuals’ fitness to guide the search.This paper proposes a new algorithm in which oriented hill-climbing mechanism is added to genetic algorithm.The new algorithm is named Oriented Hill-Climbing based Genetic Algorithm(OHCGA) which combines merits of hill-climbing method and TGA.Through the comparison of individuals,the algorithm uses the oriented hill-climbing operator to guide search to promising areas.Numerical experiments show that OHCGA improves the convergence speed and the ability of search optimal solutions compared with TGA.

摘要: 爬山法是一种局部搜索能力相当好的算法,主要是因为它是通过个体的优劣信息来引导搜索的。而传统的遗传算法作为一种全局搜索算法,在搜索过程中却没有考虑个体间的信息,而仅依靠个体适应度来引导搜索,使得算法的收敛性受到限制。将定向爬山机制应用于遗传算法,提出了一种基于定向爬山的遗传算法(OHCGA)。该算法结合了爬山法与遗传算法的优点,通过比较个体的优劣,使用定向爬山操作引导算法向更优秀的解区域进行搜索。实验结果表明,与传统遗传算法(TGA)相比,OHCGA较大地提高了算法的收敛速度和搜索最优解的能力。