Appropriate Combination of Crossover Operator and Mutation Operator in Genetic Algorithms for the Travelling Salesman Problem

Genetic algorithms(GAs)are very good metaheuristic algorithms that are suitable for solving NP-hard combinatorial optimization problems.AsimpleGAbeginswith a set of solutions represented by a population of chromosomes and then uses the idea of survival of the fittest in the selection process to select some fitter chromosomes.It uses a crossover operator to create better offspring chromosomes and thus,converges the population.Also,it uses a mutation operator to explore the unexplored areas by the crossover operator,and thus,diversifies the GA search space.A combination of crossover and mutation operators makes the GA search strong enough to reach the optimal solution.However,appropriate selection and combination of crossover operator and mutation operator can lead to a very good GA for solving an optimization problem.In this present paper,we aim to study the benchmark traveling salesman problem(TSP).We developed several genetic algorithms using seven crossover operators and six mutation operators for the TSP and then compared them to some benchmark TSPLIB instances.The experimental studies show the effectiveness of the combination of a comprehensive sequential constructive crossover operator and insertion mutation operator for the problem.The GA using the comprehensive sequential constructive crossover with insertion mutation could find average solutions whose average percentage of excesses from the best-known solutions are between 0.22 and 14.94 for our experimented problem instances.

Solving the Generalized Traveling Salesman Problem Using Sequential Constructive Crossover Operator in Genetic Algorithm

The generalized travelling salesman problem(GTSP),a generalization of the well-known travelling salesman problem(TSP),is considered for our study.Since the GTSP is NP-hard and very complex,finding exact solutions is highly expensive,we will develop genetic algorithms(GAs)to obtain heuristic solutions to the problem.In GAs,as the crossover is a very important process,the crossovermethods proposed for the traditional TSP could be adapted for the GTSP.The sequential constructive crossover(SCX)and three other operators are adapted to use in GAs to solve the GTSP.The effectiveness of GA using SCX is verified on some GTSP Library(GTSPLIB)instances first and then compared against GAs using the other crossover methods.The computational results show the success of the GA using SCX for this problem.Our proposed GA using SCX,and swap mutation could find average solutions whose average percentage of excesses fromthe best-known solutions is between 0.00 and 14.07 for our investigated instances.

Genetic Crossover Operators for the Capacitated Vehicle Routing Problem

We study the capacitated vehicle routing problem(CVRP)which is a well-known NP-hard combinatorial optimization problem(COP).The aim of the problem is to serve different customers by a convoy of vehicles starting from a depot so that sum of the routing costs under their capacity constraints is minimized.Since the problem is very complicated,solving the problem using exact methods is almost impossible.So,one has to go for the heuristic/metaheuristic methods and genetic algorithm(GA)is broadly applied metaheuristic method to obtain near optimal solution to such COPs.So,this paper studies GAs to find solution to the problem.Generally,to solve a COP,GAs start with a chromosome set named initial population,and then mainly three operators-selection,crossover andmutation,are applied.Among these three operators,crossover is very crucial in designing and implementing GAs,and hence,numerous crossover operators were developed and applied to different COPs.There are two major kinds of crossover operators-blind crossovers and distance-based crossovers.We intend to compare the performance of four blind crossover and four distance-based crossover operators to test the suitability of the operators to solve the CVRP.These operators were originally proposed for the standard travelling salesman problem(TSP).First,these eight crossovers are illustrated using same parent chromosomes for building offspring(s).Then eight GAs using these eight crossover operators without any mutation operator and another eight GAs using these eight crossover operators with a mutation operator are developed.These GAs are experimented on some benchmark asymmetric and symmetric instances of numerous sizes and various number of vehicles.Our study revealed that the distance-based crossovers are much superior to the blind crossovers.Further,we observed that the sequential constructive crossover with and without mutation operator is the best one for theCVRP.This estimation is validated by Student’s t-test at 95%confidence level.We further determined a comparative rank of the eight crossovers for the CVRP.

An Improved Genetic Algorithm with Quasi-Gradient Crossover

The convergence of genetic algorithm is mainly determined by its core operation crossover operation. When the objective function is a multiple hump function, traditional genetic algorithms are easily trapped into local optimum, which is called premature conver- gence. In this paper, we propose a new genetic algorithm with improved arithmetic crossover operation based on gradient method. This crossover operation can generate offspring along quasi-gradient direction which is the Steepest descent direction of the value of objective function. The selection operator is also simplified, every individual in the population is given an opportunity to get evolution to avoid complicated selection algorithm. The adaptive mutation operator and the elitist strategy are also applied in this algorithm. The case 4 indicates this algorithm can faster converge to the global optimum and is more stable than the conventional genetic algorithms.

