Modification point depth and genome growth in genetic programming

The evolutionary computation community has shown increasing interest in arbitrary-length representations, particularly in the field of genetic programming. A serious stumbling block to the scalability of such representations has been bloat: uncontrolled genome growth during an evolutionary run. Bloat appears across the evolutionary computation spectrum, but genetic programming has given it by far the most attention. Most genetic programming models explain this phenomenon as a result of the growth of introns, areas in an individual which serve no functional purpose. This paper presents evidence which directly contradicts intron theories as applied to tree-based genetic programming. The paper then uses data drawn from this evidence to propose a new model of genome growth. In this model, bloat in genetic programming is a function of the mean depth of the modification (crossover or mutation) point. Points far from the root are correspondingly less likely to hurt the child's survivability in the next generation. The modification point is in turn strongly correlated to average parent tree size and to removed subtree size, both of which are directly linked to the size of the resulting child.     

遗传算法与进化规划的比较研究

遗传算法和退化规划是目前工程应用研究中最普遍的两种进化算法，由于它们的来源及原理的不同导致它们在生物基础、算法操作及实施细节上均存在很大差异，适最终影响到它们的实施效果及性能。通过系统的理论分析及函数仿真实验研究表明。进化规划无论是生物基础、算法实施选是计算性能方面都明显优于遗传算法，是处理工程优化问题的一种更理想的方法。     

Two fast tree-creation algorithms for genetic programming

Genetic programming is an evolutionary optimization method that produces functional programs to solve a given task. These programs commonly take the form of trees representing LISP s-expressions, and a typical evolutionary run produces a great many of these trees. For this reason, a good tree-generation algorithm is very important to genetic programming. This paper presents two new tree-generation algorithms for genetic programming and for “strongly typed” genetic programming, a common variant. These algorithms are fast, allow the user to request specific tree sizes, and guarantee probabilities of certain nodes appearing in trees. The paper analyzes these two algorithms, and compares them with traditional and recently proposed approaches     

Knowledge engineering

Summary Several new and emerging computational paradigms for engineering problem solving automation and processing of various types of knowledge are reviewed. They are artificial intelligence/sybmolic processing, object-oriented programming paradigm, machine learning, evolutionary computing/genetic algorithms, and neurocomputing. Examples of recent research efforts in each area are briefly described.     

Quantum inspired evolutionary algorithm for ordering problems

This paper proposes a new quantum-inspired evolutionary algorithm for solving ordering problems. Quantum-inspired evolutionary algorithms based on binary and real representations have been previously developed to solve combinatorial and numerical optimization problems, providing better results than classical genetic algorithms with less computational effort. However, for ordering problems, order-based genetic algorithms are more suitable than those with binary and real representations. This is because specialized crossover and mutation processes are employed to always generate feasible solutions. Therefore, this work proposes a new quantum-inspired evolutionary algorithm especially devised for ordering problems (QIEA-O). Two versions of the algorithm have been proposed. The so-called pure version generates solutions by using the proposed procedure alone. The hybrid approach, on the other hand, combines the pure version with a traditional order-based genetic algorithm. The proposed quantum-inspired order-based evolutionary algorithms have been evaluated for two well-known benchmark applications – the traveling salesman problem (TSP) and the vehicle routing problem (VRP) – as well as in a real problem of line scheduling. Numerical results were obtained for ten cases (7 VRP and 3 TSP) with sizes ranging from 33 to 101 stops and 1 to 10 vehicles, where the proposed quantum-inspired order-based genetic algorithm has outperformed a traditional order-based genetic algorithm in most experiments.     

An introduction to simulated evolutionary optimization

Natural evolution is a population-based optimization process. Simulating this process on a computer results in stochastic optimization techniques that can often outperform classical methods of optimization when applied to difficult real-world problems. There are currently three main avenues of research in simulated evolution: genetic algorithms, evolution strategies, and evolutionary programming. Each method emphasizes a different facet of natural evolution. Genetic algorithms stress chromosomal operators. Evolution strategies emphasize behavioral changes at the level of the individual. Evolutionary programming stresses behavioral change at the level of the species. The development of each of these procedures over the past 35 years is described. Some recent efforts in these areas are reviewed.     

Evolutionary computation: comments on the history and current state

