1
$\begingroup$

I've just started to learn genetic algorithms and I have found these measurements of runs that I don't understand:

MBF: The mean best fitness measure (MBF) is the average of the best fitness values over all runs.

AES: The average number of evaluation to solution.

I have an initial random population. To evolve a population I do:

  1. Tournament selection
  2. One point crossover.
  3. Random resetting.
  4. Age based replacement with elitism (I replace the population with all offsprings generated).
  5. If I have generated G generations (in other words, I have repeated these four points G times) or I have found the solution, the algorithm ends, otherwise, it comes back to point 1.

Is the mean of the best fitness the mean fitness of all of each generations (G best fitness)?

MBF = (BestFitness_0 + ... + BestFitness_G) / G

I'm not English and I don't understand the meaning of "run" here.

$\endgroup$

1 Answer 1

2
$\begingroup$

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$ "best" 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 "good enough" solution, but the general concept is the same.

$\endgroup$
2
  • $\begingroup$ So, a run is when I do Tournament selection, One point crossover, Random resetting, Age based replacement with elitism, isn't it? I'm having problems understanding the meaning of run. I do all of those steps, and I use the offspring I got as the population of s new execution algorithm. And I do this G times. Do I need to get the best fitness G times, and then get the mean value? $\endgroup$
    – VansFannel
    Jul 19, 2018 at 12:42
  • $\begingroup$ By a "run", I mean a complete test of your GA. You choose parameters for each test -- tournament selection, 1x crossover, bitwise mutation with probability p, population size of 100, etc. One of those parameters has to be a stopping condition of some sort. Do you run for 500 generations? Do you run until you solve the puzzle? Whatever. At some point, your algorithm terminates. That whole process from initial random population until it terminates is one "run". $\endgroup$
    – deong
    Jul 20, 2018 at 13:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .