= Iterated local search acceptance rule
An \b[iterated local search acceptance rule] chooses the next current solution after a perturbation has been followed by <local search>. Let the current locally improved solution be $s$ and the new locally improved candidate be $q$, with a minimized <objective function> $f$. The decision concerns these search states, not just the potentially poor intermediate output of the <local-search perturbation>.<Iterated Local Search by Helena R. Lourenço and others>[§2, framework; §3.3, acceptance criteria]{ref}
One rule accepts only improvement:
$$
s_{\mathrm{next}}=\begin{cases}q,&f(q)<f(s),\\s,&f(q)\geq f(s).\end{cases}
$$
The paper calls this policy Better. Its current costs cannot increase, which follows immediately from the two cases. That property does not establish that the search will reach a <global minimum>. The RW rule instead retains the latest candidate regardless of cost, allowing movement among locally improved solutions.<Iterated Local Search by Helena R. Lourenço and others>[§3.3, equations(1)–(2), Better and RW]{ref}
For an original numerical comparison, suppose $f(s)=10$. A perturbation temporarily raises the cost to18, and subsequent <local search> lowers it to12. Better rejects the candidate with cost12, while RW accepts it; neither decision is made by comparing10 with the intermediate18. If the same procedure instead reaches cost8, both accept.
A <simulated annealing>-type option accepts a worse candidate with probability $\exp[-(f(q)-f(s))/T]$, with $T>0$. At cost difference2 and $T=2$, this probability is $e^{-1}\simeq0.368$. The temperature is a parameter of the rule, not a guarantee that a particular finite run escapes every trap.<Iterated Local Search by Helena R. Lourenço and others>[§3.3, LSMC acceptance criterion]{ref}
A permissive current-state rule can retain a candidate worse than an earlier result. Keeping a separate best-so-far solution preserves that result while allowing exploration. Report both the current-state acceptance policy and the best-result bookkeeping when comparing search runs.
Back to article page
