一种基于种群划分及杂交的免疫遗传算法

在免疫遗传算法中引入免疫算子可以提高算法的收敛速率,但也会降低种群个体多样性,不利于搜索.该文提出一种基于种群划分和杂交的免疫遗传算法,通过划分种群并对种群间的最优个体进行杂交来提高算法的速率和稳定性.实验表明,该算法在性能上可提高10%左右,收敛速度快、稳定性好、精确度高.     

蜜蜂双种群进化型遗传算法

为了改善传统遗传算法的性能,由蜜蜂种群繁殖进化的方式得到启发,提出了一种蜜蜂双种群进化型遗传算法(DBPGA).算法共有两个种群,一个是通过迭代进行遗传操作得到的;另一个在每代进化过程中随机引入.每个种群中的最优个体作为蜂王分别以概率与其它个体(雄蜂)进行交配操作.既能增强对种群最优个体所包含信息的开采能力,又能提高算法的勘探能力,从而避免算法过早地收敛.实验结果表明,该算法对于改进和提高遗传算法性能及求解连续非线性规划问题是有效可行的.     

带密度加权的自适应遗传算法

为了改善传统自适应遗传算法收敛速度慢、易陷入局部最优解的情况,提出了带密度加权的自适应遗传算法. 该算法基于种群的分布密度,动态调整遗传算法的交叉概率和变异概率,并且在算法中使用了保留最佳个体法. 实验结果表明：该算法在破坏种群局部稳定性、跳出局部极值的同时,又能以较快的速度收敛于全局最优,提高了算法的实用性和鲁棒性.     

并行遗传算法收敛性分析及优化运算

经典遗传算法（Canonical Genetic Algorihms)利用单一种群对种群个体进行交叉、变异和选择操作，在进行过程中的超级个体易产生过早收敛现象，粗粒度并行遗传算法利用多个子群进行进化计算，各子群体分别独立进行遗传操作，相互交换最优个体后继续进化。文证明了该算法的搜索过程是一个有限时齐遍历马尔柯夫链，给出粗粒度并行遗传算法全局最优收敛性证明。对于旅行商问题TSP（Traveling Salesman Problem)利用粗粒度并行遗传算法进行了求解，以解决经典遗传算法的收敛到局部最优值问题。仿真结果表明，算法的收敛性能优于经典遗传算法。     

双精英协同进化遗传算法

针对传统遗传算法早熟收敛和收敛速度慢的问题,提出一种双精英协同进化遗传算法(double elite coevolutionary genetic algorithm,简称DECGA).该算法借鉴了精英策略和协同进化的思想,选择两个相异的、高适应度的个体(精英个体)作为进化操作的核心,两个精英个体分别按照不同的评价函数来选择个体,组成各自的进化子种群.两个子种群分别采用不同的进化策略,以平衡算法的勘探和搜索能力.理论分析证明,该算法具有全局收敛性.通过对测试函数的实验,其结果表明,该算法能搜索到几乎所有测试函数的最优解,同时能够有效地保持种群的多样性.与已有算法相比,该算法在收敛速度和搜索全局最优解上都有了较大的改进和提高.     

多源扩散蚁群遗传算法

传统的遗传算法在处理多模态函数优化问题时,容易出现早熟收敛,并且局部搜索能力不强.根据蚁群信息素扩散和小生境思想,提出了一种多源扩散蚁群遗传算法.该算法采用了多源选取和保留机制,在每一代种群的个体中选出多个源中心点,并把这些点保留至下一代种群;同时每个源中心点都产生和扩散信息素以指导个体寻优.与简单遗传算法,模拟退火遗传算法和小生境遗传算法进行对比实验,数据表明该算法能搜索到更好的全局最优解,收敛速度更快.     

一种基于蜜蜂双种群进化的遗传算法

提出了一种基于蜜蜂双种群进化的遗传算法（BDPGA）。算法共有两个种群,一个是通过迭代进行遗传操作得到的,一个是在每代进化过程中随机引入的。每个种群中的最优个体作为蜂王分别以概率与其它个体（雄蜂）进行交配操作。既能增强对种群最优个体所包含信息的开采能力,又能提高算法的勘探能力,从而避免算法过早地收敛。实验结果表明,该算法对于改进和提高遗传算法性能是有效可行的。     

一种新的种群数自适应遗传算法*

针对简单遗传算法存在早收敛和在进化后期搜索效率较低的缺点,提出了一种新的种群数自适应遗传算法。该算法在对进化种群数进行宏观调控的同时,再用个体寿命限制个体的生存期,实现对种群数的微观调控。实验数据表明,该算法具有比简单遗传算法好的收敛性能。     

