Friday, September 14, 2007

2001 Genetic algorithms evolve optimum satellite orbits

Genetic algorithms evolve optimum satellite orbits

  • 17:57 16 October 2001
  • From New Scientist Print Edition. Subscribe and get 4 free issues.
  • Will Knight

Software that simulates genetic evolution can improve the coverage provided by a network of low orbiting satellites.

Researchers at Purdue University in Indiana have "evolved" a solution to the complex problem of organising small groups of the satellites to cover as much of the Earth as possible. In some cases, their approach reduced gaps in coverage by 25 per cent.

Constant coverage over an area can be provided by satellites in geostationary orbit at 36,000 kilometres, but these are more expensive to launch and need more powerful transmitters than those circling the Earth at a few hundred kilometers altitude.

"It is an innovative idea," says Ali Zalzala, an expert in evolutionary computing at Heriot-Watt University in Scotland. "Genetic algorithms are simple but can come up with very effective solutions."

William Crossley and fellow researcher Edwin Williams say that their genetically evolved answers took some seasoned satellite engineers by surprise. "The [optimum] constellations might have two satellites spaced very far apart, and the third one will be very close to the second one," says Crossley.

Complex orbits

Low orbit satellites travel around the Earth about every 90 minutes but groups of three or four satellites will have periods when they all are out of sight of some ground receivers.

Finding the best configuration is deceptively complicated because, despite the small number of satellites, the number of possible orbit combinations is vast. So the Purdue researchers turned to a genetic algorithm.

These put crucial parameters of a problem through an artificial process of natural selection. The algorithm randomly mutates parameters, in this case the height, speed and direction of different satellites. It then selects the "fittest" combinations from each generation - those with the greatest coverage - and runs the process again.

Random mutation

Genetic algorithms cannot entirely automate the process of finding the best configuration. "The genetic algorithm can provide a good starting point," said Crossley. "But fine tuning or refinement need to be done to obtain the best final solution."

The approach is already used to solve similar complex problems in other areas. For example, telecommunications companies use genetic algorithms to determine the optimum position for a network of mobile phone masts.

Andy Keane, at Southampton University, says the principle behind organising satellites is not very different, but he says using genetic algorithms is a novel application.

No comments: