论文部分内容阅读
蚁群优化算法(Ant Colony Optimization,ACO)和粒子群算法(Particle SwarmOptimization,PSO)是两种典型的群体智能算法。由于算法的高效性和易实现性,因此成为了众学者的研究焦点。目前,这两种算法已被应用到函数优化和工程技术领域,并取得了较好的效果。另一方面,算法在许多领域的研究还处于起步阶段,算法本身存在着一些不足之处。旅行商问题(Traveling Salesman Problem,TSP)是一种经典的、受到广泛研究的组合优化问题之一。迄今为止,已经有多种不同的求解方法被提出。蚁群优化算法和粒子群算法均被尝试应用于旅行商问题的求解,并取得了较大进展。然而,与一些专门用于求解旅行商问题的启发式方法相比,算法在所求解的质量上仍存在一些不足。因此,如何对算法加以改进使其具有更好的性能具有重要的意义。本文在前人工作的基础上,对蚁群优化算法、粒子群算法及其在旅行商问题中的应用进行了研究。主要工作如下:1.针对蚁群优化算法容易陷入局部最优的缺陷,提出了一种基于排列的动态自适应蚁群算法。首先,为了避免算法后期陷入停滞状态,信息素的下界被设置为一个非零常数,根据蚁群中蚂蚁获得的解的质量的优劣,选出部分最优秀的蚂蚁按其解的优劣程度酌量释放信息素,以增强蚂蚁后期探索最优解的能力;其次,采用了一种更具智能性的行为选择规则,使蚁群在搜索过程中可以动态调整探索和开发之间的平衡系数,有效抑制收敛过程中的早熟现象,提高算法的搜索能力。最后为了验证所提出的方法的有效性和可行性,对TSPLIB标准库中的多个实例进行了测试,并给出了数值结果。2.针对标准粒子群算法在求解旅行商问题过程中容易出现早熟和停滞现象的缺点,提出了一种改进的粒子群算法。首先,在初始解的选取过程中,利用改进的贪婪策略直接获得一组高性能初始解以提高算法的搜索效率。其次,通过引入次优吸引子,使粒子在搜索过程中可以更加充分地利用群体的信息来提高自身的性能,有效抑制收敛过程中的停滞现象,提高算法的搜索能力。为了验证所提出的算法的有效性和可行性,对两个无约束优化问题以及TSPLIB标准库中的多个实例进行了测试,并与其他的已知算法进行了比较,给出了数值结果。