Waffle Mixer A Library for Distributing Genetic Algorithms Ariel Rideout arideout mit edu Ryan Williams breath mit edu David Ziegler david ziegler ws May 6 2004 Abstract We describe a toolkit that enables simple parallelization of genetic algorithms Genetic algorithms are favored for optimization problems because they lend themselves to both continuous and discrete combinatorial problems and are less susceptible to becoming trapped at local optima in comparison to gradient search methods Unfortunately GAs are typically computationally expensive The toolkit enables writers of genetic algorithm applications to choose between local one machine operation or distributed computation at runtime The distributed approach achieves the same result or better than a local computation but significantly diminishes the required computation time An analysis of the system s performance is described 1 Introduction Genetic algorithms are one of many approaches used to solve optimization problems such as the traveling salesman problem In a genetic algorithm strings of bits called individuals are generated each representing a solution to the problem Individuals are evaluated and the best individuals survive to the next generation Individuals can mate to create offspring new individuals that share characteristics of their parents Genetic algorithms are favored for many optimization problems because they are less susceptible to local optima A genetic algorithm typically has an element of randomness built in that allows the algorithm to work its way from such local optima Although a genetic algorithm typically does not provide a deterministic optimal solution the solution is often good enough One difficulty with genetic algorithms is that for many problems the performance of the algorithm is hampered by the time taken to evaluate an individual In this paper we present a toolkit the Waffle Mixer for distributing the computation of a genetic algorithm across a network of machines to speed computation Such a distributed computation adds complexities crossovers and mutations are based on both local individuals and individuals seen from the network The Waffle Mixer described addresses issues of network topology host and individual naming genome storage announcement and fault tolerance The addition of new nodes to the network is done with a minimum of effect on other nodes and every client once it has joined is able to contribute equally to the computation 2 Related Work There has been a good deal of research into the parallelization of genetic algorithms GAs 3 Genetic algorithms offer the possibility of speeding computation of optimization problems signifi1 cantly when the optimal solution is not necessary but often the cost of evaluation is a significant portion of the computation Therefore the common approach to parallel genetic algorithm PGA problems is to divide the computation such that the evaluation of individuals is spread out There are three prevailing methods of parallelization The first is do perform global parallelization In this form of PGA there is only one population of individuals as in a typical GA However the evaluation of individuals is expressly parallelized Selection is unmodified and all individuals have the chance to mate with all others This type of parallelization is often straightforward to implement and can provide a significant speedup as long as the communication costs do not dominate the computation costs A coarse grained PGA divides the individuals into several subpopulations or demes Each deme evolves individually from all others To exchange information between demes individuals occasionally migrate between demes Coarse grained PGAs are not as straightforward to implement as globally parallelized PGAs as they fundamentally change the way in which the population s evolve The third mechanism for parallelizing GAs is fine grained parallelism where the number of demes is very large and the size of each is quite small The extreme and ideal case is to have precisely one individual for every processing element in the system and therefore demes with only one individual but this is not a strict requirement This model is typically implemented on massively parallel computers but can easily be adapted to any multiprocessing system 2 1 Global Parallelization In global parallelization the distributed work is usually the evaluation of individuals as this operation is very computationally expensive in most GAs Mutation and cross breeding could also be farmed out Typically one master maintains the entire population of individuals and assigns slaves to evaluate some subset of the population Once the fitness scores are returned the master creates a new population and repeats the process Typically globally parallelized PGAs are synchronous that is all individuals in the population are evaluated before the next generation is created Asynchronous globally parallelized PGAs are also possible but in practice have different characteristics than traditional GAs The communication overhead in globally parallelized PGAs can become a problem especially in cases where the evaluation of one individual requires information about the entire population Additionally sometimes the chromosomes that comprise individuals are large and the cost of transferring many individuals between computation nodes is prohibitive 2 2 Coarse Grained Parallelization Coarse grained parallelization is the most common approach to GA parallelization and much research has been done The approach is popular for several reasons First the conversion of a simple GA to a coarse grained PGA is straightforward run the original GA on many machines and exchange individuals occasionally Additionally coarse grained parallel computers are widely available and can easily be simulated with available software such as PVM 2 and MPI 1 Importantly the performance of coarse grained PGAs is good Research has shown that the parameters used to determine the rate of migration are critical Specifically with too low a rate of migration the individual demes tend to be unaffected by arriving individuals migrating from other demes Several different approaches to migrating individuals have been studied and the 2 specifics used to determine how an individual chooses the deme to migrate to seem to be relatively unimportant it is number of individuals that migrate and how often migrations occur that are the significant factors Some research into communication