论文部分内容阅读
旅行商(TSP)问题,是一个古老而又典型的NP-hard组合优化问题。该问题的有效求解,不仅有着重要的理论和学术价值,同时对于许多实际工程应用问题有着重要的指导意义。因此,寻求高效的TSP优化算法一直是优化领域的一个热点课题。微粒群算法是一种新型的群智能计算方法,算法模型简单、操作便捷,具有自组织、自适应、自学习等智能特性,已被证明是一种求解大规模复杂问题的有效工具,因此也是求解TSP问题的一种智能计算方法。然而,面对复杂的离散组合优化问题,现有的微粒群算法模型存在着效率低下,求解精度不高,易于早熟等缺陷。为此,本论文基于TSP优化问题,着重围绕离散微粒群算法的模型设计和性能改进,进行以下内容的研究:一、基于微粒群算法的优化机理,分析了离散微粒群算法设计的主要方法和基本原则,进而研究了离散微粒群算法的关键技术,包括离散问题的编码、个体微粒的评价及其主要进化操作,为后续的研究提供技术基础。二、为提高离散微粒群算法的全局收敛性,提出了一种引入局部扰动策略的改进微粒群算法。首先基于整数编码,并结合遗传算法中的PMX算子,对离散微粒群算法中的速度、位置及其进化操作进行了重新定义,其次引入微粒的活力信息来实现控制参数的自适应调节,构造局部扰动策略以避免群体局部收敛。改进算法被用于典型TSP测试问题,其仿真结果表明该算法的有效性。三、为提高离散微粒群算法对复杂问题的求解能力,提出一种基于边编码,采用表示边的两城市点之间所有点依次倒置插入的微粒更新操作的改进离散微粒群算法。并在对算法方程进行重新定义的基础之上,加入微粒适应值变优则更新,变差按一定概率更新的策略。通过在典型中型TSP问题上进行的实验,求解时间、求解精度上均令人满意。然后在这个改进算法的基础之上加入多级规约策略,为微粒群算法求解大规模问题提供了一种思路。