Evolving Evolutionary Algorithms with Patterns

A new model for evolving evolutionary algorithms (EAs) is proposed in this paper. The model is based on the multi expression programming (MEP) technique. Each MEP chromosome encodes an evolutionary pattern which is repeatedly used for generating the individuals of a new generation. The evolved pattern is embedded into a standard evolutionary scheme which is used for solving a particular problem. Several evolutionary algorithms for function optimization are evolved by using the considered model. The evolved evolutionary algorithms are compared with a human-designed genetic algorithm. Numerical experiments show that the evolved evolutionary algorithms can compete with standard approaches for several well-known benchmarking problems.     

Memetic evolutionary training for recurrent neural networks: an application to time-series prediction

Abstract: Artificial neural networks are bio-inspired mathematical models that have been widely used to solve complex problems. The training of a neural network is an important issue to deal with, since traditional gradient-based algorithms become easily trapped in local optimal solutions, therefore increasing the time taken in the experimental step. This problem is greater in recurrent neural networks, where the gradient propagation across the recurrence makes the training difficult for long-term dependences. On the other hand, evolutionary algorithms are search and optimization techniques which have been proved to solve many problems effectively. In the case of recurrent neural networks, the training using evolutionary algorithms has provided promising results. In this work, we propose two hybrid evolutionary algorithms as an alternative to improve the training of dynamic recurrent neural networks. The experimental section makes a comparative study of the algorithms proposed, to train Elman recurrent neural networks in time-series prediction problems.     

演化算法时间复杂性的趋势条件

计算时间复杂性是演化理论中的一个重大课题.将趋势分析引入演化算法的平均时间复杂性分析,可用于很广一类演化算法及许多问题.基于趋势分析,研究了确定演化算法时间复杂性的一些有用的趋势条件.这些条件应用于完全欺骗问题以验证其有效性.     

Filtering algorithms for the multiset ordering constraint

Constraint programming (CP) has been used with great success to tackle a wide variety of constraint satisfaction problems which are computationally intractable in general. Global constraints are one of the important factors behind the success of CP. In this paper, we study a new global constraint, the multiset ordering constraint, which is shown to be useful in symmetry breaking and searching for leximin optimal solutions in CP. We propose efficient and effective filtering algorithms for propagating this global constraint. We show that the algorithms maintain generalised arc-consistency and we discuss possible extensions. We also consider alternative propagation methods based on existing constraints in CP toolkits. Our experimental results on a number of benchmark problems demonstrate that propagating the multiset ordering constraint via a dedicated algorithm can be very beneficial.     

How evolutionary algorithms are applied to statistical natural language processing

Statistical natural language processing (NLP) and evolutionary algorithms (EAs) are two very active areas of research which have been combined many times. In general, statistical models applied to deal with NLP tasks require designing specific algorithms to be trained and applied to process new texts. The development of such algorithms may be hard. This makes EAs attractive since they offer a general design, yet providing a high performance in particular conditions of application. In this article, we present a survey of many works which apply EAs to different NLP problems, including syntactic and semantic analysis, grammar induction, summaries and text generation, document clustering and machine translation. This review finishes extracting conclusions about which are the best suited problems or particular aspects within those problems to be solved with an evolutionary algorithm.     

Dynamic combinatorial optimisation problems: an analysis of the subset sum problem

The field of evolutionary computation has traditionally focused on static optimisation problems. Recently, many new approaches have been proposed that adapt traditional evolutionary algorithms to the dynamic domain to deal with the task of tracking high-quality solutions as the search space changes over time. These novel algorithms are subsequently evaluated on a wide range of different optimisation problems, including well-specified benchmark generators. However, due to a lack of theoretical results, as well as a general lack of references to actual real-world scenarios, it is not entirely clear whether these benchmarks capture any of the characteristics found in NP-hard dynamic optimisation problems. In this paper, we extensively analyse the properties of the NP-hard (dynamic) subset sum problem. In particular, we highlight the correlation between the dynamic parameters of the problem and the resulting movement of the global optimum. It is shown by empirical means that the degree to which the global optimum moves in response to the underlying dynamics is correlated only in specific cases. Furthermore, the role of the representation used to encode the problem, as well as the impact of the formulation of the objective function on the dynamics are also discussed.     

Parallel Algorithms for Dynamic Programming Recurrences with More Than O(1) Dependency

We study the parallel computation of dynamic programming. We consider four important dynamic programming problems which have wide application, and that have been studied extensively in sequential computation: (1) the 1D problem, (2) the gap problem, (3) the parenthesis problem, and (4) the RNA problem. The parenthesis problem has fast parallel algorithms; almost no work has been done for parallelizing the other three. We present a unifying framework for the parallel computation of dynamic programming recurrences with more than O(1) dependency. We use two well-known methods, the closure method and the matrix product method, as general paradigms for developing parallel algorithms. Combined with various techniques, they lead to a number of new results. Our main results are optimal sublinear-time algorithms for the 1D, parenthesis, and RNA problems.     

