一种用于矩形排样优化的改进遗传算法

矩形排样优化属于NPC问题,在工业界有着广泛的应用,如布料切割、金属下料和新闻组版等。提出了一种基于环形交叉算子和环形变异算子的自适应遗传算法,并将改进的自适应遗传算法和IBL启发式布局算法相结合,有效地解决了矩形排样优化问题。对比实验结果表明,环形交叉算子和环形变异算子对遗传算法是有效的,所提出的改进混合自适应遗传算法能够在一个较短的时间内找到满意解。     

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

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

基于改进遗传算法的带时间窗VRP问题研究

带时间窗约束的VRP问题(VRPTW)属于NP-hard问题,采用改进遗传算法探索最优方案。首先分析了带时间窗VRP问题的一般数学模型,并采用罚函数的方法对时间窗约束进行处理;设计了带权重的适应度函数,并采用了基于基因库的跨世代精英选择算子、PMX交叉算子和局部爬山变异算子;最后通过仿真实验与传统遗传算法和自适应遗传算法进行了对比研究,仿真结果表明改进遗传算法在解决带时间窗VRP问题中具有较高收敛速度和全局搜索能力。     

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

文章首先介绍TSP问题与遗传算法的基本特点及其基本步骤。接着讨论用遗传算法解决TSP问题的编码、适应度函数设计方面的采用的方法,以及选择算子,交叉算子和变异算子的应用现状以及效果,最后对解决TSP问题的前景提出了展望。     

一种结合粒子群优化理论改进的郭涛算法及其应用

郭涛算法是目前求解TSP(traveling salesman problem)问题最为高效的进化算法之一。算法中提出一种求解TSP旅行商问题的高效Inver-over算子,该算子使基因序列以一定概率进行自适应的序列倒置,同时具有遗传算法中的变异算子以及杂交算子的特性。对Inver-over算子进行改进,使粒子编码得到更加充分的序列倒置;并引入粒子群优化算法的思想以加快算法收敛速度,提高了郭涛算法求解效率。将改进后的郭涛算法应用于钢卷自动优化组合堆垛问题,实验验证了改进郭涛算法的有效性。     

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

TSP问题是典型的NP完全问题,遗传算法是求解NP完全问题的一种理想方法。文章针对解决TSP问题,提出使用改进的遗传算法,即用浓度控制选择策略以保证群体的多样性,用贪婪交叉算子和启发式倒位变异算子来提高算法的收敛速度,较好地解决了群体的多样性和收敛速度的矛盾。算法的分析和测试表明,该文算法的改进是有效的。     

基于选择性集成的整数编码遗传算法及TSP问题求解

基于遗传算法的求解TSP(Traveling Salesman Problem)研究是近几年的研究热点.设计高效的遗传算法求解,有重要的理论意义和实用价值.本文考察了基于整数编码的遗传算法的选择算子、交叉算子、变异算子,运用选择性集成的思想,将几种算子集成,随进化的进程对交叉概率和变异概率做自适应调整,用Matlab编写遗传算法程序,求解中国31城市TSP问题,获得了优于目前同类工作的结果.     

用遗传算法求解TSP问题

介绍TSP 问题和遗传算法的基本原理.针对解决TSP 问题,阐述遗传算法在编码表示和遗传操作算子等方面的应用情况,以及该算法在实现过程中的一些处理方法,最后给出该算法的运行结果和总结.     

基于遗传算法的避障TSP问题算法设计

主要探讨复杂环境下避障TSP问题的遗传算法的求解方法.针对TSP问题和避障TSP问题的不同,在染色体的编码方式、有效范围、基因选取、遗传算子等方面对传统遗传算法进行改进,同时引入了代价矩阵和基因库以提高算法的收敛速度.     

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

主要研究了用遗传算法求解TSP问题。阐述了简单遗传算法的设计方法、基本原理和基本步骤。描述了简单遗传算法在TSP问题中的应用现状。根据种群个体的多样性和分布情况,提出了判定遗传算法的截止代数。简单遗传算法具有易于陷入局部最优解、收敛速度慢的特点,针对这些特点,通过改进交叉算子,加入初始化启发信息,提高了遗传算法解的精度和收敛性。     

用于TSP的自适应贪婪GA算法

TSP问题是一个典型的组合优化问题,很多现实生活中的问题都可以归结为TSP问题,GA算法是一种典型的优化算法。通过对GA算法要点的分析,提出了一种自适应贪婪GA算法,以解决TSP问题。自适应适应度函数的各种定义、定理,确保了算法的正确性。通过平均复制的方法进行选择操作,使得算法不会过早地陷入局部最优。通过建立基于哈密顿回路的双向环贪婪插入算子进行交叉操作,确保了算法收敛的高效性。最后通过实例的计算分析及与传统GA算法的比较,说明了所提出的自适应贪婪GA算法在TSP研究中能够更好地发挥作用。     

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

