Paper Info
Title
Sequence Analysis with Motif-Preserving Genetic Algorithm for Iterated Parrondo Games
Abstract
Comparison of simple genetic algorithm with motif preserving genetic algorithm is made for the sequence analysis of Parrondo games, which is an analogue to the flashing Brownian ratchet in non-equilibrium statistical physics. The original Parrondo game consists of two individual games: game A and game B. Here game A is a coin-tossing game with winning probability p(A) slightly less than half, so that its persistent usage will be losing in the long run. Game B has two coins, and an integer parameter M. If the current cumulative capital (in discrete unit) is a multiple of M, an unfavorable coin with winning probability p(b) < 0.5 is used, otherwise a favorable coin with winning probability p(g) > 0.5 is used. Game B is also a losing game if played alone. Paradoxically, combination of game A and game B could lead to a winning game, either through random mixture, or deterministic switching. The resolution of this paradox can be made using Markov Chain analysis [1]. In this paper, we are interested in the analysis of finite deterministic switching sequences of N Parrondo game, so the number of possible sequences is 2(N). For small N, exhaustive search and backward induction have been applied successfully to short sequences. However, for long but finite deterministic sequence, the optimal ordering of games requires the use of combinatorial optimization techniques. Here we employ genetic algorithm to find the optimal game sequence. The structure found in short sequences using a problem-independent genetic algorithm, such as ABABB, is a motif. Using these motifs we invent motif-preserving point mutation operator and one-point crossover operator to exploit the structure of the optimal game sequences for large N. We show by numerical results the adapted motif-preserving genetic algorithm has great improvement in solution quality over simple genetic algorithm. The technique of motif preserving genetic algorithm can be applied to similar problem in sequence analysis once the condition of optimality is defined.
Year
DOI
Venue
2014
10.1007/978-3-319-26393-9_3
Studies in Computational Intelligence
Keywords
Field
DocType
Genetic algorithm,Parrondo game,Optimization,Game theory
Combinatorics,Crossover,Brute-force search,Markov chain,Combinatorial optimization,Game theory,Iterated function,Genetic algorithm,Mathematics,Backward induction
Conference
Volume
ISSN
Citations 
620
1860-949X
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Degang Wu1103.85
Kwok Yip Szeto26421.47