基于Petri网和改进遗传算法的多资源调度问题

针对混流装配线工序加工资源需求多样、工艺复杂、装配工期长等问题,采用Petri网和改进遗传算法对该问题进行优化求解。建立混流装配线赋时库所Petri网(timed place Petri net, TPPN)调度模型,基于模型激发序列,采用基于工序的编码方式进行染色体编码;采用精英保留策略选择优异个体,改进遗传算法的交叉、变异操作,用改进后的遗传算法求解混流装配线调度问题。通过对比案例及实例数据计算结果验证了方案的有效性。

一种改进的自适应遗传算法

针对现有遗传算法在求解多参数问题时出现收敛精度低、收敛速度慢、易陷入局部最优等问题,提出一种改进的自适应遗传算法。该算法引入复制算子、种群密集度函数和精英选择策略,提出根据种群迭代次数和个体适应度的自适应策略调节交叉概率和变异概率,很好地平衡了遗传算法的全局搜索能力和局部寻优能力。总结出具有代表意义的测试函数,通过求解测试函数和旅行商问题,证明改进的自适应遗传算法的收敛精度、收敛速度等均有明显的提高。

基于主成分分析的DBSCAN分类差分进化算法改进

差分进化算法(DE)是一类基于种群搜索最优解的全局优化算法,具有收敛速度快、算法简单易懂、参数数量少和稳定性高等特点。但DE算法的性能在很大程度上取决于参数值的设置、个体突变的方向和距离。考虑到不同的种群密度对参数的需求不同,采用主成分分析技术将30或50维的数据降到2维;再采用DBSCAN算法,依据邻域半径和最小邻域数将2维数据分类为簇,通过簇的数量判断种群整体密度和个体之间的差异度,并在不同取值范围内生成合适的变异因子和交叉因子,以此来满足不同种群的进化需求。通过基准函数测试集和多个检验方法验证,证明了所提方法的寻优能力和鲁棒性均优于另外5种先进算法。

基于改进遗传算法的柔性作业车间调度研究

针对柔性作业车间的多目标调度问题,文章建立以最大完工时间、能耗为目标的数学模型,提出一种多目标的改进遗传算法的求解方法。首先,在交叉算子中使用均匀交叉法,采用了基于邻域的变异算子。其次,针对交叉变异算子进行了非均匀改进,旨在增加算法搜索能力。通过动态调整非均匀交叉和非均匀变异的概率,提高搜索空间覆盖率,避免陷入局部最优解。最后,采用基准算例Kacem测试集进行测试。实验证明,该改进算法有效地解决了同时考虑最大完工时间和能耗的多目标调度问题,取得了显著的改善效果。

Recombination and repeat-induced point mutation landscapes reveal trade-offs between the sexual and asexual cycles of Magnaporthe oryzae

The fungal disease caused by Magnaporthe oryzae is one of the most devastating diseases that endanger many crops worldwide.Evidence shows that sexual reproduction can be advantageous for fungal diseases as hybridization facilitates host-jumping.However,the pervasive clonal lineages of M.oryzae observed in natural fields contradict this expectation.A better understanding of the roles of recombination and the fungi-specific repeat-induced point mutation(RIP)in shaping its evolutionary trajectory is essential to bridge this knowledge gap.Here we systematically investigate the RIP and recombination landscapes in M.oryzae using a whole genome sequencing data from 252 population samples and 92 cross progenies.Our data reveal that the RIP can robustly capture the population history of M.oryzae,and we provide accurate estimations of the recombination and RIP rates across different M.oryzae clades.Significantly,our results highlight a parent-of-origin bias in both recombination and RIP rates,tightly associating with their sexual potential and variations of effector proteins.This bias suggests a critical trade-off between generating novel allelic combinations in the sexual cycle to facilitate host-jumping and stimulating transposon-associated diversification of effectors in the asexual cycle to facilitate host coevolution.These findings provide unique insights into understanding the evolution of blast fungus.

SFGA-CPA: A Novel Screening Correlation Power Analysis Framework Based on Genetic Algorithm

