论文部分内容阅读
组合优化是运筹学的重要分支,主要通过对数学方法的研究寻找离散事件的最优编排、分组、次序或筛选等。大多数这类问题通常在多项式时间里无法求解,属于NP完全问题。随着问题规模的扩大,问题空间呈现组合爆炸特征,无法用常规的方法求解。旅行商问题(TSP)就是一个经典的组合优化问题,属于NP完全问题。此类问题目前只能用启发式算法进行求解。 自从上世纪50年代中期创立仿生学以来,人们不断地从生物进化的机理中得到启发,提出了许多用于解决复杂优化问题的新方法,比如神经网络、遗传算法、模拟退火算法、进化规划等,并成功应用于解决实际问题。由意大利学者M.Dorigo,V.Maniezzo,A.Colorni于1992年首先提出的蚁群系统(Ant Colony System,ACS),是一种新颖的仿生进化算法,适用于求解复杂组合优化问题。目前,蚁群系统已成功应用于求解旅行商问题(TSP)、二次分配问题和job-shop调度问题,取得了很好的实验效果。受其影响,蚁群系统的研究已经逐渐引起了更多学者和专家的关注。虽然,该研究方法处于研究的初级阶段,但是一些研究成果已经显示出蚁群系统在求解复杂优化问题方面的优越性。 本文以近年来国内外学者提出的蚁群算法思想为基础,分析了基本蚁群算法易于出现早熟停滞现象的主要原因,并针对此在信息激素的更新技术上进行了改进,同时引入变参数及局部最优搜索策略,有效地抑制了收敛过程中的早熟停滞现象。并将改进后算法应用于求解TSP问题,实验结果表明,改进后算法加快了算法的收敛速度,改善了求解的性能。