A search problem and no algorithm for it I would like to learn about the following search problem, in particular, which kind of algorithms exist for it.

Suppose we have a huge search space $S$. For each element $s \in S$, we have the weight function $w(s)$. We start at some element $s_0 \in S$ and want to find an element with very low $w$-value.

How can we traverse this search space? For each element $s_1 \in S$, there exists a set of keys $K_S$, and we have some function $a : S \times K_S \rightarrow S$, that computes a new element $s_2 = a(s_1,k)$ for some $k \in K_S$.

We can evaluate the weight of some element $s$ only once it is given. But computing the weight is expensive, and should be minimalized. In order to find a good choice how to traverse throughout this graph, we are given a heuristic $h(s)$, that is supposed to compute a "good" key.

We know for small changes of the key (say, in Hamming distance), the weight of $w(s)$ does not change to much.

Question: Is such a problem known in theoretical computer science, and does there exist theory for it? In particular I am looking for algorithms for problems like these, and conditions on the heuristic $h$ to provide a "good" heuristic. 

The description is deliberately vague, in order to allow for wider range of answers. I think many search algorithms do not apply, because they are too generous with search space evaluation. Maybe the problem is even too ill-posed to be accessible to CST tools.

Thank you very much!
Your description is a bit vague, but the problem you describe seems very similar to the canonical problem defining the complexity class PLS (http://en.wikipedia.org/wiki/PLS_(complexity)). Problems in PLS can be described by an exponentially sized graph that you have access to using two polynomial time algorithms: one for evaluating the weight of a current vertex, and one for directing you to the neighbors of a current vertex. The goal is to find a local-minimum in the graph: any vertex such that none of its neighbors have lower weight. 

Complete problems for this class include computing pure strategy Nash equilibria in congestion games (See e.g. here), and no polynomial time algorithms for such problems are known.