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.