Optaplanner邻域搜索算法

评论

Local Search Concepts

Step

一个step，是一个优胜的move，局部搜索在当前状态，会尝试很多move，然后挑选最佳的那一个move当作step

注意到Local Search并没有使用到搜索树，而是走出了一个Search Path，这条Path不会产生大量分支，所以Local Search是Scalable的

Decide the Next Step

Local Search由以下三种组件来辅助决策下一个step：

  • MoveSelector：MoveSelector挑选出当前状态所有可能的move
  • Acceptor：Acceptor筛选并去除那些不可接受的move
  • Forager：Forager汇聚了所有可被接受的move，然后从中挑选一个当作下一个step

Forager

一个Forager汇聚了所有的可被接受的move，通常它会挑选得分最高的move，如果有许多得分相同的move，那么它会随机挑选一个

acceptedCountLimit

当存在太多的可能的move的时候，如果每一个step都去衡量每个move的得分，那么效率会变得极其低下，我们可能只希望衡量全体move的一个子集

acceptedCountLimit限制了每一轮step有多少个move是我们需要关注的

pickEarlyType

一个Forager可以在一个step的开局就挑选一个move，忽略后续挑选的move

  • NEVER：所有可接受的move的得分都要计算，这是默认选项
  • FIRST_BEST_SCORE_IMPROVING：挑选第一个让最佳得分增加的move
  • FIRST_LAST_STEP_SCORE_IMPROVING：挑选第一个让上一步的得分增加的move

whoseJam