Correlation power analysis(CPA)combined with genetic algorithms(GA)now achieves greater attack efficiency and can recover all subkeys simultaneously.However,two issues in GA-based CPA still need to be addressed:key degeneration and slow evolution within populations.These challenges significantly hinder key recovery efforts.This paper proposes a screening correlation power analysis framework combined with a genetic algorithm,named SFGA-CPA,to address these issues.SFGA-CPA introduces three operations designed to exploit CPA characteris-tics:propagative operation,constrained crossover,and constrained mutation.Firstly,the propagative operation accelerates population evolution by maximizing the number of correct bytes in each individual.Secondly,the constrained crossover and mutation operations effectively address key degeneration by preventing the compromise of correct bytes.Finally,an intelligent search method is proposed to identify optimal parameters,further improving attack efficiency.Experiments were conducted on both simulated environments and real power traces collected from the SAKURA-G platform.In the case of simulation,SFGA-CPA reduces the number of traces by 27.3%and 60%compared to CPA based on multiple screening methods(MS-CPA)and CPA based on simple GA method(SGA-CPA)when the success rate reaches 90%.Moreover,real experimental results on the SAKURA-G platform demonstrate that our approach outperforms other methods.

基于改进遗传算法优化BP网络的密度预测

为了能利用工艺参数实时预测药柱密度并提高密度预测精度,提出采用改进遗传算法优化BP网络(improved genetic algorithm backpropagation neural network,IGA-BPNN)的炸药密度预测模型。通过动态调整GA的交叉概率和变异概率,确定BPNN权重和阈值的最优值,构建IGA-BP预测模型,利用采集的工艺参数,基于所构建模型进行炸药密度预测。实验结果表明:改进的GA对交叉率和变异率做出了更好的调整,能快速搜寻BPNN的最优权重和阈值,提高炸药压制密度的预测精度。

基于遗传算法的智能排课系统的设计

为解决教学资源利用率低、排课效率低、冲突率高的问题,采用遗传算法设计智能排课系统。在对排课原则分析基础之上构建排课约束条件,采用十进制对课程进行编码,构建智能排课求解优化模型。优化模型求解采用改进遗传算法,具体改进方法为蒙特卡洛概率接受法改进选择操作,交叉与变异概率采用自适应交叉与变异。结果表明,相对传统遗传算法,改进遗传算法对课程的排课效率大大提升,排课方案更合理。

锚杆钻车钻臂定位控制方法

目前常用代数法和几何法实现锚杆钻车钻臂定位控制,存在效率低、有无解或多解情况、通用性差等问题。采用粒子群优化(PSO)算法进行机械臂定位控制具有编程简单、搜索性能强、容错性好等优势,但易陷入局部最优解。目前基于改进PSO算法的机械臂定位控制整体寻优效率较低,寻优时间过长。针对上述问题,在精英反向粒子群优化(EOPSO)算法基础上,引入混沌初始化、交叉操作、变异操作和极值扰动,设计了混沌交叉精英变异反向粒子群优化(CEMOPSO)算法。采用标准测试函数对PSO算法、EOPSO算法、交叉精英反向粒子群优化(CEOPSO)算法、CEMOPSO算法进行测试,结果表明CEMOPSO算法的稳定性、精度、收敛速度最优。建立了锚杆钻车钻臂运动模型,采用CEMOPSO算法进行钻臂定位控制,并在Matlab软件中对控制性能进行仿真研究,结果表明:在相同的迭代次数和误差精度约束条件下,采用CEMOPSO算法时钻臂位置误差和姿态误差从迭代初期即具有极快的收敛速度,且位置误差和姿态误差均小于其他3种算法,误差曲线较平稳,最大位置误差为0.005 m,最大姿态误差为0.005 rad;设定位置误差为1 mm、姿态误差为0.01 rad时,CEMOPSO算法的平均迭代次数为343,位置误差为0.1 mm、姿态误差为0.001 rad时平均迭代次数为473,在相同的定位精度条件下,CEMOPSO算法的收敛速度和稳定性优于其他3种算法,满足工程应用要求,且求解精度越高,其优越性越突出。

改进多目标鲸鱼优化算法的武器目标分配研究

针对武器目标分配问题中存在求解精度低的问题,提出一种改进多目标鲸鱼优化算法(CMMWOA)的武器目标分配方法。通过分别计算鲸鱼个体的非支配等级和拥挤度大小,对鲸鱼种群进行排序,并在父代和子代个体中筛选出优秀个体组成下一代鲸鱼个体,同时加入交叉和变异机制,增加鲸鱼种群间多样性。仿真结果表明,CMMWOA在5个多目标测试函数中,具有更好的寻优能力,在武器目标分配模型中,CMMWOA与其他算法那相比,在相同的条件下得到的目标分配的打击效果也是最大,验证了CMMWOA的有效性。

改进混合萤火虫算法求解CVRP