基于种群优化的遗传算法的MUSIC谱峰搜索技术

传统MUSIC算法的谱峰搜索过程中计算量较大,导致其实时性较差.为了改善这一缺陷,将蜜蜂种群繁殖进化的过程进行抽象化,提出一种基于种群优化的遗传算法(IPGA),并将其与MUSIC谱峰搜索相结合.该算法中,种群的最优个体作为蜂王与被选中的个体以一定概率进行交叉操作,从而增强了对种群最优个体所包含信息的开采能力;同时,为了避免过早收敛,算法在种群次优解周围进行局部搜索,引入新的个体,增加种群个体的多样性;使用分阶段调整的策略对种群规模进行动态调控.由于种群规模的渐进式变化,不但保证了种群的多样性,同时提高了算法克服未成熟收敛的能力.通过实验数据可以证明该方法具有很好的全局搜索能力,可以对多个目标进行搜索.同时,通过计算量的分析,证明与传统方法相比,该算法通过极大地降低计算量而获得了较好的实时性.     

求解带时间窗车辆路径问题的混沌遗传算法

针对遗传算法随机性大、末成熟收敛等缺点,提出了将混沌搜索技术和遗传算法相耦合的混沌遗传算法来求解带时间窗的物流配送车辆路径问题(VRPTW)。该算法将混沌变量映射到优化变量的取值范围中,把得到的混沌变量进行编码生成初始种群,然后在遗传操作进行之后对优秀个体增加混沌扰动,促进种群的进化收敛速度,得到最优解。实例计算结果与其他算法比较表明,该算法在求解VRPTW问题时,搜索效率高,能以较快的速度收敛于全局最优解,为求解VRPTW问题提供了一种新方法。     

A new query reweighting method for document retrieval based on genetic algorithms

In this paper, we present a new method for query reweighting to deal with document retrieval. The proposed method uses genetic algorithms to reweight a user's query vector, based on the user's relevance feedback, to improve the performance of document retrieval systems. It encodes a user's query vector into chromosomes and searches for the optimal weights of query terms for retrieving documents by genetic algorithms. After the best chromosome is found, the proposed method decodes the chromosome into the user's query vector for dealing with document retrieval. The proposed query reweighting method can find the best weights of query terms in the user's query vector, based on the user's relevance feedback. It can increase the precision rate and the recall rate of the document retrieval system for dealing with document retrieval.     

基于量子染色体评估的演化算法

提出一种基于量子染色体评估的演化算法(Evolutionary Algorithm Based on Evaluating Quantum Chromosomes,简称EQEA)。提出了染色体评估、自适应调整旋转角度和分组调整策略。旋转角度的方向和大小由评估量子染色体得到的二进制个体和组内当前最优个体确定,且随着演化的过程自适应调整。实例验证,EQEA在函数优化和背包问题上都有优异性能。该算法在单染色体下也能取得很好的效果。     

Parallel Mesh Algorithms for Grid Graph Shortest Paths with Application to Separation of Touching Chromosomes

The grid graph shortest path problem has many applications. In this paper, we present practical mesh algorithms using a local cost-reducing operation for various forms of the grid graph shortest path problem. The algorithms are very simple and can easily mark the vertices on shortest paths between any two vertices. The time complexity of the algorithm is proportional to the maximum length of the shortest paths with a very small multiplicative constant. Also in this paper, we discuss the application of the parallel algorithms in automatic chromosome analysis to intelligently split touching chromosomes. We identify local features useful for finding a potential path to separate touching chromosomes. We then define a distance measure based on the local features and find the best splitting path to cut touching chromosomes. The splitting algorithm only uses local information and is highly parallel.     

Co-evolutionary genetic algorithm for fuzzy flexible job shop scheduling

Fuzzy flexible job shop scheduling problem (FfJSP) is the combination of fuzzy scheduling and flexible scheduling in job shop environment, which is seldom investigated for its high complexity. We developed an effective co-evolutionary genetic algorithm (CGA) for the minimization of fuzzy makespan. In CGA, the chromosome of a novel representation consists of ordered operation list and machine assignment string, a new crossover operator and a modified tournament selection are proposed, and the population of job sequencing and the population of machine assignment independently evolve and cooperate for converging to the best solutions of the problem. CGA is finally applied and compared with other algorithms. Computational results show that CGA outperforms those algorithms compared.     

GAKREM: A novel hybrid clustering algorithm

