Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Procedure de recherche adaptative aleatoire gloutonne

OPTIMISATION DECISIONNEL Procédure de recherche adaptative aléatoire gloutonne présenter par farah bannour CPlan DEFINITION EXEMPLE D'APPLICAION VUE ALGORITHMIQUE PRINCIPAUX COMPOSANTS CL ? algorithme Greedy Randomized Adaptive Search Procedure GRASP est une métaheuristique introduite par Feo et Resende en C -dé ?nition GRASP est une technique itérative d'échantillonnage aléatoire dans laquelle chaque itération fournit une solution au problème posé La solution en place sur toutes les itérations GRASP est conservée comme résultat ?nal Il y a deux phases dans chaque itération GRASP Construit intelligemment une solution initiale via une fonction gloutonne randomisée adaptative Applique une procédure de recherche locale à la solution construite dans l'espoir de trouver une amélioration C -dé ?nition Le Procédure de recherche adaptative aléatoire gourmande s'agit d'une méthode de recherche constructive elle commence par une solution vide et ajoute éléments de solution à une solution partielle jusqu'à ce qu'elle soit complète On peut soutenir que cela C'est exactement la manière dont fonctionne une méthode de construction gourmande C -dé ?nition Les méthodes gourmandes n'e ?ectuent pas de recherche elles construisent une solution unique dans un de manière itérative en évaluant tous les éléments de solution restants et selon leur performance les ajouter à la solution partielle Les éléments sont ajouté tant que le solution est améliorée Si ce n'est plus le cas la construction est arrêtée et la solution ?nale est renvoyée C -dé ?nition GRASP utilise une liste restreinte de candidats RCL qui permet à l'algorithme d'échantillonner di ?érentes solutions à partir de l'espace des solutions et donc d'e ?ectuer une chercher L'idée principale de l'algorithme est d'assouplir la condition d'ajouter le meilleur élément performant Au lieu de cela une liste d'éléments candidats prometteurs est construite C -Vue algorithmique Explication des symboles G une fonction performance RCL liste restreinte de candidats s solution vide ci élément de solution C l ? ensemble des éléments non encore ajoutés CRépetées jusqu'à critère de terminaison soit satisfait qui est généralement un nombre maximum de solutions construites Etape commencer avec une solution vide s c a d aucun élément de solution n'est encore ?xé Etape répétées jusqu'à ce qu'une solution complète soit construite CEtape l'élément de solution ci est évalué à l'aide de la fonction g Ces ci sont triés par ordre de performance croissant dans une liste dite restreinte de candidats Etape En utilisant ces évaluations la liste restreinte de candidats RCL est construite les meilleurs éléments sont ajoutés à la liste restreinte de candidats Etape Dans cette liste un élément aléatoire est choisi et ajouté à la solution CEtape Chaque solution complète est ensuite optimisée à l'aide d'une procédure de recherche locale Etape Chaque solution nouvellement générée est comparée à la meilleure solution trouvée jusqu'à présent Etape ?nalement stocké comme meilleure solution si elle dépasse la qualité C - Principux composants Construction de la solution de la métaheuristique GRASP C - Principux composants Au sommet les éléments sont a ?chés qui restent à ajouter à la solution partielle actuelle c c cn C - Principux composants Une fonction