M²ICAL: A tool for analyzing imperfect comparison algorithms

Abstract

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 2ICAL, 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. © 2007 IEEE.