选择的遗传漂移分析

进化算法存在早熟收敛和丢失可选解的趋势，其原因可归咎于由选择压、采样噪声和交叉算子引起的遗传漂移。建立选择算子的马尔可夫链模型，通过吸收态和吸收概率分析证明遗传漂移的必然性和早熟收敛的可能性，分析早熟收敛与选择压和适应值函数峰值分布的关系。针对2解问题，通过计算种群多样度期望值，分析漂移过程的动态特征，应用实验的方法比较不同采样方法对漂移速度和早熟收敛的影响。其结论为进化算法的实现和改进提供了理论依据和经验指导。     

Statistical properties analysis of real world tournament selection in genetic algorithms

Genetic algorithms (GAs) are probabilistic optimization methods based on the biological principle of natural evolution. One of the important operators in GAs is the selection strategy for obtaining better solutions. Specifically, finding a balance between the selection pressure and diversity is a critical issue in designing an efficient selection strategy. To this extent, the recently proposed real world tournament selection (RWTS) method has showed good performance in various benchmark problems. In this paper, we focus on analyzing characteristics of RWTS from the viewpoint of both the selection probabilities and stochastic sampling properties in order to provide a rational explanation for why RWTS provides improved performance. Statistical experimental results show that RWTS has a higher selection pressure with a relatively small loss of diversity and higher sampling accuracy than conventional tournament selection. The performance tests in a traveling salesman problem further confirm that the comparatively higher pressure and sampling accuracy, which are inherent in RWTS, can enhance the performance in the selection strategy.     

Impacts of sampling strategies in tournament selection for genetic programming

Tournament selection is one of the most commonly used parent selection schemes in genetic programming (GP). While it has a number of advantages over other selection schemes, it still has some issues that need to be thoroughly investigated. Two of the issues are associated with the sampling process from the population into the tournament. The first one is the so-called “multi-sampled” issue, where some individuals in the population are picked up (sampled) many times to form a tournament. The second one is the “not-sampled” issue, meaning that some individuals are never picked up when forming tournaments. In order to develop a more effective selection scheme for GP, it is necessary to understand the actual impacts of these issues in standard tournament selection. This paper investigates the behaviour of different sampling replacement strategies through mathematical modelling, simulations and empirical experiments. The results show that different sampling replacement strategies have little impact on selection pressure and cannot effectively tune the selection pressure in dynamic evolution. In order to conduct effective parent selection in GP, research focuses should be on developing automatic and dynamic selection pressure tuning methods instead of alternative sampling replacement strategies. Although GP is used in the empirical experiments, the findings revealed in this paper are expected to be applicable to other evolutionary algorithms.     

求解最大子团的随机抽样免疫遗传算法

针对遗传算法在最大子团求解中保持群体多样性能力不足、早熟、耗时长、成功率低等缺陷,利用随机抽样方法对交叉操作进行重新设计,结合免疫机理定义染色体浓度,设计克隆选择策略,提出了求解最大子团问题的随机抽样免疫遗传算法。用仿真算例说明了新算法在解的质量、收敛速度等各项指标上均有提高,且不比DLS-MC、QUALEX等经典搜索算法差,对某些算例还得到了更好解。     

Real-coded genetic algorithm with variable rates of cross-over and mutation: a basis of global optimization for multi-modal functions via interval technique

A hybrid method consisting of a real-coded genetic algorithm (RCGA) and an interval technique is proposed for optimizing bound constrained non-linear multi-modal functions. This method has two different phases. In phase I, the search space is divided into several subregions and the simple genetic algorithm (SGA) is applied to each subregion to find the one(s) containing the best value of the objective function. In phase II, the selected subregion is divided into two equal halves and the advanced GA, i.e. the RCGA, is applied in each half to reject the subregion where the global solution does not exist. This process is repeated until the interval width of each variable is less than a pre-assigned very small positive number. In the RCGA, we consider rank-based selection, multi-parent whole arithmetical cross-over, and non-uniform mutation depending on the age of the population. However, the cross-over and mutation rates are assumed as variables. Initially, these rates are high and then decrease from generation to generation. Finally, the proposed hybrid method is applied to several standard test functions used in the literature; the results obtained are encouraging. Sensitivity analyses are shown graphically with respect to different parameters on the lower bound of the interval valued objective function of two different problems.     

