<br><br><div class="gmail_quote">On Nov 28, 2007 12:59 AM, Stefan van der Walt <<a href="mailto:firstname.lastname@example.org">email@example.com</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="Ih2E3d">On Tue, Nov 27, 2007 at 11:07:30PM -0700, Charles R Harris wrote:<br>> This is not a trivial problem, as you can see by googling mixed integer least<br>> squares (MILS). Much will depend on the nature of the parameters, the number of
<br>> variables you are using in the fit, and how exact the solution needs to be. One<br>> approach would be to start by rounding the coefficients that must be integer<br>> and improve the solution using annealing or genetic algorithms to jig the
<br>> integer coefficients while fitting the remainder in the usual least square way,<br>> but that wouldn't have the elegance of some of the specific methods used for<br>> this sort of problem. However, I don't know of a package in scipy that
<br>> implements those more sophisticated algorithms, perhaps someone else on this<br>> list who knows more about these things than I can point you in the right<br>> direction.<br><br></div>Would this be a good candidate for a genetic algorithm? I haven't
<br>used GA before, so I don't know the typical rate of convergence or its<br>applicability to optimization problems.<br></blockquote><div><br>It depends. Just to show the sort of problems involved, suppose you have 32 integer variables and are looking for the last bit of optimization. If the floating point optimum is at (.5, .5, ...., .5) and the error is symmetrical, then each vertex of the surrounding integer cube is a solution and there are 2**32 of them. If the error isn't symmetrical, and chances are that with that many variables it is very far from that, then you have to search a larger region. That's a lot of points. The more sophisticated algorithms try to eliminate whole regions of points and keep narrowing things down, but even so the problem can easily get out of hand. If you just need a good solution, a genetic algorithm is a good bet to find one without too much hassle. I had a similar problem in designing a digital min/max FIR filter where I needed 15 bit integer coefficients for hardware implementation. There was a narrow high rejection band in the filter and simply rounding the coefficients left spikes in the response through that band. With a GA I was able to eliminate the spikes in about 30 minutes of evolution using a python/Numeric program. In that case the performance of annealing was quite dependent on choosing the right parameters for cooling rate, etc., while the GA was quite robust and straight forward. There was no guarantee the I ended up with the best solution, but what I got was good enough.