基于基因库求解旅行商问题的遗传算法

针对传统遗传算法(genetic algorithm, GA)求解旅行商问题(traveling salesman problem, TSP)存在寻优效率低、实验结果缺乏一致性等问题,提出了一种基于基因库的遗传算法(genetic algorithm based on genes pool, GPGA)。GPGA从种群中搜索减小哈密顿圈长度的边,并当做优良基因构成基因库。父代哈密顿圈在基因库引导下产生更优的子代哈密顿圈,基因库也随着种群的不断进化而同步更新,引导种群个体逐步向最优解靠近。算例结果表明在同样条件下,GPGA比传统遗传算法和几种改进遗传算法的性能更优。     

指针网络改进遗传算法求解旅行商问题

虽然遗传算法相较于其他算法能够更好地求解旅行商问题,但这种算法在使用的过程中容易陷入局部最优的问题,进而导致问题求解遭遇困境。文章在简要介绍旅行商问题的基础上,介绍了遗传算法求解旅行商问题的思路和方法,并明确算法应用中存在的不足。在此基础上提出基于指针网络改进遗传算法求解旅行商问题的新思路,为弥补遗传算法的缺陷提供相应的原理支持。     

遗传算法求解旅行商问题的精英选择策略研究

随着经济的发展,物流配送等路径规划问题的重要性逐渐凸显。旅行商问题作为此类问题的经典之一,具有极高的研究价值。本文使用遗传算法研究这一问题的求解算法,重点聚焦于对于遗传算法中的精英选择策略的研究分析。实验表明,遗传算法是解决此类路径规划问题的有力手段,同时实验结果显示了精英选择策略是遗传算法中的关键环节,在实际应用中需要谨慎选择。     

改进的遗传算法求解旅行商问题

提出一种解决旅行商问题的改进遗传算法.在传统遗传算法的基础上,引入贪婪算法进行种群初始化;从遗传进化代数和个体适应函数值两个方面实现遗传参数自适应调节,在加快寻优速度的同时防止寻优陷入局部最优;采用基于贪婪方法的启发式交叉算子优化交叉结果;对交叉前后的种群分别实施精英个体保留策略,保证最优基因结构得以延续.实验结果分析表明,改进的遗传算法可以在种群规模较小的情况下具有更可靠的寻优能力.     

基于遗传算法的多人旅行商问题求解

旅行商问题是一个经典的XP完全问题,多人旅行商问题的求解则更具挑战性。以往对求解多人旅行商问题的研究局限于以所有成员路径总和最小为优化标准,面对以所有成员路径最大值最小为优化标准的另一类多人旅行商问题却未加注意。文章给出了这两类多人旅行商问题的形式化描述,探讨了利用遗传算法求解这两类多人旅行商问题的基本思想和具体方案,进行了仿真实验验证。仿真实验数据表明,这是一种高效而且适应性强的多人旅行商问题求解方法。     

基于混合杂交的遗传算法求解旅行商问题

通过混合使用多种杂交算子,提出了一种求解旅行商问题的新型遗传算法,并给出了实验验证。通过实验用该算法求解了城市数为50到100不等的旅行商问题,获得了比其它算法更精确或更接近最优的解,表明了算法的有效性。     

使用遗传算法求解旅行商问题

遗传算法模拟自然界动物的繁衍来解决全局寻优问题,。旅行商问题是典型的组合优化问题,而且非常适于演示遗传算法的基本思想。对于遗传算法的优化,国内外许多专家结合旅行商问题提出了很多算子,结合其中的一些经典算子实现应用遗传算法解决旅行商问题的演示程序。     

基于并行遗传算法多旅行商问题的求解

以往求解多旅行商问题的研究仅局限于以各旅行商路程总和最小为优化标准的传统遗传算法,而没有考虑他们的速度和所花时间。在MPI并行环境下,用C++语言实现了粗粒度模型的并行遗传算法。结合并行遗传算法的特点,提出了解决多旅行商问题的策略以及给出相应的算法过程,并进行了有效验证。通过研究结果表明,与传统遗传算法相比,并行遗传算法提高了运算速度,降低了平均开销时间并且最小总路径值更理想。     

基于近邻策略的旅行商问题求解

根据TSP问题的特征信息并借鉴邻域搜索算法的有关思想,提出了一种基于近邻策略的TSP问题求解算法,该算法首先依据TSP问题的特殊性求出相应的近邻模式,再将近邻模式用于初始种群的生成,而后在进化过程中随机引入这类模式。该算法可以大大缩短遗传进程,提高进化效率。通过仿真实验,验证了该算法的有效性,并且随着城市数目的增加其优越性更为明显。     

