Late Acceptance Hill Climbing Algorithm

Question

I am writing code to address the Nurse Restoring Problem

I have implemented Simulated Annealing and I am interested in comparing the results to Late Acceptance Hill Climbing

I have found some pseudo code for Late Acceptance but need a little help to write it in Java:

Produce an initial solution s
Calculate initial cost function C(s)
Set the initial number of steps I=0
For all k in ( 0.. L-1 ) C_hat[k]=C(s)
Do until a stopping condition
 Construct a candidate solution s*
 Calculate its cost function C(s*)
 v = I mod L
 If C(s*) <= C_hat[v]
 Then accept s*
 Insert cost value into the list C_hat[v] = C(s)
 Increment a number of steps I=I+1
End do

I really don't get this bit: For all k in ( 0.. L-1 ) C_hat[k]=C(s)

The pseudo code is from http://www.yuribykov.com/LAHC/LAHC_wonders.pdf

Answer 1

I'm writing in for the "element of" relation and C_hat[k] for the C with the "hat" on top and subscript k, as those things don't display well in this format.

For all k in ( 0.. L-1 ) C_hat[k]=C(s)

The purpose of this line is that in the rest of the algorithm, you assume that you can take any value v in the range 0 to L-1 and test whether If C(s*) <= C_hat[v]. This doesn't make sense unless C_hat[v] is already defined. the line quoted above ensures that every such C_hat[v] has a well-defined value before you attempt to use that value.

It also means you'll never accept any solution worse than the first one you tried.

---

By the way, I am suspicious about the way the following line is written in the source document:

Insert cost value into the list C_hat[v] = C(s)

Based on the formatting of the algorithm in the source document, I would conclude that this operation is to be performed on every iteration of the loop, whether or not the new solution is accepted. The next time the index v comes up, the newest solution only has to be better than the one previously tried for index v, even if that proposed solution was horribly bad. That does not seem right. I wonder if that line was actually supposed to be part of the then clause, to be executed only if the solution is accepted.