Multi-Objective Methods for Tree Size Control

Variable length methods for evolutionary computation can lead to a progressive and mainly unnecessary growth of individuals, known as bloat. First, we propose to measure performance in genetic programming as a function of the number of nodes, rather than trees, that have been evaluated. Evolutionary Multi-Objective Optimization (EMOO) constitutes a principled way to optimize both size and fitness and may provide parameterless size control. Reportedly, its use can also lead to minimization of size at the expense of fitness. We replicate this problem, and an empirical analysis suggests that multi-objective size control particularly requires diversity maintenance. Experiments support this explanation.The multi-objective approach is compared to genetic programming without size control on the 11-multiplexer, 6-parity, and a symbolic regression problem. On all three test problems, the method greatly reduces bloat and significantly improves fitness as a function of computational expense. Using the FOCUS algorithm, multi-objective size control is combined with active pursuit of diversity, and hypothesized minimum-size solutions to 3-, 4- and 5-parity are found. The solutions thus found are furthermore easily interpretable. When combined with diversity maintenance, EMOO can provide an adequate and parameterless approach to size control in variable length evolution.     

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.     

GP-induced and explicit bloating of the seeds in incremental GP improves evolutionary success

The parsimony control in genetic programming (GP) is one of the limiting factors in the quick evolution of efficient solutions. A variety of parsimony pressure methods have been developed to address this issue. The effects of these methods on the efficiency of evolution are recognized to depend on the characteristics of the applied problem domain. On the other hand, the implications of using parsimony pressure in evolving the seeds for incremental genetic programming (IGP) are still poorly known and remain uninvestigated. In this work we present a study on the cumulative effect of the bloat and the seeding of the initial population on the efficiency of incremental evolution of simulated snake-like robot (Snakebot). In the proposed IGP, the task of coevolving the locomotion gaits and sensing of the bot in a challenging environment is decomposed into two sub-tasks, implemented as two consecutive evolutionary stages. First, to evolve the pools of sensorless Snakebots, we use GP featuring the following three bloat-control methods: (1) linear parametric parsimony pressure, (2) lexicographic parsimony pressure and (3) no bloat control. During the second stage of IGP, we use these pools to seed the initial population of Snakebots applying two methods of seeding: canonical seeding and seeding inspired by genetic transposition (GT).     

Size Fair and Homologous Tree Crossovers for Tree Genetic Programming

Size fair and homologous crossover genetic operators for tree based genetic programming are described and tested. Both produce considerably reduced increases in program size (i.e., less bloat) and no detrimental effect on GP performance.GP search spaces are partitioned by the ridge in the number of program v. their size and depth. While search efficiency is little effected by initial conditions, these do strongly influence which half of the search space is searched. However a ramped uniform random initialization is described which straddles the ridge.With subtree crossover trees increase about one level per generation leading to subquadratic bloat in program length.     

Genetic programming with one-point crossover and subtree mutation for effective problem solving and bloat control

Genetic programming (GP) is one of the most widely used paradigms of evolutionary computation due to its ability to automatically synthesize computer programs and mathematical expressions. However, because GP uses a variable length representation, the individuals within the evolving population tend to grow rapidly without a corresponding return in fitness improvement, a phenomenon known as bloat. In this paper, we present a simple bloat control strategy for standard tree-based GP that achieves a one order of magnitude reduction in bloat when compared with standard GP on benchmark tests, and practically eliminates bloat on two real-world problems. Our proposal is to substitute standard subtree crossover with the one-point crossover (OPX) developed by Poli and Langdon (Second online world conference on soft computing in engineering design and manufacturing, Springer, Berlin (1997)), while maintaining all other GP aspects standard, particularly subtree mutation. OPX was proposed for theoretical purposes related to GP schema theorems, however since it curtails exploration during the search it has never achieved widespread use. In our results, on the other hand, we are able to show that OPX can indeed perform an effective search if it is coupled with subtree mutation, thus combining the bloat control capabilities of OPX with the exploration provided by standard mutation.     