Evolutionary computation has started to receive significant attention during the last decade, although the origins can be traced back to the late 1950's. This article surveys the history as well as the current state of this rapidly growing field. We describe the purpose, the general structure, and the working principles of different approaches, including genetic algorithms (GA) (with links to genetic programming (GP) and classifier systems (CS)), evolution strategies (ES), and evolutionary programming (EP) by analysis and comparison of their most important constituents (i.e. representations, variation operators, reproduction, and selection mechanism). Finally, we give a brief overview on the manifold of application domains, although this necessarily must remain incomplete     

Graph-based evolutionary design of arithmetic circuits

We present an efficient graph-based evolutionary optimization technique, called evolutionary graph generation (EGG), and the proposed approach is applied to the design of combinational and sequential arithmetic circuits based on parallel counter-tree architecture. The fundamental idea of EGG is to employ general circuit graphs as individuals and manipulate the circuit graphs directly using new evolutionary graph operations without encoding the graphs into other indirect representations, such as the bit strings used in genetic algorithm (GA) proposed by Holland (1992) and trees used in genetic programming (GP) proposed by Koza et al. (1997). In this paper, the EGG system is applied to the design of constant-coefficient multipliers and the design of bit-serial data-parallel adders. The results demonstrate the potential capability of EGG to solve the practical design problems for arithmetic circuits with limited knowledge of computer arithmetic algorithms. The proposed EGG system can help to simplify and speed up the process of designing arithmetic circuits and can produce better solutions to the given problem     

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.     

Large scale structural optimization: Computational methods and optimization algorithms

Summary The objective of this paper is to investigate the efficiency of various optimization methods based on mathematical programming and evolutionary algorithms for solving structural optimization problems under static and seismic loading conditions. Particular emphasis is given on modified versions of the basic evolutionary algorithms aiming at improving the performance of the optimization procedure. Modified versions of both genetic algorithms and evolution strategies combined with mathematical programming methods to form hybrid methodologies are also tested and compared and proved particularly promising. Furthermore, the structural analysis phase is replaced by a neural network prediction for the computation of the necessary data required by the evolutionary algorithms. Advanced domain decomposition techniques particularly tailored for parallel solution of large-scale sensitivity analysis problems are also implemented. The efficiency of a rigorous approach for treating seismic loading is investigated and compared with a simplified dynamic analysis adopted by seismic codes in the framework of finding the optimum design of structures with minimum weight. In this context a number of accelerograms are produced from the elastic design response spectrum of the region. These accelerograms constitute the multiple loading conditions under which the structures are optimally designed. The numerical tests presented demonstrate the computational advantages of the discussed methods, which become more pronounced in large-scale optimization problems.     

On evolutionary algorithms,neural-network computations,and genetic programming. Mathematical problems

Some problems related to evolutionary and genetic algorithms, genetic programming, and neural-network computations on solving applied problems that are reduced to analysis of functions prescribed at permutations are roughly studied. Natural parallelism of these algorithms and possibility of their realization on modern computers are noted.     

利用进化规划设计人工神经网络

近年来,人们开发了许多的神经网络自动设计方法,其中进化算法与神经网络的结合最引人注目,形成一类进化人工神经网络。对用遗传算法实现神经网络的进化进行研究的时间最早,并得到广泛的评论,而最近越来越多的研究支持利用进化规划设计神经网络是一种更优的方法。该文讨论了这一领域的研究进展并阐明了进一步的研究方向。     

Redundant representations in evolutionary computation

This paper discusses how the use of redundant representations influences the performance of genetic and evolutionary algorithms. Representations are redundant if the number of genotypes exceeds the number of phenotypes. A distinction is made between synonymously and non-synonymously redundant representations. Representations are synonymously redundant if the genotypes that represent the same phenotype are very similar to each other. Non-synonymously redundant representations do not allow genetic operators to work properly and result in a lower performance of evolutionary search. When using synonymously redundant representations, the performance of selectorecombinative genetic algorithms (GAs) depends on the modification of the initial supply. We have developed theoretical models for synonymously redundant representations that show the necessary population size to solve a problem and the number of generations goes with O(2(kr)/r), where kr is the order of redundancy and r is the number of genotypic building blocks (BB) that represent the optimal phenotypic BB. As a result, uniformly redundant representations do not change the behavior of GAs. Only by increasing r, which means overrepresenting the optimal solution, does GA performance increase. Therefore, non-uniformly redundant representations can only be used advantageously if a-priori information exists regarding the optimal solution. The validity of the proposed theoretical concepts is illustrated for the binary trivial voting mapping and the real-valued link-biased encoding. Our empirical investigations show that the developed population sizing and time to convergence models allow an accurate prediction of the empirical results.     

