摘要
提出了一种新的求解旅行商问题的贪婪边重组交叉算子。该交叉算子吸取了边重组交叉算子的优点,使得父代在进化过程中获得的优良的边能顺利地遗传给子代。同时,在边重组的过程中,该交叉算子引入所求旅行商问题的具体信息以指导新边的生成,从而该交叉算子具有贪婪特征。实验结果表明:对于简单的旅行商问题,贪婪边重组交叉算子能显著提高算法效率;对于大规模的旅行商问题,该交叉算子的效果也较理想。
A greedy edge recombination crossover is proposed.This crossover,which utilizes the advantages of the edge recombination crossover,makes the offspring succeed to the excellent edge belonging to the parents.Meanwhile,it has the characteristic of greed by introducing the problem-specific knowledge in the process of edge recombination.The numerical simulations demonstrate that the greedy edge recombination crossover can remarkably improve the efficiency in dealing with the simple traveling salesman problem,and the experimental results of solving the large-scale traveling salesman problem are also satisfying.
出处
《计算机工程与应用》
CSCD
北大核心
2006年第31期19-22,共4页
Computer Engineering and Applications
基金
教育部重点研究项目(205098)
湖北省教育厅重大研究项目(Z200511001)
湖北省教育厅研究项目(2001A19006)
关键词
旅行商问题
遗传算法
贪婪边重组交叉算子
traveling salesman problem
genetic algorithms
greedy edge recombination crossover
