Feature - Evolving towards the future of science: genetic algorithms and grid computing

Computer engineers are mimicking biological genetics to create algorithms able to optimize solutions to computing problems. These “genetic algorithms” are possible thanks to the recent advent of cheap, readily available computing power, such as that available from computing grids. Stock image from sxc.hu

Great innovations are not rare—we are surrounded by them.

For inspiration, look not at buildings and machinery, but at plants and animals. Some of our best synthetic technologies copy what we see in nature: think of seed-styled Velcro, mollusk-inspired epoxy, air conditioning based on termite mounds and solar panels that imitate insect eyes.

Now, a relatively new type of biomimicry is helping researchers find great ideas.

Mutating the way to perfection 

“Genetic algorithms” are search functions that “evolve” towards the optimum solution to a problem. Imitating life’s genetic evolution, the simulations progress a “population” of potential solutions or “phenotypes” towards better and better solutions.

Now the technology that makes these simulations possible—high performance computing—is also benefiting from it.

At the University Politehnica of Bucharest, computer engineers Florin Pop and Valentin Cristea have designed a genetic algorithm called DIOGENES that optimizes grid scheduling.  

The genetic algorithm DIOGENES can create an optimum schedule for up to 100 grid jobs in just one or two seconds, using a “mutating” population of task-processor pairs or “genes” to evolve the perfect solution. Images courtesy of Wikipedia

Genius DIOGENES

Standing for Distributed Optimal GENEtic algorithm for Grid applications Scheduling, DIOGENES quickly determines the most efficient way to schedule of a set of jobs on a computing grid, optimizing both time and resources in the process.

In principal, it is fairly simple: represent a problem’s possible solutions in a genetic way, with each “solution” behaving as an individual, select the individuals that perform the best, combine their “genetic material” and repeat. After several generations you’ll have a set of star performers.

In the DIOGENES algorithm, the mapping between one task and one processor is the equivalent of a “gene” and is free to “mutate.”

“At the beginning of the algorithm the mapping is random,” says Cristea. “Using crossover [swapping bits of genetic material between two chromosomes] and mutation, we change the mapping between task and processor.”

How fit is your function? 

To measure the success of individuals in the population, a “fitness function” selects those solutions that run the jobs faster while consuming fewer resources. In seconds, the genetic algorithm can create a map showing the optimum way to organize a set of jobs.

Finding a good fitness function, says Pop, is the most difficult part of the process. The function’s role is demanding: it must complete some tasks before others can begin, properly conserve the balance between time and resource consumption, manage very complicated schedules and guard against rapid convergence to non-ideal solutions. Pop and Cristea are pleased, however, with their fitness function and say schedules mapped using DIOGENES reduce job execution time by an average of five to six percent when compared with schedules created using other genetic algorithm schedulers.

DIOGENES and similar algorithms are likely to be the way of the scheduling future. Cristea says scheduling calculations run using other, non-genetic, algorithms are enormously sluggish in comparison:

“For a normal algorithm finding a schedule for, say, 100 tasks can take one to two minutes. But with genetic algorithms you can reach a solution in one or two seconds,” says Cristea.

Waiting an extra minute? Who has the time for that?

DIOGENES is currently scheduling jobs for several Romanian National Grids, including MedioGRID and GridMOSI. In January 2008, it was also put into production on SEE-GRID. By May 2008, the team hopes to offer the algorithm on the Enabling Grids for E-sciencE e-infrastructure.

- Danielle Venton, EGEE