How can I calculate the "mean best fitness" measure in genetic algorithms?
The typical way you'll see a GA measured is that an algorithm with a population size of $N$ is ran $K$ times from new random seeds each time. That gives you $K$ total runs of the algorithm, each of which, at the end, had a final population of $N$ individuals. If you take the best of those $N$ from each run, you get $K$ &quot;best&quot; solutions found. The average fitness value of those $K$ solutions is your MBF.
AES here refers to the number of evaluations of the objective function the algorithm required. The reason for this is to provide a standardized amount of computation budget each algorithm used. Imagine if you compared algorithms on the basis of how many generations it took to find a good solution. In that case, I could just increase the population size of my algorithm by 100-fold or 1000-fold, and I'll probably look better. Same number of generations, but I gave my algorithm far more chances to find something good. Suppose I use wall-clock time. Now my algorithm might look better than yours just because I ran it on a much more powerful computer than you did.
The insight to make here is that GAs work by evaluating new search points. Let's just count how many times that happens. You can run a larger population for a shorter number of generations, or you can allocate the same amount of computation to running a longer time with fewer points each generation. What matters is just how many fitness function evaluations you exhausted in finding the answer.
For sudoku, you might have a fitness function that counted the number of rows, columns, or blocks that don't contain the correct digits of 1-9 and you minimize that function. You run your algorithm $K$ times from random seeds, and for each run, you record how many times you had to evaluate that fitness function before you found a $0$ (i.e., the puzzle was successfully solved). Average all $K$ of those counts, and that's your AES.
Generalizing a bit, you might calculate average evaluations to find some &quot;good enough&quot; solution, but the general concept is the same.