提出一种改进混合萤火虫算法(KM-HFA)来解决带容量约束的车辆路径问题。该算法利用K-Means聚类方法将客户集先进行分类,再构建初始解,以较好的初始解开始萤火虫算法的寻优过程,减少了算法的计算量。在萤火虫算法中引入部分匹配交叉算子,2H-opt交换算子,局部搜索算子和变异算子,这些方法加快了算法的收敛速度,提高了萤火虫算法跳出局部最优的能力。选取小规模及中规模数据集进行仿真实验,共94组标准算例。对于79组实例,KM-HFA得到的解优于对照的混合萤火虫算法和CC-CVRP所得的求解方案,KM-HFA所求方案的车辆行驶总距离更小。KM-HFA计算了5组小规模实例,即A-n33-k6,A-n37-k6,P-n16-k8,P-n19-k2和P-n20-k2,在不增加车辆配送路径数目的情况下,得到比经典解更好的配送方案。对于实例P-n22-k8和P-n23-k8,文中算法在比经典解路径数增加了一条的前提下,找到了车辆行驶总距离更小的解。仿真实验结果表明KM-HFA具有较好的稳定性和有效性。

双曲正切高斯与两阶段反向学习平衡优化算法

针对平衡优化算法易陷入局部最优以及收敛速度慢等缺点,提出双曲正切高斯与两阶段反向学习平衡优化算法.首先,将双曲正切函数与黄金分割系数融入高斯分布动态调整算法的全局搜索能力,提高算法寻优精度;其次,为了缓解迭代中种群多样性减少,对种群个体执行遗传算法中交叉和变异操作,使种群最大程度上避免多样性减少;然后,通过两阶段反向学习,种群个体能够通过一般反向学习或随机反向学习增强算法逃离局部最优的能力和加快算法收敛的速度;最后,使用12个基准测试函数、CEC2014函数集、Wilcoxon秩和检验及Friedman秩检验测试改进算法的综合性能,并与其他改进群智能算法进行对比,实验结果表明改进算法优势明显.

自适应多目标遗传算法的集成剪枝用于人脸表情识别

在集成剪枝中,为了同时高效地选择优质、独立的分类器,文中提出了一种新的动态自适应交叉策略的遗传算法用于分类器的集成剪枝。该方法使用轮盘赌和贪婪策略动态更新每个交叉策略的优先级,根据优先级计算每个策略被选中的概率,从而在算法迭代过程中自适应选择不同的交叉策略。此外,该方法考虑了交叉概率和变异概率动态自适应变化,并使用大多数投票法对挑选出来的分类器进行集成以获得最终结果。将文中所提方法与一些集成剪枝方法在5个真实人脸表情数据集上进行对比,实验结果表明文中所提该方法可以选出效果更好、冗余度更低的分类器,并在CK+数据集上具有22.50%的最低误差。

基于改进粒子群算法的儿童防护系统优化

为保障儿童乘车安全,采用改进多目标粒子群算法优化儿童约束防护系统。首先,开展40%偏置碰撞的台车试验,验证儿童座椅台车试验仿真模型的有效性,建立儿童安全气囊模型;然后,建立防护系统参数与儿童头部、胸部损伤指标的二阶响应曲面模型,融合遗传算法的交叉变异和精英保留策略,提出改进的多目标粒子群算法,并验证改进算法的有效性;最后,利用多目标模糊优选决策算法获得系统设计参数的最优值,结合台车试验仿真模型,验证优化模型及算法的有效性。结果表明:模型的最优值兼顾对儿童头部和胸部的防护;遗传算法和粒子群算法的融合算法,可提高模型的收敛速度。

基于DE算法的改进ACO算法求解旅行商问题

以旅行商问题(TSP)为研究对象,提出一种基于差分(DE)算法的改进蚁群算法(ACO&DE)。ACO算法具有快速构造机制,DE算法可以扩展ACO算法的搜索范围,避免蚁群算法陷入局部最优。为了使DE算法适合求解离散TSP问题,对变异算子和交叉算子的策略进行重新设计。同时,在ACO算法中嵌入DE算法来改进解的质量。仿真结果验证了ACO&DE算法在求解TSP问题时的有效性,可以扩展应用到TSP的变型和其他物流运输领域。

改进的增强型蚁群算法

针对传统增强型蚁群算法容易出现早熟和停滞现象的缺陷,提出了一种改进的增强型蚁群算法。该方法将传统的增强型蚁群算法和遗传算法中交叉操作和变异操作相结合,实验结果表明,该方法比传统的增强型蚁群算法具有更好的搜索全局最优解的能力。