A comparative study on the performance of dissortative mating and immigrants-based strategies for evolutionary dynamic optimization

Traditional Genetic Algorithms (GAs) mating schemes select individuals for crossover independently of their genotypic or phenotypic similarities. In Nature, this behavior is known as random mating. However, non-random protocols, in which individuals mate according to their kinship or likeness, are more common in natural species. Previous studies indicate that when applied to GAs, dissortative mating - a type of non-random mating in which individuals are chosen according to their similarities - may improve their performance (on both speed and reliability). Dissortative mating maintains genetic diversity at a higher level during the run, a fact that is frequently observed as a possible cause of dissortative GAs’ ability to escape local optima. Dynamic optimization demands a special attention when designing and tuning a GA, since diversity plays an even more crucial role than it does when tackling static ones. This paper investigates the behavior of the Adaptive Dissortative Mating GA (ADMGA) in dynamic problems and compares it to GAs based on random immigrants. ADMGA selects parents according to their Hamming distance, via a self-adjustable threshold value. The method, by keeping population diversity during the run, provides an effective means to deal with dynamic problems. Tests conducted with dynamic trap functions and dynamic versions of Road Royal and knapsack problems indicate that ADMGA is able to outperform other GAs on a wide range of tests, being particularly effective when the frequency of changes is low. Specifically, ADMGA outperforms two state-of-the-art algorithms on many dynamic scenarios. In addition, and unlike preceding dissortative mating GAs and other evolutionary techniques for dynamic optimization, ADMGA self-regulates the intensity of the mating restrictions and does not increase the set of parameters in GAs, thus being easier to tune.     

Multi-objective genetic local search algorithm using Kohonen’s neural map

Genetic Algorithms (GAs) are population based global search methods that can escape from local optima traps and find the global optima regions. However, near the optimum set their intensification process is often inaccurate. This is because the search strategy of GAs is completely probabilistic. With a random search near the optimum sets, there is a small probability to improve current solution. Another drawback of the GAs is genetic drift. The GAs search process is a black box process and no one knows that which region is being searched by the algorithm and it is possible that GAs search only a small region in the feasible space. On the other hand, GAs usually do not use the existing information about the optimality regions in past iterations.In this paper, a new method called SOM-Based Multi-Objective GA (SBMOGA) is proposed to improve the genetic diversity. In SBMOGA, a grid of neurons use the concept of learning rule of Self-Organizing Map (SOM) supporting by Variable Neighborhood Search (VNS) learn from genetic algorithm improving both local and global search. SOM is a neural network which is capable of learning and can improve the efficiency of data processing algorithms. The VNS algorithm is developed to enhance the local search efficiency in the Evolutionary Algorithms (EAs). The SOM uses a multi-objective learning rule based-on Pareto dominance to train its neurons. The neurons gradually move toward better fitness areas in some trajectories in feasible space. The knowledge of optimum front in past generations is saved in form of trajectories. The final state of the neurons determines a set of new solutions that can be regarded as the probability density distribution function of the high fitness areas in the multi-objective space. The new set of solutions potentially can improve the GAs overall efficiency. In the last section of this paper, the applicability of the proposed algorithm is examined in developing optimal policies for a real world multi-objective multi-reservoir system which is a non-linear, non-convex, multi-objective optimization problem.     

GA-TSKfnn: Parameters tuning of fuzzy neural network using genetic algorithms

Fuzzy logic allows mapping of an input space to an output space. The mechanism for doing this is through a set of IF-THEN statements, commonly known as fuzzy rules. In order for a fuzzy rule to perform well, the fuzzy sets must be carefully designed. A major problem plaguing the effective use of this approach is the difficulty of automatically and accurately constructing the membership functions. Genetic Algorithms (GAs) is a technique that emulates biological evolutionary theories to solve complex optimization problems. Genetic Algorithms provide an alternative to our traditional optimization techniques by using directed random searches to derive a set of optimal solutions in complex landscapes. GAs literally searches towards the two end of the search space in order to determine the optimum solutions. Populations of candidate solutions are evaluated to determine the best solution. In this paper, a hybrid system combining a Fuzzy Inference System and Genetic Algorithms—a Genetic Algorithms based Takagi-Sugeno-Kang Fuzzy Neural Network (GA-TSKfnn) is proposed to tune the parameters in the Takagi-Sugeno-Kang fuzzy neural network. The aim is to reduce unnecessary steps in the parameters sets before they can be fed into the network. Modifications are made to various layers of the network to enhance the performance. The proposed GA-TSKfnn is able to achieve higher classification rate when compared against traditional neuro-fuzzy classifiers.     

