Measuring performance of Genetic Algorithms

Question

I'm looking for information concerning Genetic Algorithm (GA) outputs reliability. I've found some papers applying metaheuristics that have run their algorithms 30 times and got the best solution among them. However, I did not find a consistent reference (i.e., book or scientific papers) affirming that 30 times is an appropriate quantity to run the algorithm. Does anyone know if there is a reference addressing that in more detail?

Regarding the solution gaps of GA or other metaheuristics: Is there a consensus about it? For example, could I say that an algorithm is reliable if its solutions gap is lower than 10%?

Answer 1

There is no magic. Considering that the algorithm is carefully designed, it is a matter of solution quality versus running time. If each run needs a lot of time to converge, running it 30 times could be too long for practical use. If the algorithm converges very fast, in milliseconds, why not running it hundreds of times.

Now, if an iterative algorithm has been launched a large number of times to converge toward quality solutions, it means that the algorithm in question is more like a basic random search and then that this one is not so innovative from a scientific point of view. Nevertheless, in some cases (for example, when tackling highly non-convex problems), random search-like approaches with many restarts may be the best practical way to get quality solutions in short running times.

Answer 2

Assuming the random seed is different every time, genetic algorithms (and by extension stochastic algorithms) are non-deterministic by nature, which is why they need to be run many times until we get "lucky".

There is no meaningful "gap" per se in this context, as genetic algorithms can't rigorously bound the problem to generate an optimality gap. There can be an integrality gap, but this is not really meaningful for GA as they are not guaranteed to iteratively improve that gap.

The probability of finding solutions is complicated to calculate, especially for MINLP problems, and I am not aware of any general proofs on convergence for general MINLPs. This means that the number of times the algorithm must be run varies on a case-by-case basis, and as far as I am aware the theoretical bound for that number for general problems is infinity.

In practice, the main use case for these algorithms is for problems that are so large/computationally expensive that normal solvers can't handle them (e.g. industrial CFD or structural analysis). In these cases, we typically run the GA many times, and in many different configurations, until we get a solution that is "good enough".

The secondary use case is for optimisation beginners, as GA are a great way of getting a workable solution without knowing much about the theory & algorithms.

Running the problem 30 times is an empirical rule of thumb for expensive-ish problems, which usually translates to roughly a week or two of calculations (so about 6-12 hours/run). If we don't have a workable solution by then, we simply change how the algorithm mutates and hope for the best on the next batch.