Discrete Benchmark Functions - Self-Adaptive Heuristics for Evolutionary Computation - page 147

Gr666

TSP problem of TSPlib from Reinelt [117]: coordinates of 666 cities on earth;
geographical distances; length of optimal tour f ( x ∗ ) = 294358. We skip the
presentation of the coordinates.

B.2 SAT-Problem

3-SAT

Boolean / propositional satisfiability problem, each clause contains k = 3 literals;
NP-complete; random generation of formulas with N = 50 variables and 150
clauses; fitness function:

#of true clauses
#of all clauses

(B.1)

For the experiments in chapter 6, fifty random formulas were generated accord-
ing to the above specifications, and each formula was tested 10 times, i.e. the
experimental results are based on 500 runs.