一种改进的TSP启发交叉算子

旅行商问题（TSP,Traveling Salesman Problem）是一种经典的NP组合优化问题。遗传算法在求解这类组合问题方面明显优于传统算法,同时也提出了许多求解较好路径的交叉算子。在对比分析唐立新提出的两种启发式交叉算法的基础上,提出了一种新的交叉算子。该算子通过判断父代的城市是否相邻来保存有效基因片断,通过加入一个移动的窗口来加快算法收敛。实验结果表明了该算子的有效性。     

求解旅行商问题的探索—开发—跳跃策略单亲遗传算法

针对遗传算法求解旅行商问题(TSP)时容易早熟、收敛速度慢等问题,提出一种基于探索—开发—跳跃策略的单亲遗传算法(EDJS-PGA)。该算法将基因移位、倒序、交换三种算子组合构成探索策略,用于扩展解的搜索空间,增强算法全局搜索能力;再将logistic混沌映射和改良圈操作融合为一种混沌映射改良圈算子,用于增强算法的局部搜索能力,构成开发策略;最后针对种群中的同优个体设计了近邻变异算子,构成跳跃策略,增强了算法跳出局部最优解的能力,使其兼具个体变异、局部优化、防止早熟等多重作用。通过对18个TSP实例进行仿真实验,结果表明EDJS-PGA相较于传统单亲遗传算法具有更高的求解精度和收敛速度,且最优解偏差率和平均误差率均处于较低水平;与其他文献对比,EDJS-PGA具有更强的鲁棒性和求解效率。     

一种改进的求解旅行商问题的单亲遗传算法

单亲遗传算法具有操作简单、收敛较快等优点,因此被用于求解各种组合优化问题。针对旅行商问题,在早期单亲遗传算法的基础上引入了基因段贪心替换、基于相似度的家族竞争等一些控制策略,提出了一种新型、高效的单亲遗传算法。实验表明,该算法不仅能够保留收敛较快等优点,而且具备了比现有的单亲遗传算法以及改进的GT算法更强的全局寻优能力。     

带冲突图的着色旅行商问题模型与算法

着色旅行商问题是多旅行商问题的一个重要变种，它被广泛地应用于带有重叠区域的多机工程系统。现有的着色旅行商问题难以有效应对带冲突的场景，这种冲突通常表现为两个城市不允许被同一旅行商访问。受带冲突图的组合优化问题的启发，提出了带冲突图的着色旅行商问题，且给出了其形式化的表达。带冲突图的着色旅行商问题是一个NP难问题，精确算法求解器CPLEX仅能在小规模问题实例上获得问题的最优解。为了求解更大规模的实例，提出了一个有效的模因算法。该模因算法采用了自适应大规模邻域搜索算子。对比模因算法和精确算法，模因算法在20个小规模实例中的9个结果更好，在18个实例上展现了其远超精确算法的求解速度。而比较模因算法和其他启发式算法，模因算法在全部14个中等规模实例上均取得了更好结果。此外，消融实验结果验证了模因算法中自适应大规模领域搜索算子的有效性。     

求解工作量平衡多旅行商问题的改进遗传算法

针对工作量平衡的多旅行商问题,提出了一种融合杂草算法繁殖机制和局部优化变异算子的改进遗传算法（Reproductive mechanism and Local optimization mutation operator based Genetic Algorithm,RLGA）。该算法利用入侵杂草优化算法中以适应度为基准的繁殖机制来产生种群并进行遗传操作,以此来提高算法的搜索效率;同时提出一种混合局部优化算子作为变异算子来提高算法的局部搜索能力,从而提高收敛精度。实验结果表明,RLGA在求解工作量平衡的多旅行商问题时可以快速收敛到较优解,并且求解精度得到了很大的提高。     

一种基于基因库求解TSP的单亲遗传算法

