7
$\begingroup$

I have a genetic algorithm for an optimization problem. I plotted the running time of the algorithm on several runs on the same input and the same parameters (population size, generation size, crossover, mutation).

The execution time changes between executions. Is this normal?

I also noticed that against my expectation the running time sometimes decreases in place of increasing when I run it on a larger input. Is this expected?

How can I analyze the performance of my genetic algorithm experimentally?

$\endgroup$

migrated from cstheory.stackexchange.com Feb 6 '14 at 4:13

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 5
    $\begingroup$ GAs and heuristics are often unpredictable, and it can be very hard to understand or analyze them theoretically. Based on the data you provide, I don't think anyone can provide an answer better than "it's probably normal, I don't know." You could try running your GA with the same parameters multiple times, and record say the average number of iterations. Then tweak the parameters, and try again. $\endgroup$ – Juho Jan 7 '14 at 16:27
  • 2
    $\begingroup$ Yes, it is normal, it is a heuristic algorithm (it is not a nondeterministic algorithm, that has a technical meaning, these are different concepts). It is also normal for any algorithm to perform better on some larger inputs than on some smaller inputs because they might be simpler to solve, size if not the only determining factor. One cannot say much about the performance of an algorithm on practical instances usually other than how they perform and particular data sets and how they compare to other algorithms for the problem on those data sets. $\endgroup$ – Kaveh Jan 18 '14 at 17:46
  • $\begingroup$ you didn't mention how you monitor your running time. besides what everybody said about heuristics being hard to predict, if you don't measure the actual computational effort (for example by determining the running time according to the computer's clock), it is very likely you'll get awkward results... $\endgroup$ – Ron Teller Feb 6 '14 at 11:28
  • 1
    $\begingroup$ I don't quite get the gist of the question. What is the performance measure you are interested in? What kind of result are you after that can not be got by running N times and averaging? $\endgroup$ – Raphael Feb 9 '14 at 23:01
7
$\begingroup$

The typical approach is performing several runs of the evolutionary algorithm (EA) and plot the average performance over time (average performance of best-of-run-individual NOT population average).

A good rule of thumb is performing a minimum of 30 runs (of course 50-100 runs is better).

The average is better than the best-value-achieved-in-a-set-of-runs but variance should also be taken into account.

There are some nice examples on Randy Olson's website:


average fitness of both algorithms over several replicates

The average fitness of both algorithms over several replicates. From this graph, we would conclude that our algorithm performs better than the current best algorithm on average.

average fitness with a 95% confidence interval

The average fitness with a 95% confidence interval for each algorithm. This graph shows us that our algorithm does not actually perform better than the current best algorithm, and only appeared to perform better on average due to chance.


The basic breakdown of how to calculate a confidence interval for a population mean is as follows:

  1. Identify the sample mean $\bar{x}$. While $\bar{x}$ differs from $\mu$, population mean, they are still calculated the same way: $$\bar{x} = \sum {x_{i} \over n}$$

  2. Identify the (corrected) sample standard deviation $s$: $$s = \sqrt{\frac{\sum_{i=1}^{n}{(x_i - \bar{x})^2}} {n-1}}$$ $s$ is an estimation of the population standard deviation $\sigma$.

  3. Calculate the critical value, $t^*$, of the Student-t distribution. This value is dependent on the confidence level, $C$, and the number of observations, $n$.

    The critical value is found from the t-distribution table (most statistical textbooks list it). In this table $t^*$ is written as $$t^*(\alpha, r)$$ where $r = n-1$ is the degrees of freedom (found by subtracting one from the number of observations) and $\alpha = {1-C \over 2}$ is the significance level.

    A better way to a fully precise critical $t^*$ value is the statistical function implemented in spreadsheets (e.g. T.INV.2T function), scientific computing environments (e.g. SciPy stats.t.ppf), language libraries (e.g. C++ and boost::math::students_t).

  4. Plug the found values into the appropriate equations: $$\left({\bar x} - t^{*}{\frac {s} {\sqrt n}}, {\bar x} + t^{*}{\frac {s} {\sqrt n}}\right)$$

  5. The final step is to interpret the answer. Since the found answer is an interval with an upper and lower bound it's appropriate to state that, based on the given data, the true mean of the population is between the lower bound and upper bound with the chosen confidence level.


The more the confidence intervals of two algorithms overlap, the more likely the algorithms are to perform the same (or we haven't sampled enough to discriminate between the two). If the 95% confidence intervals don't overlap, then the algorithm with the highest average performance performs significantly better.

In EA, the source distribution is essentially never normal and what said so far formally applies only if it's a normal distribution!

Indeed it still tells many things. The following table summarizes the performance of the t-intervals under four situations:

                             Normal curve | Not Normal curve
Small sample size (n < 30)      Good      |       Poor
Larger sample size (n ≥ 30)     Good      |       Fair

For more accurate answers non-parametric statistics are the way to go (see An Introduction to Statistics for EC Experimental Analysis by Mark Wineberg and Steffen Christensen for further details).

$\endgroup$
1
$\begingroup$

Answer: you analyse performance statistically.

For example, See the figure 3 of this paper: A Building-Block Royal Road Where Crossover is Provably Essential where performance of various GA are compared against each other.

The plot shows changes in fitness (Y-axis) vs iteration number (X-axis). Each algorithm is run multiple times and the average, min and max fitness is shown in the plot. Hence, showing clearly some GA variation have better performance than others.

The asymptotic convergence of fitness over iteration as suggested by vzn's answer is also very useful for most cases.

...

(Except for when fitness doesn't converge when you have an evolving fitness function.)

$\endgroup$
0
$\begingroup$

the basic strategy is to graph the fitness function over time. one can graph the fitness of the best solution or average fitness of solutions, worst solution etc. the best/worst will exhibit stairstep-like properties and the average will show an asymptotic convergence toward the optimum achievable by the GA. there is not really generally an a priori "execution time" associated with finding a solution for GAs, one usually terminates the algorithm at a point that is "good enough" by inspection of this asymptotic curve.

see eg graphs at the end of this slideshow:

$\endgroup$
  • $\begingroup$ How can one determine the time needed to converge on a "good enough" solution based on input size? $\endgroup$ – soandos Jan 19 '16 at 22:19

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.