Lest my comments here appear entirely negative, conventional ways of measuring the merit of optimisation processes on particular problems include: cost of a solution and time to find a solution. For info-theory metrics, there's the number of trials, and the number of 'generations' of trials (there's a general generational form of optimisation problems with discrete trials).

These metrics have the advantage of being reasonable to calculate while not presuming knowlege of unexplored areas of the search space. Also, they do not depend heavily on the size of the search space (which is often unbounded).