Evolutionary Computation

Evolutionary Computation



Erik Goodman, Professor
William F. Punch, Associate Professor
Ronald C. Averill, Associate Professor
Xiaobo Tan, Assistant Professor
Subir Biswas, Associate Professor
Charles Ofria, Associate Professor
Philip K. McKinley, Professor
Betty Cheng, Professor
Kalyanmoy Deb, Koenig Endowed Chair Professor

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.


Related Websites:  Genetic Algorithms Research and Applications Group (GARAGe)