Mixed Strategy May Outperform Pure Strategy: An Initial Study
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Evolutionary AlgorithmsSimilar Papers 제목 키워드 기반
Pure Strategy or Mixed Strategy?
Mixed strategy EAs aim to integrate several mutation operators into a single algorithm. However few theoretical analysis has been made to answer the question whether and when the performance of mixed strategy EAs is bett…
Optimization-Based Algorithm for Evolutionarily Stable Strategies against Pure Mutations
Evolutionarily stable strategy (ESS) is an important solution concept in game theory which has been applied frequently to biological models. Informally an ESS is a strategy that if followed by the population cannot be ta…
On the Approximate Purification of Mixed Strategies in Games with Infinite Action Sets
We consider a game in which the action set of each player is uncountable, and show that, from weak assumptions on the common prior, any mixed strategy has an approximately equivalent pure strategy. The assumption of this…
Mixed Strategy Game Model Against Data Poisoning Attacks
In this paper we use game theory to model poisoning attack scenarios. We prove the non-existence of pure strategy Nash Equilibrium in the attacker and defender game. We then propose a mixed extension of our game model an…
Data PoisoningModel PoisoningLearning Revenue Maximization using Posted Prices for Stochastic Strategic Patient Buyers
We consider a seller faced with buyers which have the ability to delay their decision, which we call patience. Each buyer's type is composed of value and patience, and it is sampled i.i.d. from a distribution. The seller…