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.

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.

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.

Using Genetic Algorithms for Solving the Comparison-Based Identification Problem of Multifactor Estimation Model

In this paper the statement and the methods for solving the comparison-based structure-parametric identification problem of multifactor estimation model are addressed. A new method that combines heuristics methods with genetic algorithms is proposed to solve the problem. In order to overcome some disadvantages of using the classical utility functions, the use of nonlinear Kolmogorov-Gabor polynomial, which contains in its composition the first as well as higher characteristics degrees and all their possible combinations is proposed in this paper. The use of nonlinear methods for identification of the multifactor estimation model showed that the use of this new technique, using as a utility function the nonlinear Kolmogorov-Gabor polynomial and the use of genetic algorithms to calculate the weights, gives a considerable saving in time and accuracy performance. This method is also simpler and more evident for the decision maker (DM) than other methods.

On Some Basic Concepts of Genetic Algorithms as a Meta-Heuristic Method for Solving of Optimization Problems

The genetic algorithms represent a family of algorithms using some of genetic principles being present in nature, in order to solve particular computational problems. These natural principles are: inheritance, crossover, mutation, survival of the fittest, migrations and so on. The paper describes the most important aspects of a genetic algorithm as a stochastic method for solving various classes of optimization problems. It also describes the basic genetic operator selection, crossover and mutation, serving for a new generation of individuals to achieve an optimal or a good enough solution of an optimization problem being in question.

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.

An Improved Real-Coded Genetic Algorithm and Its Application

Real-coded genetic algorithm（RGA）usually meets the demand of consecutive space problem.However,compared with simple genetic algorithm（SGA）RGA also has the inherent disadvantages such as prematurity and slow convergence when the solution is close to the optimum solution.This paper presents an improved real-coded genetic algorithm to increase the computation efficiency and avoid prematurity,especially in the optimization of multi-modal function.In this method,mutation operation and crossover operation are improved.Examples are given to demonstrate its com p utation efficiency and robustness.

A REAL-VALUED GENETIC ALGORITHM FOR OPTIMIZATION PROBLEM WITH CONTINUOUS VARIABLES

A real valued genetic algorithm(RVGA) for the optimization problem with continuous variables is proposed. It is composed of a simple and general purpose dynamic scaled fitness and selection operator, crossover operator, mutation operators and adaptive probabilities for these operators. The algorithm is tested by two generally used functions and is used in training a neural network for image recognition. Experimental results show that the algorithm is an efficient global optimization algorithm.

An adaptive genetic algorithm for solving bilevel linear programming problem

Bilevel linear programming, which consists of the objective functions of the upper level and lower level, is a useful tool for modeling decentralized decision problems. Various methods are proposed for solving this problem. Of all the algorithms, the ge- netic algorithm is an alternative to conventional approaches to find the solution of the bilevel linear programming. In this paper, we describe an adaptive genetic algorithm for solving the bilevel linear programming problem to overcome the difficulty of determining the probabilities of crossover and mutation. In addition, some techniques are adopted not only to deal with the difficulty that most of the chromosomes maybe infeasible in solving constrained optimization problem with genetic algorithm but also to improve the efficiency of the algorithm. The performance of this proposed algorithm is illustrated by the examples from references.

An improved genetic algorithm for searching for pollution sources

As an optimization method that has experienced rapid development over the past 20 years, the genetic algorithm has been successfully applied in many fields, but it requires repeated searches based on the characteristics of high-speed computer calculation and conditions of the known relationship between the objective function and independent variables. There are several hundred generations of evolvement, but the functional relationship is unknown in pollution source searches. Therefore, the genetic algorithm cannot be used directly. Certain improvements need to be made based on the actual situation, so that the genetic algorithm can adapt to the actual conditions of environmental problems, and can be used in environmental monitoring and environmental quality assessment. Therefore, a series of methods are proposed for the improvement of the genetic algorithm： （1） the initial generation of individual groups should be artificially set and move from lightly polluted areas to heavily polluted areas; （2） intervention measures should be introduced in the competition between individuals; （3） guide individuals should be added; and （4） specific improvement programs should be put forward. Finally, the scientific rigor and rationality of the improved genetic algorithm are proven through an example.

Genetic Algorithm for the Thermal Stresses Optimum Design ofFunctionally Gradient Material Plate

Based on the thermal stress distribution for functionally gradient material (FGM) plates, a Genetic Algorithm (GA) method for the thermal stresses optimum design of FGM plate with computer technologies is given. The minimum thermal stresses combination distribution for FGM is obtained.

