  In pure strategy meta-heuristics, only one search strategy is applied for all
time. In mixed strategy meta-heuristics, each time one search strategy is
chosen from a strategy pool with a probability and then is applied. An example
is classical genetic algorithms, where either a mutation or crossover operator
is chosen with a probability each time. The aim of this paper is to compare the
performance between mixed strategy and pure strategy meta-heuristic algorithms.
First an experimental study is implemented and results demonstrate that mixed
strategy evolutionary algorithms may outperform pure strategy evolutionary
algorithms on the 0-1 knapsack problem in up to 77.8% instances. Then
Complementary Strategy Theorem is rigorously proven for applying mixed strategy
at the population level. The theorem asserts that given two meta-heuristic
algorithms where one uses pure strategy 1 and another uses pure strategy 2, the
condition of pure strategy 2 being complementary to pure strategy 1 is
sufficient and necessary if there exists a mixed strategy meta-heuristics
derived from these two pure strategies and its expected number of generations
to find an optimal solution is no more than that of using pure strategy 1 for
any initial population, and less than that of using pure strategy 1 for some
initial population.
