浮点遗传算法中一种新的杂交算子

为了提高浮点遗传算法在优化计算时向最优解收敛的速度, 提出了一种新的遗传算子 :代间差分杂交算子. 通过应用于非线性参数估计的仿真计算, 表明了这种杂交算子的有效性及其相对于普通杂交算子的优点.     

Self-adaptive genetic algorithms with simulated binary crossover

Self-adaptation is an essential feature of natural evolution. However, in the context of function optimization, self-adaptation features of evolutionary search algorithms have been explored mainly with evolution strategy (ES) and evolutionary programming (EP). In this paper, we demonstrate the self-adaptive feature of real-parameter genetic algorithms (GAs) using a simulated binary crossover (SBX) operator and without any mutation operator. The connection between the working of self-adaptive ESs and real-parameter GAs with the SBX operator is also discussed. Thereafter, the self-adaptive behavior of real-parameter GAs is demonstrated on a number of test problems commonly used in the ES literature. The remarkable similarity in the working principle of real-parameter GAs and self-adaptive ESs shown in this study suggests the need for emphasizing further studies on self-adaptive GAs.     

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 formal analysis of the role of multi-point crossover in genetic algorithms

On the basis of early theoretical and empirical studies, genetic algorithms have typically used 1 and 2-point crossover operators as the standard mechanisms for implementing recombination. However, there have been a number of recent studies, primarily empirical in nature, which have shown the benefits of crossover operators involving a higher number of crossover points. From a traditional theoretical point of view, the most surprising of these new results relate to uniform crossover, which involves on the averageL/2 crossover points for strings of lengthL. In this paper we extend the existing theoretical results in an attempt to provide a broader explanatory and predictive theory of the role of multi-point crossover in genetic algorithms. In particular, we extend the traditional disruption analysis to include two general forms of multi-point crossover:n-point crossover and uniform crossover. We also analyze two other aspects of multi-point crossover operators, namely, their recombination potential and exploratory power. The results of this analysis provide a much clearer view of the role of multi-point crossover in genetic algorithms. The implications of these results on implementation issues and performance are discussed, and several directions for further research are suggested.     

Robust confidence intervals applied to crossover operator for real-coded genetic algorithms

In this work we propose a new approach to crossover operators for real-coded genetic algorithms based on robust confidence intervals. These confidence intervals are an alternative to standard confidence intervals. In this paper, they are used for localising the search regions where the best individuals are placed. Robust confidence intervals use robust localization and dispersion estimators that are highly recommendable when the distribution of the random variables is not known or is distorted. Both situations are likely when we are dealing with the best individuals of the population, especially if the problem under study is multimodal. The performance of the crossovers based on robust intervals is evaluated using a well characterised set of optimisation problems. We have chosen problems with different features of modality, separability, regularity, and correlation among their variables. The results show that the performance of the crossovers based on robust confidence intervals is less dependent on the problem than the performance of the crossovers based on Gaussian confidence intervals. We have also made comparisons between several standard crossovers that show very interesting results, which support the idea underlying the defined operators.     

Hybrid crossover operators for real-coded genetic algorithms: an experimental study

Most real-coded genetic algorithm research has focused on developing effective crossover operators, and as a result, many different types have been proposed. Some forms of crossover operators are more suitable to tackle certain problems than others, even at the different stages of the genetic process in the same problem. For this reason, techniques which combine multiple crossovers have been suggested as alternative schemes to the common practice of applying only one crossover model to all the elements in the population. Therefore, the study of the synergy produced by combining the different styles of the traversal of solution space associated with the different crossover operators is an important one. The aim is to investigate whether or not the combination of crossovers perform better than the best single crossover amongst them. In this paper we have undertaken an extensive study in which we have examined the synergetic effects among real-parameter crossover operators with different search biases. This has been done by means of hybrid real-parameter crossover operators, which generate two offspring for every pair of parents, each one with a different crossover operator. Experimental results show that synergy is possible among real-parameter crossover operators, and in addition, that it is responsible for improving performance with respect to the use of a single crossover operator.     

RGFGA: an efficient representation and crossover for grouping genetic algorithms

