Changing the Ratio Dynamically
As we explained, the shape of the ratio has a major importance on the behavior of cEAs. Reducing the ratio means reducing the global selection intensity on the population, thus promoting exploration. This is expected to allow for a higher diversity in the algorithm that improves the results in difficult problems (e.g., multimodal and epistatic problems). On the other hand, the search performed inside each neighborhood is guiding the exploitation of the algorithm. So using high ratio values we promote the exploitation of the population.
This indicates that the ratio effects on the search efficiency. We immediately can think on changing the ratio during the search to shift from exploration to exploitation [AT00]. Moreover, this change is a unique feature of cEAs that can be used to shift from exploration to exploitation at a minimum complexity without introducing just another new algorithm.
In Figure 1 we can see three static and two more dynamic pre-programmed ratios used in [AT00] for solving a set of three different problems (MMDP, FMS, and P-PEAKS). As we can see in Figure 1, these pre-programmed ratios changes the population shape at a previously fixed point during the search. One of them changes from a square shape to a narrow one, representing a change from exploitation to exploration. The other change makes the inverse operation; it first explores the population and then exploits it (narrow grid to a square one). The change is made when the algorithm makes half the mean number of function evaluations needed for solving the problem with the square grid.
|
| Figure 1. Static and dynamic ratio cEAs yielding 5 different algorithms. From top to bottom: a square grid, a rectangular grid, and a narrow grid, kept constant through the search. The two last cases show two cEAs that change from change from high (low) to low (high) ratio at generation tm. |
The numeric results obtained by Alba and Troya using the algorithms showed in Figure 1 for solving MMDP, FMS and P-PEAKS are placed in Table 1. These numbers summarizes the average results of 30 independent runs for solving the three problems.
|
||||||||||||||||||||||||
| Table1. Mean number of evaluations |
If we first analyze the case of using a static ratio (the
first three columns) we can see that reducing the ratio is more efficient in
FMS and P-PEAKS. For irregular (FMS) and, especially, for highly epistatic problems
(P-PEAKS) the reduced selection pressure of a smaller ratio improves exploration.
However, for the MMDP problem the higher pressure of the square grid (0.110)
is more efficient. We note in red the more efficient
results in Table 3.
The next natural step for this study will consist in making the algorithm capable
of changing itself during the execution the ratio towards the better one at
each time. This new concept is introduced in [AD03].
The basic idea is to get one or more measures
of the evolution of the algorithm and checking every certain time interval the
acceleration improved by the population in terms of the measures selected. As
this acceleration be the algorithm will change the ratio to one bigger or smaller,
or keep it constant. The self-guide mechanism
proposed modifies the population topology during the search as a
factor of the convergence speed. In the next algorithm it is described a model
of how does this criterion works; where 
and
represent the convergence's measures to use:
The way we control the grid shape consists
on including a slant towards square grids (bigger exploitation) when the algorithm
evolves slowly (i.e. the acceleration of the convergence between consecutive
populations changes less than a 
value). This is represented by the condition of line 1 in the algorithm above.
If in the other hand the search is considered too fast the population shape
will then change to a more rectangular (narrow) one. The condition for detecting
this situation is expressed by line 3 in the algorithm above. It can be seen
that this is expected to occur when the acceleration is greater than 
times the last known one.
The main objective of these adaptive criteria will be trying to maintain the diversity for longer, decreasing this way the possibilities of falling in local optima.
Function ChangeTo(square/rectangular) the algorithm above changes the population grid shape to the immediately next more square/rectangular allowed one (the limits are the absolutely square grid and the completely linear one). In these cases wherein the change is not possible because the algorithm is using an extreme grid shape yet and we will need to exceed that limit (i.e. ChangeTo(square) being already the actual grid shape square, or ChangeTo(rectangular) if the current grid shape is the most narrow one) the algorithm does not make any change in the grid shape. For finishing the definition of adaptation for our criteria we have just to specify how the grid change is accomplished: position (i,j) of an individual in the new grid is calculated as shown in Equation 1.
 |
(1) |
These adaptive criteria have two important advantages: