Next: Bibliography Up: An Adaptive Evolutionary Algorithm Previous: Comparison with Local Search



Discussion

It is interesting to analyze the role of the adaptation mechanism in ASAP. For lack of space, we do not report the results obtained by EvoSAT on the considered benchmark instances, but we briefly compare them with those obtained by ASAP. On instances of the Test Suites 1,2 the performance of EvoSAP is similar to the one of ASAP. However, on the DIMACS instances EvoSAP has a worse performance than ASAP. For example, on the instance jnh212 EvoSAP has a success rate of 0.9, it takes 10855 iterations (on the average) to find a solution, and over 1.2 millions (on the average) of accepted flips.

As illustrated in the tables on the DIMACS experiments, the restart mechanism of ASAP is not used in some experiments (e.g., on the classes aim-100-6_0 and ii8). However, in other experiments, the mechanism is more effective. For example, on the instance jnh212 the performance of ASAP without the restart mechanism becomes poor: ASAP is able to find a solution only in five of the ten runs. Thus the results indicate that the adaptation mechanism of ASAP improves the performance of the evolutionary algorithm.

In conclusion, on the tested benchmarks ASAP has a rather satisfactory performance, indicating that hybridization of evolutionary algorithms with meta-heuristics based on local search provides a powerful tool for solving hard satisfiability problems.



Next: Bibliography Up: An Adaptive Evolutionary Algorithm Previous: Comparison with Local Search
Claudio Rossi
1999-11-30