Jorge Quitério Search
Mathematics

Statistical comparison of genetic algorithm parameter settings

Genetic algorithms have many parameters, and a single successful run proves little. A sound comparison of settings requires repeated runs and non-parametric tests, which can change the conclusion. The comparison is demonstrated with thirty seeds per setting.

Genetic algorithms are easy to explain and easy to implement. A population of candidate solutions evolves through selection, crossover and mutation, and over the generations it tends to improve.

They also have many parameters: population size, crossover rate, mutation rate and selection pressure. It is tempting to change a parameter, run the algorithm once, observe a better result and conclude that the new setting is superior. In my optimisation course, the assignment on genetic algorithms became an exercise in statistics, because that conclusion is not justified: the result of a genetic algorithm is a random variable. This article shows how to compare two settings properly, using thirty seeds per setting.

The difficulty is familiar outside optimisation. A cyclist who tries a new set of tyres on one ride and records a faster time has learnt little, because wind, traffic and fatigue vary from ride to ride. A fair comparison repeats both sets of tyres many times under matched conditions. For a genetic algorithm the random seed plays the role of the day's conditions, and running both settings on the same seeds is the matched comparison.

The relevant literature is as follows.

Holland (1975) laid the foundations of genetic algorithms. Fortin and colleagues (2012) published DEAP, the Python library I used.

Wilcoxon (1945) introduced the signed-rank test for paired samples, and Friedman (1937) the rank test for comparing several treatments on the same blocks. Neither assumes normal data.

Derrac, García, Molina and Herrera (2011) wrote the practical tutorial on using these non-parametric tests to compare evolutionary and swarm algorithms: repeated independent runs, rank-based tests, and post-hoc corrections when there are more than two configurations.

Calvet and colleagues (2017) describe learnheuristics, which combine metaheuristics with machine learning for problems whose inputs change during optimisation.

Two test problems

Both have known optimal solutions, so it is possible to measure how far the algorithm gets.

  • A 0/1 knapsack with 22 items and optimal value 1030. Infeasible solutions were repaired by removing items until they fit.
  • A small portfolio problem: choose weights for ten assets to minimise risk subject to a minimum expected return of 7%. Constraint violations were penalised in the fitness function, and the result was compared with the exact solution of a quadratic programming solver.

Both problems have direct practical counterparts. The knapsack is the problem of a courier loading a van of limited capacity with the parcels that bring the most revenue, or of a committee funding the most valuable projects within a fixed budget. The portfolio problem is the one a pension fund solves when it looks for the least volatile mix of assets that still meets a target return.

Variability between runs

A first configuration (population 50, crossover 0.7, mutation 0.2, tournament size 3) gave an average best value of about 1006 on the knapsack. After tuning (population 100, crossover 0.6, tournament size 2), a run reached the optimum of 1030. On the portfolio, the tuned algorithm found a risk of 0.0918, equal to the exact optimum.

However, a different seed gives a different result. The relevant question is whether the tuned version performs better reliably.

Repeated runs and a non-parametric test

So both configurations ran with the same 30 seeds. On the knapsack, the tuned one averaged 1021.6 (standard deviation 16.3) against 1000.1 (31.9), and reached the optimum in 77% of runs against 43%.

The results are not normally distributed: they are bounded above by the optimum and pile up there. A t-test is therefore not appropriate. The Wilcoxon signed-rank test, which uses only ranks of the paired differences, gave p=0.002p = 0.002. On the portfolio the difference was even clearer (p≈6.5×10−9p \approx 6.5 \times 10^{-9}).

To compare more than two settings, for example populations of 30, 100 and 300, the Friedman test is the analogue. It gave χ2=39.1\chi^2 = 39.1 (p≈3×10−9p \approx 3 \times 10^{-9}), with means of 977, 1021 and 1030. Larger populations helped consistently on this problem.

Sensitivity analysis

Sensitivity maps over pairs of parameters were more informative than single results. On the knapsack the mutation rate mattered most: too little and the population stagnated, too much and good solutions were destroyed. On the portfolio, the step size of the mutation traded exploration against fine adjustment.

The figure below reproduces the experiment. A single run cannot tell two settings apart, thirty paired runs and a rank test can, and the answer depends on the computational budget.

A small genetic algorithm in JavaScript on a random 22-item knapsack, solved exactly for reference, with population 20 against population 100 and everything else equal. It is not the DEAP setup from the article, but it shows the same statistics.

Suggested settings:

  1. Default comparison. At 40 generations, the larger population reaches the optimum in about two thirds of the seeds, the smaller one almost never, and the Wilcoxon p-value is tiny.
  2. Individual seeds. Many dots of the two settings overlap: on many seeds both reach the same value, and a single-run comparison on such a seed would say "no difference". Change the budget (next two steps) and look for a seed where population 20 wins; a comparison based on that one seed would have reached the opposite conclusion.
  3. Small budget. Set 10 generations. Both settings fall short of the optimum, but the larger population is still better almost every time. A small budget makes the difference more reliable, not less.
  4. Large budget. Set 150 generations and run again. Population 100 now finds the optimum in almost every seed and population 20 in nearly half; the gap in the means shrinks and the p-value grows by orders of magnitude, though it stays significant. The question of which setting is better, and by how much, can only be answered for a stated budget.

The Wilcoxon signed-rank test. The Wilcoxon signed-rank test ranks the absolute paired differences ∣di∣|d_i| from smallest to largest and sums the ranks of the positive ones, W+W^+. If the two settings were equivalent, each difference would be equally likely to be positive or negative, so E[W+]=n(n+1)/4E[W^+] = n(n+1)/4 and Var⁡(W+)=n(n+1)(2n+1)/24\operatorname{Var}(W^+) = n(n+1)(2n+1)/24, with nn the number of non-zero differences. The statistic z=(W+−E[W+])/Var⁡(W+)z = (W^+ - E[W^+])/\sqrt{\operatorname{Var}(W^+)} is approximately standard normal, which is what the widget uses. Because only ranks enter, the pile-up at the optimum and the long lower tail do not distort the test, as they would a t-test.

The output of a heuristic is a random variable, so report its distribution rather than its best run:

  • Run each setting on the same set of seeds (at least 30), so the comparison is paired.
  • Use rank-based tests: Wilcoxon for two settings, Friedman with post-hoc corrections for more.
  • State the computational budget, because the ranking of settings can change with it. A route planner that must finish before the vans leave in the morning faces a different ranking from one that runs overnight.
  • Look at the sensitivity maps as well as the winner. They show which parameter matters.

References

  1. J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, 1975.
  2. M. Friedman, "The use of ranks to avoid the assumption of normality implicit in the analysis of variance", Journal of the American Statistical Association, 32(200), 675-701, 1937.
  3. F. Wilcoxon, "Individual comparisons by ranking methods", Biometrics Bulletin, 1(6), 80-83, 1945.
  4. F.-A. Fortin, F.-M. De Rainville, M.-A. Gardner, M. Parizeau and C. Gagné, "DEAP: Evolutionary algorithms made easy", Journal of Machine Learning Research, 13, 2171-2175, 2012.
  5. J. Derrac, S. García, D. Molina and F. Herrera, "A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms", Swarm and Evolutionary Computation, 1(1), 3-18, 2011.
  6. L. Calvet, J. de Armas, D. Masip and A. A. Juan, "Learnheuristics: hybridizing metaheuristics with machine learning for optimization with dynamic inputs", Open Mathematics, 15(1), 261-280, 2017.