基于定向爬山的遗传算法  

Oriented hill-climbing based genetic algorithm

作　　者：罗彪[1] 郑金华[1] 杨平[1] 

机构地区：[1]湘潭大学信息工程学院,湖南湘潭411105

出　　处：《计算机工程与应用》2008年第6期92-95,106,共5页Computer Engineering and Applications

基　　金：国家自然科学基金(the National Natural Science Foundation of Chinaunder Grant No.60773047);国家高技术研究发展计划(863)(the National High-Tech Researchand Development Plan of Chinaunder Grant No.2001AA114060);教育部留学回国人员科研启动基金(The Project-sponsored by SRF for ROCS;SEM;No.教外司留[2005]546号);湖南省自然科学基金(the Natural Science Foundation of Hunan Province of Chinaunder Grant No.05JJ30125);湖南省教育厅重点科研项目(No.06A074)。

摘　　要：爬山法是一种局部搜索能力相当好的算法,主要是因为它是通过个体的优劣信息来引导搜索的。而传统的遗传算法作为一种全局搜索算法,在搜索过程中却没有考虑个体间的信息,而仅依靠个体适应度来引导搜索,使得算法的收敛性受到限制。将定向爬山机制应用于遗传算法,提出了一种基于定向爬山的遗传算法(OHCGA)。该算法结合了爬山法与遗传算法的优点,通过比较个体的优劣,使用定向爬山操作引导算法向更优秀的解区域进行搜索。实验结果表明,与传统遗传算法(TGA)相比,OHCGA较大地提高了算法的收敛速度和搜索最优解的能力。The hill-climbing method is a local search algorithm,which has a good local search performance mainly because its seareh 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 Genetie 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.

关 键 词：遗传算法 定向爬山 收敛性 最优解 引导搜索 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]