论文部分内容阅读
社会性动物的群集活动往往能产生惊人的自组织行为，如个体行为显得盲目的蚂蚁在组成蚁群后能够发现从蚁巢到食物源的最短路径。蚁群算法正是基于蚂蚁觅食行为提出的，该算法的出现引起了学者们的极大关注，在过去短短十多年的时间里，已在组合优化、网络路由、函数优化、数据挖掘、机器人路径规划等领域获得了广泛的应用，并取得了很好的效果。
蚁群算法具有正反馈、启发式搜索、良好的可扩充性等优点，但也存在初期信息素匮乏导致算法收敛速度慢、运行时间长、易陷入局部最优等缺点。为了克服这些缺点，本文在大量实验研究的基础上，对算法进行了改进，并将其应用于求解可满足问题（SAT）和旅行商问题（TSP），取得了很好的效果。
本文的主要工作和创新如下：
（1）以最大最小蚂蚁系统（MMAS）为模型，在分析各个参数的作用及对算法性能的影响的基础上，通过大量实验验证，给出了蚁群算法中各参数理想的取值范围。
（2）将蚁群算法应用于求解可满足问题（SAT），提出了求解SAT问题的最大最小蚂蚁系统（MMAS-SAT）。在改进的算法中，给出了SAT问题的构造图，对启发式信息值进行了改进，自适应的改变衰变系数ρ值。测试问题的数值实验表明，采用MMAS-SAT的结果优于Gwsat，Walksat、Novelty等求解SAT问题的局部搜索算法。
（3）针对蚁群算法的缺点，提出了IMMAS算法。该算法的改进主要包括：在算法的开始阶段采用遗传算法得到较优解，生成信息素的初始分布；改变了状态转移规则中概率的计算时机和方式；采用了2-交换算法和Metropolis接受准则相结合的局部搜索策略。并通过仿真实验将IMMAS运用于TSP问题，实验结果表明IMMAS在收敛速度、运行时间、求解精度上都优于最大最小蚂蚁系统（MMAS）。
蚁群算法具有正反馈、启发式搜索、良好的可扩充性等优点，但也存在初期信息素匮乏导致算法收敛速度慢、运行时间长、易陷入局部最优等缺点。为了克服这些缺点，本文在大量实验研究的基础上，对算法进行了改进，并将其应用于求解可满足问题（SAT）和旅行商问题（TSP），取得了很好的效果。
本文的主要工作和创新如下：
（1）以最大最小蚂蚁系统（MMAS）为模型，在分析各个参数的作用及对算法性能的影响的基础上，通过大量实验验证，给出了蚁群算法中各参数理想的取值范围。
（2）将蚁群算法应用于求解可满足问题（SAT），提出了求解SAT问题的最大最小蚂蚁系统（MMAS-SAT）。在改进的算法中，给出了SAT问题的构造图，对启发式信息值进行了改进，自适应的改变衰变系数ρ值。测试问题的数值实验表明，采用MMAS-SAT的结果优于Gwsat，Walksat、Novelty等求解SAT问题的局部搜索算法。
（3）针对蚁群算法的缺点，提出了IMMAS算法。该算法的改进主要包括：在算法的开始阶段采用遗传算法得到较优解，生成信息素的初始分布；改变了状态转移规则中概率的计算时机和方式；采用了2-交换算法和Metropolis接受准则相结合的局部搜索策略。并通过仿真实验将IMMAS运用于TSP问题，实验结果表明IMMAS在收敛速度、运行时间、求解精度上都优于最大最小蚂蚁系统（MMAS）。