混合量子遗传算法及其在VRP中的应用  

Hybrid Quantum Genetic Algorithm and Its Application in VRP

作　　者：蔡蓓蓓[1] 张兴华[1] 

机构地区：[1]南京工业大学自动化学院,江苏南京210009

出　　处：《计算机仿真》2010年第7期267-270,334,共5页Computer Simulation

摘　　要：物流配送车辆路径问题(VRP)是一类典型的NP问题。针对提高寻优能力问题,构造了一种混合量子遗传算法(HQGA),即在传统量子遗传算法(QGA)随机全局搜索的基础上引入一个免疫算子,通过该算子的局部搜索操作实现线路内次序的再优化。给出了该算法的具体实现方法和流程,并用实例进行测试。仿真结果表明混合量子遗传算法的寻优性能优于传统量子遗传算法(QGA)及文献中的其它方法,可以避免出现早熟收敛,是求解车辆路径问题的一种有效的算法。The vehicle routing problem is a kind of NP problem.In order to solve this problem,this paper employs a Hybrid Quantum Genetic Algorithm（HQGA ） which not only has the global searching capacity of Conventional Quantum Genetic Algorithm（QGA）,but also uses immune operator as a local searching scheme to optimize subroutes. The implementation method and procedure of this algorithm are introduced in detail in the paper.The experimental results of a VRP instance show that HQGA is superior to the conventional quantum genetic algorithm and other reported algorithms.HQGA can avoid the problem of premature convergence,so it is an efficient method for solving the vehicle routing problem.

关 键 词：车辆路径问题 混合量子遗传算法 免疫算子 疫苗 

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