求解货郎担问题的量子进化算法  

QUANTUM EVOLUTIONARY ALGORITHM FOR SOLVING TRAVELLING SALES PERSON PROBLEM

作　　者：赵俊生[1] 

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

出　　处：《计算机应用与软件》2013年第2期202-204,共3页Computer Applications and Software

基　　金：甘肃省自然科学基金项目(1010RJZP126)

摘　　要：货郎担问题属于NP完全问题,对它的近似求解方法主要是智能算法及线性规划,但其中的基本量子进化算法易陷于局部最优解。为此,提出一种新的量子进化算法,结合乡村货郎运输问题,对算法进行测试。结果表明,该算法在全局寻优能力及种群多样性方面均比传统算法有所改进,是求解乡村货郎担问题的一种有效算法。Travelling sales person problem（TSP） is an NP-complete problem.Approximate solutions for it are mainly the intelligence algorithm and the linear programming,but the basic quantum evolutionary algorithm（QEA） among these solutions is prone to fall into local optimum,therefore an improved QEA is proposed.The algorithm is tested in combination with travelling sales person transportation problem.Experimental result demonstrates that the new algorithm is improved in population diversity and global search capacity compared with the conventional algorithms,and is effective in solving the TSP.

关 键 词：量子算法 量子进化算法 乡村货郎担问题 HAMILTON圈 

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