并行遗传算法研究及其应用

GA是一类基于自然选择和遗传学原理的有效搜索方法，它从一个种群开始，利用选择、交叉、变异等遗传算子对种群进行不断进化。最后得到全局最优解。但随着求解问题的复杂性及难度的增加，提高GA的运行速度便显得尤为突出，采用并行遗传算法（PGA）是提高搜索效率的方法之一。本文分析了并行遗传算法的四种模型，最后应用于0-1背包问题的求解。实验结果表明．该算法在具有较高搜索效率的同时，仍能维持很高的种群多样性。     

元胞遗传算法的收敛性分析和收敛速度估计

元胞遗传算法是空间结构化种群的遗传算法,将遗传操作限制在相邻个体之间进行,限制优势基因的扩散速度,保持种群的多样性,改善遗传算法的性能。但是,目前有关元胞遗传算法收敛性的分析还较缺乏。文中根据元胞遗传算法的特性,建立元胞遗传算法的吸收态 Markov链模型,证明元胞遗传算法的收敛性。提出元胞遗传算法的首达最优解期望时间的估算方法,并估计标准同步元胞遗传算法首达最优解期望时间的上下界。     

并行遗传算法研究及其应用

GA是一类基于自然选择和遗传学原理的有效搜索方法,它从一个种群开始,利用选择、交叉、变异等遗传算子对种群进行不断进化,最后得到全局最优解.但随着求解问题的复杂性及难度的增加,提高GA的运行速度便显得尤为突出,采用并行遗传算法(PGA)是提高搜索效率的方法之一.本文分析了并行遗传算法的四种模型,最后应用于0-1背包问题的求解.实验结果表明,该算法在具有较高搜索效率的同时,仍能维持很高的种群多样性.     

遗传算法交换操作的可达性

交换是遗传算法中的一个重要操作,本文分析了遗传算法交换操作的特性,证明了对于互补的两个二进制串,通过交换操作可达其它任意互补的两个二进制串。     

遗传算法收敛性分析的统一方法

建立了种群中最佳个体的马尔可夫链模型,定义了仅包含所有全局最妥的状态子集;根据从任意状态转移至该子集的概率的极限分布,给出了独立于搜索曲面拓扑结构的遗传算法全局收性的精确定义;提出并严格地证明了与编码方式和选择自力更生无关的、统一的全局收敛性判据定理。对几种不同的遗传算法进行全局收敛性分析的结果表明,统一的判断方法具有普遍的适用性。     

提高遗传算法收敛速度的方法

我们知道简单遗传算法的搜索速度太慢，为了提高自救的速度，本文提出了加快算法速度的方法。它们是保持当前最好解，每次搜索不同的区域，及改变种群后表示变量的串长（接近最优解时，缩小搜索的步长）。先用不同的方法，分别进行计算机模拟，再把上述几种方法结合，进行模拟。后一种模拟结果显示，这种方法极大地提高了遗传算法的速度，可以反它应用于某些实时控制中。     

遗传算法优化速度的改进

分析了传统变异算子的不足,提出用二元变异算子代替传统的变异算子,并讨论了它在克服早熟收敛方面的作用.同时,针对二进制编码的遗传算法的特点,提出了解码算法的隐式实现方案,使得遗传算法的寻优时间缩短6～50倍.实验从多方面对二元变异算子的遗传算法进行性能测试,结果表明,改进型算法收敛快,参数鲁棒性好,能有效地克服“早熟”收敛.通过改进变异算子和解码算法,遗传算法的优化速度得到了很大的提高.     

遗传算法及其发展动向

遗传算法是一种建立在自然选择和群体遗传学基础上的随机、迭代、进化且具有广泛适应性的参数搜索方法。介绍了遗传算法及其最新发展。     

最优保留遗传算法及其收敛性分析

最优保留ＧＡ（ＥＧＡ）是目前ＧＡ收敛性研究中比较典型的一类。在已有研究成果的基础上给出了ＥＧＡ更一般的规范化定义,指明了ＥＧＡ全局收敛的本质及其两种实现方式,并分别对它们进行了收敛性分析。最后提出一种变形的全局收敛的ＥＧＡ。     

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.     

一种快速收敛的混合遗传算法

利用遗传算法早熟的特点 ,构造出一种快速收敛的混合算法来求解优化问题 ,并分析了它的收敛性。它是使用遗传算法来生成搜索方向 ,从而保证了算法的收敛性。该算法利用遗传算法的全局搜索能力 ,并采用 Nelder- Mead单纯形法来加强算法的局部搜索能力 ,加快了算法的收敛速率。模拟实验表明 ,该方法具有高效性和鲁棒性     