研究商品流通路线问题,TSP是组合优化问题的典型代表。针对TSP问题提出了一种改进的遗传算法。以引入＂基因库＂为基础,为了寻找出最优路径,提出一种只使用变异算子和选择算子繁殖后代的单亲遗传算法（PGA）,并设计了一种新的组合算子作为算法的主搜索算子。算法利用基因库指导单亲遗传演化的进化方向,利用设计的组合算子来增强算法的搜索能力,从而很好地仿真了自然界的进化过程。计算结果证明,基因库的PGA算法具有较高的求解质量和求解效率,尤其是在求解Lin318 TSP问题时获得了优于目前最好解最短路径,可为设计提供有效的参考。     

一种求解旅行商问题的新型单亲遗传算法

论文针对旅行商问题,提出了一种新型的单亲遗传算法。它在同一条染色体上采用基因换位、基因段移位、基因段逆转和基因分组定界等操作进行基因重组,取消了传统遗传算法中的交叉算子,遗传操作简单,收敛速度快。但过早的收敛将影响结果精度,使全局最优解的出现机率很小。为此,该算法模拟自然界演化的周期性,使用基因插入操作增强算法的搜索能力,并提出运算终止的两个准则,使所得的解为全局最优解的可信度大为提高。给出了该算法的数值算例,实验结果表明,该算法较好地解决了收敛速度和寻优能力的矛盾,证明了该算法的有效性。     

带固定半径近邻搜索3-opt的离散烟花算法求解旅行商问题

传统烟花算法求解大规模离散问题存在收敛速度慢、求解精度不高等问题.针对旅行商问题的特点,提出一种带固定半径近邻搜索3-opt的离散烟花算法.该算法基于基本烟花算法进行离散化改进,采用整数编码的路径表示方法来表示旅行商问题的解,对爆炸算子、高斯变异算子进行离散化操作策略设计.为了使算法具有较好的局部搜索能力,提出固定半径近邻搜索3-opt策略来提高算法精度和收敛速度,同时采用不检测标志策略提高算法效率.实验结果表明:该算法能有效地求解旅行商问题,其离散烟花算子在全局收敛能力、收敛精度、求解时间和稳定性等方面均优于传统烟花算子;基准测试算例的最优解平均误差率仅为0.002％,优于对比算法.     

求解最小比率旅行商问题的离散蝙蝠算法

研究了以总路程与总收益之比为目标函数的最小比率旅行商问题,提出了求解该问题的离散蝙蝠算法。介绍了蝙蝠算法的基本思想,重新定义了位置与位置的减法操作算子、实数与位置的乘法操作算子以及速度与位置的加法操作算子,引入了城市子序列逆序策略来对线路进行局部搜索。给出了算法的具体实现方案,并通过仿真和比较实验验证算法的优化性能,实验结果表明该算法可以有效求解最小比率旅行商问题。     

求解旅行商问题的位置一次序编码差分演化算法

首先利用“差异算子”和“选择算子”描述了差分演化算法（DE）的基本原理，然后提出了一种新的、通用的特殊编码方法：位置-次序编码法，并利用此编码方法，提出了求解著名旅行商问题的离散差分演化算法：基于位置-次序编码的差分演化算法（PODE）。对于TSPLIB中两个不同规模的旅行商问题实例的计算表明，PODE算法具有极好的收敛性和稳定性。     

用一种含启发式变异策略的遗传算法求解TSP

通过分析TSP问题的特征,结合以减少周游路线中交叉边为启发式信息,引入了一个遗传算法中新的变异策略用于TSP求解。对新策略的有效性进行了证明并且给出了具体的实现方案,同时通过TSP Lib上的测试样例将该启发式变异算子和另外两个传统的变异算子(插入式变异和交换式变异)进行了比较。比较结果表明了新变异策略具有更大的优势。     

一种求解TSP问题的新算法

为了求解TSP问题,提出了一种新的遗传算法。它利用距离密集度和适应度定义了自适应的交叉和变异概率,采用改进的交换启发交叉算子,产生不差于父代的个体。根据最优和次优个体的差异,采用2变换法产生新个体或者进行模拟退火操作,局部搜索加快了算法向最优个体靠近的速度。仿真实验表明新算法是一种求解TSP问题的有效方法。     

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