Deriving operating policies for multi-objective reservoir systems: Application of Self-Learning Genetic Algorithm

Optimal multi-reservoir operation is a multi-objective problem in nature and some of its objectives are nonlinear, non-convex and multi-modal functions. There are a few areas of application of mathematical optimization models with a richer or more diverse history than in reservoir systems optimization. However, actual implementations remain limited or have not been sustained.Genetic Algorithms (GAs) are probabilistic search algorithms that are capable of solving a variety of complex multi-objective optimization problems, which may include non-linear, non-convex and multi-modal functions. GA is a population based global search method that can escape from local optima traps and find the global optima. However GAs have some drawbacks such as inaccuracy of the intensification process near the optimal set.In this paper, a new model called Self-Learning Genetic Algorithm (SLGA) is presented, which is an improved version of the SOM-Based Multi-Objective GA (SBMOGA) presented by Hakimi-Asiabar et al. (2009) [45]. The proposed model is used to derive optimal operating policies for a three-objective multi-reservoir system. SLGA is a new hybrid algorithm which uses Self-Organizing Map (SOM) and Variable Neighborhood Search (VNS) algorithms to add a memory to the GA and improve its local search accuracy. SOM is a neural network which is capable of learning and can improve the efficiency of data processing algorithms. The VNS algorithm can enhance the local search efficiency in the Evolutionary Algorithms (EAs).To evaluate the applicability and efficiency of the proposed methodology, it is used for developing optimal operating policies for the Karoon-Dez multi-reservoir system, which includes one-fifth of Iran's surface water resources. The objective functions of the problem are supplying water demands, generating hydropower energy and controlling water quality in downstream river.     

Beer game order policy optimization under changing customer demand

The present work analyses the optimal Beer Game order policy when customers demand increases. The optimal policy is found by means of a Genetic Algorithms (GAs) technique. GAs are specially suited for this problem because of the high dimension of the search space, and because the objective function i.e. the global score of the chain, has many local minima. Our results show that the best performance of the chain is obtained when the sectors have different order policies. The advantage increases with the increasing change in the customer demand.     

遗传算法在计算机辅助创新作曲中的应用

对遗传算法在作曲中的应用进行了一定的研究,分析了遗传算法作曲系统应用,主要对交互式遗传算法在作曲进化方面进行了探讨并加以实验测试。     

一种嵌入式的协同进化模型

为了提高遗传算法的性能,论文提出了一个能够体现生态进化中各种协同进化关系的协同进化模型,该模型能很容易地嵌入到遗传算法中。计算机模拟实验表明该模型的嵌入能在一定的程度解决遗传算法中的早熟现象,加快后期的收敛速度,提高遗传算法的自适应能力。     

进化算法研究进展

进化算法是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，主要包括遗传算法，（ｇｅｎｅｒｉｃａｌｇｏｒｉｔｈｍｓ，简记为ＧＡｓ）、进化规划（ｅｖｏｌｕｔｉｏｎａｒｙｐｒｏｇｒａｍｍｉｎｇ，简记为ＥＰ）和进化策略（ｅｖｏｌｕｔｉｏｎａｒｙｓｔｒａｔｅｇｉｅｓ，简记为ＥＳｓ），它们可以用解决优化和机器学习等问题，进化算法的两个主要特点中群体搜索策略及群体中个体之间的信息交换，进化算法不依赖于梯度信     

一种基于遗传算法的话者身份确认系统建模方法

本文描述了一种采用短语和基于遗传算法的话者身份确认系统的建模方法,利用遗传算法的全局搜索和优化特性,系统只需利用话者的短语音,就可快速建立话者的一类较优秀的模板。实验结果表明,这种方法既降低了用户的语音数据采集量,有利于话者模板的建立,又提高了系统的确认性能及鲁棒性,较传统方法有明显的优越性。     

