共查询到20条相似文献,搜索用时 375 毫秒
1.
2.
基于求解TSP问题,提出一种离散型萤火虫群优化(DGSO)算法,该算法结合TSP问题特点,给出一种有效编码和解码方法,并定义适合编码的个体间距离计算公式和编码更新公式.同时,为增强算法求解TSP问题的局部搜索能力,加快算法的收敛速度,算法使用了操作简单的2-Opt优化算子.最后,通过对10个TSP问题进行仿真实验,实验结果表明本文提出的算法是在种群规模较小,迭代次数较少的情况下就可以收敛到已知最优解.在大规模TSP算例中算法获得的最优值与理论最优值的误差也在1%以下. 相似文献
3.
4.
针对蚁群算法在求解大规模优化问题时存在的3个缺点:消耗时间长、蚂蚁在下次搜索时目标导向不强导致搜索随机性大、寻优路径上的信息素过度增强导致得到假的最优解。本文提出了基于边缘初始化和自适应全局信息素的改进蚁群算法。在相同参数下,其搜索时间大大缩短,并且得到了更好的最优解。将其应用到旅行商(TSP)问题中,和基本蚁群算法、遗传算法相比较,其具有以下优点:较好的搜索最优解的能力;对新解不会过早的终止;探索新解的能力进一步增强。因此,改进的蚁群算法在求解TSP等组合优化问题时非常有效。 相似文献
5.
6.
7.
本文提出样本空间经过K-均值聚类算法聚类加工处理后,算法通过动态地调整选择路径概率,优化TSP求解过程中解的分布均衡性,可以在加速收敛和防止早熟、停滞现象之间取得很好的平衡。这种新的算法提供了在样本空间预处理情况下,动态自适应地解决TSP问题最优解的新方法。比起普通蚁群算法,此算法对大规模数据的最优解的求解更有显著效果。 相似文献
8.
旅行商问题(TSP)是一种经典的组合优化问题.传统的蚁群算法运用正反馈和分布式计算机制,具有较强的鲁棒性.但是该算法搜索时间长、易出现早熟停滞现象.因此本文根据旅行商问题的模型特点,在蚁群算法的基础上针对TSP问题提出了一种新型的改进蚁群算法:即变参数选择城市策略,并且在交叉策略中选择PMX(Partially Matched Crossover)交叉策略.实验结果表明,与传统基本蚁群算法和遗传算法相比,能够较快地找到最优解,解的质量也相对较好,因此提高了蚁群算法对TSP问题的求解效率. 相似文献
9.
多无人机协同任务规划 总被引:1,自引:0,他引:1
为解决多无人机协同规划军事目标打击的问题,基于多旅行商(TSP)数字规划理论进行路径和时间的优化。文中建立了多旅行商(TSP)数字规划模型,并根据任务性能和区域划分理论,利用退火算法求解出该模型的最优解。使用A*路径规划算法,通过编程仿真规划出了无人机的时间最优路径。结果表明,该方法较好地解决了当前无人机协同作战的目标分配问题,大幅提高了无人机协同作战的能力。 相似文献
10.
混沌优化算法在组合优化问题中的应用 总被引:3,自引:0,他引:3
组合优化问题一直都受到理论界和工程界的重视,此类问题的求解方法也有很多,却各有缺点和局限性,不能满足实际应用的需要。混沌优化算法在解决数值优化问题上具有一定的普遍性,可以很快找到全局最优解,不过组合优化问题的解不是一个数值,因此在前人研究的基础上,提出求解组合优化问题的混沌优化算法。首先分析混沌优化,并针对组合优化问题中的TSP问题,提出一种混沌优化策略,探讨在TSP问题中应用混沌优化算法的方法。结果表明了该方法的有效性。 相似文献
11.
钟文亮 《微电子学与计算机》2006,23(Z1):183-186
通过选择合适的算子和参数,遗传算法(GA)可以有效求解旅行商问题(TSP)。GA通常可以获得满意解,但容易陷入早熟,因而较难求得全局最优解。传统的变异算子在求解该问题时性能并不理想,甚至会引起反作用。文章通过实验分析多种变异算子在求解TSP时的表现,提出了一个改进的破坏重建变异法,并利用该方法对算法进行优化。经仿真实验测试,该方法效果明显。 相似文献
12.
《现代电子技术》2019,(14)
对于求解TSP问题,提出一种贪婪随机自适应灰狼优化算法(GRAGWO)。GRAGWO算法基于贪婪随机自适应搜索算法(GRASP),采用其构造阶段生成初始解,在局部搜索阶段采用灰狼优化算法(GWO)对结果进行优化。GWO算法不能直接用于求解离散问题,易陷入局部最优,导致后期收敛速率较低。根据TSP问题的特性,针对易形成局部最优路径和随着迭代次数增进而导致种群多样性减退这两个缺陷,重新定义灰狼编码方式,与GRASP启发式算法相结合,应用于求解TSP问题。采用TSPLIB中的多组不同规模的TSP问题作为实验用例,并将GRAGWO算法与其他仿生算法进行对比,结果表明在求解准确率、稳定性和解决大型城市问题方面具有相对优势。 相似文献
13.
基于并行遗传算法的弹性TSP研究 总被引:6,自引:0,他引:6
江雷 《微电子学与计算机》2005,22(8):130-133,137
文章针对并行遗传算法求解TSP问题,探讨了使用弹性策略来维持群体的多样性,使得算法跨过局部收敛的障碍,向全局最优解方向进化.通过对算法的分析和实验,尤其是在典型的CHN144 TSP求解上发现了新的最优解这一结果表明,本文算法的改进是有效的. 相似文献
14.
用参数正交选优神经网络算法解货郎问题 总被引:1,自引:1,他引:0
本文发现了货郎问题(TSP)能量函数的参数空间中的吸引域与全局性优化解之间存在着确定的对应关系,并找到了许多参数空间中的吸引域.在此基础上提出了一种新算法——参数正交选优神经网络算法求解TSP,30城市、31城市(中国)和300城市TSP的求解结果都十分满意,表明这种新算法的有效性. 相似文献
15.
一种快速求解TSP问题的遗传算法 总被引:9,自引:1,他引:8
文章受求最短路径算法的启发,提出一个启发算子用于遗传算法求解TSP问题,通过50,144,150等城市的TSP问题求解,表明该算法求解速度快并且解的质量也非常好。 相似文献
16.
本文对于使用遗传算法解答TSP问题进行了研究分析,指出初始种群的选择在具体的问题中不能一概而论,提出一种基于距离矩阵的初始种群选择策略,分析了将其应用于TSP问题的合理性,并通过算例证明这种改进型遗传算法在实际的应用中比简单遗传算法更有效率。 相似文献
17.
TSP问题是一个经典的NP难度的组合优化问题,遗传算法是求解TSP问题的有效方法之一。本文通过分析动态TSP问题的特点,将2-OPT算法、弹性松弛算法和遗传算法结合起来,设计并实现了一种解决动态TSP问题的算法。仿真实验结果表明,该算法有较快的收敛速度,能有效地遏止早熟;无论在静态环境下还是动态环境下都可行、高效。 相似文献
18.
基于遗传算法的TSP问题求解与仿真 总被引:1,自引:0,他引:1
TSP问题常用的自然编码方式在进行遗传操作时,会产生不合法路径.设计了一种新的编码方式,能有效避免这一问题,遗传操作简单易行,无需对不合理的基因片段进行合法化修正.在求解过程中,为了解决遗传算法的收敛速度和全局收敛性之间的矛盾、避免早熟,运用了Doping策略和参数切换方法.最后进行了仿真测试.结果表明,该算法能迅速淘汰劣解,具有较快的收敛速度;能有效遏制早熟,对不同规模的TSP问题能有效求得最优解. 相似文献
19.
Hopfield络求解TSP两种改进算法的仿真研究 总被引:1,自引:0,他引:1
针对Hopfield神经网络在求解旅行商问题(TSP)时出现的无效解和局部极小值问题,分析和比较两种改进的求解方法.首先从理论上证明算法的有效性,然后对两种算法分别进行计算机仿真,探讨网络收敛于全局有效解的途径.研究表明,改进的算法都可避免无效解,在求解10城市问题时可获得近乎100%的最优解. 相似文献
20.
基于改进遗传算法的TSP问题研究 总被引:9,自引:1,他引:9
周涛 《微电子学与计算机》2006,23(10):104-106,110
通过对遗传算法和TSP问题的研究.提出了离散赌轮选择算子EPMX交叉算子和Dmutation变异算子等,对遗传算法的各个算子进行了改进。利用改进的遗传算法有效的解决了TSP问题.实验验证其与传统的解决方式相比有更好的收敛特性,解的准确性更好。 相似文献