abstract-evolution_0.jpgDescription:

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 evolutionary algorithms (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 genetic programming (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. Hierarchical Fair Competition (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.

Courses & Labs:

  • ECE 802: Evolutionary Multi-Criterion Optimization and Decision-Making (3 credits, Lecture)
  • ECE 848: Evolutionary Computing (3 credits, Lecture)
  • CSE 801: Introduction to Computational Science for Evolutionary Biologists (3 credits, Lecture)
  • CSE 845: Multi-disciplinary Research Methods for the Study of Evolution (3 credits, Lecture)
  • CSE 941: Selected Topics in Artificial Intelligence (3 credits, Lecture)

Faculty:

Erik Goodman, William F. Punch, Ronald C. Averill, Xiaobo Tan, Subir Biswas, Charles Ofria, Philip K. McKinley, Betty Cheng, Kalyanmoy Deb