Home Overview People Algorithms Publication Softwares

HFC-EA with Adaptive Topology (Adaptive Allocation of Subpopulations to Fitness Levels)

Overview

 In the previous HFC model [2], the allocation of subpopulations to fitness levels is configured before the evolution is started. A shortcoming of this method is that in the initial generations, the high –fitness-level subpopulations won’t actually contain any qualified individuals, and so, according to this method, are not activated for evolution. This reduces the effective population size. In the case of large cluster PC system, the better strategy would be first use the the demes at all computing nodes to discover the first level solutions. When the second level solutions are discovered, we allocate partial of the computing nodes (demes) to the second level HFC search. This strategy has another benefit which serves as a general idea. In HFC evolutionary search, it seems always a good practice to use greediest EA search until somewhat stagnation before we activate HFC simultaneous search at all levels. This can be achieved with a start-up stage in HFC by first evaluating a large number of individuals to get a distribution of fitness gradient. 

Approach

The solution presented here is to adaptively allocate subpopulations to fitness levels. In the beginning, all subpopulations are allocated to the bottom level. Later, once certain higher levels get some qualified individuals, then all intermediate levels are activated and the whole subpopulations on those activated levels are allocated according to some strategy. One simple strategy is illustrated in Figure 2. This HFC framework with adaptive topology works like a rubber band. At the initial stage, it is quite compressed, but gradually, the rubber band stretches to accommodate individuals within a larger range of fitness. In the work reported in this paper, we simply allocate the subpopulations evenly to all activated levels. Details of this procedure are described in [1].

How to achieve automatic trigging of new levels

References:

[1] Jianjun Hu, Erik D. Goodman, Kisung Seo, Zhun Fan, Ronald C. Rosenberg. HFC: a Continuing EA Framework for Scalable Evolutionary Synthesis. AAAI Symposium2003 on Computational Synthesis, Stanford March 23-26. (The analysis and solution of premature convergence problem!).

[2] Jianjun Hu, E. Goodman. Hierarchical Fair Competition Model for Parallel Evolutionary Algorithms. (WCCI2002, Congress of Evolutionary Computation 2002. Hawaii). (HTML version)

HFC Home [Overview] [People] [Algorithms] [Publication] [Softwares]