I have a surface defined by values on a two-dimensional grid. I would like to find an approximate function which would give me a value for any arbitrary point within certain range of xs and ys.
My general idea is to construct some sort of polynomial, and then tweak it's coefficients by using some sort of evolutionary algorithm until the polynomial behaves as I want it to. But how should my polynomial look in general?
You might be interested in Lagrange interpolation (link only talks about one-variable version). Just input 100 points from your values and you'll probably get something good. You may need more points for it to be accurate at locations of high variance. If you insist on using an evolutionary algorithm, you might use it to choose near-optimal choices of data points, but in many cases you could probably do almost as well by spreading them around evenly.
Two-variable interpolation isn't on Wikipedia. But it is Google-able, and I found it described in sufficient generality in section 3 of this paper. Or, if you have access to MATLAB, a "static" 2D-interpolater has already been coded in this script (I haven't used this one, so it might be unwieldy or otherwise unsuited to your purposes).
Hope this helps you out!
The optimal method depends on the structure of your grid and your problem in general.
The first question you should ask yourself: Does your problem require that the resulting function exactly coincides with the given values at the grid points? This approach would be called interpolation, e.g. polynomial interpolation as suggested by the previous answer. Downsides of that approach are the following:
1) the resulting function is going to have strong oscillations between the gridpoints if the gridpoints lie close to each other.
2) If you are interested in the values outside the grid, you won't be able to use the interpolating polynomial at all.
If these are serious restrictions to your use case, you should consider another approach where you approximate instead of interpolate (usually using a least-squares or $L^2$ approach). The most prominent approach here is (linear) regression.
In the end, what method works better depends on where your data is coming from and what you are trying to infer from it. In any case, for both of these approaches there are many free software implementations available.
