遗传算法进化中积木块的识别和利用研究  

Study on the Recognition and Utilization of Building Block in the Iterations of Genetic Algorithm

作　　者：吕军[1] 冯博琴[1] 李波[1] 

机构地区：[1]西安交通大学电子与信息工程学院,西安710049

出　　处：《西安交通大学学报》2006年第2期133-137,共5页Journal of Xi'an Jiaotong University

基　　金：国家高技术研究发展计划资助项目(2003AA001048)

摘　　要：提出了一种基于积木块识别的遗传算法,该算法通过对进化过程中的候选积木块进行识别与利用来加速搜索,从而避免遗传算法随机搜索的盲目性.利用经典的对称旅行商问题求解过程来测试各种识别方法,再利用积木块的识别结果改进原有遗传算法,包括改进积木块的识别率以及基于积木块的交叉、变异算子.与基本遗传算法的计算结果对比分析表明,所提算法可显著提高遗传算法的搜索效率,减小遗传算法随机搜索的波动性.A genetic algorithm （GA） based on building block recognition was proposed, in which building block candidates were recognized in evolving process to speed up the search so as to avoid the blindness of GA random searching. The typical symmetric TSP （traveling salesman problem） solving process was used to test various recognition methods, and then the test results were used to improve the traditional GA, including improving the recognition rate of building blocks and mutation and crossover operators based on building block. Compared with the computational result of traditional GA, it shows that the searching efficiency of GA can be improved remarkably and the fluctuation of random searching can be reduced by recognizing building block.

关 键 词：遗传算法 积木块 旅行商问题 

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