改进梯度算子的小生境遗传算法

为避免小生境遗传算法存在的早熟和收敛速度慢等问题,本文提出了一种改进的梯度算子,以保证进化朝最优解方向前进,提高计算峰值的精度。同时,利用进化代数和个体的适应度值,动态调整个体的交叉算子和变异算子,有效保证种群的多样性,改善全局搜索能力,加快收敛速度。将改进的梯度算子引入到基本小生境遗传算法和自适应小生境遗传算法,通过Shubert函数测试,证明本文改进后的算法与基本小生境遗传算法和自适应小生境遗传算法相比,不仅大大提高了收敛速度,并能搜索到所有全局最优解。     

用于智能组卷的自适应小生境复合遗传算法

传统遗传算法的选择策略缺乏多样性保护机制,易出现早熟收敛。为解决智能组卷问题,采取小生境技术完成遗传操作中的种群进化机制。利用个体浓度的大小,设置自适应变异算子,保证种群多样性,防止种群陷入局部收敛;增加阈值以保证算法在接近最优解时回归到自适应遗传算法,简化算法计算量,加快算法的收敛速度。本文提出一种自适应与小生境技术复合遗传算法,来均衡算法的全局搜索和局部快速开发能力。最后,实例验证了所提算法的有效性。     

非线性方程组求解的一种新方法

针对现有的非线性方程组求解方法不能同时收敛到所有解的问题,提出了一种混合小生境遗传算法的求解新方法.采用确定性拥挤小生境创造出种群的小生境进化环境,克服遗传算法的遗传漂移现象,维持种群的多样性,使算法能同时收敛到多个解;以拟牛顿算法作为遗传算法的局部搜索算子进行精确搜索,进一步提高算法收敛速度和精度.选择了几组典型的多解非线性方程组进行了求解验证,结果表明所设计的混合小生境遗传算法能在解的定义域内同时收敛到所有解,收敛速度快、精度高,是求解非线性方程组全局解的一种有效方法.     

自适应梯度小生境混合优化算法

通过对梯度法和小生境遗传算法优缺点的分析,提出了一种自适应梯度小生境混合优化算法。小生境算法利用当前种群适应度和种群代数来设计交叉算子和变异算子,保持了种群的多样性,改善全局搜索能力,应用自适应变步长梯度算法的快速寻优特点来减少运行的时间,优化极值精度,加快了收敛速度。对Shubert函数的仿真试验,证明该算法能明显的改善全局搜索能力,加快算法收敛速度。     

基于自适应小生境遗传算法的船型优化

自适应小生境遗传算法能够克服基本小生境遗传算法操作复杂和计算费时的缺陷,同时具有保持种群的稳定性,获取合适的子种群规模,从而更快地获得最优解的特点。为快速获得阻力性能优良的船型,以势流兴波阻力理论Rankine源法为基础,采用自适应小生境遗传算法并结合CAD技术进行船型优化设计。S60船型的优化算例结果表明,采用自适应小生境遗传算法进行船型优化具有可行性。     

面向多模态函数优化的自适应小生境遗传算法

为了解决小生境遗传算法不能准确识别小生境的缺陷,以及算法无法有效平衡快速收敛和保持种群多样性的冲突问题,提出一种自适应小生境遗传算法.在算法中,设计一种改进的小生境识别方法来确定小生境范围,引入用于度量种群多样性的小生境熵概念,并利用小生境熵自适应调整进化参数的取值.同时,改进选择、交叉策略,在识别的小生境基础上将交叉分为境外交叉和境内交叉,用于提高算法的全局搜索能力和局部收敛速度.实验表明,算法对于解决多模态函数优化问题具有收敛速度快和计算量小等优点,能够有效避免遗传漂移现象.     

基于个体优化的自适应小生境遗传算法

针对遗传算法在处理复杂多峰函数优化问题时易于早熟和局部搜索能力差等问题,提出一种基于个体优化的自适应小生境遗传算法。在自适应小生境的基础上,利用进化过程中相邻个体的信息产生的试探点标记的算法进化方向,缩短邻域搜索的区间,提高算法的局部搜索能力。对复杂多峰问题进行的优化实验结果证明,该算法能快速可靠地收敛到全局最优解,其收敛速度和解精度均优于简单遗传算法和其他小生境算法。     

