Overview of HFC: How to Achieve Sustainable Evolution

Inspired by the sustainable evolutionary process in societal and economic systems, HFC solves the loss of exploratory capability problem in EAs by enforcing that evolution continues simultaneously at all fitness levels. Instead of depleting the potentials of the basic frameworks, the continuing innovation at the low-fitness level provides a constant stream of new frameworks for higher-level exploitation. These bottom-up moving individuals can survive the competition they face (thus allowing sufficient assembly of building blocks) due to the maintenance of fair competition: only individuals with similar performance levels are allowed to compete.  From the perspective of avoiding local optima, instead of depending on jumping out of the local basin of attraction occupied by the highly converged population, which is often very improbable, HFC deals with trapping in local basins of attraction by allowing new individuals in other basins of attraction to emerge continuously. When examined in terms of search effort allocation, the competition among individuals is not constrained among the individuals of the current population. Instead, the allocation of computing resource takes a much stronger global view by ensuring that the assembly of building blocks happens at all absolute fitness levels. So the unit of allocation of search effort is not individuals, but fitness levels.

Several forms of multi-population HFC have already been introduced (Hu & Goodman, 2002; Hu, Goodman et al., 2002, Hu, Kisung et al., 2003).  In those models, the number of fitness levels is specified by the user or may be determined adaptively. The major goals of this framework can be summarized as follows:  

a) To ensure fair competition among individuals by segregating competition among different levels of individuals,

In this way, the high-fitness individuals won’t threat the existence of lower-level fitness as in most EAs. The protection of “inferior individuals are much more effective and simpler than other techniques such as fitness sharing  and species conserving algorithm SCGA(Li, et al., 2002). Two selection operators enforce the fair competition. One is the operator for choosing breeding parents. The other is the operator to select the individuals to be replaced by new offspring.

b) To assure that exploration and exploitation occur at all fitness levels

By allocating computing cycles to demes of all fitness levels, innovation happens all the way from the embryo primitives to the highly evolved (then also highly biased) individuals. By concatenating higher-level to lower-level fitness demes, a building block assembly line is established. In analogy to the Cambrian Age innovation stage in the history of biological evolution, HFC essentially keeps Cambrian emergence of new species operating. Therefore, HFC provides the capability of sustainable evolution for GP. It also greatly relieves the conventional demand for large population sizes to achieve good performance, as will be shown in the following experimental section.

c) To provide hierarchical elitism (one-way elitism)

In the multi-deme HFC, when the fitness of the offspring is lower than the fitness admission threshold of the current level, this offspring will be discarded. Otherwise, it may continue to stay in the current fitness level or be exported to a higher level. This appears as a one-way migration from lower-level demes to higher-level demes. In the context of GP, since usually higher fitness individuals have higher complexity, the elitism here can effectively remove those individuals which have unnecessary complexity for their fitness level. This mechanism helps to control the bloating phenomenon in GP.

d) To incorporate new genetic material continually to provide a constant influx of evolutionary potential

A random individual generator is configured at the bottom of the HFC deme hierarchy to provide inflow of unbiased genetic material to higher fitness levels. From the bottom level to the highest fitness level, this convergent evolutionary process will never deplete its evolutionary potential. Instead, it provides a mechanism to allow innovation to happen continually at all fitness levels.