Sensitivity to parameters and general applicability of genetic algorithms and simulated annealing algorithms for mapping data to multicomputers. (c1994)

Abstract

We analyze the sensitivity to parameters and the general applicability of genetic algorithms and simulated annealing algorithms for mapping data to distributed-memory multicomputers, using the loosely synchronous computation model. The analysis includes sensitivity to user parameters, fault tolerance capability, and applicability to different multicomputer topologies. The user parameters are either objective function dependent or algorithm dependent. The fault tolerance capability is demonstrated by using the mapping algorithms for mapping data to a multicomputer that has some failed processors. We assume a hypercube multicomputer architecture in most experiments. However, comparative results for mesh, array, ring, tree, star graph, and fully connected topologies are presented. The mapping algorithms used are sequential hybrid genetic algorithm, versions of a distributed genetic algorithm, sequential simulated annealing algorithm, and a simulated parallel simulated annealing algorithm. The experimental results verifY that these algorithms are insensitive to user parameters in wide ranges, completely fault tolerant, and unbiased towards particular multicomputer topologies. These results support the conjecture that physical optimization algorithms are flexible and have general applicability, where these properties are necessary for the automation of the mapping process.