Dynamic limits for bloat control in genetic programming and a review of past and current bloat theories

Bloat is an excess of code growth without a corresponding improvement in fitness. This is a serious problem in Genetic Programming, often leading to the stagnation of the evolutionary process. Here we provide an extensive review of all the past and current theories regarding why bloat occurs. After more than 15 years of intense research, recent work is shedding new light on what may be the real reasons for the bloat phenomenon. We then introduce Dynamic Limits, our new approach to bloat control. It implements a dynamic limit that can be raised or lowered, depending on the best solution found so far, and can be applied either to the depth or size of the programs being evolved. Four problems were used as a benchmark to study the efficiency of Dynamic Limits. The quality of the results is highly dependent on the type of limit used: depth or size. The depth variants performed very well across the set of problems studied, achieving similar fitness to the baseline technique while using significantly smaller trees. Unlike many other methods available so far, Dynamic Limits does not require specific genetic operators, modifications in fitness evaluation or different selection schemes, nor does it add any parameters to the search process. Furthermore, its implementation is simple and its efficiency does not rely on the usage of a static upper limit. The results are discussed in the context of the newest bloat theory.

Repeated patterns in genetic programming

Evolved genetic programming trees contain many repeated code fragments. Size fair crossover limits bloat in automatic programming, preventing the evolution of recurring motifs. We examine these complex properties in detail using depth vs. size Catalan binary tree shape plots, subgraph and subtree matching, information entropy, sensitivity analysis, syntactic and semantic fitness correlations. Programs evolve in a self-similar fashion, akin to fractal random trees, with diffuse introns. Data mining frequent patterns reveals that as software is progressively improved a large proportion of it is exactly repeated subtrees as well as exactly repeated subgraphs. We relate this emergent phenomenon to building blocks in GP and suggest GP works by jumbling subtrees which already have high fitness on the whole problem to give incremental improvements and create complete solutions with multiple identical components of different importance.     

The influence of mutation on population dynamics in multiobjective genetic programming

Using multiobjective genetic programming with a complexity objective to overcome tree bloat is usually very successful but can sometimes lead to undesirable collapse of the population to all single-node trees. In this paper we report a detailed examination of why and when collapse occurs. We have used different types of crossover and mutation operators (depth-fair and sub-tree), different evolutionary approaches (generational and steady-state), and different datasets (6-parity Boolean and a range of benchmark machine learning problems) to strengthen our conclusion. We conclude that mutation has a vital role in preventing population collapse by counterbalancing parsimony pressure and preserving population diversity. Also, mutation controls the size of the generated individuals which tends to dominate the time needed for fitness evaluation and therefore the whole evolutionary process. Further, the average size of the individuals in a GP population depends on the evolutionary approach employed. We also demonstrate that mutation has a wider role than merely culling single-node individuals from the population; even within a diversity-preserving algorithm such as SPEA2 mutation has a role in preserving diversity.     

Operator equalisation for bloat free genetic programming and a survey of bloat control methods

Bloat can be defined as an excess of code growth without a corresponding improvement in fitness. This problem has been one of the most intensively studied subjects since the beginnings of Genetic Programming. This paper begins by briefly reviewing the theories explaining bloat, and presenting a comprehensive survey and taxonomy of many of the bloat control methods published in the literature through the years. Particular attention is then given to the new Crossover Bias theory and the bloat control method it inspired, Operator Equalisation (OpEq). Two implementations of OpEq are described in detail. The results presented clearly show that Genetic Programming using OpEq is essentially bloat free. We discuss the advantages and shortcomings of each different implementation, and the unexpected effect of OpEq on overfitting. We observe the evolutionary dynamics of OpEq and address its potential to be extended and integrated into different elements of the evolutionary process.     

求解非线性规划问题的改进直觉模糊遗传算法

