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.