Genetic Algoriothms have been applied to several combinational optimisation problems, including the well known task allocation problem, originating from aprallel computing. We introduce random task graphs as a model of applications which display irregular global communication patterns. Unfiorm croissover is the standard genetic recombination operator, that is applied to solution encoded chromosomes. How-ever, application of a uniform crossover may heavily disrupt low ocst sub-solutions, or building blocks, of a chromosome. Therfore, we define a locality preserving recombination operator, exploiting the connectivity of the task graph. Experiemtns show that his new operator increases the convergence rate of the Genetic Alorithm applied to the task allocation problem.
展开▼
