M2ICAL: A Tool for Analyzing Imperfect Comparison Algorithms

Practical optimization problems often have objective functions that cannot be easily calculated. As a result, comparison-based algorithms that solve such problems use comparison functions that are imperfect (i.e. they may make errors). Machine learning algorithms that search for game-playing programs are typically imperfect comparison algorithms. This paper presents M²ICAL, an algorithm analysis tool that uses Monte Carlo simulations to derive a Markov chain model for imperfect comparison algorithms. Once an algorithm designer has modeled an algorithm using M2ICAL as a Markov chain, it can be analyzed using existing Markov chain theory. Information that can be extracted from the Markov chain include the estimated solution quality after a given number of iterations; the standard deviation of the solutions´ quality; and the time to convergence.