The Influence of Ratio in cEAs

As shown in [SJ96], the grid-neighborhood relationship can be quantified by the relative ratio between their radii (Eq. 1). Algorithms with similar ratio show a similar selection pressure.


In Figure 1 we can see this effect, where an L5 neighborhood on a 32x32 grid with ratio of 0.06815 produces a growth curve nearly identical to a C21 neighborhood on a 64x64 grid with a ratio of 0.06891.

Figure 1. Emergent growth curves using constant radius ratios

Looking at Eq. 1 we can notice that it is possible to change the ratio just by modifying the value of either the neighborhood or the grid radius, or both of them. In Figure 2 we show how does the ratio changes when we change the grid shape, keeping the same neighborhood.

Figure 2. Relation between grid radius and the ratio

In [AT00] and [AD03] we can find an extensive study in the influence of this ratio on the efficiency in the search of a cEA. In these two studies the neighborhood is kept constant in size (NEWS is used) and the population shape is the parameter that varies for changing the ratio. These two works conclude that a cEA with a thin grid -low ratio- is more efficient for multimodal and/or epistatic problems while higher-ratio cEAs are more efficient in non-epistatic and simple problems. Finally, cEAs with a medium ratio seem to be more proper for combinatorial optimization problems. These two works also have studied the improvement in the efficiency of the algorithm when using dynamic ratios, which change the value of the ratio during the execution.