Application of Genetic Algorithm in Estimation of Gyro Drift Error Model

Extended Kalman Filter(EKF)algorithm is widely used in parameter estimation for nonlinear systems.The estimation precision is sensitively dependent on EKF’s initial state covariance matrix and state noise matrix.The grid optimization method is always used to find proper initial matrix for off-line estimation.However,the grid method has the draw back being time consuming hence,coarse grid followed by a fine grid method is adopted.To further improve efficiency without the loss of estimation accuracy,we propose a genetic algorithm for the coarse grid optimization in this paper.It is recognized that the crossover rate and mutation rate are the main influencing factors for the performance of the genetic algorithm,so sensitivity experiments for these two factors are carried out and a set of genetic algorithm parameters with good adaptability were selected by testing with several gyros’experimental data.Experimental results show that the proposed algorithm has higher efficiency and better estimation accuracy than the traversing grid algorithm.

Three-Objective Programming with Continuous Variable Genetic Algorithm

The subject area of multiobjective optimization deals with the investigation of optimization problems that possess more than one objective function. Usually, there does not exist a single solution that optimizes all functions simultaneously;quite the contrary, we have solution set that is called nondominated set and elements of this set are usually infinite. It is from this set decision made by taking elements of nondominated set as alternatives, which is given by analysts. Since it is important for the decision maker to obtain as much information as possible about this set, our research objective is to determine a well-defined and meaningful approximation of the solution set for linear and nonlinear three objective optimization problems. In this paper a continuous variable genetic algorithm is used to find approximate near optimal solution set. Objective functions are considered as fitness function without modification. Initial solution was generated within box constraint and solutions will be kept in feasible region during mutation and recombination.

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

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

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

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

一种求解多目标校车路径问题的改进遗传算法

针对多目标校车路径优化问题的NP-hard和现有求解方法的不足,提出了一种新颖的“站点—车辆”两阶段编码策略,通过站点排序和车辆分配两个阶段生成个体,降低了编码冗余度,保证了解的合法性。设计了一种新型的双序列交叉算子,在继承父代优良基因的同时,增加了种群的多样性,加快了算法的收敛速度。在实验方面,选取3组不同规模的基准测试数据,对算法的解质量和计算效率进行了评测,并与标准遗传算法(SGA)、模拟退火算法(SA)等经典启发式算法进行比较。实验结果表明,算法在解的质量和收敛速度方面均优于其他算法,展现出了良好的求解性能和应用前景。

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

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

遗传算法能量分析中初始化与变异机制研究

人工智能与侧信道密码分析相结合,给密码分析学带来了新的研究方向。近十年来,遗传算法被引入侧信道分析,国际上出现了一系列相关研究成果。然而,现有基于遗传算法的相关能量分析存在局部最优问题,使整个分析过程的效率偏低。本文旨在建立局部最优与成功率之间的关系,选取科学的初始化与变异机制,以显著提升使用人工智能算法开展侧信道分析的效率。我们首先探究了遗传算法能量分析成功、以及陷入局部最优的本质原因,随后从初始化机制、变异机制两个角度尝试克服局部最优问题,引入随机初始化、相关能量分析初始化、随机字节变异、基于密钥适应度排名的启发式变异等四种机制进行组合对比。通过参数选取、成功率对比、计算代价对比等多次实验得到结论:相关能量分析初始化结合随机字节变异的方法具有最高的成功率,同时计算代价也最小。与此同时,本文总结了遗传算法相关能量分析方法不适用于软件实现、难以分析大位宽运算、攻击防护对策时复杂度高、信噪比低时复杂度高等局限性问题,建议密码硬件计算过程中尽量不要将以字节或比特为单位计算的值存入寄存器,以防护遗传算法类能量分析攻击,并对未来工作进行了展望。我们认为,新方法在分析无防护硬件实现的分组密码算法时具有较高的实用性,建议应用于实际的侧信道分析测评工作。

Global optimization over linear constraint non-convex programming problem

A improving Steady State Genetic Algorithm for global optimization over linear constraint non-convex programming problem is presented. By convex analyzing, the primal optimal problem can be converted to an equivalent problem, in which only the information of convex extremes of feasible space is included, and is more easy for GAs to solve. For avoiding invalid genetic operators, a redesigned convex crossover operator is also performed in evolving. As a integrality, the quality of two problem is proven, and a method is also given to get all extremes in linear constraint space. Simulation result show that new algorithm not only converges faster, but also can maintain an diversity population, and can get the global optimum of test problem.