We introduce a novel clustering algorithm named GAKREM (Genetic Algorithm K-means Logarithmic Regression Expectation Maximization) that combines the best characteristics of the K-means and EM algorithms but avoids their weaknesses such as the need to specify a priori the number of clusters, termination in local optima, and lengthy computations. To achieve these goals, genetic algorithms for estimating parameters and initializing starting points for the EM are used first. Second, the log-likelihood of each configuration of parameters and the number of clusters resulting from the EM is used as the fitness value for each chromosome in the population. The novelty of GAKREM is that in each evolving generation it efficiently approximates the log-likelihood for each chromosome using logarithmic regression instead of running the conventional EM algorithm until its convergence. Another novelty is the use of K-means to initially assign data points to clusters. The algorithm is evaluated by comparing its performance with the conventional EM algorithm, the K-means algorithm, and the likelihood cross-validation technique on several datasets.     

A deterministic annular crossover genetic algorithm optimisation for the unit commitment problem

One of the disadvantages of traditional genetic algorithms is premature convergence because the selection operator depends on the quality of the individual, with the result that the genetic information of the best individuals tends to dominate the characteristics of the population. Furthermore, when the representation of the chromosome is linear, the crossover is sensitive to the encoding or depends on the gene position. The ends of this type of chromosome have only a very low probability of changing by mutation. In this work a genetic algorithm is applied to the unit commitment problem using a deterministic selection operator, where all the individuals of the population are selected as parents according to an established strategy, and an annular crossover operator where the chromosome is in the shape of a ring. The results obtained show that, with the application of the proposed operators to the unit commitment problem, better convergences and solutions are obtained than with the application of traditional genetic operators.     

Effects of different chromosome representations in developing genetic algorithms to solve DFJS scheduling problems

This paper attempts to compare the effect of using different chromosome representations while developing a genetic algorithm to solve a scheduling problem called DFJS (distributed flexible job shop scheduling) problem. The DFJS problem is strongly NP-hard; most recent prior studies develop various genetic algorithms (GAs) to solve the problems. These prior GAs are similar in the algorithmic flows, but are different in proposing different chromosome representations. Extending from this line, this research proposes a new chromosome representation (called S_OP) and develops a genetic algorithm (called GA_OP) to solve the DFJS problem. Experiment results indicate that GA_OP outperforms all prior genetic algorithms. This research advocates the importance of developing appropriate chromosome representations while applying genetic algorithms (or other meta-heuristic algorithms) to solve a space search problem, in particular when the solution space is high-dimensional.     

Cooperative-Competitive Algorithms for Evolutionary Networks Classifying Noisy Digital Images

We describe an efficient method of combining the global search of genetic algorithms (GAs) with the local search of gradient descent algorithms. Each technique optimizes a mutually exclusive subset of the network's weight parameters. The GA chromosome fixes the feature detectors and their location, and a gradient descent algorithm starting from random initial values optimizes the remaining weights. Three algorithms having different methods of encoding hidden unit weights in the chromosome are applied to multilayer perceptrons (MLPs) which classify noisy digital images. The fitness function measures the MLP classification accuracy together with the confidence of the networks.     

一种组合测试用例生成的可配置混合算法

组合测试是一种经过实践证明的科学有效的测试方法,其研究重点之一是组合测试用例集的生成算法。基于参数顺序渐进扩充策略IPO(In-Parameter-Order)是其中一种具有代表性的通用算法,其优势在于水平扩充算法的可选择性和测试用例集的可扩展性。算法在提取影响IPO策略效果的参数的基础上,给出可配置的IPO策略;采用遗传算法(Genctic-Algorithm)配置IPO策略中的水平扩充,得到新的混合算法IPO_GA。通过实验对可配置IPO策略中各个参数对算法的影响进行了对比分析;将IPO_ GA与部分已有算法进行了比较,结果表明在水平扩充过程中染色体较短时,IPO_GA效果较好;在解空间规模过大而导致染色体较长时,IPO_GA效果略差。     

A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops

Obtaining an optimal solution for a permutation flowshop scheduling problem with the total flowtime criterion in a reasonable computational timeframe using traditional approaches and optimization tools has been a challenge. This paper presents a discrete artificial bee colony algorithm hybridized with a variant of iterated greedy algorithms to find the permutation that gives the smallest total flowtime. Iterated greedy algorithms are comprised of local search procedures based on insertion and swap neighborhood structures. In the same context, we also consider a discrete differential evolution algorithm from our previous work. The performance of the proposed algorithms is tested on the well-known benchmark suite of Taillard. The highly effective performance of the discrete artificial bee colony and hybrid differential evolution algorithms is compared against the best performing algorithms from the existing literature in terms of both solution quality and CPU times. Ultimately, 44 out of the 90 best known solutions provided very recently by the best performing estimation of distribution and genetic local search algorithms are further improved by the proposed algorithms with short-term searches. The solutions known to be the best to date are reported for the benchmark suite of Taillard with long-term searches, as well.