一种解决TSP问题的自适应协同演化计算方法

王智广，王兴会，何文俊

(中国石油大学(北京)信息工程学院，北京 102249)

演化计算来自于达尔文的自然进化理论，其通过使用种群、进化、评估、迭代等方法来体现自然界中“优胜劣汰”原则，以获得问题的最优解，常被用于组合优化问题求解.演化计算是一种非常重要的算法思想，最初由Fogel在1952年博士论文中提出，由Holland和其学生提出的遗传算法将这种思想推广并进行深度应用[1]. 目前在演化计算思想上发展出了许多算法，主要包括两个方面的内容：一种是以遗传算法、差分进化[2]、演化编程为代表的演化算法；另一种是以蚁群算法[3]、粒子群算法[4]、蜂群算法[5]为代表的群智能算法.演化算法主要以自然进化为理论依据，通过种群之间的迭代演化完成问题的求解.而群智能算法通过模拟自然界中的群智能生物(蚂蚁、大雁、蜜蜂)行为来完成问题的求解.由于两种类型的算法关注点不同，从而导致在解决问题时所产生的效果也是不同的.虽然现在没有统一的理论来规定什么样的问题适用于什么样的演化算法.但是从解决问题的实践来看，这两种类型算法具有互补性.遗传算法通过种群进行目标寻优，其强调的是全局搜索能力而对局部的细致搜索不足，而蚁群算法通过信息素的正反馈来强化局部搜索能力，但其全局搜索能力不强，而全局搜索和局部搜索不足均可能导致早熟和停滞的现象方式.因此如果能够将两种算法结合起来运行，将……