Mixed strategy may outperform pure strategy: An initial study

A pure strategy metaheuristic is one that applies the same search method at each generation of the algorithm. A mixed strategy metaheuristic is one that selects a search method probabilistically from a set of strategies at each generation. For example, a classical genetic algorithm, that applies mutation with probability 0.9 and crossover with probability 0.1, belong to mixed strategy heuristics. A (1+1) evolutionary algorithm using mutation but no crossover is a pure strategy metaheuristic. The purpose of this paper is to compare the performance between mixed strategy and pure strategy metaheuristics. The main results of the current paper are summarised as follows. (1) We construct two novel mixed strategy evolutionary algorithms for solving the 0-1 knapsack problem. Experimental results show that the mixed strategy algorithms may find better solutions than pure strategy algorithms in up to 77.8% instances through experiments. (2) We establish a sufficient and necessary condition when the expected runtime time of mixed strategy metaheuristics is smaller that that of pure strategy mixed strategy metaheuristics.