H F C- the Hierarchical Fair Competition Model for
Scalable, Sustainable and Robust Evolutionary Computation
Problems with Current Evolutionary Computation
Current evolutionary computation systems
have failed to achieve the desired scalability for solving many complex
problems. They are unable to evolve solutions with high-complexity like
an electric circuit with several thousands of components, even given
huge amount of computers (e.g. 1000PC). They are not sustainable in term
of making innovations: all EC users have the experience that some
impressive innovation in the early stages, the evolution seems not be
able to achieve any major progress quickly, whatever more computing
cycles are available. They are opportunistic, sometimes they get some
good results, some times they don't. We are interested in asking the
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:
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.
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
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.
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.
MSU Genetic Algorithm Research & Application Group (GARAGe) EB2340, MSU East Lansing, MI 48824 USA