提出一种改进的直觉模糊遗传算法用于求解带有多维约束的非线性规划问题。以遗传算法在迭代寻优中的个体适应度大小构造相应可行解的隶属度和非隶属度函数,将非线性规划问题直觉模糊化转化为直觉模糊非线性规划问题,通过建立直觉模糊推理系统,自适应地调节遗传算法的交叉率和变异率;并采用一种改进的选择策略,将个体按适应度值大小排序、等量分组,对适应度低的个体组随机选择复制,保留不可行解中可能隐含的有利寻优信息,增强种群个体的多样性和竞争性。仿真实验结果表明,该算法求解非线性规划问题时是可行和有效的。     

On the abstraction method for the container relocation problem

The container relocation problem or the blocks relocation problem is a classic combinatorial optimisation problem that occurs in day-to-day operations for facilities that use block stacking systems. A typical place where this problem arises is a container terminal where containers can be stacked vertically in order to utilise the scarce resource of yard surface, thus at times resulting in the unproductive reshuffling moves for containers stacked above the target container for retrieval. Due to the problem class being NP-hard, a number of studies on this topic propose heuristic approaches to solve this problem. There are a few exact methods (search-based algorithms or mathematical programming) proposed for this problem but the feasible problem size of such methods is quite restricted, limiting their practical significance. In this paper, we propose a new insight into reducing the search space of this problem by the abstraction method. Our main contribution to the existing literature is two-fold: the reduction in the search space by the abstraction method and the bidirectional search using the pattern database. Our computational results confirm that our approach enables instances of a near-practical size to be solved optimally within a reasonable computation time.     

Locating input and output points in facilities design - acomparison of constructive, evolutionary, and exact methods

This paper formulates and compares four new approaches to optimally locate the input and output station for each department within a facility design such that material handling costs are minimized. This problem is an NP-hard combinatorial problem with many real-life applications of considerable economic consequence. A genetic algorithm (GA) is shown to be an effective and efficient optimization method when compared to integer programming, simulated annealing, and three versions of a greedy constructive heuristic on a suite of test problems of varying size. Seeding versus random initialization of GA populations are compared     

A Hyper-Heuristic Framework for Lifetime Maximization in Wireless Sensor Networks With A Mobile Sink

Maximizing the lifetime of wireless sensor networks(WSNs) is an important and challenging research problem. Properly scheduling the movements of mobile sinks to balance the energy consumption of wireless sensor network is one of the most effective approaches to prolong the lifetime of wireless sensor networks. However, the existing mobile sink scheduling methods either require a great amount of computational time or lack effectiveness in finding high-quality scheduling solutions. To address the above issues, this paper proposes a novel hyperheuristic framework, which can automatically construct high-level heuristics to schedule the sink movements and prolong the network lifetime. In the proposed framework, a set of low-level heuristics are defined as building blocks to construct high-level heuristics and a set of random networks with different features are designed for training. Further, a genetic programming algorithm is adopted to automatically evolve promising high-level heuristics based on the building blocks and the training networks. By using the genetic programming to evolve more effective heuristics and applying these heuristics in a greedy scheme, our proposed hyper-heuristic framework can prolong the network lifetime competitively with other methods, with small time consumption. A series of comprehensive experiments, including both static and dynamic networks,are designed. The simulation results have demonstrated that the proposed method can offer a very promising performance in terms of network lifetime and response time.     

A Comparison of three evolutionary strategies for multiobjective genetic programming

We report what we believe to be the first comparative study of multi-objective genetic programming (GP) algorithms on benchmark symbolic regression and machine learning problems. We compare the Strength Pareto Evolutionary Algorithm (SPEA2), the Non-dominated Sorting Genetic Algorithm (NSGA-II) and the Pareto Converging Genetic Algorithm (PCGA) evolutionary paradigms. As well as comparing the quality of the final solutions, we also examine the speed of convergence of the three evolutionary algorithms. Based on our observations, the SPEA2-based algorithm appears to have problems controlling tree bloat—that is, the uncontrolled growth in the size of the chromosomal tree structures. The NSGA-II-based algorithm on the other hand seems to experience difficulties in locating low error solutions. Overall, the PCGA-based algorithm gives solutions with the lowest errors and the lowest mean complexity.     

