论文部分内容阅读
路径规划优化方法及其应用是人工智能领域备受关注的一个研究方向,基于蚁群算法研究路径规划是其中具有代表意义的方法之一。从不同的应用问题背景来看,目前已提出的基于蚁群算法的路经规划方法,在收敛时长、个体适应度、易陷入局部最优解等方面还存在值得进一步改善之处。鉴于此,本文从二维、三维路径规划两个应用角度出发,引入多策略组合优化思想和变异算子,重点研究了面向路径规划的改进型蚁群算法。主要开展了以下研究工作:1.研究提出了面向二维路径规划的一种多策略组合优化蚁群算法ACA-CMs(Ant Colony Algorithm based on Combined Multi-strategy)。该算法通过信息素更新、2-opt局部优化、限定信息素浓度范围等多策略组合优化的方法来改进传统蚁群算法,以改善传统蚁群算法收敛时间慢、易陷入局部最优解等缺陷。二维TSP(Traveling Salesman Problems)求解实例及与基本蚁群算法、基于遗传机制蚁群算法的比对实验表明,ACA-CMs算法是有效可行的,且在收敛时间降低、搜索路径缩短、提高最优解质量等方面效果良好。2.研究提出了面向三维路径规划的一种变异算子蚁群算法ACA-MO(Ant Colony Algorithm based on Mutation Operator)。该算法在改进启发式函数设计、选择概率确定、信息素更新策略等基础上,引入逆转变异和插入变异算子,通过选择逆转点反序排列部分路径节点和随机插入路径节点的方法搜索无碰路径,对蚁群算法进行了局部优化改良。TSPLIB模拟数据集上的三维路径规划仿真实验表明,相比基本蚁群算法和基于遗传机制改进的蚁群算法,ACA-MO算法在搜索路径、收敛时间、个体适应度等方面有明显改善,算法是有效可行的。本文研究贡献主要在于从信息素更新策略、2-opt局部优化策略、限定信息素浓度范围策略、启发式函数设计、选择概率确定及变异算子引入等多方面对基本蚁群算法进行改进,并应用于二维和三维路径规划问题求解。