通过改进经典遗传算法的交叉算子和变异算子,提出了一种改进遗传算法。介绍了该算法的基本步骤及特点,并对TSP问题进行了仿真实验。实验结果表明改进算法有效地提高了算法的收敛速度与寻优质量,在解决TSP问题时表现出良好特性,与经典遗传算法相比具有明显优势。     

带有单亲遗传特征的蚁群算法

蚁群算法是一种新型的模拟进化算法,具有许多优良的性质,但同时也存在着计算时间过长和易导致早熟收敛等缺点.单亲遗传算法不使用基本遗传算法常用的交叉算子,简化了遗传操作过程,且不要求初始群体具有广泛多样性,计算速度较快,不存在早熟收敛现象.将这两种算法结合,提出一种具有单亲遗传特征的蚁群算法.将蚁群算法每次搜索结果作为初始种群,进行单亲遗传优化改良,求得最短路由.在旅行商问题上的实验证明了该算法的有效性.     

旅行商问题的一种插入交叉算子

求解TSP问题是遗传算法应用的一个重要领域,其本质是TSP问题中巡回路径编码串的组合最优化问题。对于符号编码方式的遗传算法,通常需要设计特定的交叉算子以提高算法的运行效率和性能。该文针对自然数编码的方式,提出了一种较适合于大规模TSP问题求解的遗传交叉算子:插入交叉(InsertCrossover,简称IX)算子。该算子以优良的交叉策略,保证了算法的快速收敛和全局寻优。仿真实验结果证明,IX算子对于大规模TSP问题具有比较好的性能。     

Memetic Algorithm based on Improved Inver-over operator and Lin-Kernighan local search for the Euclidean traveling salesman problem

In this study, an Improved Inver-over operator is proposed to solve the Euclidean traveling salesman problem (TSP) problem. The Improved Inver-over operator is tested on 14 different TSP examples selected from TSPLIB. The application of the Improved Inver-over operator gives much more effective results regarding to the best and average error values than the Basic Inver-over operator. Then an effective Memetic Algorithm based on Improved Inver-over operator and Lin-Kernighan local search is implemented. To speed up the convergence capability of the presented algorithm, a restart technique is employed. We evaluate the proposed algorithm based on standard TSP test problems and show that the proposed algorithm performs better than other Memetic Algorithm in terms of solution quality and computational effort.     

基于交换-单亲遗传算法的砂岩三维显微图像重建

根据二维显微图像中孔隙的统计特征,重建具有相同特征的三维孔隙结构具有重要意义.本文提出用交换算子产生子代个体,替代传统单亲遗传算法中倒位算子、移位算子和突变算子,构建交换-单亲遗传算法.和传统单亲遗传算法相比,该算法能快速更新子代个体的适应值,算法复杂度大大降低.实验结果表明,与常用的模拟退火重建算法相比,交换-单亲遗传算法能有效加快个体能量下降速度,重建结果的统计特征与二维图像更相符,更适合应用于三维重建问题.     

求解标准化组卷问题的单亲遗传算法

组卷问题是一个多重约束目标的问题求解。为此,我们设计了一个求解标准化组卷问题的单亲遗传算法,提出了独立编码和针对该编码的组内单亲交叉算子、组内变异算子,引入小生境技术。通过实际使用,较好地解决了一次产生多套满足需要的标准化试卷的实际需要。     

应用改进的遗传算法求解TSP问题

旅行商问题,也称货郎担问题,属于完全NP问题,而遗传算法在解决组合排列问题方面占有很重要的地位.针对TSP问题,提出了一种改进的遗传算法.利用交换启发交叉算子和可变交叉概率实现局部搜索,加快算法的收敛速度,利用变换变异算子和可变变异概率维持群体的多样性防止算法早熟收敛.Java仿真实验结果表明,改进后的算法明显优于传统的遗传算法,说明该算法具有良好的有效性和可行性.