一种防止浮点遗传算法早熟收敛的父代选择策略

通过对浮点遗传算法早熟收敛现象的分析，提出了一种新的父代选择策略，既使用当前代的子代个体作为下代的父代个体，可使交叉算子持续地探索和开发新空间。引入对个体的代数保护策略，即在它发生变异前保证有足够的演化，可以避免对新空间不成熟的开发。通过与其它父代选择策略的对比，并通过实验和GENOCOP系统比较，表明本方法能得到较好的结果。     

改进的蜜蜂进化型遗传算法

提出一种改进的蜜蜂进化型遗传算法.在该算法中,种群的最优个体作为蜂王与被选的每个个体(雄蜂)以一定概率进行交叉操作,从而增强了对种群最优个体所包含信息的开采能力;同时,为了避免过早收敛,算法在种群次优解周围进行局部搜索,引入新的随机个体,增加算法的多样性.实验结果表明,该算法能有效地提高遗传算法性能的求解精度和收敛速度.     

一类自适应蚁群算法及其收敛性分析

为了克服蚁群算法易陷入局部最小点的缺点,同时提高算法的收敛速度,提出一类自适应蚁群算法.该算法利用自适应改变信息激素的挥发系数改善传统蚁群算法的全局搜索能力和收敛速度.通过马尔科夫过程对算法的全局收敛性进行分析,得出该类蚁群算法全局收敛性条件.并构造出该类算法的一种信息激素更新策略,证明了这种算法全局收敛性.利用提出的算法对典型的TSP问题进行仿真研究,结果表明比典型蚁群算法在收敛速度和解的性能上都有较大改善.     

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.     

Solving a timetabling problem using hybrid genetic algorithms

All over the world, human resources are used on all kinds of different scheduling problems, many of which are time-consuming and tedious. Scheduling tools are thus very welcome. This paper presents a research project, where Genetic Algorithms (GAs) are used as the basis for solving a timetabling problem concerning medical doctors attached to an emergency service. All the doctors express personal preferences, thereby making the scheduling rather difficult. In its natural form, the timetabling problem for the emergency service is stated as a number of constraints to be fulfilled. For this reason, it was decided to compare the strength of a Co-evolutionary Constraint Satisfaction (CCS) technique with that of two other GA approaches. Distributed GAs and a simple special-purpose hill climber were introduced, to improve the performance of the three algorithms. Finally, the performance of the GAs was compared with that of some standard, nonGA approaches. The distributed hybrid GAs were by far the most successful, and one of these hybrid algorithms is currently used for solving the timetabling problem at the emergency service. © 1997 John Wiley & Sons, Ltd.     

遗传算法的几乎必然强收敛性--鞅方法

遗传算法已有的收敛性的分析大都是在概率收敛意义下考虑的且基于算法的遍历性分析，这种敛性分析不确保算法在有限步内收敛到问题的全局最优解且所获得结果不仅对带“杰出者记录策略”的算法有效。该文首次尝试运用鞅论研究遗传算法的几乎必然强收敛性，证明一大类不带“杰出者记录策略”的遗传算法能以概率1确保在有限步内达到全局最优解，所获结果为遗传算法的实际应用奠定了理论基础，且所使用的鞅论分析方法为遗传算法研究提供了全新的分析工具。     

Generalizing the notion of schema in genetic algorithms

In this paper we examine some of the fundamental assumptions which are frequently used to explain the practical success which Genetic Algorithms (GAs) have enjoyed. Specifically, the concept of schema and the Schema Theorem are interpreted from a new perspective. This allows GAs to be regarded as a constrained random walk, and offers a view which is amenable to generalization. The minimal deceptive problem (a problem designed to mislead the genetic paradigm) is analyzed in the context provided by our interpretation, where a different aspect of its difficulty emerges.     

改进遗传算法全局收敛性分析

传统的遗传算法大多数没有给出收敛性准则。一类新的改进的遗传算法被提出,该算法即考虑了优化问题的全局性要求——每一步构造一个新函数,而这往往却比局部最优理论和方法困难得多;同时通过对选择算子的改进,对遗传算法后期进化缓慢问题得到了有效控制,最后给出了算法的收敛性证明以及收敛性准则。实例证明该算法是有效的。