Metrics of quality of parameter space exploration
It is somewhat common to measure the number of operations involved in the search. This is only really useful if you're doing scientific work, because the computational cost of measuring it accurately is quite high. For example, if you were using a GA that used tournament-based fitness selection, and wanted to compare it to one that used round-robin selection, counting the number of evaluations of individuals would be a good measure of total computational effort.

In Genetic Programming, it is fairly common to build the measurement of the total op count into the interpreter you write for the programs. You can then compare that directly to the number of evals times the length of the genomes for something like a GA.