检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

基于蚁群算法的一类扩展型TSP研究

系统工程 2003年第1期21卷 17-21页

作者：赵学峰西北师范大学数学与信息科学学院甘肃兰州730070

旅行售货问题 ( TSP)是经典的组合优化难题 ,本文研究它的一种推广模型。蚁群算法是近年来发展起来的一种新型的启发式随机优化搜索算法 ,本文在蚁群算法中采用了优势个体指导机制。实验模拟结果显示算法的有效性。

关键词：蚁群算法扩展型TSP 旅行售货商问题信息素组合优化 NP问题

在线全文

学校读者我要写书评

暂无评论

求解TSP的自适应优秀系数粒子群优化算法

计算机应用 2017年第3期37卷 750-754,781页

作者：程毕芸鲁海燕黄洋许凯波江南大学理学院江苏无锡214122

针对基本离散粒子群优化(PSO)算法求解旅行售货商问题(TSP)时容易陷入局部最优解和早熟收敛的问题,提出了一种基于自适应优秀系数的粒子群(SECPSO)算法。为了提高算法的全局搜索能力,在已有工作的基础上,进一步利用启发式信息对静态的... 详细信息

针对基本离散粒子群优化(PSO)算法求解旅行售货商问题(TSP)时容易陷入局部最优解和早熟收敛的问题,提出了一种基于自适应优秀系数的粒子群(SECPSO)算法。为了提高算法的全局搜索能力,在已有工作的基础上,进一步利用启发式信息对静态的路径优秀系数进行修改,使之可根据解的搜索过程进行自适应动态调整;另外,为了进一步提高解的精确性和算法的收敛速度,添加了3-opt搜索机制,提高算法的局部搜索能力。利用Matlab进行了实验仿真,用国际通用的TSP数据库(TSPLIB)中的若干经典实例对算法性能进行了测试。实验结果表明,与其他几种算法相比,SECPSO算法在全局寻优能力和更快的收敛速度方面表现更优,是求解TSP问题的一种有潜力的智能算法。

关键词：自适应优秀系数 3-opt 粒子群优化算法旅行售货商问题

求解TSP的改进信息素二次更新与局部优化蚁群算法

在线全文

学校读者我要写书评

暂无评论

计算机应用 2017年第6期37卷 1686-1691页

作者：许凯波鲁海燕程毕芸黄洋江南大学理学院江苏无锡214122

针对蚁群(ACO)算法收敛速度慢、容易陷入局部最优的缺陷,提出了一种改进信息素二次更新局部优化蚁群算法(IPDULACO)。该算法对蚁群搜索到的当前全局最优解中路径贡献度大于给定的路径贡献阈值的子路径信息素进行二次更新,以提高构成潜... 详细信息

针对蚁群(ACO)算法收敛速度慢、容易陷入局部最优的缺陷,提出了一种改进信息素二次更新局部优化蚁群算法(IPDULACO)。该算法对蚁群搜索到的当前全局最优解中路径贡献度大于给定的路径贡献阈值的子路径信息素进行二次更新,以提高构成潜在最优解的子路径被选择的概率,从而加快算法的收敛。然后,在搜索过程中,当蚁群陷入局部最优时,使用随机插入法对局部最优解中城市的排序进行调整,以增强算法跳出局部最优解的能力。将改进算法应用于若干经典的旅行售货商问题(TSP)进行仿真实验,实验结果表明,对于小规模的TSP,IPDULACO可以在较少的迭代次数内获得已知最优解;对于较大规模的TSP,IPDULACO可以在较少的迭代次数内获得更精确的解。因此,IPDULACO具有更强的搜索全局最优解的能力和更快的收敛速度,可以高效求解TSP。

关键词：旅行售货商问题蚁群算法信息素二次更新局部优化

在线全文

学校读者我要写书评

暂无评论

蚁群算法的改进及其在若干优化问题中的应用

蚁群算法的改进及其在若干优化问题中的应用

作者：许凯波江南大学

学位级别：硕士

蚁群优化(Ant colony optimization,简称ACO)算法是根据蚂蚁寻找食物时发现路径的行为提出的,该算法具有并行式、正反馈、自组织等许多优良的性质。最初ACO算法用于求解旅行售货商问题(Traveling Salesman Problem,简称TSP),随后又被用... 详细信息

