hw5.md

home | copyright ©2016, tim@menzies.us

overview | syllabus | src | submit | chat

---

Homework5: Your Second Optimizer (Basic Max Walk Sat)

Read the lecture on Max Walk Sat.

Code MaxWalkSat for the Osyczka2 model.

Do not be clever. This is throw away code. As quick and as dirty as you like.

Use the same energy calcs as for SA.

Try and make a report that looks like the output from SA.

Tips

Not everything is "ok".

Note that this model has constraints-- so after you mutate a solution, you must check if it is ok (I.e. does not violate the constraints-- otherwise, mutate again until ok).

Local Search

Not sure that this is useful to you but, for what its worth, here is my local search code. First, for each column, it knows how to spin over min to max of each col:

import random
def r(): return random.random()

class Column:
  "This code is in a class that knows min,max for each decision"
  ...
  def any(i):
    return i.min + r()*(i.max - i.min)
  def localSearch(i):
    for j in xrange(0,10):
      yield i.min + j/10*(i.max - i.min)

def mwsfiddle(old):
  new = old[:]  # copy
  col = random.choice(cols) # pick any column
  i   = col.pos # we will change things in this column
  if r() > 0.5: # just do anything
    new[i] = col.any()
    return new
  best = None
  for x in col.localSearch():
    new[i] = x
    if better(new,best): # insert your scoring function here
      best = new[:]
  return best

When

Use p=0.5

Watch those evals

Note that now, when you report evals, then you are reporting steps * evals. So when you report how long it takes to reach a solution, remember to reports steps * evals.