自适应小生态遗传算法的理论分析和加速技术

提出了联赛选择和相似个体概率替换的自适应小生态遗传算法，建立了小生态生长的动力学模型．平衡态理论分析和仿其实验表明，概率联赛小生态技术选择能够形成和维持稳定的子种群．提出了种群聚类分割和单纯形搜索的并行局部搜索算于，定性地分析了其搜索性能．对复杂多峰问题的优化结果表明，结合概率联赛选择和并行局部搜索算子的小生态遗传算法不但能够快速可靠地收敛到全局最优解，且能并行地搜索到多个局部最优解，其收敛速度和全局收敛可靠性均显著地优于简单遗传算法和其它小生态方法．     

基于聚类的伪并行遗传算法

针对遗传算法中存在的早熟收敛和后期收敛速度慢的问题,分析传统的小生境遗传算法和多种群遗传算法的特点和不足,提出基于聚类的伪并行遗传算法.当种群进化到一定程度后,进行聚类分析.在各个聚类内部,利用局部搜索算法获得极值点.其余未分类个体与聚类代表元按照小生境技术进一步搜索,从而获得较好的全局探索能力.从理论上证明该算法的收敛性.采用典型函数进行实例计算,并与杰出保留遗传算法、确定性排挤遗传算法和传统的多种群遗传算法的性能进行比较,结果表明本文算法的有效性.     

基于适应值共享的多生境排挤遗传算法

针对优化多模函数时单纯使用共享和排挤机制的遗传算法所存在的缺陷,提出了基于适应值共享的多生境排挤遗传算法。基本思想是：按照共享的思想在对个体的适应值进行调整的同时,将排挤选择和相似个体中适应度最差个体被替换的策略分别应用于选择算子和群体的进化中。理论分析和数值实验表明,该算法很好地维持了种群多样性,对于各类多峰函数具有较强的搜索能力。     

适应值共享拥挤遗传算法

保持遗传算法在演化过程中的种群多样性,是将遗传算法成功应用于解决多峰优化问题和多目标优化问题的关键。适应值共享遗传算法和拥护遗传算法分别从不同角度改善了遗传算法的搜索能力,是寻找多个最优解的常用算法。将这两种算法的优点加以结合,提出适应值共享拥护遗传算法。数值测试结果表明,该算法比标准适应值共享遗传算法和确定性拥挤遗传算法具有更强的搜索能力。     

基于混合并行遗传算法的文本聚类研究

针对传统K-Means聚类算法对初始聚类中心的选择敏感,易陷入局部最优解的问题,提出一种基于混合并行遗传算法的文本聚类方法。该方法首先将文档集合表示成向量空间模型,并在文档向量中随机选择初始聚类中心形成染色体,然后结合K-Means算法的高效性和并行遗传算法的全局优化能力,通过种群内的遗传、变异和种群间的并行进化、联姻,有效地避免了局部最优解的出现。实验表明该算法相对于K-Means算法、简单遗传算法等文本聚类方法具有更高的精确度和全局寻优能力。     

对适应值共享遗传算法的分类及评价

针对多峰函数优化问题先后出现了一系列适应值共享类的遗传算法.这些算法都需要事先提供某种信息.本文基于事先提供信息的区别提出了一种新的适应值共享类遗传算法的分类方法,并通过一个复杂的标准测试问题对这些算法进行了比较和评价,结果表明在各种算法中,清除算法、动态小生境共享算法和新聚类适应值共享算法具有较高的搜索能力和优化速度.本文的工作对于这些适应值共享类遗传算法的应用和进一步改进具有指导意义.     

一种基于相似性排挤的多种群混合遗传算法

在遗传算法优化的研究中,针对简单遗传算法存在的局部搜索能力差和早熟收敛的问题,提出一种相似性排挤的多种群混合遗传算法.新算法主要在宏观上设置多个子种群与一个最优保存种群的进化架构,并在子种群中引入模拟退火算法,构成合理的混合结构,用于提高算法的局部搜索能力.在微观方面,个体在子种群间交流时采取相似性评判标准,进而实施排挤替换操作,维护种群多样性,用于改善算法的早熟收敛问题.最后,通过对TSP问题的求解,验证算法的有效性与实用性.     

基于加权二叉树的自适应遗传算法研究