改进GAs算法在大规模资源分配问题中的应用

采用改进ＧＡｓ算法建立了求解大规模规划的资源分配模型．针对大规模资源分配问题的具体特点，设计了合适的ＧＡｓ算子，并以实例验证了算法的合理性及有效性．     

A genetic algorithm with disruptive selection

Genetic algorithms are a class of adaptive search techniques based on the principles of population genetics. The metaphor underlying genetic algorithms is that of natural evolution. Applying the “survival-of-the-fittest” principle, traditional genetic algorithms allocate more trials to above-average schemata. However, increasing the sampling rate of schemata that are above average does not guarantee convergence to a global optimum; the global optimum could be a relatively isolated peak or located in schemata that have large variance in performance. In this paper we propose a novel selection method, disruptive selection. This method adopts a nonmonotonic fitness function that is quite different from traditional monotonic fitness functions. Unlike traditional genetic algorithms, this method favors both superior and inferior individuals. Experimental results show that GAs using the proposed method easily find the optimal solution of a function that is hard for traditional GAs to optimize. We also present convergence analysis to estimate the occurrence ratio of the optima of a deceptive function after a certain number of generations of a genetic algorithm. Experimental results show that GAs using disruptive selection in some occasions find the optima more quickly and reliably than GAs using directional selection. These results suggest that disruptive selection can be useful in solving problems that have large variance within schemata and problems that are GA-deceptive     

遗传算法辅助作曲研究

对遗传算法在作曲中的应用进行了一定的研究。介绍了遗传算法作曲系统目前的发展情况,分析了这一研究领域存在的问题,提出了一种新的交互式遗传算法作曲系统,借助Matlab 6.5下的遗传算法工具箱对系统进行了验证,取得了很好的效果。     

Adaptive estimated maximum-entropy distribution model

The Estimation of Distribution Algorithm (EDA) model is an optimization procedure through learning and sampling a conditional probabilistic function. The use of conditional density function permits multivariate dependency modelling, which is not captured in a population-based representation, like the classical Genetic Algorithms. The Gaussian model is a simple and widely used model for density estimation. However, an assumption of normality is not realistic for many real-life problems. Alternatively, the maximum-entropy model can be used, which makes no assumption of a normal distribution. One disadvantage of the maximum-entropy model is the learning cost of its parameters. This paper proposes an Adaptive Estimated Maximum-Entropy Distribution (Adaptive MEED) model, which aims to reduce learning complexity of building a model. Adaptive MEED exploits the fact that samples have a low average fitness in the early stage, but they gradually converge to an optima towards the end of the search. Hence, it is not necessary to inference the model with a full account of observed constraints in the early stage of the search. The proposed model attempts to estimate the density function with a dynamic set of samples and active constraints. In addition, the proposed model includes a global sampling function to address the issue of a missing mutation operator. The ergodic convergence properties of the proposed model are discussed with the Markov Chain analysis. The preliminary experimental evaluation shows that the proposed model performs well against genetic algorithms on several clustering problems.     

Evolutionary design of Evolutionary Algorithms

Manual design of Evolutionary Algorithms (EAs) capable of performing very well on a wide range of problems is a difficult task. This is why we have to find other manners to construct algorithms that perform very well on some problems. One possibility (which is explored in this paper) is to let the evolution discover the optimal structure and parameters of the EA used for solving a specific problem. To this end a new model for automatic generation of EAs by evolutionary means is proposed here. The model is based on a simple Genetic Algorithm (GA). Every GA chromosome encodes an EA, which is used for solving a particular problem. Several Evolutionary Algorithms for function optimization are generated by using the considered model. Numerical experiments show that the EAs perform similarly and sometimes even better than standard approaches for several well-known benchmarking problems.     

Effective Memetic Algorithms for VLSI design = Genetic Algorithms + local search + multi-level clustering

