论文部分内容阅读
组合优化是运筹学的重要分支,主要通过对数学方法的研究寻找离散事件的最优编排、分组、次序或筛选等。大多数这类问题通常在多项式时间里无法求解,属于NP完全问题。随着问题规模的扩大,问题空间呈现组合爆炸特征,无法用常规的方法求解。旅行商问题(TSP)就是一个经典的组合优化问题,属于NP完全问题。此类问题适合用启发式算法进行求解。
自从上世纪50年代中期创立仿生学以来,人们不断地从生物进化的机理中得到启发,提出了许多用于解决复杂优化问题的新方法,比如神经网络、遗传算法、模拟退火算法、进化规划等,并成功应用于解决实际问题。由意大利学者M.Dorigo,V. Maniezzo,A.Colomi于1992年首先提出的蚁群系统(Ant Colony System,ACS),是一种新颖的仿生进化算法,适用于求解复杂组合优化问题。目前,蚁群系统己成功应用于求解旅行商问题(TSP)、二次分配问题和job-shop调度问题,取得了很好的实验效果。受其影响,蚁群算法的研究已经逐渐引起了更多学者和专家的关注。但对直接影响蚁群算法的参数调整策略却研究较少。
本文讨论并提出了一种基于自适应参数调整的蚁群算法。文章首先分析了算法中各个参数的作用及其对算法性能的影响,使用大量实验证实了参数的调整对蚁群算法计算性能的影响,并给出了一组用于基本蚁群算法的较优参数。针对蚁群算法的参数与计算结果之间不存在明显规律性且难于用显式表示其关系的特点,本文将算法中的众多参数当作一个整体考虑,把蚁群算法的参数调整问题看作一个以参数为输入变量的最优化问题,提出了一种基于人工鱼群算法(Artificial Fish Swarm Algorithm, AFSA)的自适应参数调整策略。并讨论了人工鱼群的初始分布对算法性能的影响,使用实验证明基于均匀分布的初始化分布更有利于算法取得较好的结果。