12.13

Greedy hill-climbing with random restarts (GSAT)

1. Start from a random truth assignment A.
2. Repeatedly flip the single variable whose change raises the number of satisfied clauses the most; stop when no flip helps.
3. Remember the best assignment found, restart from step 1 a fixed number of times, and finally return the best of all runs.

Pseudocode

MAX-SAT-GSAT(F, R, T)  # F: set of clauses
 best ← randomAssignment()
 bestVal ← satisfied(F, best)
 for r = 1 .. R do
  A ← randomAssignment()
  for t = 1 .. T do
   if satisfied(F, A) = |F| then return A # optimal
   v* ← argmax_v Δ(F, A, v) # gain of flipping v
   if Δ(F, A, v*) ≤ 0 then break # local optimum
   flip v* in A
   update best if A is better
 return best

Here Δ(F, A, v) is the change in satisfied-clause count obtained by toggling variable v.

Python reference implementation

import random
def gsat(clauses, nvars, restarts=50, flips=1000):
 def score(A):
  return sum(any(lit>0 and A[lit] or lit<0 and not A[-lit] for lit in c) for c in clauses)
 bestA = [False]*(nvars+1); bestS = -1
 for _ in range(restarts):
  A = [False]+[random.choice([True,False]) for _ in range(nvars)]
  for _ in range(flips):
   s = score(A)
   if s == len(clauses): return A[1:]
   gain = []
   for v in range(1, nvars+1):
    A[v] = not A[v]; gain.append(score(A)-s); A[v] = not A[v]
   v = max(range(1,nvars+1), key=gain.__getitem__)
   if gain[v-1] <= 0: break
   A[v] = not A[v]
  if s > bestS: bestA, bestS = A, s
 return bestA[1:]

Complexity: a flip costs O(m) where m is the number of clauses; total time O(m R T).

This simple heuristic is fast, easy to code, and typically achieves solutions very close to the maximum for large MAX-SAT instances.

Back to Chapter 12