There is substantial research into genetic algorithms that are used to group large numbers of objects into mutually exclusive subsets based upon some fitness function. However, nearly all methods involve degeneracy to some degree.We introduce a new representation for grouping genetic algorithms, the restricted growth function genetic algorithm, that effectively removes all degeneracy, resulting in a more efficient search. A new crossover operator is also described that exploits a measure of similarity between chromosomes in a population. Using several synthetic datasets, we compare the performance of our representation and crossover with another well known state-of-the-art GA method, a strawman optimisation method and a well-established statistical clustering algorithm, with encouraging results.     

Adaptive crossover,mutation and selection using fuzzy system for genetic algorithms

Genetic algorithms use a tournament selection or a roulette selection to choice better population. But these selections couldn’t use heuristic information for specific problem. Fuzzy selection system by heuristic rule base help to find optimal solution efficiently. And adaptive crossover and mutation probabilistic rate is faster than using fixed value. In this paper, we want fuzzy selection system for genetic algorithms and adaptive crossover and mutation rate fuzzy system. This work was presented in part and awarded as Young Author Award at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

A new crossover mechanism for genetic algorithms with variable-length chromosomes for path optimization problems

Genetic Algorithm (GA) has found wide application in path optimization problem. In many fields such as navigating system, oil transportation, paths between the starting node and the termination node often have distinct number of relay-nodes, which leads to the corresponding chromosomes would have different length. We refer to chromosomes with non-consistent lengths as the variable-length chromosomes. This paper first investigated GAs with variable-length chromosomes widely used and found that Same Point (SP) crossover is the most popular crossover mechanism. Then, a new crossover mechanism called Same Adjacency (SA) is proposed for GA with variable-length chromosomes for path optimization problem, which outperforms GA with SP by a better search capability as the mathematical analysis shows. The simulation study indicates that GAs with our crossover operators could obtain a better solution, as compared to GAs with SP, while still being able to converge fast in different networks with varied sizes.     

Development of a novel crossover of hybrid genetic algorithms for large-scale traveling salesman problems

This article proposes a novel crossover operator of hybrid genetic algorithms (HGAs) with a Lin-Kernighan (LK) heuristic for solving large-scale traveling salesman problems (TSPs). The proposed crossover, tentatively named sub-tour recombination crossover (SRX), collects many short sub-tours from both parents under some set of rules, and reconnects them to construct a new tour of the TSP. The method is evaluated from the viewpoint of tour quality and CPU time for ten well-known benchmarks, e.g., dj38, qa194, …, ch71009.tsp, in the TSP website of the Georgia Institute of Technology. We compare the SRX with three conventional crossover operators, a variant of the maximal preservative crossover operator (MPX3), a variant of the greedy sub-tour crossover operator (GSX2), and a variant of the edge recombination crossover operator (ERX6), and show that the SRX succeeded in finding a better solution and running faster than the conventional methods mentioned above.     

Hybrid crossover operators with multiple descendents for real‐coded genetic algorithms: Combining neighborhood‐based crossover operators

Most real‐coded genetic algorithm research has focused on developing effective crossover operators, and as a result, many different types of crossover operators have been proposed. Some forms of crossover operators are more suitable to tackle certain problems than others, even at the different stages of the genetic process in the same problem. For this reason, techniques that combine multiple crossovers, called hybrid crossover operators, have been suggested as alternative schemes to the common practice of applying only one crossover model to all the elements in the population. On the other hand, there are operators with multiple offsprings, more than two descendants from two parents, which present a better behavior than the operators with only two descendants, and achieve a good balance between exploration and exploitation. © 2009 Wiley Periodicals, Inc.     

Real-coded memetic algorithms with crossover hill-climbing

This paper presents a real-coded memetic algorithm that applies a crossover hill-climbing to solutions produced by the genetic operators. On the one hand, the memetic algorithm provides global search (reliability) by means of the promotion of high levels of population diversity. On the other, the crossover hill-climbing exploits the self-adaptive capacity of real-parameter crossover operators with the aim of producing an effective local tuning on the solutions (accuracy). An important aspect of the memetic algorithm proposed is that it adaptively assigns different local search probabilities to individuals. It was observed that the algorithm adjusts the global/local search balance according to the particularities of each problem instance. Experimental results show that, for a wide range of problems, the method we propose here consistently outperforms other real-coded memetic algorithms which appeared in the literature.     

