4 ms·

Hi, I did my masters research into this very problem. A lot of research here does just simply revolve around iterations of hill climbing [1] One thing which ha

by ac2u 8y ago

Hi, I did my masters research into this very problem. A lot of research here does just simply revolve around iterations of hill climbing [1] One thing which has been done quite a lot (and that's not to say you don't already do this), is to measure the gradient of improvement of your fitness function, and if it's been flat for too long, to relax the conditions/weights by X percent (X becomes another thing to tinker here, but I start with 10%). The flatness here suggests that you may be in a local optimum in the candidate space. This will allow worse solutions for many more iteration, (and a graph tracking the fitness will go the wrong direction), but in the end, you might find that you end up with a solution that is much 'fitter' than before the algorithm relaxed the conditions. (In the academic papers I read at the time, various words were used for this, sometimes it was called 'reheat') It seems that even if you don't do this, you know about it intuitively anyway since you talked about tinkering with the weights, just thought I'd chime in to mention that the tinkering part is often automated now. [1] https://en.wikipedia.org/wiki/Great_Deluge_algorithm https://en.wikipedia.org/wiki/Great_Deluge_algorithm EDIT: A sibling comment pointed out Simulated Annealing also, which provides a more analogous means to discuss the 'reheat' stage here.

lodrein 8y ago
That's interesting. Our approach is based on Mixed Integer Programming and Generalized Quadratic Assignment.
- ac2u 8y ago
  I'm sure other approaches can be much more effective, my research was almost 8 years ago and was framed around trying to parallelise one of the algorithms. So my focus was half on the theory behind these solution search algorithms and half on parallelism and the associated theory. I've a gut feeling that a superior algorithm often gets you better ROI than parallelising an existing solution. The TLDR of my findings was that for the algorithm in question, it wasn't greatly suited to parallelism. Performance didn't scale linearly with cores due to too much shared state, and the best you could hope for was seeding each parallel run of the algorithm with different randomisation seeds and it's own state and bank on certain runs not getting caught in local optimum. So it got you better performance, but not so much that you'd jump right in to doing work to parallelise. Probably better to use algorithms that are built to be embarrassingly parallel from the ground up.
mikeash 8y ago
That's cool. I'll keep that in mind if I need improvements or just feel like doing something more with it. I don't think tinkering with the weights is quite the same thing. That happens when the algorithm is doing a good job of optimizing the scoring function, but the scoring function isn't doing a good job of representing what people want. It does remind me of another thing I occasionally do when I don't quite get the results I want, which is to manually change one of the assignments and then have it climb the hill from there. Sometimes I'll just clear some assignments and re-run, which is pretty much a manual, ad-hoc version of what you describe.
- ac2u 8y ago
  Ah I understand, half the battle is terminology (I was introduced to the 'weights' as hard and soft constraints, with corresponding penalties against the fitness function score). Even though I did research on it, I found that the field is subject to a lot of colloquialisms (for lack of a better term) when it comes to different research cliques, and therefore the terminology I use isn't any more of less correct as a result. It seems like you've got as good a handle on it as anyone. My research was mainly involving investigating parallelism of the above algorithm (not very friendly to parallelism without work). Nowadays, there's so many academic open source optimizers, as well as commerical, that I would usually tell people if you're solving for a business case, it's often more cost effective to frame your problem in a format digestible by the solvers and let them at it than writing the solvers yourself. Of course, where's the fun in that? I'm jealous that you got to use this for a problem that you had, rather than in my approach which was for a problem I didn't need solved myself. I bet that was satisfying.
QML 8y ago
Before trying Simulated Annealing, try out all the industry grade constraint optimization solvers! They’re surprisingly more effective on average case inputs. I had to learn this the hard way when, for a class project, I was thoroughly beat out by people who just used dedicated solvers for TSP.
wodenokoto 8y ago
Hill climbing, I wanna ask, is it the same as gradient descend, but obviously they are in different directions ...
- pouetpouet 8y ago
  It is similar, but Hill Climbing moves one parameter at a time. While gradient descent moves along the steepest gradient adjusting multiple parameters at a time, but it requires the function to be differentiable https://en.wikipedia.org/wiki/Hill_climbing#Mathematical_description https://en.wikipedia.org/wiki/Hill_climbing#Mathematical_des...

by ac2u 8y ago

lodrein 8y ago

That's interesting. Our approach is based on Mixed Integer Programming and Generalized Quadratic Assignment.

ac2u 8y ago
I'm sure other approaches can be much more effective, my research was almost 8 years ago and was framed around trying to parallelise one of the algorithms. So my focus was half on the theory behind these solution search algorithms and half on parallelism and the associated theory. I've a gut feeling that a superior algorithm often gets you better ROI than parallelising an existing solution. The TLDR of my findings was that for the algorithm in question, it wasn't greatly suited to parallelism. Performance didn't scale linearly with cores due to too much shared state, and the best you could hope for was seeding each parallel run of the algorithm with different randomisation seeds and it's own state and bank on certain runs not getting caught in local optimum. So it got you better performance, but not so much that you'd jump right in to doing work to parallelise. Probably better to use algorithms that are built to be embarrassingly parallel from the ground up.

mikeash 8y ago

That's cool. I'll keep that in mind if I need improvements or just feel like doing something more with it. I don't think tinkering with the weights is quite the same thing. That happens when the algorithm is doing a good job of optimizing the scoring function, but the scoring function isn't doing a good job of representing what people want. It does remind me of another thing I occasionally do when I don't quite get the results I want, which is to manually change one of the assignments and then have it climb the hill from there. Sometimes I'll just clear some assignments and re-run, which is pretty much a manual, ad-hoc version of what you describe.

ac2u 8y ago
Ah I understand, half the battle is terminology (I was introduced to the 'weights' as hard and soft constraints, with corresponding penalties against the fitness function score). Even though I did research on it, I found that the field is subject to a lot of colloquialisms (for lack of a better term) when it comes to different research cliques, and therefore the terminology I use isn't any more of less correct as a result. It seems like you've got as good a handle on it as anyone. My research was mainly involving investigating parallelism of the above algorithm (not very friendly to parallelism without work). Nowadays, there's so many academic open source optimizers, as well as commerical, that I would usually tell people if you're solving for a business case, it's often more cost effective to frame your problem in a format digestible by the solvers and let them at it than writing the solvers yourself. Of course, where's the fun in that? I'm jealous that you got to use this for a problem that you had, rather than in my approach which was for a problem I didn't need solved myself. I bet that was satisfying.

QML 8y ago

Before trying Simulated Annealing, try out all the industry grade constraint optimization solvers! They’re surprisingly more effective on average case inputs. I had to learn this the hard way when, for a class project, I was thoroughly beat out by people who just used dedicated solvers for TSP.

wodenokoto 8y ago

Hill climbing, I wanna ask, is it the same as gradient descend, but obviously they are in different directions ...

pouetpouet 8y ago
It is similar, but Hill Climbing moves one parameter at a time. While gradient descent moves along the steepest gradient adjusting multiple parameters at a time, but it requires the function to be differentiable https://en.wikipedia.org/wiki/Hill_climbing#Mathematical_description https://en.wikipedia.org/wiki/Hill_climbing#Mathematical_des...