摘要
爬山法是一种局部搜索能力相当好的算法,主要是因为它是通过个体的优劣信息来引导搜索的。而传统的遗传算法作为一种全局搜索算法,在搜索过程中却没有考虑个体间的信息,而仅依靠个体适应度来引导搜索,使得算法的收敛性受到限制。将定向爬山机制应用于遗传算法,提出了一种基于定向爬山的遗传算法(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.
出处
《计算机工程与应用》
CSCD
北大核心
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)。
关键词
遗传算法
定向爬山
收敛性
最优解
引导搜索
genetic algorithm
oriented hill-climbing
convergence
optimal solutions
guide search
