共查询到17条相似文献,搜索用时 62 毫秒
1.
2.
一种解旅行商问题的并行模拟退火算法 总被引:8,自引:0,他引:8
本基于模拟退火思想,提出一种解旅行商问题的并行算法,并在Transputer多处理机系统上实现,该算法具有较高的优化程度和较快的运算速度。 相似文献
3.
旅行商问题(TSP)的一种改进遗传算法 总被引:16,自引:1,他引:16
传统的序号编码遗传算法(GA)使用PMX、CX和OX等特殊的交叉算子,这些算子实施起来很麻烦。针对TSP问题的求解,提出了一种新的改进遗传算法:单亲进化遗传算法(PEGA),PEGA是利用父体所提供的有效边的信息,使用保留最小边的方法进行个体的进化。与传统的遗传算法相比,PEGA算法弥补了它们的不足之处,简化了遗传算法。给出了PEGA算法的数值算例,仿真实验表明了该算法对于对称的TSP和非对称的TSP问题,都具有收敛速度快的特点,证明了该算法的有效性。 相似文献
4.
郭乐新 《电脑与微电子技术》2012,(2):3-5,18
旅行商问题TSP是一类典型的NP完全问题.围绕着这个问题有各种不同的求解方法,已有的算法例如动态规划法、分支限界法、回溯法等,这些精确式方法都是指数级的,根本无法解决目前的实际问题.贪心法是近似方法.无法达到比较满意的近似比。常用的遗传算法也是求解这类问题的常用方法之一。由于该问题的解是一种特殊的序列.所以遗传算法在求解该问题时的性能也并不理想。模拟退火算法具有描述简单、使用灵活、运用广泛、运行效率高和较少受到初始条件约束等优点.是解决旅行商问题的一种很好的算法。 相似文献
5.
通过分析传统模拟退火算法的原理和存在的不足,提出了一个用于求解TSP问题的改进模拟退火算法。新算法增加了记忆当前最好状态的功能以避免遗失当前最优解,并设置双阈值使得在尽量保持最优性的前提下减少计算量。根据TSP和SA的特征设计了个体邻域搜索方法和高效的计算能量增量方法,加快了算法的运行速度。实验测试的结果表明,新算法比传统的模拟退火算法具有更快的收敛速度和更优的解质量。 相似文献
6.
一种改进遗传算法在旅行商(TSP)问题中的应用 总被引:3,自引:0,他引:3
遗传算法(GA)是一种基于自然群体遗传机制的高效搜索算法,由于它在搜索空间中同时考虑许多点。这样就减少了收敛于局极小的可能,同时也增加了处理的并行性。因此,可以利用遗传算法研究典型的组合优化实例-TSP问题的求解问题。本文采用了启发式三交叉算子并提出了一种全新的变异算子,使得收敛速度更快,能更有效的解决TSP问题。 相似文献
7.
本文分析了遗传算法和模拟退火算法的优缺点,提出遗传模拟退火算法的程序设计方法和各项参数的设置,并将该算法应用于TSP问题求解之中,提高了解决问题的能力。 相似文献
8.
根据蚁群算法与模拟退火算法的特性,提出了求解旅行商问题的混合算法.由模拟退火算法生成信息素分布,然后由蚁群算法根据累计更新的信息素找出若干组解,再经过模拟退火算法在邻域内找另外一个解的操作,得到更有效的解.与模拟退火算法、标准遗传算法、蚁群算法和随机初始化的蚁群算法进行比较,4种混合算法效果都比较好,策略D的混合算法效果最好. 相似文献
9.
利用模拟退火算法给出了求解旅行商问题的一种新方法.在模拟退火算法的基本原理基础上,针对解变换只交换两个城市而容易落入局部最优解的缺点,提出了在解变换产生新解的过程中,采用逆转操作的改进方法.这使得迭代过程突破局部最优圈,然后跳到另一个搜索空间.这样能够使其更具多样性,改善了模拟退火算法的局部搜索能力.并将其应用于求解旅行商问题,显著改善了它局部寻优的能力.在几个公共测试数据集上的结果表明,算法稳定可行,在求解组合优化问题方面,具有良好的性能. 相似文献
10.
TSP问题是典型的NP-hard组合优化问题,遗传算法是求解此类问题的一种方法,但它存在如何较快地找到全局最优解,并防止“早熟”收敛的问题。针对上述问题并结合TSP问题的特点,提出将遗传算法与模拟退火算法相结合形成遗传模拟退火算法。为了解决群体的多样性和收敛速度的矛盾,采用了部分近邻法来生成初始种群,生成的初始种群优于随机产生初始种群。仿真实验结果证明,该算法相对于基本遗传算法的收敛速度、搜索质量和最优解输出概率方面有了明显的提高。 相似文献
11.
对模拟退火算法进行了改进,从不同的初始状态开始搜索来解决TSP问题,并将计算的结果与遗传算法的计算结果进行比较,优于文献[1]中遗传算法的结果。 相似文献
12.
Simulated Annealing versus Metropolis for a TSP instance 总被引:1,自引:0,他引:1
Klaus Meer 《Information Processing Letters》2007,104(6):216-219
In a recent paper [I. Wegener, Simulated Annealing beats Metropolis in combinatorial optimization, in: L. Caires, G.F. Italiano, L. Monteiro, C. Palamidessi, M. Yung (Eds.), Proc. ICALP 2005, in: LNCS, vol. 3580, 2005, pp. 589-601] Wegener gave a first natural example of a combinatorial optimization problem where for certain instances a Simulated Annealing algorithm provably performs better than the Metropolis algorithm for any fixed temperature. Wegener's example deals with a special instance of the Minimum Spanning Tree problem. In this short note we show that Wegener's technique as well can be used to prove a similar result for another important problem in combinatorial optimization, namely the Traveling Salesman Problem. The main task is to construct a suitable TSP instance for which SA outperforms MA when using the well known 2-Opt local search heuristic. 相似文献
13.
14.
求解多峰函数问题的模拟退火算法 总被引:2,自引:0,他引:2
论文提出了一种与演化算法群体搜索技术相结合的模拟退火算法(SimulatedAnnealingAlgorithmbasedonIn-dividuals,以下简记为ISA)。与传统的模拟退火算法(SimulatedAnnealing,以下简记为SA)不同的是它由多个个体在搜索空间里同时搜索,个体与个体之间没有信息交换,在遗传算子的作用下每个个体各自朝着适应值高的方向迅速演化,因而只要初始群体是均匀、随机地分布在搜索空间里并且个体数目适当多,算法最终都能找到多峰函数的所有峰值点。 相似文献
15.
16.
武器-目标分配问题的模拟退火算法 总被引:1,自引:0,他引:1
武器-目标分配(WeaponTargetAssignment)问题是一个典型的优化问题,模拟退火算法是求解此问题的一种有效方法。文章采用模拟退火算法对WTA问题进行求解,通过实验得到了理想的仿真结果。 相似文献
17.
TSP问题是一个经典的组合优化问题。本文采用基于凸多边形的插入方法来构造路径,然后使用调整算法对路径进行调整以缩短回路长度,最后采用遗传算法中的交叉算子,再对路径进行优化。实验结果表明,该算法具有较高精度和较强实用性。 相似文献