2

I'm using OptaPlanner to solve some plannig problems. I read the documentation and I'm not quite sure how does exactly Hill Climbing and Tabu Search algorithms work. What I'm unsure of is:

  • does hill climbing pick only moves with THE BEST score that is BETTER than current one or does it allow to pick moves with THE BEST score that is NOT WORSE than the current one?
  • does tabu search allow picking moves that have WORSE score than the current one if there is no move leading to a solution with better or equal score to the current one?
gadzix90
  • 744
  • 2
  • 13
  • 28

1 Answers1

3

For Hill Climbing, see HillClimbingAcceptor#isAccepted(...). It accepts any move that has a score that is better or equal to the lastest step score. And looking at the default forager config for hill climing (in LocalSearchPhaseConfig, which says foragerConfig.setAcceptedCountLimit(1);), as soon as 1 move is accepted, it is the winning move.

For Tabu Search, it will select moves that have a worse score, if:

  • in the number of moves it selects per step (usually acceptedCountLimit is configured to 1000 or so), no better move is seen
  • OR all the moves that do lead to a better score are in the tabu list (they are "taboo to use"). For solutionTabu, this means that there's a guarantee that they won't lead to a new best solution (but solutionTabu is useless). For entityTabu there is no such 100% guarantee, but you will get a better results in about 99.999999999999999999999999999999999999999999999999999999999999999% of the cases if you have more than let's say 50+ variables (and more if you have a 1000+ variables).

PS: Hill Climbing sucks. There's never a good reason to not use Late Acceptance or Tabu Search instead.

PPS: Use the Benchmarker, do let HC, LA, TS, ... fight against each other. It will give you a lot of insight.

Geoffrey De Smet
  • 26,223
  • 11
  • 73
  • 120