Research of multi-population agent genetic algorithm for feature selection

Search algorithm is an essential part of feature selection algorithm. In this paper, through constructing double chain-like agent structure and with improved genetic operators, the authors propose one novel agent genetic algorithm-multi-population agent genetic algorithm (MPAGAFS) for feature selection. The double chain-like agent structure is more like local environment in real world, the introduction of this structure is good to keep the diversity of population. Moreover, the structure can help to construct multi-population agent GA, thereby realizing parallel searching for optimal feature subset. In order to evaluate the performance of MPAGAFS, several groups of experiments are conducted. The experimental results show that the MPAGAFS cannot only be used for serial feature selection but also for parallel feature selection with satisfying precision and number of features.     

并行混合遗传算法及其在布局设计中的应用

布局问题在理沦上属于NPC问题，在工程实践上具有广泛的应用。为较好地求解该问题，该文以并行遗传算法（PGA）为基础，针对其早熟和收敛速度慢两大缺陷加以改进，给出了一种并行混合遗传算法(PHGA)．PHGA采用该文提出的压力插他排序选择算子，起到了双重作用：一是在进化初期可以防止早熟；二是在进化后期有利于加快算法的收敛。算法利用混沌初始化可提高初始群体的质量，并依自适应交叉和变异概率值对子群体进行分类，与Powell法混合可以很好地改善算法的局部搜索性能。文中通过标准函数优化和布局设计的算例验证了该算法的可行性和有效性。     

Some issues of designing genetic algorithms for traveling salesman problems

This paper demonstrates that a robust genetic algorithm for the traveling salesman problem (TSP) should preserve and add good edges efficiently, and at the same time, maintain the population diversity well. We analyzed the strengths and limitations of several well-known genetic operators for TSPs by the experiments. To evaluate these factors, we propose a new genetic algorithm integrating two genetic operators and a heterogeneous pairing selection. The former can preserve and add good edges efficiently and the later will be able to keep the population diversity. The proposed approach was evaluated on 15 well-known TSPs whose numbers of cities range from 101 to 13509. Experimental results indicated that our approach, somewhat slower, performs very robustly and is very competitive with other approaches in our best surveys. We believe that a genetic algorithm can be a stable approach for TSPs if its operators can preserve and add edges efficiently and it maintains population diversity.     

遗传算法选择方法的比较分析

本文基于改进的基本遗传算法实验,对选择方法进行了比较分析的研究,测试了四种不同选择方法：轮盘赌选择法、锦标赛选择法、随机遍历选择法以及一种新的基于种群交流的选择方法,分析比较这四种不同选择方法封种群发展及最佳适应值的影响。结果表明各种选择方法各有特点。最後为了防止陷入局部收敛,而对轮盘赌选择方法进行了改进,并比较了改进前後的结果,发现改进后的结果要好一些。     

Fuzzy genetic sharing for dynamic optimization

Recently,genetic algorithms(GAs) have been applied to multi-modal dynamic optimization(MDO).In this kind of optimization,an algorithm is required not only to find the multiple optimal solutions but also to locate a dynamically changing optimum.Our fuzzy genetic sharing(FGS) approach is based on a novel genetic algorithm with dynamic niche sharing(GADNS).FGS finds the optimal solutions,while maintaining the diversity of the population.For this,FGS uses several strategies.First,an unsupervised fuzzy clustering method is used to track multiple optima and perform GADNS.Second,a modified tournament selection is used to control selection pressure.Third,a novel mutation with an adaptive mutation rate is used to locate unexplored search areas.The effectiveness of FGS in dynamic environments is demonstrated using the generalized dynamic benchmark generator(GDBG).     

基于遗传算法的进化压力的研究