Combining global and local search is a strategy used by many successful hybrid optimization approaches. Memetic Algorithms (MAs) are Evolutionary Algorithms (EAs) that apply some sort of local search to further improve the fitness of individuals in the population. Memetic Algorithms have been shown to be very effective in solving many hard combinatorial optimization problems. This paper provides a forum for identifying and exploring the key issues that affect the design and application of Memetic Algorithms. The approach combines a hierarchical design technique, Genetic Algorithms, constructive techniques and advanced local search to solve VLSI circuit layout in the form of circuit partitioning and placement. Results obtained indicate that Memetic Algorithms based on local search, clustering and good initial solutions improve solution quality on average by 35% for the VLSI circuit partitioning problem and 54% for the VLSI standard cell placement problem.     

Niche identification techniques in multimodal genetic search with sharing scheme

Genetic algorithms with sharing have been applied in many multimodal optimization problems with success. Traditional sharing schemes require the definition of a common sharing radius, but the predefined radius cannot fit most problems where design niches are of different sizes. Yin and Germay proposed a sharing scheme with cluster analysis methods, which can determine design clusters of different sizes. Since clusters are not necessarily coincident with niches, sharing with clustering techniques fails to provide maximum sharing effects. In this paper, a sharing scheme based on niche identification techniques (NIT) is proposed, which is capable of determining the center location and radius of each of existing niches based on fitness topographical information of designs in the population. Genetic algorithms with NIT were tested and compared to GAs with traditional sharing scheme and sharing with cluster analysis methods in four illustrative problems. Results of numerical experiments showed that the sharing scheme with NIT improved both search stability and effectiveness of locating multiple optima. The niche-based genetic algorithm and the multiple local search approach are compared in the fifth illustrative problem involving a discrete ten-variable bump function problem.     

一种克服遗传算法收敛于局部极小的方法

本文针对遗传算法可能收敛于局部极上而最终得不到全局最优解的问题，提出了一种改进方法，并用实例验证了该方法的有效性。     

Using Disruptive Selection to Maintain Diversity in Genetic Algorithms

Genetic algorithms are a class of adaptive search techniques based on the principles of population genetics. The metaphor underlying genetic algorithms is that of natural evolution. With their great robustness, genetic algorithms have proven to be a promising technique for many optimization, design, control, and machine learning applications. A novel selection method, disruptive selection, has been proposed. This method adopts a nonmonotonic fitness function that is quite different from conventional monotonic fitness functions. Unlike conventional selection methods, this method favors both superior and inferior individuals. Since genetic algorithms allocate exponentially increasing numbers of trials to the observed better parts of the search space, it is difficult to maintain diversity in genetic algorithms. We show that Disruptive Genetic Algorithms (DGAs) effectively alleviate this problem by first demonstrating that DGAs can be used to solve a nonstationary search problem, where the goal is to track time-varying optima. Conventional Genetic Algorithms (CGAs) using proportional selection fare poorly on nonstationary search problems because of their lack of population diversity after convergence. Experimental results show that DGAs immediately track the optimum after the change of environment. We then describe a spike function that causes CGAs to miss the optimum. Experimental results show that DGAs outperform CGAs in resolving a spike function.     

基于多种群及水平集的任务调度算法

随着任务调度问题的广泛研究,包括遗传算法在内的许多新方法被引入到任务调度领域。然而,传统的遗传算法存在早熟收敛和后期进化停滞两个严重不足。为了克服这些不足,提出了算法MPLS。MPLS算法采用多种群共同进化的思想来维持种群多样性。同时,MPLS算法将水平集概念引入到任务调度研究中,以改进迭代收敛速度。基于第三方测试数据集,将MPLS的性能和GTMS、MSGS和NGS算法进行了对比。比较结果表明,MPLS算法获得的调度长度远好于GTMS、MSGS算法,略好于NGS算法。MPLS算法能将种群多样性维持在一个很高的水平。MPLS算法在调度长度和种群多样性方面要优于其它算法。     

基于遗传算法的工程项目资源优化

基于遗传算法建立了面向工程项目的资源优化模型。通过在模型中构造一个能反映“资源分配”和“资源均衡”两方面优化程度的适应度函数,并在复制操作中,对群中个体先进行分类再选择复制,有效地解决了多种资源的综合优化问题。给出了利用遗传算法对资源优化问题的求解设计思路,阐述了算法的实现流程,并通过实例验证了该模型的可行性。