mTSP(multiple traveling salesman problem)是一类在实际应用中经常遇到的问题,比如多机器人任务规划,城市公交车的调度等等。然而,在理论上,mTSP是一类著名的NP-困难问题(nondeterministicpolynomial time hardness problem),目前并没有有效的精确求解算法,于是,人们就尝试去寻找求解mTSP的各种近似算法。在求解mTSP的各种近似算法中,遗传算法作为一种复杂系统优化的具有鲁棒性的搜索算法,为求解复杂系统问题提供了一个通用的框架。本文围绕mTSP问题的求解展开深入研究,提出了一种新型的具有自适应能力的智能混合式遗传算法,为mTSP的求解提供了新的研究思路与求解方法,该新型智能混合式遗传算法具有以下两个主要特点:一、充分利用已知的启发式信息来指导遗传算法的搜索方向。在启发式信息的利用中,通过结点之间的边的α-接近度而不是边的权重来衡量结点之间的相邻性,可以较大的提高两结点相邻的可信度,从而改善算法的整体性能。二、提出了采用分层评估的思想来指导遗传算法的计算过程。在该评估思想的指导下,遗传算法中解的搜索过程不再仅仅由染色体的适应值所决定,而是由染色体的适应值以及其它更上层的评估值综合决定。染色体的适应值负责微观层面的解的搜索,上层的评估值负责整个算法的搜索方向,即宏观层面的搜索,从而在解的搜索过程中,形成高低搭配,共同为寻找最优解服务。