L'approche du portfolio d’algorithmes pour la construction des algorithmes robustes et adaptatifs
Institution:
GrenobleDisciplines:
Directors:
Abstract EN:
THIS THESIS FOCUS ON APPROACHES FOR AUTOMATIC ALGORITHM COMBINATION. THE SUBJECT IS INTERESTING SINCE ON MANY COMPUT A TIONAL PROBLEMS, WE CAN FIND MANY ALGORITHMS WITH DIFFERENT PERFORMANCE ON PROBLEM INSTANCES. IT IS THEN INTERESTING TO BUILD MECHANISM TO EXPLOIT THE DIVERSITY OF ALGORITHMSSOL VING A SAME PROBLEM. OUR MAIN THESIS PROPOSE TO USE THE ALGORITHM PORTFOLIO MODEL FOR AUTOMA TIC COMBINATION. AN ALGORITHM PORTFOLIO DEFlNES A CONCURRENT EXECUTION OF MANY ALGORITHMS SOL VING A SAME PROBLEM. THE EXECUTION OF ALGORITHMS IS INTERLEA VED lN TIME OR lN SP ACE. THE EXECUTION IS INTERRUPTED ON THE INSTANCE TO SOLVE WHEN ONE ALGORITHM FINDS A SOL UTION. THIS THESIS PROPOSES A CLASSIFICATION OF EXISTING TECHNIQUES FOR AUTOMATIC ALGORITHM COMBINATION. WE ALSO PROPOSE TWO TECHNIQUES FOR BUILDING ALGORITHM PORTFOLIO. THE FIRST IS BASED ON AN ADAPTATION OF THE NEAREST NEIGHBOUR METHOD lN MACHINE LEARNING TO ALGORITHM AND THE SECOND IS BASED ON A DISCRETE RESSOURCE SHARING PROBLEM. THESE TECHNIQUES ARE EVALUA TED ON THE RESOLUTION OF SPARSE LINEAR SYSTEMS AND THE SAT PROBLEMS. THE OBTAlNED RESUL TS SHOW THAT THE PROPOSED SOLUTIONS CAN SERVE EFFECTIVEL Y TO EXPLOIT COMPLEMENTARITIES BETWEEN ALGORITHMS lN ORDER TO OBTAIN ROBUST AND ADAPTIVE ALGORITHMS.
Abstract FR:
CETTE THÈSE TRAITE DES APPROCHES DE COMBINAISON AUTOMATIQUE D'ALGORITHMES. CETIE É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 A RÉSOUDRE IL EST INTÉRESSANT DE DÉVELOPPER DES MÉCANISMES DE CHOIX PERMETTANT DE TROUVER EN FONCTION DE L'INSTANCE A RÉSOUDRE ET DE L'OBJECTIF DE PERFORMANCE CIBLE L'ALGORITHME OU LA COMBINAISON D'ALGORITHME LA MIEUX ADAPTÉE. NOUS DÉFENDONS DANS CETIE THÈSE L'USAGE DES PORTFOLIO POUR LA COMBINAISON DES ALGORITHMES. UN PORTFOLIO D'ALGORITHMES DÉFINIT UNE EXÉCUTION CONCURRENTE DE PL USIEURS 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 A RÉSOUDRE, L'EXÉCUTION EST INTERROMPUE DÈS QU'UN DES ALGORITHMES TROUVE UNE SOLUTION. DANS CETIE 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 A TROUVER UNE SOLUTION EN MOYENNE PLUS ROBUSTE QUE CHACUN DES ALGORITHMES CANDIDATS PRIS SÉPARÉMMENT. . 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 SOL VEURS 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.