为改进传统遗传算法局部搜索能力较差、收敛速度慢等缺点,提出一种基于加权二叉树的遗传算法.通过构建遗传基因二叉树,对种群染色体进行编码,根据子代基因的适应值挑选优秀基因替换弱势基因,采用蚁群信息素对不同的遗传基因进行加权操作,依权重择优进行交叉操作,利用自适应排序选择最优解,并通过对比实验对该算法和基本遗传算法进行了全方位的比较.试验结果表明该算法大大提高了遗传算法的局部搜索能力,加快了算法的收敛速度.     

基于并行遗传算法的K-means聚类研究

针对传统K-means聚类算法对初始聚类中心的选择敏感,以及聚类数K难以确定的问题,提出一种基于并行遗传算法的K-means聚类方法.该方法采用一种新型的可变长染色体编码方案,随机选择样本点作为初始聚类中心形成染色体,然后结合K-means算法的高效性和并行遗传算法的全局优化能力,通过种群内的遗传、变异和种群间的并行进化、联姻,有效地避免了局部最优解的出现,同时得到了优化的聚类数目和聚类结果.实验表明该方法是一种精确高效的聚类方法.     

基于均匀分割的多种群并行遗传算法

针对标准遗传算法在处理多峰函数优化问题时易出现的成熟前收敛现象，在讨论了模式样本分布特点的基础上，提出了一种通过均匀分割对种群分类的多种群并行遗传算法。由均匀分割可以得到几个既不重叠又都能反映函数整体性质的子空间，在这些子空间上并行搜索最优解，同时将每一代在各自空间上搜索到的优秀个体集中在一起，进而在全空间上搜索最优解的具体位置。由于在这些子空间上的搜索是彼此独立的，所以同时发生“早熟”现象的机会大大降低。理论分析和对多峰函数的仿真结果均表明，该算法在不影响收敛速度的条件下，发生成熟前收敛的概率明显下降。     

The crowding approach to niching in genetic algorithms

A wide range of niching techniques have been investigated in evolutionary and genetic algorithms. In this article, we focus on niching using crowding techniques in the context of what we call local tournament algorithms. In addition to deterministic and probabilistic crowding, the family of local tournament algorithms includes the Metropolis algorithm, simulated annealing, restricted tournament selection, and parallel recombinative simulated annealing. We describe an algorithmic and analytical framework which is applicable to a wide range of crowding algorithms. As an example of utilizing this framework, we present and analyze the probabilistic crowding niching algorithm. Like the closely related deterministic crowding approach, probabilistic crowding is fast, simple, and requires no parameters beyond those of classical genetic algorithms. In probabilistic crowding, subpopulations are maintained reliably, and we show that it is possible to analyze and predict how this maintenance takes place. We also provide novel results for deterministic crowding, show how different crowding replacement rules can be combined in portfolios, and discuss population sizing. Our analysis is backed up by experiments that further increase the understanding of probabilistic crowding.     

多模态函数优化的拥挤聚类遗传算法

对多模态函数优化问题，分析了各种小生境策略；将拥挤模型与聚类算法相结合，提出了一种拥挤聚类遗传算法．拥挤模型在适应值曲面上形成多个小生境，聚类算法消除了每个小生境内部的基因漂移现象．理论分析证明了算法的收敛性能．数值实例表明，拥挤聚类模型在多极值搜索的数量、质量和精度上都优于拥挤模型与确定性拥挤模型．将拥挤聚类遗传算法应用于国家同步辐射实验室变间距全息光栅的设计，取得了满意的效果．     

Crowding clustering genetic algorithm for multimodal function optimization

Interest in multimodal function optimization is expanding rapidly since real-world optimization problems often require location of multiple optima in a search space. In this paper, we propose a novel genetic algorithm which combines crowding and clustering for multimodal function optimization, and analyze convergence properties of the algorithm. The crowding clustering genetic algorithm employs standard crowding strategy to form multiple niches and clustering operation to eliminate genetic drift. Numerical experiments on standard test functions indicate that crowding clustering genetic algorithm is superior to both standard crowding and deterministic crowding in quantity, quality and precision of multi-optimum search. The proposed algorithm is applied to the practical optimal design of varied-line-spacing holographic grating and achieves satisfactory results.     

一种基于小生境遗传算法的中文文本聚类新方法

