基于知识库求解TSP问题的改进遗传算法  

An Improved Genetic Algorithm Based on Case Base for Traveling Salesman Problem

作　　者：韦雪洁[1] 黎明[1] 刘高航[1] 田贵超[1] 

机构地区：[1]南昌航空工业学院测试与控制系,江西南昌330034

出　　处：《计算机仿真》2006年第8期161-163,共3页Computer Simulation

基　　金：国家自然科学基金项目(60475002)

摘　　要：旅行商问题是一个典型的、易于描述却难以处理的np完全问题,快速有效地解决旅行商问题具有重要的理论和实际意义。该文提出了一种改进的遗传算法求解旅行商问题。该算法将遗传算法和知识库结合起来,利用遗传算法全局搜索能力强和知识库具有存储记忆功能的特点,提高了遗传算法求解旅行商问题的效率。并通过实验数据对基本遗传算法和改进遗传算法的求解结果进行比较,证明改进遗传算法的可行性和有效性。最后给出了改进遗传算法的重要问题和新的研究方向。Traveling Salesman Problem （TSP） is a typical nondeterministic polynomial time problem which is described easily but solved difficultly. Solving TSP efficiently and fast is of great significance in theory and practice. An improved Genetic Algorithm is put forward to solve TSP in this paper. The algorithm which combines the Genetic Algorithm with Case Base, can solve the TSP problem more effectively with strong global search capability of Genetic Algorithm and memory storage functionality of Case Base. The experimental results of simple Genetic Algorithm and the improved Genetic Algorithm are compared secondly. And the result shows the feasibility and effectiveness of the improved Genetic Algorithm. Finally, this paper points out the problem of the improved Genetic Algorithm and the new research direction.

关 键 词：遗传算法 知识库 旅行商问题 相似性问题 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]