Self-tuning geometric semantic Genetic Programming

The process of tuning the parameters that characterize evolutionary algorithms is difficult and can be time consuming. This paper presents a self-tuning algorithm for dynamically updating the crossover and mutation probabilities during a run of genetic programming. The genetic operators that are considered in this work are the geometric semantic genetic operators introduced by Moraglio et al. Differently from other existing self-tuning algorithms, the proposed one works by assigning a (different) crossover and mutation probability to each individual of the population. The experimental results we present show the appropriateness of the proposed self-tuning algorithm: on seven different test problems, the proposed algorithm finds solutions of a quality that is better than, or comparable to, the one achieved using the best known values for the geometric semantic crossover and mutation rates for the same problems. Also, we study how the mutation and crossover probabilities change during the execution of the proposed self-tuning algorithm, pointing out an interesting insight: mutation is basically the only operator used in the exploration phase, while crossover is used for exploitation, further improving good quality solutions.     

A hyper-heuristic approach to automated generation of mutation operators for evolutionary programming

Evolutionary programming can solve black-box function optimisation problems by evolving a population of numerical vectors. The variation component in the evolutionary process is supplied by a mutation operator, which is typically a Gaussian, Cauchy, or Lévy probability distribution. In this paper, we use genetic programming to automatically generate mutation operators for an evolutionary programming system, testing the proposed approach over a set of function classes, which represent a source of functions. The empirical results over a set of benchmark function classes illustrate that genetic programming can evolve mutation operators which generalise well from the training set to the test set on each function class. The proposed method is able to outperform existing human designed mutation operators with statistical significance in most cases, with competitive results observed for the rest.     

Improved genetic algorithm inspired by biological evolution

The process of mutation has been studied extensively in the field of biology and it has been shown that it is one of the major factors that aid the process of evolution. Inspired by this a novel genetic algorithm (GA) is presented here. Various mutation operators such as small mutation, gene mutation and chromosome mutation have been applied in this genetic algorithm. In order to facilitate the implementation of the above-mentioned mutation operators a modified way of representing the variables has been presented. It resembles the way genetic information is coded in living beings. Different mutation operators pose a challenge as regards the determination of the optimal rate of mutation. This problem is overcome by using adaptive mutation operators. The main purpose behind this approach was to improve the efficiency of GAs and to find widely distributed Pareto-optimal solutions. This algorithm was tested on some benchmark test functions and compared with other GAs. It was observed that the introduction of these mutations do improve the genetic algorithms in terms of convergence and the quality of the solutions.     

Evolution of Appropriate Crossover and Mutation Operators in a Genetic Process

Traditional genetic algorithms use only one crossover and one mutation operator to generate the next generation. The chosen crossover and mutation operators are critical to the success of genetic algorithms. Different crossover or mutation operators, however, are suitable for different problems, even for different stages of the genetic process in a problem. Determining which crossover and mutation operators should be used is quite difficult and is usually done by trial-and-error. In this paper, a new genetic algorithm, the dynamic genetic algorithm (DGA), is proposed to solve the problem. The dynamic genetic algorithm simultaneously uses more than one crossover and mutation operators to generate the next generation. The crossover and mutation ratios change along with the evaluation results of the respective offspring in the next generation. By this way, we expect that the really good operators will have an increasing effect in the genetic process. Experiments are also made, with results showing the proposed algorithm performs better than the algorithms with a single crossover and a single mutation operator.     

Linear analysis of genetic algorithms

