Local Search Optimization Algorithms in Applied Settings — How best to explain to applied researchers?

Question

I realize this may be an opinion-based question, but relevant nonetheless in my opinion.

Context:

I have a local search optimization algorithm, A.

I designed A to address a specific biological question.

A returns many local optima and often gets stuck near said optima.

My target audience (biologists) don't understand this. They want a single plausible answer (the global optimum) or at least many plausible answers (local optima) with low variability. The reason for this is that biologists will need to incur high cost and large effort to reach their end goal. They feel uneasy that A returns many plausible solutions.

Specifics:

The problem faced by the biologists revolves around sampling. Specifically, they would like to know, given current sampling levels, how much more sampling is required to estimate genetic diversity within species.

Unfortunately, there is no means of comparison with other algorithms because this problem hasn't been thought about in a computational light before. Biologists just sample randomly in the field. Crude estimates of necessary sample sizes range from 5-10 individuals, but sometimes only 1-2 can be reasonably collected (due to say, species rarity and/or project budget).

Algorithm A suggests sample sizes 1-2 orders of magnitude larger than the crude estimate, but the variability is large.

For instance, A might suggest anywhere from 200-250 individuals should be sampled to capture 95% of existing genetic variation for a given species.

All plausible sample sizes returned by A are close to the required 95% cutoff, yet the variation in the estimates themselves is quite large.

The makes the biologists uncomfortable because it suggests that A is not very good.

One way I try to frame things is with the analogy of climbing a mountain or hill. We want to get to the top (the global optimum), but there are a lot of obstacles (local optima) in the form of ridges and valleys in the way.

Putting this into a more CS-centric context:

The Travelling Salesman Problem (TSP) is an NP hard problem of great theoretical interest. For this reason, TSP is often solved via local search (e.g., simulated annealing (SA) or genetic algorithms (GA)). Since both SA and GA are stochastic, they will return different routes each time the algorithm is run.

Clearly, the shortest route is targeted. If many local routes are possible, why use local search in the first place?

I realize the answer to the about question is "to get a 'good enough' solution in a finite amount of computation time". However, this doesn't fit well with applied researchers.

Put another way:

In the case of TSP, why would an airport rely on a local search algorithm to find the optimal path if this could mean wasted money and resources?

My question: How can we justify the use of local search algorithms with the same kind of behaviour as A to researchers in very applied fields who otherwise lack math/stats/computer science knowledge?

Answer 1

The question is a bit unclear, but just to add my two cents:

• Simulated Annealing and Genetic Algorithms are not classified as ”local” optimization algorithms. They have been designed to overcome the limitations of local searches so they are usually put in the “global” optimization basket.
• The fact that they are stochastic doesn’t mean that their results are not reproducible. Standard implementations of SA and GA allow you to specify a random seed, so the optimizations are perfectly reproducible.

So you have many local optima from your algorithm. Do the “better” local optima tell you anything more than the worse ones? What is the actual, physical meaning of your optima? Is there any way you could compare your algorithm with other, established optimization procedures to assess the quality of your implementation? How many parameters (optimization variables) does your model have? Is your objective function expensive to evaluate or quick? We haven’t seen your model so it’s difficult to suggest anything about possible arguments to convince your colleagues.

That said, having an objective function full of local optima is nothing new, very many real life applications are like that. However, in almost all cases we strive for better and better optima all the time (I.e. lower objective functions in minimizations, higher for maximizations) and when we have to account for many optima (for example, for forecasting a matched model) we usually have a good, physical explanation for what we are doing.

I have to admit that your case is a bit unusual, as having orders of magnitude different optima is unheard of (at least for me). But since you haven’t provided a model nor benchmarked your algorithm against others I am afraid these is the best suggestions I can come up with.