I realize this may be an opinion-based question, but relevant nonetheless in my opinion.
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.
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?