Note publique d'information : Les problèmes d'optimisation combinatoire sont souvent complexes et NP-difficiles.
En outre, ceux issus de l'industrie sont particulièrement caractérisés par une évolution
continuelle de leur modélisation en termes de contraintes et d'objectifs, et leur
résolution est souvent gourmande en ressources matérielles. L'utilisation de plate-formes
(ou frameworks) pour l'optimisation à grande échelle s'avère nécessaire pour la conception
rapide et flexible de méthodes parallèles hybrides réutilisables pour le traitement
de problèmes réels sur grilles de calcul. Nous proposons une plate-forme logicielle
libre appelée ParadisEO, dédiée à la conception de méta-heuristiques parallèles hybrides
pour la résolution de problèmes mono et multi-objectifs nécessitant en particulier
la mise en oeuvre conjointe de méthodes avancées d'optimisation et des systèmes parallèles
et distribués. La démarche méthodologique de conception de cette plate-forme est dirigée
par une séparation conceptuelle claire entre les méthodes de résolution et les problèmes
à traiter. Il s'agit de l'une des rares plates-formes existantes intégrant différents
modèles parallèles et mécanismes d'hybridation pouvant être exploités de manière transparente
sur réseaux de stations à mémoire distribuée et machines parallèles à mémoire partagée.
Dans les premières expérimentations des différents modèles et mécanismes, nous montrons
que les ressources de calcul atteignent vite leurs limites avec l'augmentation de
la taille du problème et/ou la mise en oeuvre de plusieurs niveaux de coopération
et d'hybridation. Aussi, le parallélisme à grande échelle basé sur l'utilisation de
grilles de calcul devient incontournable.
Note publique d'information : Dans le cadre de l'ACI GRID DOC-G, nous nous sommes intéressés à la " gridification"
de la plate-forme. Nous montrons que le déploiement sur environnements de Méta-Computing
n'est pas immédiat. Différentes problématiques ont été identifiées: l'hétérogénéité
matérielle et logicielle, la volatilité des ressources, de longs délais de communication,
le passage à l'échelle, etc. Afin d'assurer un déploiement sûr et efficace à l'exécution,
nous proposons diverses solutions en terme d'algorithmique. Divers aspects ont été
considérés et relèvent de l'asynchronisme des communications, de la mise en oeuvre
conjointe de plusieurs modèles parallèles hiérarchiques et enfin du checkpointing
au niveau applicatif. Dans sa phase de validation, la plate-forme ParadisEO a été
évaluée sur plusieurs problèmes académiques et réels. Deux applications industrielles
ont été modélisées et traitées: le design de réseaux cellulaires en téléphonie mobile
(contrat France Telecom R&D) et la sélection d'attributs en fouille de données spectroscopiques.
Les expérimentations réalisées successivement sur grappes de SMPs dédiées et sur un
réseau enseignement de stations non dédiées ont permis d'obtenir des résultats significatifs
sur des instances de grande taille. Ils montrent la performance à l'exécution des
différents modèles parallèles supportés par ParadisEO et ce, sur différentes architectures
(parallèles et/ou distribuées).