为了解影响进化压力的因素,在群体大小的选择、选择运算（Selection）、交叉运算（Crossover）三个方面进行了详细的分析。通过在遗传算法的三个阶段,选取不同的方案来解决复杂的函数优化问题的实验方法,得出了不同方案对进化压力的影响差异。时差异进行了比较分析,并对实际运用中方案的选择提出了一些建议。     

Parallel distributed genetic fuzzy rule selection

Genetic fuzzy rule selection has been successfully used to design accurate and compact fuzzy rule-based classifiers. It is, however, very difficult to handle large data sets due to the increase in computational costs. This paper proposes a simple but effective idea to improve the scalability of genetic fuzzy rule selection to large data sets. Our idea is based on its parallel distributed implementation. Both a training data set and a population are divided into subgroups (i.e., into training data subsets and sub-populations, respectively) for the use of multiple processors. We compare seven variants of the parallel distributed implementation with the original non-parallel algorithm through computational experiments on some benchmark data sets.     

基于遗传算法改进的少数类样本合成过采样技术的非平衡数据集分类算法

针对少数类样本合成过采样技术(SMOTE)在处理非平衡数据集分类问题时,为少数类的不同样本设置相同的采样倍率,存在一定的盲目性的问题,提出了一种基于遗传算法(GA)改进的SMOTE方法--GASMOTE.首先,为少数类的不同样本设置不同的采样倍率,并将这些采样倍率取值的组合编码为种群中的个体;然后,循环使用GA的选择、交叉、变异等算子对种群进行优化,在达到停机条件时获得采样倍率取值的最优组合;最后,根据找到的最优组合对非平衡数据集进行SMOTE采样.在10个典型的非平衡数据集上进行的实验结果表明:与SMOTE算法相比,GASMOTE在F-measure值上提高了5.9个百分点,在G-mean值上提高了1.6个百分点;与Borderline-SMOTE算法相比,GASMOTE在F-measure值上提高了3.7个百分点,在G-mean值上提高了2.3个百分点.该方法可作为一种新的解决非平衡数据集分类问题的过采样技术.     

A genetic algorithm-based method for feature subset selection

As a commonly used technique in data preprocessing, feature selection selects a subset of informative attributes or variables to build models describing data. By removing redundant and irrelevant or noise features, feature selection can improve the predictive accuracy and the comprehensibility of the predictors or classifiers. Many feature selection algorithms with different selection criteria has been introduced by researchers. However, it is discovered that no single criterion is best for all applications. In this paper, we propose a framework based on a genetic algorithm (GA) for feature subset selection that combines various existing feature selection methods. The advantages of this approach include the ability to accommodate multiple feature selection criteria and find small subsets of features that perform well for a particular inductive learning algorithm of interest to build the classifier. We conducted experiments using three data sets and three existing feature selection methods. The experimental results demonstrate that our approach is a robust and effective approach to find subsets of features with higher classification accuracy and/or smaller size compared to each individual feature selection algorithm.     

An efficient hybrid genetic algorithm to design finite impulse response filters

Although genetic algorithms (GAs) have proved their ability to provide answers to the limitations of more conventional methods, they are comparatively inefficient in terms of the time needed to reach a repeatable solution of desired quality. An inappropriate selection of driving parameters is frequently blamed by practitioners. The use of hybrid schemes is interesting but often limited as they are computationally expensive and versatile. This paper presents a novel hybrid genetic algorithm (HGA) for the design of digital filters. HGA combines a pure genetic process and a dedicated local approach in an innovative and efficient way. The pure genetic process embeds several mechanisms that interact to make the GA self-adaptive in the management of the balance between diversity and elitism during the genetic life. The local approach concerns convergence of the algorithm and is highly optimized so as to be tractable. Only some promising reference chromosomes are submitted to the local procedure through a specific selection process. They are more likely to converge towards different local optima. This selective procedure is fully automatic and avoids excessive computational time costs as only a few chromosomes are concerned. The hybridization and the mechanisms involved afford the GA great flexibility. It therefore avoids laborious manual tuning and improves the usability of GAs for the specific area of FIR filter design. Experiments performed with various types of filters highlight the recurrent contribution of hybridization in improving performance. The experiments also reveal the advantages of our proposal compared to more conventional filter design approaches and some reference GAs in this field of application.     