Towards a Constraint-Based Engineering Framework for Algorithm Design and Application

The search for programming frameworks that provide the formalism that can help organize literally thousands of algorithmic ideas and facilitate their applications to new problems is an important research direction in computer science. That is, we are seeking to develop a practical programming environment that allows the user to state a family of problems, and subsequently systematically apply a collection of established algorithmic techniques to individual problems correctly. In this note we informally discuss constraint networks as a vehicle that provides a general framework for the synthesis, abstraction and application of problem-specific algorithms.     

Solving fuzzy assembly-line balancing problem with genetic algorithms

Assembly-line balancing problem is known as one of difficult combinatorial optimization problems. This problem has been solved with linear programming, dynamic programming approaches, but unfortunately these approaches do not lead to efficient algorithms. Recently, genetic algorithm has been recognized as an efficient and usefull procedure for solving large and hard combinatorial optimization problems, such as scheduling problems, travelling salesman problems, transportation problems, and so on. Fuzzy sets theory is frequently used to represent uncertainty of information. In this paper, to treat the data of real-world problems we use a fuzzy number to represent the processing time and show that we can get a good performance in solving this problem using genetic algorithms.     

A statistical study of a class of cellular evolutionary algorithms.

Parallel evolutionary algorithms, over the past few years, have proven empirically worthwhile, but there seems to be a lack of understanding of their workings. In this paper we concentrate on cellular (fine-grained) models, our objectives being: (1) to introduce a suite of statistical measures, both at the genotypic and phenotypic levels, which are useful for analyzing the workings of cellular evolutionary algorithms; and (2) to demonstrate the application and utility of these measures on a specific example-the cellular programming evolutionary algorithm. The latter is used to evolve solutions to three distinct (hard) problems in the cellular-automata domain: density, synchronization, and random number generation. Applying our statistical measures, we are able to identify a number of trends common to all three problems (which may represent intrinsic properties of the algorithm itself), as well as a host of problem-specific features. We find that the evolutionary algorithm tends to undergo a number of phases which we are able to quantitatively delimit. The results obtained lead us to believe that the measures presented herein may prove useful in the general case of analyzing fine-grained evolutionary algorithms.     

On-Line Resource Management with Application to Routing and Scheduling

We propose a framework to model on-line resource management problems based on an on-line version of positive linear programming. We consider both min cost problems and max benefit problems and propose logarithmic competitive algorithms that are optimal up to a constant factor. The proposed framework provides a general methodology that applies to a wide class of on-line problems: shop scheduling, packet routing, and in general a class of packing and assignment problems. Previously studied problems as on-line multiprocessor scheduling and on-line virtual circuit routing can also be modeled within this framework. Received December 18, 1996; revised March 2, 1997.     

进化算法研究进展

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

Genetic algorithms to solve the cover printing problem

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.     

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.     

求解随机时变背包问题的精确算法与进化算法

随机时变背包问题(RTVKP)是一种新的动态背包问题,也是一种新的动态组合优化问题,目前它的求解算法主要是动态规划的精确算法、近似算法和遗传算法.本文首先利用动态规划提出了一个求解RTVKP问题的新精确算法,对算法时间复杂度的比较结果表明:它比已有的精确算法更适于求解背包载重较大的一类RTVKP实例.然后,分别基于差分演化和粒子群优化与贪心修正策略相结合,提出了求解RTVKP问题的两个进化算法.对5个RTVKP实例的数值计算结果比较表明: 精确算法一般不宜求解大规模的RTVKP实例,而基于差分演化、粒子群优化和遗传算法与贪心修正策略相结合的进化算法却不受实例规模与数据大小的影响,对于振荡频率大且具有较大数据的大规模RTVKP实例均能求得的一个极好的近似解.     

A swarm optimization algorithm inspired in the behavior of the social-spider

Swarm intelligence is a research field that models the collective behavior in swarms of insects or animals. Several algorithms arising from such models have been proposed to solve a wide range of complex optimization problems. In this paper, a novel swarm algorithm called the Social Spider Optimization (SSO) is proposed for solving optimization tasks. The SSO algorithm is based on the simulation of cooperative behavior of social-spiders. In the proposed algorithm, individuals emulate a group of spiders which interact to each other based on the biological laws of the cooperative colony. The algorithm considers two different search agents (spiders): males and females. Depending on gender, each individual is conducted by a set of different evolutionary operators which mimic different cooperative behaviors that are typically found in the colony. In order to illustrate the proficiency and robustness of the proposed approach, it is compared to other well-known evolutionary methods. The comparison examines several standard benchmark functions that are commonly considered within the literature of evolutionary algorithms. The outcome shows a high performance of the proposed method for searching a global optimum with several benchmark functions.     

