Conceptually, at least, it would be good to have the option for fitness functions to be expressed as map-reduce programs. Unfortunately, having mappers spawn MR programs runs the real risk of dead-lock, especially on less than grandiose clusters.
To me, that indicates that if the fitness function is nasty enough to require map-reduce to compute, then either: a) the executive that manages the population and generates mutations should be written in sequential form or b) the evolutionary algorithm has to be written in such a way as to be able to manipulate a map-reduce program so that evolution and evaluation can be merged into a single (composite) map-reduce program. I vote for (a) because if fitness computations are so complex as to need MR, then the cost of sorting the population will be negligible. This raises the question of how the population should be communicated to the parallel evaluator. On Tue, May 27, 2008 at 1:52 AM, deneche abdelhakim <[EMAIL PROTECTED]> wrote: > In a GA there are many things that can be distributed, and one should > always start with the most compute demanding task . This is very problem > dependent, but in most cases the fitness evaluation function (FEF) "is" the > part to distribute. > > The FEF evaluates each single individual in the population, and it may need > some datas (D) to do so. For example in the traveling Salesman Problem, the > problem is defined by a set of cities and the distances between them, the > FEF needs those distances to evaluate the individuals. > > I see 2 ways to distribute the FEF: > > A. if the datas D is not big and can fit in each single cluster node, then > the easiest solution is to use each Mapper to evaluate one individual and to > pass the Datas D to all the mappers (using some Job parameter or the > DistributedCache). The input of the job is the population of individuals. > For someone used to work with Watchmaker, the solution A is straightforward, > he needs to change one line of code. > > B. if the datas D are really big and span over multiple nodes, then the FEF > should be writen in the form of Mappers-Reducers, the population of > individuals is passed to all the mappers (again using the DistributedCache > or a Job parameter) and the datas D are now the input of the Job. > > [MAHOUT-56] contains a possible implementation for solution A. Now I should > start thinking about solution B and all I need is a problem that uses very > big datasets. I already proposed one in my GSoC proposal, it consists of > using a Genetic Algorithm to find good binary classification rule for a > given dataset. But I am open to any other suggestion. > > __________________________________________________ > Do You Yahoo!? > En finir avec le spam? Yahoo! Mail vous offre la meilleure protection > possible contre les messages non sollicités > http://mail.yahoo.fr Yahoo! Mail > -- ted
