I'm sort of torn on what to do for implementation of my distributed genetic algorithm problem. I would like to be able to have nodes join and part at will and not take down the whole system. But this introduces the problem of mismatch of generations. Often times a genetic algorithm simulation is capped by a certain amount of generations and if I have a node that is on 75 out of 100 generations and a brand new node joins the cluster I'm not sure if I should fake it and start at 75 and copy one of the other nodes as a starting point or have it start out at 0 and potentially have the results delayed until the end of execution of the new node. I was hoping someone had some input on what they could see as problems in addition to a long wait time with this new node if I start at 0, I am struggling to think of what could go wrong in both approaches other than that.
-
Is it just me does 100 generations seem really small when talking about genetic algorithms?– PhilipOct 2, 2013 at 15:50
-
That was just an example but yes that would be very small– csteifelOct 2, 2013 at 17:50
3 Answers
My advice is usually to never use generation count as a performance metric or termination criterion. Aside from the problem you're facing, it's just too dependent on population size to be of much use. You can't compare across runs, because if your GA has a population of 10 and mine has a population of 10,000 then of course mine will be better than yours over any fixed number of generations, as it gets to do 1000 times more searching.
Just halt the GA after a fixed number of evaluations instead. When a new node joins, it just starts contributing to the global evaluation count. If you want to alleviate some communication overhead, then let each node buffer some number of evaluations locally, and then periodically have them all increment the global counter by however many evaluations they performed since the last update. When the global count passes the limit, just terminate all the nodes and return the answer.
-
Or, if it's possible, terminate once the solution reaches a "good enough" point. It requires the solution to be compared against something like... 10% better than the manual solution, or 10 cheeses collected in 100 seconds, or whatever.– PhilipOct 2, 2013 at 16:24
-
While I agree I don't like max generation counts either I have seen it used in many cases in which the user just wants to see how good they can get really quickly and not too worried about getting the best solution just a good one in a short amount of time.– csteifelOct 2, 2013 at 17:53
-
So just multiply it by the population size and use that as the evaluation limit. It will run in the same amount of time and you'll be able to better interpret the results.– deongOct 2, 2013 at 21:36
So... a node is a collection of GA population from another computer, hence the distributed aspect? And you're asking about how to join the populations?
To reap the benefit of distributing the computation you eventually have to merge the populations. You're worried about merging populations with different amount of time and processing power being thrown at them. And yeah, the younger population is probably not going to be as advanced or as fit as the older population. Maybe.
If you add a node with a population that has had zero generations, you've essentially got a collection of random garbage with no selective forces being applies and no evolution. But you also wasted no processing time. You've literally sunk zero time evolving it and having all of them instantly weeded out isn't that big of a loss.
If you add a node with, say, half the generations as your main group then they're (eyeballing it) about half as likely to add something meaningful to the population on the whole. But hey, they might.
You benefit from having separate nodes by having different attempts at solving the same problem. You widen your search, if not adding depth. One of them will hopefully get lucky and supply an insightful boost to the whole. And it protects from monocultures getting stuck on local maxima. You don't want to outbreed and have your entire population be identical. If you have a simple search space and it's all just really hill-climbing, then distributing the GA probably doesn't help all that much. If it's a complex search space and there are a lot of local maxima to GA to get stuck on, then distributed GA can help.
But when they merge, you still select based on their fitness. If you send out a node to that ancient 486 in the corner, and the next day it only cranked through 2 generations while your server farm is on it's 10,000th generation, it probably isn't actually contributing anything of value. All of it's population is going to be thrown out. And rightfully so, all of it's population doesn't do anything to advance the current solution.
start out at 0 and potentially have the results delayed until the end of execution of the new node.
This could make it arbitrary slow: another node could join when you just catched up and so on...
The easiest way is to throw out the whole generation idea:
- In reality, there are no generations either, just older and newer individuals, no master clock.
- There's no evidence of any advantage of the generational approach.
Unless you want to exactly mimic an existing algorithm, simply cap yours by the total number of individuals. Try to use the nodes in the most efficient way according to their availability.
