解决TSP问题的一种改进遗传算法

TSP是一个典型的组合优化问题,也是一个NP难题,其可能的路径总数是随着城市数目n的增长而成几何型增长的,所以一般很难准确地求出其最优解,因而寻找出有效的近似求解算法就成了解决此问题的最佳方法。文章首先介绍了在初始化阶段经行改进的遗传方法。通过把改进方法同标准的遗传算法相比较,得出改进遗传算法在性能上有改进。最后,我们还分析了实验结果并提出了评价初始解优劣的一个指标函数——局部相似度函数,并给出了函数的具体表达式。     

一种改进的求解TSP问题的遗传算法

TSP问题是典型的NP难组合优化问题,而遗传算法是求解此类问题的一种方法。但遗传算法存在收敛速度慢和陷入局部最优的问题。针对上述问题并结合TSP的特点提出了一种改进的遗传算法,对传统遗传算法的各种操作与算子进行了优化与改进,较好地解决了种群多样性与算法收敛性的矛盾。实验结果表明,改进后的算法明显优于传统遗传算法,说明该算法具有良好的有效性与可行性。     

蚁群算法及其在TSP中的应用

根据蚂蚁生态学提出的蚁群算法是一种新颖的用于求解复杂组合优化问题的模拟进化算法,具有典型的群体智能特征,表现出较强的学习能力和适应能力。阐述了该算法的基本原理、算法模型和在旅行商问题中的具体应用过程,并对算法进行了总结和展望。     

浅谈图论中两个重要的通路

图论是一门应用广泛和内容丰富的数学分支,其应用渗透到各大领域,例如:物理、化学、信息和运筹学等.本文重点介绍"Euler通路"和"Hamilton回路"的联系和区别,以及如何判断"Euler环游"和"Hamilton"回路.     

旅行售货员问题(TSP)的模拟退火算法

旅行售货员问题(Traveling salesman problem)是计算机算法中的一个经典的难解问题,已被证明是一个NP-C(Nondeterministic Polynomial-Completeness)问题,其计算复杂度O(n!),无法找到一个多项式算法解决此类问题。本文利用最优化理论中的模拟退火法,简述了TSP问题的近似算法。     

改进遗传算法在TSP问题中的应用

旅行商问题是典型的NP组合优化问题。提出一种旅行商问题求解应用上的改进遗传算法。引入贪心算法优化初始种群,在轮盘赌选择基础上,融入最优保存策略和掺杂算子进行选择操作,以保证群体的多样性;基于两点三段随机交叉算子优化交叉结果,基于启发式倒位变异算子提高算法的收敛速度;给出了求解旅行商问题系统的体系结构。实验结果表明,改进的遗传算法具有更好的寻优能力。     

蚁群算法在TSP问题中的应用及其优化研究

蚁群算法是一种新型的模拟进化算法。分析了蚁群算法的基本模型和算法在TSP问题中的实现方式,针对其缺陷对基本的蚁群算法进行了一定的改进。     

基于并行模拟退火算法的TSP问题求解

针对标准模拟退火算法串行优化单个解，优化过程较长、效率较低的弱点，提出一种基于多种群群体优化的并行机制。该机制通过将单个解的串行优化转化为许多个解同时进行的并行优化来提高算法的整体优化效率。利用该算法求解TSP问题能够显著提高优化效率，仿真结果表明该算法是有效的。     

多种群自适应模拟退火遗传算法求解TSP问题

TSP问题是一个具有广泛应用背景和重要理论价值的组合优化NP难题。遗传算法是求解NP完全问题的一种方法。针对传统遗传算法求解TSP问题的不足,提出了一种多种群自适应模拟退火遗传算法,并给出了多种群分级、混合变异算子的设计。最后,对CHN31、ATT48和EIL51的TSP问题进行求解．仿真结果表明该改进遗传算法具有更好的收敛性,可以得到更好的最优解。     

几种解决TSP问题的蚁群算法的性能研究

文章对解决TSP问题的几种蚁群算法模型的性能进行了比较,得出了蚁群算法中参数如何对性能产生影响的分析报告．     

回溯算法求解TSP问题的改进

回溯法构成的解空间树中存在着大量的重复解,降低了搜索的效率．该文在阐述回溯算法基本思想的基础上,运用解路径反转。找出其重复解,然后从解空间树中将其删除的方法对四溯算法加以改进,改进后的算法空间复杂度只有O（n）,并省掉了重复路径的权值计算,节省了搜索时间,提高了搜索效率．     

基于遗传算法的旅行商问题的研究

巡回旅行商问题(TSP)是一个组合优化方面的问题,已经成为测试组合优化新算法的标准问题。应用遗传算法解决TSP问题,首先对访问城市序列进行排列组合的方法编码,这保证了每个城市经过且只经过一次。接着生成初始种群,并计算适应度函数,即计算遍历所有城市的距离。然后用最优保存法确定选择算子,以保证优秀个体直接复制到下一代。采用有序交叉和倒置变异法确定交叉算子和变异算子。最后用MATLAB来实现算法,仿真后,观察路径,得出最终结果。     

基于免疫单亲遗传算法在TSP中的应用

基本遗传算法保持群体多样性的能力较差,所以经常在问题求解的过程中极易陷入局部最优解。根据生物的免疫原理和单亲遗传算法并结合最近邻域算法思想提出的一种改进算法———基于免疫单亲遗传算法（IPGA）。免疫遗传算法中的基因重组、免疫记忆以及免疫元动态等特性,这些特性有助于改进基本遗传算法群体多样性的保持能力。最后结合48个城市旅行商问题进行了求解,仿真结果表明,基于免疫单亲遗传算法具有更好的性能,相对于传统的遗传算法收敛速度提高了30%。     

对货郎问题计算复杂性的研究

讨论了货郎问题的计算复杂性,指出了货郎优化问题与货郎判定问题计算复杂性的差异.     

瓶颈旅行售货员问题算法

旅行售货员问题是一个著名的组合优化问题,已经被证明是NP-完备问题。提出一个新问题:瓶颈旅行售货员问题,并给出两个多项式时间算法。     

新常态背景下农民工城市融入的现实困境与对策思考

农民工离开乡村到城市求职,表面看是个体空间位置的变化,实质上却是生产生活方式的变更,以及个体关系网络、文化构成和精神世界的巨变。新常态下,中国经济结构不断优化,经济增速放缓给农民工就业转移带来压力,立足实际应对农民工在劳动就业、工资收入、技能提升、安居乐业等方面面临的新挑战,亟须从组织、服务、培训、维权等方面改善农民工就业环境,解除农民工发展的后顾之忧。     

论新课程背景下高师语文教学法课程改革新路径

基础课程改革已启动十几年,高师院校在语文教学法课程方面也进行了诸多改革与研究,取得一定的成绩,但仍还存在诸多问题。革新教学体系,优化课程组合;采用多样化的教学方式,优化课堂教学,是新课程背景下高师语文教学法课程改革的新举措。