Effects of population size on the performance of genetic algorithms and the role of crossover

One of the most important parameters in the application of genetic algorithms (GAs) is the population size N. In many cases, the choice of N determines the quality of the solutions obtained. The study of GAs with a finite population size requires a stochastic treatment of evolution. In this study, we examined the effects of genetic fluctuations on the performance of GA calculations. We considered the role of crossover by using the stochastic schema theory within the framework of the Wright-Fisher model of Markov chains. We also applied the diffusion approximation of the Wright-Fisher model. In numerical experiments, we studied effects of population size N and crossover rate pc on the success probability S. The success probability S is defined as the probability of obtaining the optimum solution within the limit of reaching the stationary state. We found that in a GA with pc, the diffusion equation can reproduce the success probability S. We also noted the role of crossover, which greatly increases S.     

遗传算法中的联结关系

进化计算领域的一个根本问题是哪些问题适合遗传算法求解,为此需要研究问题的结构对算法性能的影响.变量之间的联结关系是问题的本质属性,决定了遗传算法求解问题的难度.如果某个变量对函数值的影响非线性依赖于其他变量,则认为这些变量之间存的联结关系不,对遗传算法的联结关系这一理论问题进行了深入研究,给出了分析一般离散问题联结结构的理论基础,通过分析傅里叶系数与函数子空间的关系,提出了检测黑箱问题联结结构的确定性和随机性算法,通过试验分析说明了算法的正确性和有效性.     

Homogeneous genetic algorithms

A new type of genetic algorithm (GA) is developed to mitigate one or both of the following two major difficulties that traditional GAs may suffer: (1) when the number of ‘active genes’ needs to be held constant or kept within some prescribed range, and (2) when the set of genes is much larger than the set of active genes of feasible solutions under consideration. These homogeneous GAs use (unordered) sets to represent ‘active genes’ in chromosomes rather than strings, and a correspondingly natural crossover operator is introduced. ‘Homogeneous’ refers to the fact that, in contrast to traditional GAs where pairs of genes that are ‘close’ have better chances of being preserved under crossover, there is no notion of proximity between pairs of genes. Examples are provided that will demonstrate superior performance of these new GAs for some typical problems in which these difficulties arise.     

Dynamic and heuristic fuzzy connectives-based crossover operators for controlling the diversity and convergence of real-coded genetic algorithms

Genetic algorithms are adaptive methods which may be used as approximation heuristic for search and optimization problems. Genetic algorithms process a population of search space solutions with three operations: selection, crossover, and mutation. A great problem in the use of genetic algorithms is the premature convergence, a premature stagnation of the search caused by the lack of diversity in the population and a disproportionate relationship between exploitation and exploration. The crossover operator is considered one of the most determinant elements for solving this problem. In this article we present two types of crossover operators based on fuzzy connectives for real-coded genetic algorithms. The first type is designed to keep a suitable sequence between the exploration and the exploitation along the genetic algorithm's run, the dynamic fuzzy connectives-based crossover operators, the second, for generating offspring near to the best parents in order to offer diversity or convergence in a profitable way, the heuristic fuzzy connectives-based crossover operators. We combine both crossover operators for designing dynamic heuristic fuzzy connectives-based crossover operators that show a robust behavior. © 1996 John Wiley & Sons, Inc.     

A taxonomy for the crossover operator for real‐coded genetic algorithms: An experimental study

The main real‐coded genetic algorithm (RCGA) research effort has been spent on developing efficient crossover operators. This study presents a taxonomy for this operator that groups its instances in different categories according to the way they generate the genes of the offspring from the genes of the parents. The empirical study of representative crossovers of all the categories reveals concrete features that allow the crossover operator to have a positive influence on RCGA performance. They may be useful to design more effective crossover models. © 2003 Wiley Periodicals, Inc.