蚁群优化(Ant colony optimization,简称ACO)算法是根据蚂蚁寻找食物时发现路径的行为提出的,该算法具有并行式、正反馈、自组织等许多优良的性质。最初ACO算法用于求解旅行售货商问题(Traveling Salesman Problem,简称TSP),随后又被用于求解路径规划、数据挖掘等问题。TSP是找一个无向带权完全图里权值最小的一条Hamilton回路;路径规划是机器人研究领域的重要内容之一,其目的是在有障碍物的环境中为机器人寻找一条满足特定指标最优的路径。应用ACO算法求解这两个问题时,都存在收敛慢、容易陷入局部最优等缺陷。为此,本文提出改进的ACO算法来求解这两个问题,主要工作概括如下:(1)针对蚁群(ACO)算法收敛速度慢、容易陷入局部最优等缺陷,提出了一种改进信息素二次更新局部优化蚁群算法(IPDULACO)。该算法对蚁群搜索到的当前全局最优解中路径贡献度大于给定的路径贡献阈值的子路径信息素进行二次更新,以提高构成潜在最优解的子路径被选择的概率,从而加快算法的收敛速度。其次,在搜索过程中,当算法陷入局部最优时,使用随机插入法对局部最优解中城市的排序进行调整,以增强算法跳出局部最优解的能力。实验结果表明,IPDULACO具有更强的搜索全局最优解的能力和更快的收敛速度。(2)针对动态环境未知时变的特点,提出一种机器人路径规划新方法。在该方法中,首先对栅格法建立的环境模型进行凸化处理,以避免机器人沿规划路径移动时陷入U型陷阱,从而加快路径规划的速度;其次,提出双层蚁群算法(DACO),在每次迭代中先用外层ACO算法寻找一条路径,然后以该路径为基础构造一个小环境,接着在该环境下用内层ACO算法重新寻优,若寻得的路径质量更高,则更新路径并执行本文给出的一种新型信息素二次更新策略;最后,针对环境中不同动态障碍物的体积和速度,提出三种避障策略。动态环境下,先由DACO算法为机器人规划一条当前环境(即静态环境)下从起点到终点的全局最优路径,然后从当前起点开始,通过自带传感器获取动态环境信息,并根据需要执行等待、正碰或追尾避障策略,到达新的起点。仿真实验表明,该方法可以在动态环境下实时地为移动机器人规划出一条安全且最短的路径,是移动机器人路径规划问题的一种切实有效的方法。(3)针对ACO算法求解三维路径规划问题时容易陷入局部最优的缺陷,以及三维环境的特点,对ACO算法进行改进。首先根据下一可选节点距终点的距离的远近赋予不同大小的权值,近的节点赋予较大的权值,远的节点赋予较小的权值;此外通过引入高度因子对节点选择概率进行改进,控制算法向适应度值高的区域搜索,进而提高最优解质量。仿真结果也表明了改进算法的有效性。

关键词：组合优化蚁群优化算法信息素旅行售货商问题移动机器人路径规划

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

TSP问题的一种改进的GRASP算法

计算机工程与科学 2008年第11期30卷 60-64页

作者：郑雅燕朱文兴福州大学数学与计算机科学学院福建福州350002 福州大学离散数学与理论计算机科学研究中心福建福州350002

本文对Marinakis等提出的扩展邻域GRASP算法进行改进。首先使用最近α值方法构造初始TSP回路,然后运用混合的局部搜索即2-opt算法、双桥策略和3-opt算法来改进初始回路,并且引进α-nearness候选集和don’t-lookbit技术来提高搜索速度。... 详细信息

本文对Marinakis等提出的扩展邻域GRASP算法进行改进。首先使用最近α值方法构造初始TSP回路,然后运用混合的局部搜索即2-opt算法、双桥策略和3-opt算法来改进初始回路,并且引进α-nearness候选集和don’t-lookbit技术来提高搜索速度。实验结果表明,本文提出的GRASP能够在合理的时间内得到很好的解,并且解的质量优于Marinakis等提出的扩展邻域GRASP算法得到的解。

关键词：旅行售货商问题贪心随机适应性搜索算法局部搜索算法候选集

{1,2}-赋权图最小最大2-路径覆盖问题的近似算法

在线全文

学校读者我要写书评

暂无评论

杭州电子科技大学学报(自然科学版) 2022年第5期42卷 89-92页

作者：姚会影周圆陈光亭陈永张安杭州电子科技大学理学院浙江杭州310018 台州学院电子与信息工程学院浙江台州318000

给定边权重为1或2的完全图,研究如何用2条顶点不相交的路径覆盖图中所有顶点,为了达到最大路径权重尽可能小的目标,在{1,2}-赋权图上旅行售货商问题的已有算法的基础上,设计了该问题的近似算法,并证明了算法的近似比不超过11/7。

关键词： {1,2}-赋权图路径覆盖旅行售货商问题近似算法