Home OverviewMetaphor People Algorithms Publication Software

Problems with Current Evolutionary Computation

Why do the evolutionary algorithms (EAs) quickly get trapped, especially in Genetic Programming (GP)? 
Why the EAs make few major innovation or progress in the later stage of evolutionary search? Is this because the current solutions in the population approximate the prefect solution or just because the EA can't make big jump in the search space? Is the success by luck the inherent nature of the stochastic evolutionary algorithms ? Are there any significant approach to make an EA as robust as possible?
Are there any inherent bias in the current evolutionary computation framework that prevent us from achieve scalable, sustainable and robust evolutionary search?

At the same time, the EC practice is highly empirical despite some of theoretical work [population sizing theory]. EC practitioners are faced with many decisions:

How should I allocate the limited computing resources to multiple short run GA/GP or to a long run? [Sean Luke, Goldberg]
How should I partially reinitialize the population to avoid loss of diversity?
How should I balance the selection pressure vs. explorative capability?
Can a GA run as greedy as possible (run as fast as possible) without ever trapped in local optima?

Our investigation started by examining the sustainable evolutionary processes of societal, economic, and biological systems and comparing them to the artificial evolutionary process in EAs and artificial life systems. We identified a fundamental unjustified bias and related assumptions in current EC framework (including the canonical GA, GP, EA, ES, many Alife systems). Understanding of these bias enabled us to be able to explain many typical phenomena in evolutionary computing which are only partially explained before. One example is the diversity-based explanation of the premature convergence of evolutionary search, why sometimes diversity works and sometimes not. We transplant the hierarchical organization principle for fair competition from societal systems and proposed the Hierarchical Fair Competition (HFC) framework for scalable, sustainable and robust evolutionary search with well-behaved controllability. Based on our preliminary results, it turns out that many conclusions about the potentials and performance of GA/GP need to be reassessed. 

Motivation

We are working toward a scalable evolutionary synthesis system using genetic programming. We hope to deal with systems such as electric circuits or mechatronic systems with hundreds or even thousands of components. However, current EAs suffer from lack of scalability. An ideal evolutionary system is characterized with three desirable attributes: Scalability (Larger-size problems can be solved when given more computing resources), Sustainability (Better innovative solutions can be continuingly discovered given more computing efforts), and Robustness (reasonable results can be obtained with high probability given a certain amount of computing cycles).  

The lack of sustainable search capability of traditional GP and its tendency to suffer from premature convergence come from two fundamental sources. One is the convergent nature of conventional EA models. The other is the variable length representation and conventional crossover and mutation operators, which cause the bloating phenomenon. HFC is a new evolutionary computation model we devised to handle the premature convergence source in term of the EA model itself.  

When compared with the natural process of evolution, which does not normally face the issues of stagnation, bloating and lack of sustainability, two significant differences can be observed. One is that, in natural evolution, an enormous population size is typically involved, while we can only use much smaller population sizes in artificial evolution.  Another major difference is that in biological evolution, evolution happens at all fitness levels, from the primitive single-cell organism to high-level mammals. This kind of simultaneous multi-level (often corresponding to fitness level) evolution in a multitude of diverse environments may contribute to the sustainability of the biological process. A similar sustainable innovation also happens in human society, in such settings as education systems. By educating students at all academic levels simultaneously and continuously, better and better students are trained to achieve increasing success. Although the population of students at one instant of time is of finite size, the unlimited timeframe and the continual importing of new students from kindergarten provide a non-depletable source for continuing innovation in the school system. In contrast, conventional GA/GP effectively terminate lower-level innovation early, as the average fitness of the population increases. That is, the probability that good building blocks contained in new randomly generated individuals become incorporated in higher-fitness individuals declines rapidly as the average fitness of the population increases. 

Understanding Conventional EA Process

Convergent Nature of Conventional Evolutionary Algorithms

Unjustified Bias and Assumptions in Conventional EC model

Previous Work on Premature Convergence of EAs

Loss of Explorative Capability (LEC): New Explanation of Premature Convergence in EAs

Generality & Impact 

This work has two potential sorts of impact. One is that it can be used to avoid or at least ameliorate the notorious premature convergence problem in evolutionary computation. The other is that it may lead to insights of other AI search algorithms.  

Ideas and techniques of HFC are applicable to any kind of population based search algorithms. These includes all flavors of evolutionary algorithms like GA, GP, ES, EP. Its conclusions are also valid for many artificial life evolution systems without controlled competition mechanisms. A paradigm shift of HFC from other EA models is that rather than trying to escape from local optima in order to battle premature convergence, HFC handles that by allowing the emergence of new optima continually in a bottom-up manner, maintaining low local selection pressure at all fitness levels, while fostering exploitation of high-fitness individuals through promotion to higher levels.

The understanding of the gradual loss of explorative capability is also applicable to simulated annealing. In this search paradigm, a (non-increasing) temperature T is used to control the accept probability of next inferior candidate. As the objective value goes up, this accept probability becomes increasingly smaller until no inferior candidate will be accepted. This is usually when the convergence happens. So simulated annealing is also a convergent algorithm. Since HFC needs a population to search simultaneously at the lower and higher fitness levels, simulated annealing can be improved by having a SA climber at each fitness levels, thus ensuring the continuing search.  

Another important insight of HFC is that solutions found in early stage of the search strong affects the possible path of later search stage (similar to the case in Genetic programming: early stage evolutions usually determines the basic framework of the solutions of later generations). Since the search in early stage is non-exhaustive or just is impossible to be searched sufficiently long (because it depends on the later evolution results to show their goodness), it is always preferred that the early search stage are conducted simultaneously with later higher level search process like in HFC.

Future Work

HFC framework has been successfully used to devise sustainable and robust GA/GPs including multi-population EAs with explicit fitness levels (HFC), multi-objective evolutionary search (HEMO), and continuous single population EA (CHFC) embodying the idea of HFC principle. We are interested in coupling HFC with new genetic programming schemes based on hierarchical composition mechanisms including modularity, hierarchy, etc. We rely on new inspirations from biological principles including evolutionary, developmental, and even neural biology.