  This article compares four probabilistic algorithms (global algorithms) for
Word Sense Disambiguation (WSD) in terms of the number of scorer calls (local
algo- rithm) and the F1 score as determined by a gold-standard scorer. Two
algorithms come from the state of the art, a Simulated Annealing Algorithm
(SAA) and a Genetic Algorithm (GA) as well as two algorithms that we first
adapt from WSD that are state of the art probabilistic search algorithms,
namely a Cuckoo search algorithm (CSA) and a Bat Search algorithm (BS). As WSD
requires to evaluate exponentially many word sense combinations (with branching
factors of up to 6 or more), probabilistic algorithms allow to find approximate
solution in a tractable time by sampling the search space. We find that CSA, GA
and SA all eventually converge to similar results (0.98 F1 score), but CSA gets
there faster (in fewer scorer calls) and reaches up to 0.95 F1 before SA in
fewer scorer calls. In BA a strict convergence criterion prevents it from
reaching above 0.89 F1.