A genetic algorithm with disruptive selection

Genetic algorithms are a class of adaptive search techniques based on the principles of population genetics. The metaphor underlying genetic algorithms is that of natural evolution. Applying the “survival-of-the-fittest” principle, traditional genetic algorithms allocate more trials to above-average schemata. However, increasing the sampling rate of schemata that are above average does not guarantee convergence to a global optimum; the global optimum could be a relatively isolated peak or located in schemata that have large variance in performance. In this paper we propose a novel selection method, disruptive selection. This method adopts a nonmonotonic fitness function that is quite different from traditional monotonic fitness functions. Unlike traditional genetic algorithms, this method favors both superior and inferior individuals. Experimental results show that GAs using the proposed method easily find the optimal solution of a function that is hard for traditional GAs to optimize. We also present convergence analysis to estimate the occurrence ratio of the optima of a deceptive function after a certain number of generations of a genetic algorithm. Experimental results show that GAs using disruptive selection in some occasions find the optima more quickly and reliably than GAs using directional selection. These results suggest that disruptive selection can be useful in solving problems that have large variance within schemata and problems that are GA-deceptive     

A tribe competition-based genetic algorithm for feature selection in pattern classification

Feature selection has always been a critical step in pattern recognition, in which evolutionary algorithms, such as the genetic algorithm (GA), are most commonly used. However, the individual encoding scheme used in various GAs would either pose a bias on the solution or require a pre-specified number of features, and hence may lead to less accurate results. In this paper, a tribe competition-based genetic algorithm (TCbGA) is proposed for feature selection in pattern classification. The population of individuals is divided into multiple tribes, and the initialization and evolutionary operations are modified to ensure that the number of selected features in each tribe follows a Gaussian distribution. Thus each tribe focuses on exploring a specific part of the solution space. Meanwhile, tribe competition is introduced to the evolution process, which allows the winning tribes, which produce better individuals, to enlarge their sizes, i.e. having more individuals to search their parts of the solution space. This algorithm, therefore, avoids the bias on solutions and requirement of a pre-specified number of features. We have evaluated our algorithm against several state-of-the-art feature selection approaches on 20 benchmark datasets. Our results suggest that the proposed TCbGA algorithm can identify the optimal feature subset more effectively and produce more accurate pattern classification.     

Quasi-random initial population for genetic algorithms

The selection of the initial population in a population-based heuristic optimizationmethod is important, since it affects the search for several iterations and often has an influence on the final solution. If no a priori information about the optima is available, the initial population is often selected randomly using pseudorandom numbers. Usually, however, it is more important that the points are as evenly distributed as possible than that they imitate random points. In this paper, we study the use of quasi-random sequences in the initial population of a genetic algorithm. Sample points in a quasi-random sequence are designed to have good distribution properties. Here a modified genetic algorithm using quasi-random sequences in the initial population is tested by solving a large number of continuous benchmark problems from the literature. The numerical results of two implementations of genetic algorithms using different quasi-random sequences are compared to those of a traditional implementation using pseudorandom numbers. The results obtained are promising.     

Mixed size tournament selection

 In genetic algorithms, tournament schemes are often applied as selection operators. The advantage is simplicity and efficiency. On the other hand, major deficiencies related to tournament selection are the coarse scaling of the selection pressure and the poor sampling accuracy. We introduce a new variant of tournament selection which provides an adjustable probability distribution, a fine-tuning facility for the selection pressure and an improved sampling accuracy at the cost of a minimal increase of the complexity and with almost no loss of efficiency.     

Hyperbolicity of the fixed point set for the simple genetic algorithm

We study an infinite population model for the genetic algorithm, where the iteration of the algorithm corresponds to an iteration of a map G. The map G is a composition of a selection operator and a mixing operator, where the latter models effects of both mutation and crossover. We examine the hyperbolicity of fixed points of this model. We show that for a typical mixing operator all the fixed points are hyperbolic.