We represent simple and fitness-scaled genetic algorithms by Markov chains on probability distributions over the set of all possible populations of a fixed finite size. Analysis of this formulation yields new insight into the geometric properties of the three phase mutation, crossover, and fitness selection of a genetic algorithm by representing them as stochastic matrices acting on the state space. This indicates new methods using mutation and crossover as the proposal scheme for simulated annealing. We show by explicit estimates that for small mutation rates a genetic algorithm asymptotically spends most of its time in uniform populations regardless of crossover rate. The simple genetic algorithm converges in the following sense: there exists a fully positive limit probability distribution over populations. This distribution is independent of the choice of initial population. We establish strong ergodicity of the underlying inhomogeneous Markov chain for genetic algorithms that use any of a large class of fitness scaling methods including linear fitness scaling, sigma-truncation, and power law scaling. Our analysis even allows for variation in mutation and crossover rates according to a pre-determined schedule, where the mutation rate stays bounded away from zero. We show that the limit probability distribution of such a process is fully positive at all populations of uniform fitness. Consequently, genetic algorithms that use the above fitness scalings do not converge to a population containing only optimal members. This answers a question of G. Rudolph (IEEE Trans. on Neural Networks 5 (1994) 96–101). For a large set of fitness scaling methods, the limit distribution depends on the pre-order induced by the fitness function f, i.e. c c′ f(c) f(c′) on possible creatures c and c′, and not on the particular values assumed by the fitness function.     

货架分配问题的一个有效混合遗传算法

针对货架分配问题提出了一个遗传算法与模拟退火算法及一个局部搜索算法混合的算法。首先,设计了一种比较直观的编码方法,用一个矩阵作为一种货架分配方案。第二,设计了与编码相应的杂交和变异算子,并且杂交、变异都能生成可行解,不需要对解进行修正。第三,为了能够生成好的初始种群,定义了一个阀值,这个阀值不仅反映了解的适应值的信息,而且还反映解的结构的信息。第四,为了增加算法的局部搜索能力,同时又尽量不增加计算的复杂度,让模拟退火算法和一种局部搜索算法并行作用于相应的子群。通过大量的数据模拟实验及与其他的几种算法模拟结果进行比较,实验显示,该算法不论是计算结果还是算法的稳定性都优于其他算法。     

Some results about the Markov chains associated to GPs and general EAs

Geiringer's theorem is a statement which tells us something about the limiting frequency of occurrence of a certain individual when a classical genetic algorithm is executed in the absence of selection and mutation. Recently Poli, Stephens, Wright and Rowe extended the original theorem of Geiringer to include the case of variable-length genetic algorithms and linear genetic programming. In the current paper a rather powerful finite population version of Geiringer's theorem which has been established recently by Mitavskiy is used to derive a schema-based version of the theorem for nonlinear genetic programming with homologous crossover. The theorem also applies in the presence of “node mutation”. The corresponding formula in case when “node mutation” is present has been established.The limitation of the finite population Geiringer result is that it applies only in the absence of selection. In the current paper we also observe some general inequalities concerning the stationary distribution of the Markov chain associated to an evolutionary algorithm in which selection is the last (output) stage of a cycle. Moreover we prove an “anti-communism” theorem which applies to a wide class of EAs and says that for small enough mutation rate, the stationary distribution of the Markov chain modelling the EA cannot be uniform.     

一种维持种群多样性的遗传算法变异算子的研究

本文针对二进制编码遗传算法中，由于传统变异算子随机地选取基因位置而对搜索全局最优的不利影响，分析了变异位置对种群多样性的影响．提出了一种新的维持种群多样性的变异算子，其变异概率和变异位置由种群基因位的多样度和个体适应度值自适应决定．经变异后优秀的个体得以保存，且在种群中每一基因坐上两种基因的比例控制在期望的范围内．本文最后用实验验证了该算于维持种群多样性的有效性．     

混沌变异算子的改进遗传算法及其应用

为解决标准遗传算法（SGA）收敛缓慢等缺点,提出一种混沌变异算子的改进遗传算法,进化过程中,为防止局部早熟收敛,对较优个体的变异操作中引入一个混沌变异算子,并把混沌运动的遍历范围“放大”到优化变量的取值范围,通过一代代地不断进化,收敛到一个最适合环境的个体上,求得问题的最优解;建立精英个体序列库,防止最优解的丢失。采用实际算例进行仿真试验,仿真结果证明了该算法的有效性。     