Neutral offspring controlling operators in genetic programming

Code bloat, one of the main issues of genetic programming (GP), slows down the search process, destroys program structures, and exhausts computer resources. To deal with these issues, two kinds of neutral offspring controlling operators are proposed—non-neutral offspring (NNO) operators and non-larger neutral offspring (NLNO) operators. Two GP benchmark problems—symbolic regression and 11-multiplexer—are used to test the new operators. Experimental results indicate that NLNO is able to confine code bloat significantly and improve performance simultaneously, which NNO cannot do.     

A computer model for power system control

A forward dynamic programming formulation of the optimal commitment of units for economic power generation is proposed, and it is shown how advantage is taken of the characteristics of the formulation as well as the structure of the problem itself to impose limiting conditions which reduce the size and complexity of the solution, while still ensuring that the generating schedules determined are costefficient. By employing a number of strategies which control the multiplicity of states, the proposed method eliminates the necessity for large computer storage—a drawback in the early dynamic programming methods. Operating constraints like non-linearities in the cost characteristics of units, deterministic spinning reserve, time-dependent start-up costs are incorporated in the model and operating schedules are produced over a 24-h horizon. Computational experience with the technique indicates its potentiality for on-line computer implementation.     

Wolfgang Banzhaf: Genetic programming and emergence

This commentary demonstrates that for genetic programming with recombination and drift repeated motif patterns emerge within individuals more often than chance. This demonstrates that such patterns emerge without the need for selection. In addition, this effect is amplified when the effective population size is reduced.     

An efficient search direction for linear programming problems

In this paper, we present an auxiliary algorithm, in terms of the speed of obtaining the optimal solution, that is effective in helping the simplex method for commencing a better initial basic feasible solution. The idea of choosing a direction towards an optimal point presented in this paper is new and easily implemented. From our experiments, the algorithm will release a corner point of the feasible region within few iterative steps, independent of the starting point. The computational results show that after the auxiliary algorithm is adopted as phase I process, the simplex method consistently reduce the number of required iterations by about 40%.Scope and purposeRecent progress in the implementations of simplex and interior point methods as well as advances in computer hardware has extended the capability of linear programming with today's computing technology. It is well known that the solution times for the interior point method improve with problem size. But, experimental evidence suggests that interior point methods dominate simplex-based methods only in the solution of very large scale linear programs. If the problem size is medium, how to combine the best features of these two methods to produce an effective algorithm for solving linear programming problems is still an interesting problem. In this research we present a new effective ε-optimality search direction based on the interior point method to start an initial basic feasible solution near the optimal point for the simplex method.     

A Simple Prior-Free Method for Non-rigid Structure-from-Motion Factorization

This paper proposes a simple “prior-free” method for solving the non-rigid structure-from-motion (NRSfM) factorization problem. Other than using the fundamental low-order linear combination model assumption, our method does not assume any extra prior knowledge either about the non-rigid structure or about the camera motions. Yet, it works effectively and reliably, producing optimal results, and not suffering from the inherent basis ambiguity issue which plagued most conventional NRSfM factorization methods. Our method is very simple to implement, which involves solving a very small SDP (semi-definite programming) of fixed size, and a nuclear-norm minimization problem. We also present theoretical analysis on the uniqueness and the relaxation gap of our solutions. Extensive experiments on both synthetic and real motion capture data (assuming following the low-order linear combination model) are conducted, which demonstrate that our method indeed outperforms most of the existing non-rigid factorization methods. This work offers not only new theoretical insight, but also a practical, everyday solution to NRSfM.