An Algorithmic Description - Design and Analysis of Learning Classifier Systems - page 178

No particular criteria determine the convergence of the genetic algorithm when
used in the following experiments. Rather, the number of iterations that it per-
forms is pre-specified. Additionally, an elitist strategy is employed by separately
maintaining the highest-fitness model structure M ∗ found so far. This model

structure is not part of the normal population, but is replaced as soon as a fitter
model structure is found.
This completes the description of the genetic algorithm that was used. It is
kept deliberately simple to not distract from the task it has to solve, which is
to find the model structure that maximises p ( M|D ). In the presented form, it
might be considered as being a simple Pittsburgh-style LCS.

8.2.2 Model Structure Search by Markov Chain Monte Carlo

The given use of the MCMC algorithm provides a sample sequence M 2 ,...

from the model structure space that follows a Markov chain with steady state
probabilities p (

M 1 ,

)[19].Assuch
a sampling process spends more time in high-probability ares of p (

M|D ), and thus allows sampling from p ( M|D

), it
takes more samples from high-probability model structures. Hence, the MCMC
algorithm can be seen as a stochastic hill-climber that aims at finding the

M|D

M

that maximises p ( ). The algorithm presented here is based on a similar

algorithm developed for CART model search in [63].
The sample sequence is generated by the Metropolis-Hastings algorithm [103],
which is give by the following procedure: given an initial model structure

M|D

M 0 ,

M a candidate model structure is created in step t + 1, based on the current

M ,with model structure M t . This candidate is accepted, that is, M t +1 =

probability

min p (

) , 1 ,

M t |M ) p ( M |D

)

(8.4)

p ( M |M t ) p ( M t |D

and otherwise rejected, in which case the sequence continues with the previous
model, that is,

M |M t ) are the probability
distributions that describes the process of generating the candidate model

M t +1 = M t . p ( M t |M )and p (

M .

As the search procedure tends to prefer model structures that improve p ( ),

it is prone to spending many steps in areas of the model structure space where
p (

M|D

) is locally optimal. To avoid being stuck in such areas, random restarts
are performed after a certain number of steps, which are executed by randomly
reinitialising the current model structure.
The initial model structure

M|D

M 0 , as well as the model structure after a random
restart, is generated by randomly initialising K classifiers, where K needs to
be given. The matching function is assumed to be sampled from a probability
distribution p ( m k ). Thus,

M 0 is generated by taking K samples from p ( m k ).
The exact form of p ( m k ) depends on the chosen representation, and thus will be
discussed later.
A new candidate model structure M is created from the current model struc-

ture M t with K t classifiers similarly to the procedure used by Chipman, George

and McCulloch [63], by choosing one of the following actions: