An improved genetic algorithm (GA) is proposed based on the analysis of population diversity within the framework of Markov chain. The chaos operator to combat premature convergence concerning two goals of maintaining...An improved genetic algorithm (GA) is proposed based on the analysis of population diversity within the framework of Markov chain. The chaos operator to combat premature convergence concerning two goals of maintaining diversity in the population and sustaining the convergence capacity of the GA is introduced. In the CHaos Genetic Algorithm (CHGA), the population is recycled dynamically whereas the most highly fit chromosome is intact so as to restore diversity and reserve the best schemata which may belong to the optimal solution. The characters of chaos as well as advanced operators and parameter settings can improve both exploration and exploitation capacities of the algorithm. The results of multimodal function optimization show that CHGA performs simple genetic algorithms and effectively alleviates the problem of premature convergence.展开更多
Considering premature convergence in the searching process of genetic algorithm, a chaotic migration-based pseudo parallel genetic algorithm (CMPPGA) is proposed, which applies the idea of isolated evolution and infor...Considering premature convergence in the searching process of genetic algorithm, a chaotic migration-based pseudo parallel genetic algorithm (CMPPGA) is proposed, which applies the idea of isolated evolution and information exchanging in distributed Parallel Genetic Algorithm by serial program structure to solve optimization problem of low real-time demand. In this algorithm, asynchronic migration of individuals during parallel evolution is guided by a chaotic migration sequence. Information exchanging among sub-populations is ensured to be efficient and sufficient due to that the sequence is ergodic and stochastic. Simulation study of CMPPGA shows its strong global search ability, superiority to standard genetic algorithm and high immunity against premature convergence. According to the practice of raw material supply, an inventory programming model is set up and solved by CMPPGA with satisfactory results returned.展开更多
The standard genetic algorithm has limitations of a low convergence rate and premature convergence in solving the job-shop scheduling problem.To overcome these limitations,this paper presents a new improved hybrid gen...The standard genetic algorithm has limitations of a low convergence rate and premature convergence in solving the job-shop scheduling problem.To overcome these limitations,this paper presents a new improved hybrid genetic algorithm on the basis of the idea of graft in botany.Through the introduction of a grafted population and crossover probability matrix,this algorithm accelerates the convergence rate greatly and also increases the ability to fight premature convergence.Finally,the approach is tested on a set of standard instances taken from the literature and compared with other approaches.The computation results validate the effectiveness of the proposed algorithm.展开更多
The mutation operator has been seldom improved because ressearchers hardly suspect its ability to prevent genetic algorithm(GA) from converging prematurely.Due to its importance to GA,the authors of this paper study i...The mutation operator has been seldom improved because ressearchers hardly suspect its ability to prevent genetic algorithm(GA) from converging prematurely.Due to its importance to GA,the authors of this paper study influence on the diversity of genes in the same locus,and point out that traditional mutation,to some extent,can result in premature convergence of genes(PCG) in the same locus.The above drawback of the traditional mutation operator causes the loss of critical alleles.Inspired by digital technique,we introduce two kinds of boolean operation into GA to develop a novel mutation operator and discuss its contribution of preventing the loss of critical alleles.The experimental results of function optimizatioin show that the improved mutation operator can effectively prevent premature convegence,and can provide a wide selection range of control parameters for GA.展开更多
The identification and characteristics of premature convergence in genetic algorithms (GAs) are investigated Through a detailed quantitative analysis on the search capability and the degree of population diversity, th...The identification and characteristics of premature convergence in genetic algorithms (GAs) are investigated Through a detailed quantitative analysis on the search capability and the degree of population diversity, the cause of premature convergence in GAs is recognized, and attributed to the maturation effect of the GAs: The minimum schema deduced from current population, which is the largest search space of a GA, converges to a homogeneous population in probability 1 ( so the search capability of the GA decreases and premature convergence occurs). It is shown that, as quantitative features of the maturation effect, the degree of population diversity converges to zero with probability 1, and the tendency for premature convergence is inversely proportional to the population size and directly proportional to the variance of the fitness ratio of zero allele at any gene position of the current population. Based on the theoretical analysis, several strategies for preventing premature convergence are展开更多
基金The National Natural Science Foundation of China !(No .699740 43 )
文摘An improved genetic algorithm (GA) is proposed based on the analysis of population diversity within the framework of Markov chain. The chaos operator to combat premature convergence concerning two goals of maintaining diversity in the population and sustaining the convergence capacity of the GA is introduced. In the CHaos Genetic Algorithm (CHGA), the population is recycled dynamically whereas the most highly fit chromosome is intact so as to restore diversity and reserve the best schemata which may belong to the optimal solution. The characters of chaos as well as advanced operators and parameter settings can improve both exploration and exploitation capacities of the algorithm. The results of multimodal function optimization show that CHGA performs simple genetic algorithms and effectively alleviates the problem of premature convergence.
文摘Considering premature convergence in the searching process of genetic algorithm, a chaotic migration-based pseudo parallel genetic algorithm (CMPPGA) is proposed, which applies the idea of isolated evolution and information exchanging in distributed Parallel Genetic Algorithm by serial program structure to solve optimization problem of low real-time demand. In this algorithm, asynchronic migration of individuals during parallel evolution is guided by a chaotic migration sequence. Information exchanging among sub-populations is ensured to be efficient and sufficient due to that the sequence is ergodic and stochastic. Simulation study of CMPPGA shows its strong global search ability, superiority to standard genetic algorithm and high immunity against premature convergence. According to the practice of raw material supply, an inventory programming model is set up and solved by CMPPGA with satisfactory results returned.
文摘The standard genetic algorithm has limitations of a low convergence rate and premature convergence in solving the job-shop scheduling problem.To overcome these limitations,this paper presents a new improved hybrid genetic algorithm on the basis of the idea of graft in botany.Through the introduction of a grafted population and crossover probability matrix,this algorithm accelerates the convergence rate greatly and also increases the ability to fight premature convergence.Finally,the approach is tested on a set of standard instances taken from the literature and compared with other approaches.The computation results validate the effectiveness of the proposed algorithm.
文摘The mutation operator has been seldom improved because ressearchers hardly suspect its ability to prevent genetic algorithm(GA) from converging prematurely.Due to its importance to GA,the authors of this paper study influence on the diversity of genes in the same locus,and point out that traditional mutation,to some extent,can result in premature convergence of genes(PCG) in the same locus.The above drawback of the traditional mutation operator causes the loss of critical alleles.Inspired by digital technique,we introduce two kinds of boolean operation into GA to develop a novel mutation operator and discuss its contribution of preventing the loss of critical alleles.The experimental results of function optimizatioin show that the improved mutation operator can effectively prevent premature convegence,and can provide a wide selection range of control parameters for GA.
基金Project supported by the National Natural Science Foundation of China.
文摘The identification and characteristics of premature convergence in genetic algorithms (GAs) are investigated Through a detailed quantitative analysis on the search capability and the degree of population diversity, the cause of premature convergence in GAs is recognized, and attributed to the maturation effect of the GAs: The minimum schema deduced from current population, which is the largest search space of a GA, converges to a homogeneous population in probability 1 ( so the search capability of the GA decreases and premature convergence occurs). It is shown that, as quantitative features of the maturation effect, the degree of population diversity converges to zero with probability 1, and the tendency for premature convergence is inversely proportional to the population size and directly proportional to the variance of the fitness ratio of zero allele at any gene position of the current population. Based on the theoretical analysis, several strategies for preventing premature convergence are
