Exploitation vs Exploration

RANDOM SEARCH  (Total exploration!)
   init X     // init genome 
   while fitness(X)<goodenough {
         X' = random()                   // random genome
         if (fitness(X')>fitness(X)) X = X'
   }

LOCAL SEARCH
   init X     // init genome 
   while fitness(X)<goodenough {
         X' = mutate(X)     // exploiting X!!!
         if (fitness(X')>fitness(X)) X = X'
   }

* access to the whole space (neutral mutation):
question of do I have good exploration?


THE BIT FLIPPING LOCAL SEARCH ALGORITHM (simple local search)
   init X
   while (fitness(X)<goodenough) {
         X' = flipRandomBit(X)
         if (fitness(X')>fitness(X)) X=X'
   }

INC/DEC
   init X
   while (fitness(X)<goodenough) {
         X' = incOrDec(X)
         if (fitness(X')>fitness(X)) X=X'
   }

init X
   while (fitness(X)<goodenough) {
         X' = flipRandomBit(X)
         if (fitness(degray(X'))>fitness(degray(X))) X=X'
   }

---------------------------

OTHER LOCAL SEARCH  (greedy exploitation by looking through neighborhood)
        BIASED!
   init X
   while (fitness(X)<goodenough) {
         loc = 0
         while (true) {
             X' = flipBit(loc, X)
             if (fitness(X')>fitness(X)) {
                 X=X'
                 break
             }
             loc = (loc + 1) % len(gene)
         }
   }


STEEPEST ASCENT LOCAL SEARCH (biased)
   init X
   while (fitness(X)<goodenough) {
         X' = allNeighbors(X)   // X' is a set!
         if (maxFitness(X')>fitness(X)) X=argmaxFitness(X')
   }


AVOID LOCAL OPTIMUM (not do random search)
approaches avoiding local optima

1. random restarts (gak)
2. simulated annealing
3. tabu search