> GA is a special case of evolutionary algorithms in general. > > If we ignore cross-over for the moment, hadoop is ideal for EA in general. > The natural implementation would have each map input record represent a > single member of the population. The mapper would mutate this member and > evaluate the fitness, outputting all records with a random key from a small > set (depends on how many reducers we want) and the combiner and reducer > would sieve out the top N members for each key value. Multiple passes of > this would be the way to run the algorithm. If the key set has cardinality > 1, then this reduces to ordinary mutation and selection, if it is larger, > then the selection of the top n becomes a bit approximate, but should not > cause any significant problems. A second pass could be used to reduce to an > exact selection if needed. Depending on how the combiner words, using a > single reduce might be very fast. > > Crossover requires that pairs items be brought together, roughly at random, > and might require an extra map-reduce.
This idea is interesting, especially that I am used to Artificial Immune Systems and that they don't need the crossover operator. But its more complicated than what I proposed, and as I am new to Mahout and Hadoop I think I should start with the first idea. > My own preference with these algorithms is to avoid cross-over and focus on > meta-mutation where some of the state in the records specifies how the > mutation should proceed. This can have dramatic positive effects in > accelerating convergence by providing somewhat of a trade-off against > convergence guarantees. Since everybody gives up the convergence guarantees > anyway, this is a nice knob to have. I describe on approach that can be > very effective in an old paper that can be found here: > http://arxiv.org/abs/0803.3838 . I can provide a sample implementation in > C, but the paper is probably easier to read. I could'nt access the paper, after registering to arXiv.org, it asks me for the ownership password of the paper !!! here is what it says "We do not allow people other than the authors of an article to claim ownership of an article before it has been publicly announced..." Is the paper available somewhere else ? Abdel Hakim Deneche _____________________________________________________________________________ Envoyez avec Yahoo! Mail. Capacité de stockage illimitée pour vos emails. http://mail.yahoo.fr