Practical performance models of algorithms in evolutionary program induction and other domains

Evolutionary computation techniques have seen a considerable popularity as problem solving and optimisation tools in recent years. Theoreticians have developed a variety of both exact and approximate models for evolutionary program induction algorithms. However, these models are often criticised for being only applicable to simplistic problems or algorithms with unrealistic parameters. In this paper, we start rectifying this situation in relation to what matters the most to practitioners and users of program induction systems: performance. That is, we introduce a simple and practical model for the performance of program-induction algorithms. To test our approach, we consider two important classes of problems — symbolic regression and Boolean function induction — and we model different versions of genetic programming, gene expression programming and stochastic iterated hill climbing in program space. We illustrate the generality of our technique by also accurately modelling the performance of a training algorithm for artificial neural networks and two heuristics for the off-line bin packing problem.We show that our models, besides performing accurate predictions, can help in the analysis and comparison of different algorithms and/or algorithms with different parameters setting. We illustrate this via the automatic construction of a taxonomy for the stochastic program-induction algorithms considered in this study. The taxonomy reveals important features of these algorithms from the performance point of view, which are not detected by ordinary experimentation.     

Scaling Up Inductive Logic Programming: An Evolutionary Wrapper Approach

Inductive logic programming (ILP) algorithms are classification algorithms that construct classifiers represented as logic programs. ILP algorithms have a number of attractive features, notably the ability to make use of declarative background (user-supplied) knowledge. However, ILP algorithms deal poorly with large data sets (>10⁴ examples) and their widespread use of the greedy set-covering algorithm renders them susceptible to local maxima in the space of logic programs.This paper presents a novel approach to address these problems based on combining the local search properties of an inductive logic programming algorithm with the global search properties of an evolutionary algorithm. The proposed algorithm may be viewed as an evolutionary wrapper around a population of ILP algorithms.The evolutionary wrapper approach is evaluated on two domains. The chess-endgame (KRK) problem is an artificial domain that is a widely used benchmark in inductive logic programming, and Part-of-Speech Tagging is a real-world problem from the field of Natural Language Processing. In the latter domain, data originates from excerpts of the Wall Street Journal. Results indicate that significant improvements in predictive accuracy can be achieved over a conventional ILP approach when data is plentiful and noisy.     

On Two Techniques of Combining Branching and Treewidth

Branch & Reduce and dynamic programming on graphs of bounded treewidth are among the most common and powerful techniques used in the design of moderately exponential time exact algorithms for NP hard problems. In this paper we discuss the efficiency of simple algorithms based on combinations of these techniques. The idea behind these algorithms is very natural: If a parameter like the treewidth of a graph is small, algorithms based on dynamic programming perform well. On the other side, if the treewidth is large, then there must be vertices of high degree in the graph, which is good for branching algorithms. We give several examples of possible combinations of branching and programming which provide the fastest known algorithms for a number of NP hard problems. All our algorithms require non-trivial balancing of these two techniques. In the first approach the algorithm either performs fast branching, or if there is an obstacle for fast branching, this obstacle is used for the construction of a path decomposition of small width for the original graph. Using this approach we give the fastest known algorithms for Minimum Maximal Matching and for counting all 3-colorings of a graph. In the second approach the branching occurs until the algorithm reaches a subproblem with a small number of edges (and here the right choice of the size of subproblems is crucial) and then dynamic programming is applied on these subproblems of small width. We exemplify this approach by giving the fastest known algorithm to count all minimum weighted dominating sets of a graph. We also discuss how similar techniques can be used to design faster parameterized algorithms. A preliminary version of this paper appeared as Branching and Treewidth Based Exact Algorithms in the Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006) [15]. Additional support by the Research Council of Norway.     

A FORTRAN 90 genetic algorithm module for composite laminate structure design

The design of the stacking sequence for a composite laminate involves a set of discrete variables (plymaterial and ply orientation), and is thus well-suited to genetic algorithms for design optimization. Such algorithms have typically been custom-designed in FORTRAN 77 to suit specific optimization problems. Fortran 90 is a modern, powerful language with features that support important programming concepts, including those used in object-oriented programming. The Fortran 90 genetic algorithm module is used to define genetic data types, the functions which use these data types, and to provide a general framework for solving composite laminate structure design problems. The language's support of abstract data types is used to build genetic structures such as populations, subpopulations, individuals, chromosomes, and genes, and these data types are combined and manipulated by module subroutines. The use of abstract data types and long variable names makes the code useful and easily understood, while dynamic memory allocation makes the module flexible enough to be used in design problems of varying size and specification.