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

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?

• I don't really understand what the question or difficulty is. We use local search algorithms if they work better than the alternatives. "Better" can mean they produce a solution of higher quality, or it can mean that they produce a solution of similar quality with less computation time. It sounds like you know why we use local search, so I'm not sure what we can add that will be useful. Is there a way to phrase your question that will make it clearer what the technical question is?
– D.W.
Commented Dec 19, 2020 at 9:17
• Have you considered that the biologists might be right? I am sympathetic to their reaction.
– D.W.
Commented Dec 20, 2020 at 6:12
• I've begun to think that this could indeed be the case since estimates returned by A are much larger than 5-10 individuals and this equates to spending more time and money to sample in the field. I guess the only reasonable thing that could be said of A given the information here is that it returns "ballpark" estimates arrived at in a more systematic (i.e., via iteration from an initial guess) way than arbitrarily proposing low sample sizes like 5-10 just to save money and time. I thought I'd ask here on CS anyway. Commented Dec 20, 2020 at 7:47