Présentation- Type de séminaire
- Soutenance de thèse
- Titre
- L’approche du portfolio d’algorithmes pour la construction des algorithmes robustes et adaptatifs
- Lieu
- Montbonnot-ENSIMAG
- Organisateur
- LIG
- Présidence
- Eric Gaussier
- Intervenant
- Yanik Ngoko
- Heure
- 10:00
- Date de fin
- 27/07/2010
- Date
- 27/07/2010
- Évènement Confirmé
- oui
- Résumé
- Cette thèse traite des approches de combinaison automatique d’algorithmes. Cette étude est motivée par le développement de nombreux algorithmes avec différentes performances (temps d’exécution, utilisation de la mémoire etc.). Etant donné un problème à résoudre il est intéressant de développer des mécanismes de choix permettant de trouver en fonction de l’instance à résoudre et de l’objectif de performance cible l’algorithme ou la combinaison d’algorithmes la mieux adaptée. Nous défendons l’usage des portfolio pour la combinaison des algorithmes. un portfolio d’algorithmes définit une exécution concurrente de plusieurs algorithmes résolvant un même problème. dans une telle exécution, les algorithmes sont entrelacés dans le temps et/ou l’espace. sur une instance à résoudre, l’exécution est interrompue dès qu’un des algorithmes trouve une solution. Dans cette thèse, nous proposons une classification des techniques de combinaison d’algorithmes et deux techniques de construction des portfolio d’algorithmes. la première technique est basée sur une adaptation de la méthode des plus proches voisins en apprentissage automatique et la seconde technique sur un problème de partage de ressources visant à trouver une solution en moyenne plus robuste que chacun des algorithmes candidats pris séparément.. L’évaluation des techniques proposées sur un jeu de matrices pour la résolution des systèmes linéaires et une base de données de solveurs SAT montre que les techniques proposées permettent de tirer profit de la complémentarité de différents algorithmes résolvant le même problème pour obtenir des algorithmes robustes et adaptatifs.
- Équipes concernées
- MOAIS
- Mots clés
- Calcul pour les sciences et technologies, Algorithmique et complexité,
- URL
- http://moais.imag.fr/membres/yanik.ngoko/
UMR 5217 - Laboratoire LIG -
Maison Jean Kuntzmann -
110 av. de la Chimie -
Domaine Universitaire de Saint-Martin-d’Hères -
BP 53 -
38041 Grenoble cedex 9 -
France
Tél. : +33 (0)4 76 51 43 61 - Fax : +33 (0)4 76 51 49 85
Tél. : +33 (0)4 76 51 43 61 - Fax : +33 (0)4 76 51 49 85