TSP问题是典型的NP-hard组合优化问题,GA是求解此类问题的一种方法。但它存在如何较快地找到最优解并防止“早熟”收敛的问题。文章针对上述问题并结合TSP问题的特点,提出了改进的遗传算法。它从相似性的思想出发,按适应值相似性将群体分级,在不同的级内采用不同的操作,产生数目不等的新解并利用加速算子使其更接近局部极小值。改进后的算法较好地解决了群体多样性与收敛性的矛盾。实验结果表明,该文算法的改进是有效的。     

广义粒子群优化模型

粒子群优化算法提出至今一直未能有效解决的离散及组合优化问题．针对这个问题,文中首先回顾了粒子群优化算法在整数规划问题的应用以及该算法的二进制离散优化模型,并分析了其缺陷．然后,基于传统算法的速度一位移更新操作,在分析粒子群优化机理的基础上提出了广义粒子群优化模型（GPSO）,使其适用于解决离散及组合优化问题．GPSO模型本质仍然符合粒子群优化机理,但是其粒子更新策略既可根据优化问题的特点设计,也可实现与已有方法的融合．该文以旅行商问题（TSP）为例,针对遗传算法（GA）解决该问题的成功经验,使用遗传操作作为GPSO模型中的更新算子,进一步提出基于遗传操作的粒子群优化模型,并以Inverover算子作为模型中具体的遗传操作设计了基于GPSO模型的TSP算法．与采用相同遗传操作的GA比较,基于GPSO模型的算法解的质量与收敛稳定性提高,同时计算费用显著降低．     

求解TSP问题的混合遗传算法

TSP问题是一类经典的NP问题,目前有很多方法对其求解,而用混合遗传算法对其求解取得了很好的成效。常见的混合遗传算法有遗传算法与最速下降法相结合（GACSDM）、遗传算法与模拟退火法相结合（SAGA）。设计了贪婪的复合变异算子（GCM）,并引入隔代爬山法算子（Climb）增加遗传算法的局部搜索能力。实验结果表明该算法是有效的。     

Hybrid immune algorithm based on greedy algorithm and delete-cross operator for solving TSP

This paper first introduces the fundamental principles of immune algorithm (IA), greedy algorithm (GA) and delete-cross operator (DO). Based on these basic algorithms, a hybrid immune algorithm (HIA) is constructed to solve the traveling salesman problem (TSP). HIA employs GA to initialize the routes of TSP and utilizes DO to delete routes of crossover. With dynamic mutation operator (DMO) adopted to improve searching precision, this proposed algorithm can increase the likelihood of global optimum after the hybridization. Experimental results demonstrate that the HIA algorithm is able to yield a better solution than that of other algorithms, which also takes less computation time.     

基于三维编码的自适应遗传算法在排课系统中的应用

将遗传算法应用于排课问题的求解,改进了遗传算法的一般编码方法,综合采用三维编码和自适应的交叉、变异概率设计方法,提出了一套基于三维编码的自适应遗传算法。     

Development a new mutation operator to solve the Traveling Salesman Problem by aid of Genetic Algorithms

In this study, a new mutation operator has been developed to increase Genetic Algorithm (GA) performance to find the shortest distance in the known Traveling Salesman Problem (TSP). We called this method as Greedy Sub Tour Mutation (GSTM). There exist two different greedy search methods and a component that provides a distortion in this new operator. The developed GSTM operator was tested with simple GA mutation operators in 14 different TSP examples selected from TSPLIB. The application of this GSTM operator gives much more effective results regarding to the best and average error values. The GSTM operator used with simple GAs decreases the best error values according to the other mutation operators with the ratio of between 74.24% and 88.32% and average error values between 59.42% and 79.51%.     

Constraint handling in genetic algorithms using a gradient-based repair method

Constraint handling is one of the major concerns when applying genetic algorithms (GAs) to solve constrained optimization problems. This paper proposes to use the gradient information derived from the constraint set to systematically repair infeasible solutions. The proposed repair procedure is embedded into a simple GA as a special operator. Experiments using 11 benchmark problems are presented and compared with the best known solutions reported in the literature. Our results are competitive, if not better, compared to the results reported using the homomorphous mapping method, the stochastic ranking method, and the self-adaptive fitness formulation method.     

求解TSP的混合遗传算法

介绍一种求解TSP的混合遗传算法,该算法结合了基于邻域的LK算法和采用Inver-Over算子的遗传算法,并在算法中增加一些控制策略,加快算法的收敛速度,又保证群体的多样性。实验表明该算法是有效的。