On Designing Genetic Algorithms for Hypercube Machines

Genetic Algorithms (GAs) [4] are stochastic optimization heuristics in which searches in solution space are carried out by imi- taring the population genetics stated in Darwin's theory of evolution. In order to apply GAs to a problem, a genetic representation of each individual (chromosome) that constitutes a solution of the problem has to be found. Then, we need to create an initial population to define a cost function to measure the fitness of each solution~ and to design the genetic operators, e.g. selection, crossover and mutation, that favor the birth and survival of the best solutions. By iteratively applying the genetic operators to the current population the fitness of the best in- dividuals in the population converges to local optima. The effectiveness of GAs depends on many parameters whose fixing may depend on the problem considered. The size of the population is particularly important. The larger the population is, the greater the possibility of reaching the optimal solution and the computationM time required. The GA compu- tational cost is commonly mitigated by exploiting parallelism. We have investigated the design of highly parallel GAs. We report results showing the behavior of different parallel GAs applied to a 105-city instance of the Traveling Salesman Problem (TSP).