Next: Adding Adaptivity Up: An Adaptive Evolutionary Algorithm Previous: Introduction



Evolutionary Local Search

The idea of integrating evolutionary algorithms with local search techniques has been beneficial for the development of successful evolutionary algorithms for solving hard combinatorial optimization problems (e.g., [8,9,10]). In a previous work [9] we have introduced a simple local search based genetic algorithm for 3-SAT. Here we consider the restriction of that algorithm to a population consisting of just one chromosome (thus crossover is not used). We call the resulting evolutionary algorithm EvoSAP. In the next section we show how EvoSAP can be improved by incorporating an adaptive diversification mechanism based on TABU search.

PROCEDURE EvoSAP
 randomly generate chromosome C;
 apply Flip Heuristic to C;
 WHILE (NOT termination condition) DO
  BEGIN
   C0=C; 
   apply mutation to C;
   apply Flip Heuristic to C;
   IF (C0 better C) C=C0;
  END 
END

In EvoSAP a single chromosome is used, which produces an offspring by first applying mutation and next local search. The best chromosome between the parent and the offspring is selected for the next generation. The process is repeated until the termination condition is satisfied, that is, when either a solution is found or a specified maximum number of chromosomes have been generated.

Let us describe the main features of EvoSAP.

Representation. A chromosome is a bit string of length equal to the number of variables describing an instantiation of the variables of the considered SAT problem, where the value of the i-th gene of the chromosome describes the assignment for the i-th variable (with respect to a fixed ordering of the variables). Fitness function. The fitness function counts the number of clauses that are satisfied by the instantiation described by the chromosome. Clearly, a chromosome is better than another one if it has higher fitness.

Mutation. The mutation operator considers each gene and it flips it if a randomly generated real number in [0,1] is smaller than the considered mutation rate mut_prob.

PROCEDURE FLIP HEURISTIC
BEGIN 
 generate a random permutation S of [1..n_vars]
 REPEAT
   improvement:=0;
   FOR i:=1..n_vars DO
    BEGIN
    flip S(i)-th gene of C;
    compute gain of flip;
    IF (gain >= 0)
     BEGIN
      accept flip;
      improvement:=improvement+gain;
     END
    ELSE  /* restore previous value */
     flip S(i)-th gene of C;
    END
  UNTIL (improvement=0)
END

Flip Heuristic. In the local search algorithm we consider, called Flip Heuristic, each gene is flipped and the flip is accepted if the number of satisfied clauses increases or remains equal ( gain >= 0). This process is repeated until no further improvement is obtained by flipping any of the genes. In the figure describing the Flip Heuristic in pseudo-code, n_vars denotes the number of the variables. The gain of the flip is computed as the number of clauses that become satisfied after the flip minus the number of clauses that become unsatisfied. If the gain is not negative then the flip is accepted, otherwise it is rejected. Note that we accept also flips that yield no improvement gain=0, that is we allow side steps. The inner loop is repeated until the last scan produces no improvement.



Next: Adding Adaptivity Up: An Adaptive Evolutionary Algorithm Previous: Introduction
Claudio Rossi
1999-11-30