Instance Selection Using Evolutionary Algorithms: An Experimental Study - Advanced Techniques in Knowledge Discovery and Data Mining - page 139

5.4.4 Population-Based Incremental Learning (PBIL) [5]

PBIL is a combination of GAs and competitive learning. It was designed for
binary search spaces. The PBIL algorithm attempts to explicitly maintain statistics
about the search space to decide where to sample next.
The objective of the algorithm is to create a real-valued probability vector, V p ,
which, when sampled, reveals high-quality solution vectors with high probability.
For example, if a good solution can be encoded as a string of alternating 0's and
1's, a suitable final V p would be 0.01, 0.99, 0.01, 0.99, etc. The values of V p are
initialized to 0.5. Sampling from this vector yields random solution vectors
because the probability of generating a 1 or 0 is equal. As the search progresses,
the values in V p gradually shift to represent high evaluation solution vectors
through the following process:

1. A number of solution vectors ( N samples ) are generated based on the
probabilities specified in V p .
2. V p is pushed toward the generated solution vector with the highest evaluation,
S best . This is accomplished as follows:

V p [ i ]= V p [ i ] • (1- LR ) + S best [ i ] • LR , (5.1)

where LR is the learning rate, which specifies how large the steps toward the best
solution are.
3. After the probability vector is updated, a new set of solution vectors is
produced by sampling from the updated probability vector, and the cycle is
continued.

Furthermore, PBIL applies mutations on V p , with a purpose analogous to
mutation in GAs: to inhibit premature convergence. Mutations perturb V p with a
small probability, P m , in a random direction, Mut_Shif .

5.5 Evolutionary Instance Selection

EAs may be applied to the IS problem, because it may be formulated as a search
problem. In this chapter, these EAs have been called evolutionary IS algorithms .
Examples of these algorithms may be found in [4], [21], [22], [23], [19], [41],
which are concerned with the application of the GAs to PS, and in [32], which is
concerned with the application of the GAs to TSS.
As we have mentioned, the objective of this chapter is to study the performance
of the four EAs described in the previous section as IS algorithms applied to PS
and to TSS, comparing their results with the ones obtained by the classical
algorithms introduced in Section 5.3.