Optimisation de trajectoires spatiales

Version imprimable

08/09/2010, 16h52
jcloupgarou

Optimisation de trajectoires spatiales

Bonjour m'sieurs-dames,

je développe un logiciel permettant de simuler un environnement spatial interplanétaire (flux de particules, énergies) et de calculer les effets des radiations sur un engin spatial pour une trajectoire donnée (4D). Un module d'orbitographie permet à l'utilisateur de définir la trajectoire de l'engin sous formes de paramètres orbitaux (altitude, apogée, excentricité, ...).

Nous en sommes là aujourd'hui : Pour choisir la trajectoire finale d'une mission, l'utilisateur doit générer une grande quantité de trajectoires en étant contraint dans l'ensemble des valeurs des paramètres (par exemple, l'engin ne doit pas s'approcher trop prés de la terre, ou ne doit pas passer dans une certaine région de l'espace). Il analyse ensuite chacune des trajectoires en fonction de plusieurs effets (nocifs) des radiations comme le dépôt de dose ou le déplacement atomique. Il tente ainsi de trouver la trajectoire minimisant tous les critères retenus pour la mission.

Nous sommes donc concrètement dans un problème d'optimisation multi-critère avec un ensemble de départ contraint. Je me renseigne depuis un moment pour identifier quelle méthode serait la plus appropriée pour traiter le sujet ! Je pencherais pour une résolution stochastique du genre algo évolutionniste (génétique), mais j'avoue que c'est celui que je connais le mieux pour l'avoir déjà codé dans le cadre du problème du voyageur de commerce.
Voici les grandes lignes de l'algo que j'imagine :
- Création d'une population de trajectoire spatiale. Comment coder chaque individu, je ne sais pas (binaire ?)
- Sélection des meilleurs individus par rapport aux critères retenues : minimisation de la dose, du LET, du taux de SEE, ...
- Croisement des individus sélectionnés ( +mutation ) + ré-injection d'individus aléatoires ou d'anciennes générations pour éviter des minima locaux
- ainsi de suite jusqu'à converger vers une trajectoire "convenant" à l'utilisateur (les conditions d'arrêts restent aussi à définir)

Voila, vous savez tout, ou presque ! C'est un logiciel gratuit développé pour le CNES et utilisé par pas mal d'agences spatiales ou industriels de ce domaine. J'ai moins de 6 mois pour développer un premier proto fonctionnel de ce module d'optimisation de trajectoires spatiales. Tout aide, réflexion, conseil ou remarque sera le bienvenu !

Merci d'avance pour l'énergie dépensée par vos cerveaux.
Jc.
09/09/2010, 04h25
benDelphic

tout simplement ton codage va être des points spécifiques d'une courbe !!! ton chromosome va être p 1|p 2|p 3|p 4|.....|p n-2|p n-1|p n !! ces points là doivent définir la trajectoire au mieux ( une b spline par exemple )
09/09/2010, 09h36
Nebulix

Je pense que ton "espace" des trajectoires ne dépend que d'un petit nombre de paramètres. Si c'est le cas l'algo de "downhill simplex" de Nelder-Mead est très bien adapté (cf Numerical Recipes)
09/09/2010, 11h11
Nemerle

Citation:

Envoyé par Nebulix

Je pense que ton "espace" des trajectoires ne dépend que d'un petit nombre de paramètres. Si c'est le cas l'algo de "downhill simplex" de Nelder-Mead est très bien adapté (cf Numerical Recipes)

Je ne savais pas que Nelder-Mead pouvait s'appliquer sur une N-fonction avec CONTRAINTES...

Sinon, plutôt qu'un algorithme génétique, utilise plutôt un essaim particulaire
sur ce type de problème, ça marche très bien.
09/09/2010, 15h51
Nebulix

Citation:

Envoyé par Nemerle

Je ne savais pas que Nelder-Mead pouvait s'appliquer sur une N-fonction avec CONTRAINTES...

Je pense au contraire que c'est la plus grande force de cet algo...
Il minimise une fonction de N variables et on peut lui interdire certains sous-espaces.
Selon Numerical Recipes : "the downhill simplex method is due to Nelder and Mead (1965)".
Et ils appellent la routine principale "amoeba" ,ce qui décrit bien le principe du programme.
voir http://www.nrbook.com/c/ page 411
Parlons nous de la même chose ?
09/09/2010, 16h08
Nemerle

Citation:

Envoyé par Nebulix

Il minimise une fonction de N variables et on peut lui interdire certains sous-espaces.

Ok; je me trompe peut-être mais si tes contraintes ne sont pas à noyaux linéaires (=sous espaces), alors ça crampe...
09/09/2010, 18h07
Nebulix

Citation:

Envoyé par Nemerle

si tes contraintes ne sont pas à noyaux linéaires

Excuse mon ignorance mais su tu peux traduire, j'aurai appris quelque chose
09/09/2010, 23h20
Clercq

Le simplex me parait aussi une bonne idée, enfin, ça colle bien avec mes souvenir.
Le problème que soulève Nemerie ne serait pas la notion de convexité de l'espace des solutions?

En tout les cas, je pense que ça peut être une approche intéressante, ne serais-ce que pour déterminer une borne (de part certaine approximation -> relâchement de contrainte).