一种求解邮路问题的量子进化算法  

Quantum Evolutionary Algorithm for Solving Postal Route Problem

作　　者：赵俊生[1] 

机构地区：[1]甘肃民族师范学院计算机科学系,甘肃合作747000

出　　处：《计算机工程》2011年第7期234-236,共3页Computer Engineering

基　　金：甘肃省教育科研基金资助项目(0614B-03)

摘　　要：乡村邮递员问题属于NP完全问题,对它的近似求解方法主要是智能算法及线性规划,但其中的基本量子进化算法易陷于局部最优解。为此,提出一种新的量子进化算法,结合城市垃圾运输问题,对算法进行测试。结果表明,该算法在全局寻优能力及种群多样性方面均比传统算法有所改进,是求解乡村邮递员问题的一种有效算法。The Village Postman Problem（VPP） is NP-complete problem.Most of the algorithms for it are intelligence algorithm and linear programming.Aiming at basic Quantum Evolution Algorithm（QEA） is easy to trap into local deceptive optima,an improved QEA is proposed.Experimental result demonstrates the improved algorithm can get better solution to the VPP than basic algorithm.It has better diversity and global search capacity.It indicates the algorithm is effective to solve the VPP.

关 键 词：量子算法 量子进化算法 乡村邮递员问题 HAMILTON圈 

分 类 号：TP311.52[自动化与计算机技术—计算机软件与理论]