Theory of Genetic Algorithms II: models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling

We present a theoretical framework for an asymptotically converging, scaled genetic algorithm which uses an arbitrary-size alphabet and common scaled genetic operators. The alphabet can be interpreted as a set of equidistant real numbers and multiple-spot mutation performs a scalable compromise between pure random search and neighborhood-based change on the alphabet level. We discuss several versions of the crossover operator and their interplay with mutation. In particular, we consider uniform crossover and gene-lottery crossover which does not commute with mutation. The Vose–Liepins version of mutation-crossover is also integrated in our approach. In order to achieve convergence to global optima, the mutation rate and the crossover rate have to be annealed to zero in proper fashion, and unbounded, power-law scaled proportional fitness selection is used with logarithmic growth in the exponent. Our analysis shows that using certain types of crossover operators and large population size allows for particularly slow annealing schedules for the crossover rate. In our discussion, we focus on the following three major aspects based upon contraction properties of the mutation and fitness selection operators: (i) the drive towards uniform populations in a genetic algorithm using standard operations, (ii) weak ergodicity of the inhomogeneous Markov chain describing the probabilistic model for the scaled algorithm, (iii) convergence to globally optimal solutions. In particular, we remove two restrictions imposed in Theorem 8.6 and Remark 8.7 of (Theoret. Comput. Sci. 259 (2001) 1) where a similar type of algorithm is considered as described here: mutation need not commute with crossover and the fitness function (which may come from a coevolutionary single species setting) need not have a single maximum.     

遗传算法在求解最小生成树中的运用

以图论和遗传算法为基础,提出了求解最小生成树问题的遗传算法。该算法解决了常用二进制编码不能正确表达最小生成树的问题,利用Prufer数对生成树进行编码;在遗传操作中对变异算子进行了改进,避免了由于变异产生大量不可行解。从而提高了遗传算法的效率;通过数值试验,表明该算法简单,高效,收敛率高。     

改进的自适应遗传算法在人体行为识别中的应用

为提高传统自适应遗传算法优化的BP神经网络对人体行为的识别率,提出了一种改进的自适应遗传算法优化的BP神经网络预测方法.该算法使用新的动态变化的交叉和变异分布指数计算公式来优化传统的二进制交叉和多项式变异操作,根据种群集中和分散的剧烈程度自适应地增大或减小交叉和变异的概率,极大地弥补了传统的交叉和变异操作所造成的破坏优...     

标记平面立体线图的自适应遗传算法

针对由理查德·迈尔斯提出的标记线图的遗传算法进行改进：采取自适应参数调 整法,同一代中适应度高于平均的个体杂交和变异率动态变化,适应度低于平均的个体杂交和 变异率设为定值;在创建初始种群时加入了约束条件,旨在改善初始种群覆盖空间的不确定性 和个体分布的相对不合理性;修正了遗传算法的适应度函数,使得以个体适应度为指标的选择 算子能正确引导算法搜索解空间。用遗传算法标记 6 幅不同的线图,变量为杂交率、变异率公 式中的参数 a 和 c,分析算法标记成功率曲线的变化趋势,探讨算子参数设置对遗传算法性能 的影响,结果表明 c 属于区间[0,0.05],a 属于区间[0.8,1.0]且为标记线图的遗传算法的最优 参数设置。     

铁路输送中平车装载问题的模型与算法

分析了铁路运输中的平车装载问题，借鉴了First Fit算法的思想，并引入条件变异算子，提出了求解平车装载问题的一种改进遗传算法，给出了该改进遗传算法编码方法、遗传算子改进方案和适应度函数的定义，该算法能有效地解决初始群体和进化过程中的无效染色体和早熟问题，并用实例验证了该算法的有效性。     

基于遗传算法的S盒的构造

