14.5 Evolutionary Algorithms 639 Procedure Randomized Tabu Search Input: State space min. problem Output: State with low evaluation Tabu {s} best s Terminate false u s while (¬Terminate) v Select(Succ(u) \ Tabu) if ( f (v)< f (u)) v best u else r Select(0, 1) if r < e f (u)-f (v) T ;; Initialize tabu list ;; Initialize currently best state ;; Initialize termination flag ;; Start search from initial state ;; Loop ;; Generate successors ;; Choose (random) successor ;; Evaluation improved, select v ;; Evaluation worse ;; Choose random probability ;; Check Boltzmann condition ;; Continue with v ;; Update tabu list ;; Modify flag ;; Output solution v u Tabu Refine(Tabu) Terminate Update(Terminate) return best