We will consider three evolutionary algorithms for SAT, here called FlipGA [9], RFGA [7] and SAW [1]. FlipGA is a heuristic based genetic algorithm combining a simple GA with the Flip Heuristic. RFGA uses an adaptive refining function to discriminate between chromosomes that satisfy the same number of clauses and a heuristic mutation operator. The SAW algorithm is a (1,) ( is the best found in a suitable number of test experiments) evolutionary strategy using the SAW-ing (stepwise adaptation of weights) mechanism for adapting the fitness function according to the behavior of the algorithm in the previous steps. We test ASAP on the same instances (test suites 1, 2) used in [1,7,9], which are 3-SAT instances generated using the generator developed by Allen van Gelder. These instances are available at http://www.in.tu-clausthal.de/~gottlieb/benchmarks/3sat. All instances lay in the phase transition, where the number of clauses is approximately 4.3 times the number of the variables.

- Test suite 1 contains four groups of three instances each. The groups have a number of variables of 30,40,50 and 100.

- Test suite 2 contains fifty instances with 50 variables.

The performance of genetic algorithms is
generally evaluated by means of two measures:
the *Success Rate (SR)*, that is, the percentage of
runs in which the algorithm found a solution for that
instance or group of instances; and
the *Average number of evaluations to Solution (AES)*
index, which counts the average number of fitness evaluations
performed to find the solution. Note that the AES takes into
account only successful runs.

Since our algorithm uses also local search, we use an approximated
estimation of the AES called *Average Flip cost in terms of fitness
Evaluation to Solution(AFES)*.
The AFES index is based on the number of flips performed during
the execution of the local search (both accepted and not accepted flips
are counted) and is an estimation of
the cost of the local search step in terms of fitness evaluations.
If the local search performs `n_flips` flips (including accepted
and not accepted flips), one
can estimate a cost of
*K * n_flips/n_vars*
fitness
evaluations (cf. [9]), where *n_vars*
is the number of variables in the
instance and *K* is the clause length. This applies only
to K-SAT instances which are randomly generated.

The results of the experiments are given in Tables 1,
2, where *n* and *m* denote the number of variables
and of clauses, respectively.
All the algorithms are run 50 times on each
problem instance, and the average of the results is reported.
Moreover, the termination conditions for all algorithms is
satisfied either if a solution is found or if
a maximum of 300000 chromosomes have been generated.

The results show that ASAP has a very good performance, with SR equal to 1 in all instances, and smaller AFES than FlipGA in all but one instance (instance 2) where it has AFES slightly bigger than FlipGA.