 |
    |
How Are We Doing? Predicting Evolutionary Algorithm Performance
Mark A. Renslow, Brenda Hinkemeyer, and Bryant A. Julstrom
Department of Computer Science, St. Cloud State University, St. Cloud, MN 56301 USAmarkminn@mac.com
brenda@nikosha.net
julstrom@eeyore.stcloudstate.edu
Abstract. Given an evolutionary algorithm for a problem and an instance of the problem, the results of several trials of the EA on the instance constitute a sample from the distribution of all possible results of the EA on the instance. From this sample, we can estimate, non-parametrically or parametrically, the probability that another run of the EA, independent of the initial ones, will identify a better solution to the instance than any seen in the initial trials. We derive such probability estimates and test the derivations using a genetic algorithm for the traveling salesman problem. We find that while the analysis holds promise, it should probably not depend on the assumption that the distribution of an EA’s results is normal.
LNCS 3103, p. 82 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004