求解旅行商问题的一个改进的遗传算法

利用遗传算法求解TSP问题,通常需要使用PCX,CX和OX等特殊的交叉算子以提高算法的运行效率。针对自然数编码的方式,提出一种改进的遗传算法,即改进传统的顺序交叉算子,进行不相同子排列顺序交叉,使子代继承父代中优秀的子排列,加快算法的收敛速度。另外,采用没有重复的稳态繁殖避免早熟。实验结果表明,此改进算法对于TSP和DHC问题均具有较好的性能。     

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

针对所有旅行商路径总和最小为优化标准的多旅行商一类问题,用遗传算法优化,并提出了矩阵解码方法。对距离非对称的多旅行商问题的实例进行了仿真,并对不同交叉算子性能进行了比较。结果表明,该算法是有效的,适用于距离对称和非对称的多旅行商问题求解。     

基于递阶遗传算法的多旅行商问题优化*

旅行商问题是一个经典的NP问题,对多人旅行商问题的求解则更具有意义。为了解决所有旅行商路径总和最小为优化标准的多旅行商一类问题,提出了一种递阶遗传算法和矩阵解码方法。该算法根据问题的特点,采用一种递阶编码方案,此编码与多旅行商问题一一对应。用递阶遗传算法优化多旅行商问题无须设计专门的遗传算子,操作简单,并且解码方法适于求解距离对称和距离非对称的多旅行商问题。计算结果表明,递阶遗传算法是有效的,能适用于优化多旅行商问题。     

求解非连通图旅行商问题的改进遗传算法

为了克服传统遗传算法的早熟收敛问题,提出改进遗传算法。采用基于旅行商遍历城市顺序的染色体编码,结合随机法与贪心法生成初始种群,提高遗传效率。通过执行优先保留交叉和平移变异操作,引入局部邻域搜索,给出最优解是否满足非连通约束的判据。最后,实验结果验证了该算法的有效性。     

The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem

Traveling salesman problem (TSP) is proven to be NP-complete in most cases. The genetic algorithm (GA) is improved with two local optimization strategies for it. The first local optimization strategy is the four vertices and three lines inequality, which is applied to the local Hamiltonian paths to generate the shorter Hamiltonian circuits (HC). After the HCs are adjusted with the inequality, the second local optimization strategy is executed to reverse the local Hamiltonian paths with more than 2 vertices, which also generates the shorter HCs. It is necessary that the two optimization strategies coordinate with each other in the optimization process. The two optimization strategies are operated in two structural programs. The time complexity of the first and second local optimization strategies are O(n) and O(n³), respectively. The two optimization strategies are merged into the traditional GA. The computation results show that the hybrid genetic algorithm (HGA) can find the better approximate solutions than the GA does within an acceptable computation time.     

旅行商问题(TSP)的伪并行遗传算法

旅行商问题(TSP)是典型的NP完全组合优化问题．本文基于遗传算法求解TSP问题时的独特性,提出一种采用无性繁殖的改进伪并行遗传算法,避免了交叉算子对良好基因模式的破坏;初始种群通过贪婪算法得到并进行预处理,提高算法的收敛速度;伪并行遗传算法中子群体之间的信息交换采用孤岛模型．这些改进措施对降低算法的复杂程度、提高算法的收敛速度和全局搜索能力有重要意义．仿真研究结果表明,该算法的寻优效率较高,有效地克服了标准遗传算法的早熟收敛问题．     

基于文化混合优化算法的旅行商问题求解

为更好地求解TSP问题,将遗传算法与模拟退火算法结合并纳入文化算法体系,提出一种求解旅行商问题的文化混合优化算法。该算法空间可分为独立并行的两部分：种群空间和信度空间。种群空间按照遗传退火混合算法实现进化,并将进化中的较优个体提供给信度空间,信度空间提取并利用较优个体所包含的信息来引导种群进化。通过求解TSP标准测试问题,将文化混合优化算法所求得的最优路径与其他优化算法所求结果相比,算法偏差均可降低0.6%～13.01%,表明了文化混合优化算法求解TSP问题的有效性与优越性。     

一种求解旅行商问题的热力学演化算法

在综合国内外演化计算研究现状的基础上,基于热力学中的自由能极小化原理,设计了一个全新的热力学演化算法,并通过对于流动旅行商问题求解的数值实验,测试了热力学演化算法的优良性能,实验结果表明了热力学演化算法求出的解比一般演化算法求出的解更加接近于全局最优。