共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
Ting Yee Lim 《Artificial Intelligence Review》2014,41(3):385-399
The Genetic Algorithm (GA) has been one of the most studied topics in evolutionary algorithm literature. Mimicking natural processes of inheritance, mutation, natural selection and genetic operators, GAs have been successful in solving various optimization problems. However, standard GA is often criticized as being too biased in candidate solutions due to genetic drift in search. As a result, GAs sometimes converge on premature solutions. In this paper, we survey the major advances in GA, particularly in relation to the class of structured population GAs, where better exploration and exploitation of the search space is accomplished by controlling interactions among individuals in the population pool. They can be classified as spatial segregation, spatial distance and heterogeneous population. Additionally, secondary factors such as aging, social behaviour, and so forth further guide and shape the reproduction process. Restricting randomness in reproduction has been seen to have positive effects on GAs. It is our hope that by reviewing the many existing algorithms, we shall see even better algorithms being developed. 相似文献
3.
4.
求解MSA问题的新型单亲遗传算法 总被引:3,自引:1,他引:2
多序列联配(MSA)在生物信息学研究中占有重要地位,MSA问题是一个典型的NP问题,遗传算法是求解NP完全问题的一种理想方法。文章针对MSA问题,提出了一种新型单亲遗传算法(PGA),不使用交叉算子,只使用变异和选择算子。并根据群体的多样性自适应调节变异概率,有效消除了算法中的欺骗性条件,使用灾变算子来确保算法的搜索能力。整个算法模拟了自然界进化的周期性,较好地解决了群体的多样性和收敛深度的矛盾。算法的分析和测试表明,该算法是有效的。 相似文献
5.
Combining genetic algorithms with BESO for topology optimization 总被引:2,自引:1,他引:1
This paper proposes a new algorithm for topology optimization by combining the features of genetic algorithms (GAs) and bi-directional
evolutionary structural optimization (BESO). An efficient treatment of individuals and population for finite element models
is presented which is different from traditional GAs application in structural design. GAs operators of crossover and mutation
suitable for topology optimization problems are developed. The effects of various parameters used in the proposed GA on the
optimization speed and performance are examined. Several 2D and 3D examples of compliance minimization problems are provided
to demonstrate the efficiency of the proposed new approach and its capability of obtaining convergent solutions. Wherever
possible, the numerical results of the proposed algorithm are compared with the solutions of other GA methods and the SIMP
method. 相似文献
6.
Selecting operators, selection strategy, and tuning parameters for genetic algorithms (GAs)is usually a very time-consuming job. In this article we introduce a method for developing an adaptive real-coded genetic algorithm (ARGA) which aims at reducing this computation time. In developing the algorithm, we first use factorial design experiments to identify ''important'' and ''sensitive'' parameters. Then these parameters will be dynamically changed during the evolutionary process by efficient computing budget allocation. At the end of the search process, not only has the optimum of the original problem been found, but also the adaptive changing pattern of the GA parameters has been captured. This algorithm is successfully used to solve some benchmark problems, a Linear-Quadratic-Gaussian (LQG) problem and a drug scheduling problem. The results show that ARGA outperforms simple GAs and other adaptive GAs which use the same type of operators. Moreover, ARGA is able to find the optimum for some difficult problems while the simple GAs with the best parameter combination can only reach the local optimum. 相似文献
7.
An adequately designed and parameterized set of operators is crucial for an efficient behaviour of Genetic Algorithms (GAs). Several strategies have been adopted in order to better adapt parameters to the problem under resolution and to increase the algorithm's performance. One of these approaches consists in using operators presenting a dynamic behaviour, that is displaying a different qualitative behaviour in different stages of the evolutionary process. In this work a comparative analysis of the effects of using an adaptive mutation operator is presented in the operational framework of a multi-objective GA for the design and selection of electrical load management strategies. It is shown that the use of a time/space varying mutation operator depending on the values achieved for each objective function increases the performance of the algorithm. 相似文献
8.
《Computers & Operations Research》2002,29(12):1641-1659
Evolutionary algorithms (EAs) have been applied to many optimization problems successfully in recent years. The genetic algorithm (GAs) and evolutionary programming (EP) are two different types of EAs. GAs use crossover as the primary search operator and mutation as a background operator, while EP uses mutation as the primary search operator and does not employ any crossover. This paper proposes a novel EP algorithm for cutting stock problems with and without contiguity. Two new mutation operators are proposed. Experimental studies have been carried out to examine the effectiveness of the EP algorithm. They show that EP can provide a simple yet more effective alternative to GAs in solving cutting stock problems with and without contiguity. The solutions found by EP are significantly better (in most cases) than or comparable to those found by GAs.Scope and purposeThe one-dimensional cutting stock problem (CSP) is one of the classical combinatorial optimization problems. While most previous work only considered minimizing trim loss, this paper considers CSPs with two objectives. One is the minimization of trim loss (i.e., wastage). The other is the minimization of the number of stocks with wastage, or the number of partially finished items (pattern sequencing or contiguity problem). Although some traditional OR techniques (e.g., programming based approaches) can find the global optimum for small CSPs, they are impractical to find the exact global optimum for large problems due to combinatorial explosion. Heuristic techniques (such as various hill-climbing algorithms) need to be used for large CSPs. One of the heuristic algorithms which have been applied to CSPs recently with success is the genetic algorithm (GA). This paper proposes a much simpler evolutionary algorithm than the GA, based on evolutionary programming (EP). The EP algorithm has been shown to perform significantly better than the GA for most benchmark problems we used and to be comparable to the GA for other problems. 相似文献
9.
10.
《Evolutionary Computation, IEEE Transactions on》2009,13(3):661-673
11.
12.
Adaptive directed mutation (ADM) operator, a novel, simple, and efficient real-coded genetic algorithm (RCGA) is proposed and then employed to solve complex function optimization problems. The suggested ADM operator enhances the abilities of GAs in searching global optima as well as in speeding convergence by integrating the local directional search strategy and the adaptive random search strategies. Using 41 benchmark global optimization test functions, the performance of the new algorithm is compared with five conventional mutation operators and then with six genetic algorithms (GAs) reported in literature. Results indicate that the proposed ADM-RCGA is fast, accurate, and reliable, and outperforms all the other GAs considered in the present study. 相似文献
13.
Inspired by successful application of evolutionary algorithms to solving difficult optimization problems, we explore in this paper, the applicability of genetic algorithms (GAs) to the cover printing problem, which consists in the grouping of book covers on offset plates in order to minimize the total production cost. We combine GAs with a linear programming solver and we propose some innovative features such as the “unfixed two-point crossover operator” and the “binary stochastic sampling with replacement” for selection. Two approaches are proposed: an adapted genetic algorithm and a multiobjective genetic algorithm using the Pareto fitness genetic algorithm. The resulting solutions are compared. Some computational experiments have also been done to analyze the effects of different genetic operators on both algorithms. 相似文献
14.
Traditional genetic algorithms use only one crossover and one mutation operator to generate the next generation. The chosen crossover and mutation operators are critical to the success of genetic algorithms. Different crossover or mutation operators, however, are suitable for different problems, even for different stages of the genetic process in a problem. Determining which crossover and mutation operators should be used is quite difficult and is usually done by trial-and-error. In this paper, a new genetic algorithm, the dynamic genetic algorithm (DGA), is proposed to solve the problem. The dynamic genetic algorithm simultaneously uses more than one crossover and mutation operators to generate the next generation. The crossover and mutation ratios change along with the evaluation results of the respective offspring in the next generation. By this way, we expect that the really good operators will have an increasing effect in the genetic process. Experiments are also made, with results showing the proposed algorithm performs better than the algorithms with a single crossover and a single mutation operator. 相似文献
15.
Robin F. Orzati A. Moreno E. Homan O.J. Bachtold W. 《Evolutionary Computation, IEEE Transactions on》2003,7(1):69-82
Genetic and simplex-downhill (SD) algorithms were used for the optimization of the electron-beam lithography (EBL) step in the fabrication of microwave electronic circuits. The definition of submicrometer structures involves complex exposure patterns that are cumbersome to determine experimentally and very difficult to optimize with linear search algorithms due to the high dimensionality of the search space. An SD algorithm was first used to solve the optimization problem. The large number of parameters and the complex topology of the search space proved too difficult for this algorithm, which could not yield satisfactory patterns. A hybrid approach using genetic algorithms (GAs) for global search, and an SD algorithm for further local optimization, was unable to drastically improve the structures optimized with GAs alone. A carefully studied fitness function was used. It contains mechanisms for reduced dependence on process tolerances. Several methods were studied for the selection, crossover, mutation, and reinsertion operators. The GA was used to predict scanning patterns for 100-nm T-gates and gate profiles with asymmetric recess and the structures were fabricated successfully. The simulation and optimization tool can help shorten response times to alterations of the EBL process by suppressing time-consuming experimental trial-and-error steps. 相似文献
16.
基于变长编码遗传算法的最小缩减计算 总被引:9,自引:1,他引:8
在数据库知识发现的过程中,属性选取是其中的一个重要步骤,它通过去除冗余属性,达到提高数据挖掘效能的目的。本文利用粗糙集合中的理论作为背景知识,讨论了使用遗传算法寻找最小缩减的方法,并提出采用个体变长编码的方法来解决最小缩减的计算问题,设计出相应的交叉、变异算子,实验证明其具有较好的收敛性能。 相似文献
17.
18.
19.
在多目标柔性车间作业调度问题的研究中,求解算法与多目标处理至关重要。因此,基于非支配排序遗传算法提出了改进遗传算法求解该问题,设计了相应的矩阵编码、交叉算子,改进了非劣前沿分级方法,并提出了基于Pareto等级的自适应变异算子以及精英保留策略。实例计算表明,该算法可以利用传统遗传算法全局搜索能力的同时可以防止早熟现象的发生。改进非劣前沿分级方法可以快速得到Pareto最优解集,进一步减小了计算复杂度,而且可以根据种群的多样性改变变异概率,有利于保持种群多样性、发掘潜力个体。 相似文献
20.
Deepak Sharma Kalyanmoy Deb N. N. Kishore 《Structural and Multidisciplinary Optimization》2011,43(4):541-554
Genetic algorithms (GAs) can precisely handle the discrete structural topology optimization of single-piece elastic structures
called compliant mechanisms. The initial population of these elastic structures is mostly generated by assigning the material
at random. This causes disconnected or unfeasible designs and further rule-based repairing can result in representation degeneracy.
However, the problem-specific initial population can affect the performance of GAs like other operators. In this paper, a
domain-specific initial population strategy is developed that generates geometrically feasible structures for path generating
compliant mechanisms (PGCMs). It is coupled with the elitist non-dominated sorting genetic algorithm (NSGA-II) which has been
customized for structural topology optimization. The performance of initial population strategy over random initialization
using customized NSGA-II is checked on single and bi-objective optimization problems. Based on the results, it is observed
that the custom initialization outperforms the random initialization by dominating all the solutions and exploring larger
area of posed objectives. The elastic structures obtained by solving two examples of PGCMs using domain specific initial population
strategy are also presented. 相似文献