引入进化梯度的改进小生境遗传算法

针对基本遗传算法易于早熟及局部寻优能力较差等不足,提出了一种引入进化梯度的改进小生境混合遗传算法(GNGA)。利用进化梯度信息调整个体向更优解进化,并根据进化代数自适应调整实数编码个体的交叉量和变异量,增强了局部寻优能力和解的精度。基于排挤的小生境算法的引入,保持了种群的个体多样性以克服早熟。在Shubert函数上的仿真结果表明,与小生境遗传算法相比该算法能有效提高解的精度及收敛速度,找到更多最优解。     

改进遗传算法在自动组卷中的应用研究

为了避免遗传算法在自动组卷中存在的未成熟收敛和收敛速度慢等弱点,根据群体适应值的分布特点,采用了基于小生境的改进自适应遗传算法。该算法采用模拟小生境法选择算子进行种群选取,并对交叉算子和变异算子进行了优化,实现了交叉和变异概率的非线性自适应调整。改进后的算法明显提高了组卷的成功率和收敛速度,取得了满意的组卷效果。     

基于共享机制的自适应混合遗传算法

共享机制小生境遗传算法常由于保持算法种群的多样性而减缓了全局收敛速度.针对共享机制的这个缺陷,提出了一种基于共享机制的自适应混合遗传算法.将熵的概念引入共享机制,提出了用以度量种群多样性的小生境熵的概念;构造了小生境半径和进化参数(交叉、变异概率)的自适应计算方法;设计了用于增强算法局部搜索寻优能力的扩展突变算子.最后实验表明,该算法对于解决多模态函数优化问题具有很好的全局搜索能力和较快的收敛速度,能够有效避免早熟收敛.     

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.     

A niching genetic k-means algorithm and its applications to gene expression data

Partitional clustering is a common approach to cluster analysis. Although many algorithms have been proposed, partitional clustering remains a challenging problem with respect to the reliability and efficiency of recovering high quality solutions in terms of its criterion functions. In this paper, we propose a niching genetic k-means algorithm (NGKA) for partitional clustering, which aims at reliably and efficiently identifying high quality solutions in terms of the sum of squared errors criterion. Within the NGKA, we design a niching method, which encourages mating among similar clustering solutions while allowing for some competitions among dissimilar solutions, and integrate it into a genetic algorithm to prevent premature convergence during the evolutionary clustering search. Further, we incorporate one step of k-means operation into the regeneration steps of the resulted niching genetic algorithm to improve its computational efficiency. The proposed algorithm was applied to cluster both simulated data and gene expression data and compared with previous work. Experimental results clear show that the NGKA is an effective clustering algorithm and outperforms two other genetic algorithm based clustering methods implemented for comparison.     

Niching Without Niching Parameters: Particle Swarm Optimization Using a Ring Topology

Niching is an important technique for multimodal optimization. Most existing niching methods require specification of certain niching parameters in order to perform well. These niching parameters, often used to inform a niching algorithm how far apart between two closest optima or the number of optima in the search space, are typically difficult to set as they are problem dependent. This paper describes a simple yet effective niching algorithm, a particle swarm optimization (PSO) algorithm using a ring neighborhood topology, which does not require any niching parameters. A PSO algorithm using the ring topology can operate as a niching algorithm by using individual particles' local memories to form a stable network retaining the best positions found so far, while these particles explore the search space more broadly. Given a reasonably large population uniformly distributed in the search space, PSO algorithms using the ring topology are able to form stable niches across different local neighborhoods, eventually locating multiple global/local optima. The complexity of these niching algorithms is only $ {cal O}(N)$, where $N$ is the population size. Experimental results suggest that PSO algorithms using the ring topology are able to provide superior and more consistent performance over some existing PSO niching algorithms that require niching parameters.      

A niche-elimination operation based NSGA-III algorithm for many-objective optimization