针对传统c-均值等算法在文本聚类中的缺陷，提出了一种基于小生境遗传算法的中文文本聚类新方法，将文本集的聚类问题转化垄多峰函数的优化问题。以多峰函数的峰值代表文本的聚类中心，聚类的数目不必预先给定。描述了该聚类方法实现文本聚类时适应值函数的构造方法以及小生境半径的动态估计方法。实验结果表明，该方法提高了文本聚类的平均准确率。     

A Review of Niching Genetic Algorithms for Multimodal Function Optimization

In this paper, a comprehensive review of approaches to solve multimodal function optimization problems via genetic niching algorithms is provided. These algorithms are presented according to their space–time classification. Methods based on fitness sharing and crowding methods are described in detail as they are the most frequently used.     

A review: accuracy optimization in clustering ensembles using genetic algorithms

The clustering ensemble has emerged as a prominent method for improving robustness, stability, and accuracy of unsupervised classification solutions. It combines multiple partitions generated by different clustering algorithms into a single clustering solution. Genetic algorithms are known as methods with high ability to solve optimization problems including clustering. To date, significant progress has been contributed to find consensus clustering that will yield better results than existing clustering. This paper presents a survey of genetic algorithms designed for clustering ensembles. It begins with the introduction of clustering ensembles and clustering ensemble algorithms. Subsequently, this paper describes a number of suggested genetic-guided clustering ensemble algorithms, in particular the genotypes, fitness functions, and genetic operations. Next, clustering accuracies among the genetic-guided clustering ensemble algorithms is compared. This paper concludes that using genetic algorithms in clustering ensemble improves the clustering accuracy and addresses open questions subject to future research.     

Model-Based Clustering by Probabilistic Self-Organizing Maps

In this paper, we consider the learning process of a probabilistic self-organizing map (PbSOM) as a model-based data clustering procedure that preserves the topological relationships between data clusters in a neural network. Based on this concept, we develop a coupling-likelihood mixture model for the PbSOM that extends the reference vectors in Kohonen's self-organizing map (SOM) to multivariate Gaussian distributions. We also derive three expectation-maximization (EM)-type algorithms, called the SOCEM, SOEM, and SODAEM algorithms, for learning the model (PbSOM) based on the maximum-likelihood criterion. SOCEM is derived by using the classification EM (CEM) algorithm to maximize the classification likelihood; SOEM is derived by using the EM algorithm to maximize the mixture likelihood; and SODAEM is a deterministic annealing (DA) variant of SOCEM and SOEM. Moreover, by shrinking the neighborhood size, SOCEM and SOEM can be interpreted, respectively, as DA variants of the CEM and EM algorithms for Gaussian model-based clustering. The experimental results show that the proposed PbSOM learning algorithms achieve comparable data clustering performance to that of the deterministic annealing EM (DAEM) approach, while maintaining the topology-preserving property.     

基于排挤遗传算法的入侵检测方法

传统遗传算法在入侵检测系统中构造的规则单一,导致检测率低,为了构造更加精确和完备的入侵规则,提出了一种基于确定性排挤遗传的规则构造算法,该算法使用确定性排挤来产生下一代种群,能够有效保持种群多样性,获得全部最优解。给出了算法的步骤和仿真,以网络数据集KDDCup99为对象,详细分析了利用该算法来生成入侵规则的具体实现过程,对染色体编码和适应度函数进行了设计和实现。最后通过实验证明了此算法的有效性,可以较好地获得入侵检测规则。     

一种高维数据聚类遗传算法

聚类分析是数据挖掘中的一个重要研究课题。在许多实际应用中,聚类分析的数据往往具有很高的维度,例如文档数据、基因微阵列等数据可以达到上千维,而在高维数据空间中,数据的分布较为稀疏。受这些因素的影响,许多对低维数据有效的经典聚类算法对高维数据聚类常常失效。针对这类问题,本文提出了一种基于遗传算法的高维数据聚类新方法。该方法利用遗传算法的全局搜索能力对特征空间进行搜索,以找出有效的聚类特征子空间。同时,为了考察特征维在子空间聚类中的特征,本文设计出一种基于特征维对子空间聚类贡献率的适应度函数。人工数据、真实数据的实验结果以及与k-means算法的对比实验证明了该方法的可行性和有效性。