采用遗传算法来构造S盒,并引入了启发式变异策略.该策略既可以防止优良的基因受到破坏,又可以保证群体中个体的多样性.基于该方法,给出了6×6的S盒构造的完整程序描述,并获得了一批高非线性度和低差分均匀度的S盒.     

Phase transitions and symmetry breaking in genetic algorithms with crossover

In this paper, we consider the role of the crossover operator in genetic algorithms. Specifically, we study optimisation problems that exhibit many local optima and consider how crossover affects the rate at which the population breaks the symmetry of the problem. As an example of such a problem, we consider the subset sum problem. In doing so, we demonstrate a previously unobserved phenomenon, whereby the genetic algorithm with crossover exhibits a critical mutation rate, at which its performance sharply diverges from that of the genetic algorithm without crossover. At this critical mutation rate, the genetic algorithm with crossover exhibits a rapid increase in population diversity. We calculate the details of this phenomenon on a simple instance of the subset sum problem and show that it is a classic phase transition between ordered and disordered populations. Finally, we show that this critical mutation rate corresponds to the transition between the genetic algorithm accelerating or preventing symmetry breaking and that the critical mutation rate represents an optimum in terms of the balance of exploration and exploitation within the algorithm.     

A new and fast rival genetic algorithm for feature selection

Feature selection is one of the significant steps in classification tasks. It is a pre-processing step to select a small subset of significant features that can contribute the most to the classification process. Presently, many metaheuristic optimization algorithms were successfully applied for feature selection. The genetic algorithm (GA) as a fundamental optimization tool has been widely used in feature selection tasks. However, GA suffers from the hyperparameter setting, high computational complexity, and the randomness of selection operation. Therefore, we propose a new rival genetic algorithm, as well as a fast version of rival genetic algorithm, to enhance the performance of GA in feature selection. The proposed approaches utilize the competition strategy that combines the new selection and crossover schemes, which aim to improve the global search capability. Moreover, a dynamic mutation rate is proposed to enhance the search behaviour of the algorithm in the mutation process. The proposed approaches are validated on 23 benchmark datasets collected from the UCI machine learning repository and Arizona State University. In comparison with other competitors, proposed approach can provide highly competing results and overtake other algorithms in feature selection.

     

自适应多位变异遗传算法的实现

Genetic algorithm is a widely used optimization method. Crossover and mutation are two Basicl operatorsof the genetic algorithm. On the basis of analyzing the principles of simple genetic algorithm and discussing its exist-ing problems of crossover point and mutation bit, this paper presents a way of the adaptive multiple bit mutation ge-netic algorithm , which not only can keep the population diversity but also has quicker convergence speed. The resultsof the multi-modal function optimization show that the adaptive multiple bit mutation genetic algorithm is practical and efficient.     

良性进化的自适应遗传算法及其仿真研究

为了搜索函数最优解,基于遗传算法基本理论,提出了良性进化的自适应遗传算法（AGA）。AGA从两个方面改进了标准遗传算法：一是交叉、变异率会自适应调节大小;二是交叉、变异具有方向性。通过对AGA的仿真研究,分析了AGA中参数取值对算法的性能影响。最后把AGA和标准遗传算法进行了仿真比较,结果表明AGA在求解函数最优解问题时具有较强的自适应性和收敛性。     

Scheduling multiprocessor tasks with genetic algorithms

In the multiprocessor scheduling problem, a given program is to be scheduled in a given multiprocessor system such that the program's execution time is minimized. This problem being very hard to solve exactly, many heuristic methods for finding a suboptimal schedule exist. We propose a new combined approach, where a genetic algorithm is improved with the introduction of some knowledge about the scheduling problem represented by the use of a list heuristic in the crossover and mutation genetic operations. This knowledge-augmented genetic approach is empirically compared with a “pure” genetic algorithm and with a “pure” list heuristic, both from the literature. Results of the experiments carried out with synthetic instances of the scheduling problem show that our knowledge-augmented algorithm produces much better results in terms of quality of solutions, although being slower in terms of execution time