Assignation de fibres optiques pour la spectroscopie multi-objets

F. Sourd

LIP6 1998/047: Rapport de Recherche LIP6 / LIP6 research reports
71 pages - Décembre/December 1998 - French document.

PostScript : 502 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Systèmes d'Aide à la Décision et à la Formation

Titre français : Assignation de fibres optiques pour la spectroscopie multi-objets
Titre anglais : Fiber-to-object assignment in multi-object spectroscopy

Résumé : Le problème d'assignation de fibres à des objets vient de l'astronomie. Ce problème de géométrie et de combinatoire vise à disposer dans le plan des segments -- ou des rectangles -- sans intersections. Pour résoudre ce problème, nous avons construit une suite d'algorithmes qui converge vers la solution maximale. En fait, les premiers éléments de cette suite donnent de très bons résultats en un temps bref. De plus, ils peuvent être améliorés par des techniques de post-optimisation basées sur ces mêmes heuristiques. Les bons résultats obtenus ont permis de lancer une recherche de la solution exacte. On montre ainsi que les méthodes heuristiques trouvent généralement la solution optimale en quelques
minutes.

Abstract : Fiber-to-Object Assignment Problem comes from Astronomy. This geometrical and combinatorial problem arranges the maximum of segments -- or rectangles -- in the plane without crossovers. In order to solve this problem, we have recursively built a series of heuristic algorithms that converge on a maximal solution. Anyway the first elements of the series give quickly very good results. They can be improved by post-optimization heuristics based on the same heuristics. The good results given by these algorithms enables the search of the exact solution. Hence it shows that the heuristics are able to reach the best solution within a few minutes.

Mots-clés : Heuristiques, optimisation, analyse combinatoire, astronomie

Key-words : Heuristics, Optimization, Combinatorial analysis, Astronomy

Publications internes LIP6 1998 / LIP6 research reports 1998

Responsable Éditorial / Editor
webmaster@lip6.fr