Decomposition-based multi-objective evolutionary algorithms have been found to be very promising for many-objective optimization. The recently presented non-dominated sorting genetic algorithm III (NSGA-III) employs the decomposition idea to efficiently promote the population diversity. However, due to the low selection pressure of the Pareto-dominance relation the convergence of NSGA-III could still be improved. For this purpose, an improved NSGA-III algorithm based on niche-elimination operation (we call it NSGA-III-NE) is proposed. In the proposed algorithm, an adaptive penalty distance (APD) function is presented to consider the importance of convergence and diversity in the different stages of the evolutionary process. Moreover, the niche-elimination operation is designed by exploiting the niching technique and the worse-elimination strategy. The niching technique identifies the most crowded subregion, and the worse-elimination strategy finds and further eliminates the worst individual. The proposed NSGA-III-NE is tested on a number of well-known benchmark problems with up to fifteen objectives and shows the competitive performance compared with five state-of-the-art decomposition-based algorithms. Additionally, a vector angle based selection strategy is also proposed for handling irregular Pareto fronts.     

基于改进小生境粒子群算法的多模函数优化

在基于粒子群算法的多模优化问题中,针对现存小生境方法需要特定参数的缺陷,提出了一种不需要参数的小生境算法。该算法通过粒子适应度在种群适应度中所占比例以及粒子之间的欧式距离两方面因素确定粒子的局部最优解,并通过每轮迭代中每个局部最优解粒子和以它作为局部最优解的普通粒子的欧式距离的平均值确定出该小生境的半径。在几个广泛的测试函数上的实验结果表明,该算法在收敛速度和成功率方面比需要小生境参数的算法(FERPSO、SPSO)更优秀。     

Finding multiple solutions in job shop scheduling by niching genetic algorithms

The interest in multimodal optimization methods is increasing in the last years. The objective is to find multiple solutions that allow the expert to choose the solution that better adapts to the actual conditions. Niching methods extend genetic algorithms to domains that require the identification of multiple solutions. There are different niching genetic algorithms: sharing, clearing, crowding and sequential, etc. The aim of this study is to study the applicability and the behavior of several niching genetic algorithms in solving job shop scheduling problems, by establishing a criterion in the use of different methods according to the needs of the expert. We will experiment with different instances of this problem, analyzing the behavior of the algorithms from the efficacy and diversity points of view.     

An investigation on niching multiple species based on population replacement strategies for multimodal functions optimization

This paper studies the niching mechanism based on population replacement in the process of evolution to solve the multimodal functions optimization (MMFO) problems. In order to niche multiple species for the MMFO tasks, the overlapping population replacement is surely needed because the offspring population most probably does not inherit all of the genetic information contained in its parental population, and the basic procedure for niching genetic algorithms with overlapping population replacement is presented. Then four niching schemes, the nearest neighbors replacement crowding (NNRC), the species conservation technique (SCT), the HFC-I (implicit hierarchical fair competition), and the CPE (clearing procedure with elitist) are investigated. These niching schemes are characterized with regard to different niching strategies and parameterizations, and the corresponding niching procedures are outlined. Finally, experiments are carried out on a suite of test functions to compare different niching strategies regarding niching efficiency and scalability. Experimental results illustrate the intrinsic difference of the four niching schemes. The NNRC and HFC-I have a mechanism of multiple species coevolution via adapting multiple species to different niches, while the SCT and CPE tend to make use of a mandatory mechanism to conserve species just like the grid searching over the solution space based on species distance or clearing radius. All niching methods are able to deal with complex MMFO problems, while the NNRC and HFC-I show a better performance in terms of niching efficiency and scalability, and are more robust regarding the algorithm parameterization.

Ensemble of niching algorithms

Although niching algorithms have been investigated for almost four decades as effective procedures to obtain several good and diverse solutions of an optimization problem, no effort has been reported on combining different niching algorithms to form an effective ensemble of niching algorithms. In this paper, we propose an ensemble of niching algorithms (ENA) and illustrate the concept by an instantiation which is realized using four different parallel populations. The offspring of each population is considered by all parallel populations. The instantiation is tested on a set of 16 real and binary problems and compared against the single niching methods with respect to searching ability and computation time. Results confirm that ENA method is as good as or better than the best single method in it on every test problem. Moreover, comparison with other state-of-the-art niching algorithms demonstrates the competitiveness of our proposed ENA.     

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

针对传统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.