进化计算简要综述

介绍进化计算的起源与发展历史、进化计算的特点与分类、进化计算有关研究与应用现状、进化计算有关软件与国际信息交流等方面的基本情况。     

广义人工生命的科学基础(I):工程技术基础

根据广义人工生命研究的特点,作者把系统论、控制论、信息论、人工智能、元胞自动机、L-系统、遗传算法、进化策略、进化规划、耗散结构理论、协同学、突变论、混沌、分形、转基因技术、克隆技术等的研究成果视为人工生命研究的主要科学基础。文章力求对元胞自动机、L-系统、遗传算法、进化策略、进化规划、耗散结构理论、协同学、突变论、混沌、分形和它们与人工生命的关系做系统而扼要的评述,为人工生命研究提供方便。     

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

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

ASYMPTOTIC CONVERGENCE PROPERTIES OF GENETIC ALGORITHMS AND EVOLUTIONARY PROGRAMMING: ANALYSIS AND EXPERIMENTS

The basic convergence properties of evolutionary optimization algorithms are investigated. Analysis indicates that the methods studied will asymptotically converge to global optima. The results also indicate that genetic algorithms may prematurely stagnate at solutions that may not even be locally optimal. Function optimization experiments are conducted that illustrate the mathematical properties. Evolutionary programming is seen to outperform genetic algorithms in searching two response surfaces that do not possess local optima. The results are statistically significant.     

Coevolving memetic algorithms: a review and progress report.

Coevolving memetic algorithms are a family of metaheuristic search algorithms in which a rule-based representation of local search (LS) is coadapted alongside candidate solutions within a hybrid evolutionary system. Simple versions of these systems have been shown to outperform other nonadaptive memetic and evolutionary algorithms on a range of problems. This paper presents a rationale for such systems and places them in the context of other recent work on adaptive memetic algorithms. It then proposes a general structure within which a population of LS algorithms can be evolved in tandem with the solutions to which they are applied. Previous research started with a simple self-adaptive system before moving on to more complex models. Results showed that the algorithm was able to discover and exploit certain forms of structure and regularities within the problems. This "metalearning" of problem features provided a means of creating highly scalable algorithms. This work is briefly reviewed to highlight some of the important findings and behaviors exhibited. Based on this analysis, new results are then presented from systems with more flexible representations, which, again, show significant improvements. Finally, the current state of, and future directions for, research in this area is discussed.     

A survey of repair methods used as constraint handling techniques in evolutionary algorithms

This paper provides a survey of the most important repair heuristics used in evolutionary algorithms to solve constrained optimization problems. Popular techniques are reviewed, such as some crossover operators in permutation encoding, algorithms for fixing the number of 1s in binary encoded genetic algorithms, and more specialized techniques such as Hopfield neural networks, heuristics for graphs and trees, and repair heuristics in grouping genetic algorithms. The survey also gives some indications about the design and implementation of hybrid evolutionary algorithms, and provides a revision of the most important applications in which hybrid evolutionary techniques have been used.     

Latent Variable Model for Estimation of Distribution Algorithm Based on a Probabilistic Context-Free Grammar

Estimation of distribution algorithms are evolutionary algorithms using probabilistic techniques instead of traditional genetic operators. Recently, the application of probabilistic techniques to program and function evolution has received increasing attention, and this approach promises to provide a strong alternative to the traditional genetic programming techniques. Although a probabilistic context-free grammar (PCFG) is a widely used model for probabilistic program evolution, a conventional PCFG is not suitable for estimating interactions among nodes because of the context freedom assumption. In this paper, we have proposed a new evolutionary algorithm named programming with annotated grammar estimation based on a PCFG with latent annotations, which allows this context freedom assumption to be weakened. By applying the proposed algorithm to several computational problems, it is demonstrated that our approach is markedly more effective at estimating building blocks than prior approaches.