机构地区: 华南理工大学理学院数学与应用数学系
出 处: 《华南理工大学学报(自然科学版)》 2004年第4期97-100,共4页
摘 要: 介绍了TSPPC(Traveling Salesman Problem with Precedence Constraint) ,并指出了普通遗传算法对于求解TSPPC的局限性及在算法过程中产生大量非可行解 ,从而降低了算法的搜索效率 .提出了基于TSPPC中约束条件的种群初始化、交叉操作以及变异操作 .由于运用这些遗传操作在算法过程中不会产生非可行解 ,因此大大提高了算法的搜索效率 . The Traveling Salesman Problem with Precedence Constraint (TSPPC) was introduced and the localization of the general genetic algorithm (GA) to solve TSPPC was pointed out. It is found that a lot of illegal chromosomes would be generated by using the general GA, thus reducing the searching efficiency of the algorithm. To overcome the disadvantages mentioned above, the species initialization, crossover and mutation based on the precedence constraint of TSP were proposed. None of these genetic operations would generate any illegal chromosome, which makes the searching efficiency of the algorithm higher. This conclusion was finally verified by corresponding theorems and examples.
关 键 词: 有约束条件的旅行商问题 遗传算法 种群初始化 交叉 变异