Algorithm to sample high-dimensional parameter space of expensive cost function
I don't know how to sample from the space of nearly-optimal solutions, but I'll share one approach you could consider.
It appears that you want to estimate the density of good solutions, at different points in the input space.  It appears you are gridding up the parameter space and estimating the density in each cell of the grid.  Here is a possible alternate method to do that.
Suppose we have a cell $C \subseteq \mathbb{R}^{20}$ in the parameter space, which might take the form $C = [\ell_1,u_1] \times \cdots \times [\ell_{20},u_{20}]$, i.e., $\ell_i$ is the lower bound on the $i$th coordinate and $u_i$ the upper bound.   Let $V(C)$ be the volume of cell $C$.  We'll estimate the density of good solutions in $C$.  Pick a volume $v$ that is a fraction of $V(C)$, let $\alpha=v^{1/20}$, and then repeat the following 100 times:

Pick a random point $w \in C$.  Form the smaller cell $C_x = [w_1-\alpha/2,w_1+\alpha/2] \times \cdots \times [w_{20}-\alpha/2,w_{20}+\alpha/2]$.  Use your optimization method to search whether there is a good solution in the cell $C_x$.  (For many optimization methods, it is easy to enforce constraints that set an upper and lower bound on each coordinate in the parameter space.)

Now based on the number of times that you were able to find a good solution, you can form an estimate of the density of good solutions in $C$.  If this count is close to zero, double $v$ and repeat.  If this count is close to 100, halve $v$ and repeat.  Repeat until you get a count that is not too close to 0 or 100, and the result should give you a pretty good estimate of the density in $C$.
You can now iterate this, once per cell $C$, and use that to produce the kind of plot you are hoping for.
Here I've adopted standard methods for #SAT, i.e., for estimating the number of solutions to a SAT instance, to your specific problem.