Remerciez-le!

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

présenter par: farah bannour Procédure de recherche adaptative aléatoire glouto

présenter par: farah bannour Procédure de recherche adaptative aléatoire gloutonne OPTIMISATION DECISIONNEL Plan 03 PRINCIPAUX COMPOSANTS 02 VUE ALGORITHMIQUE 01 DEFINITION 04 EXEMPLE D'APPLICAION 02 03 L’algorithme Greedy Randomized Adaptive Search Procedure (GRASP) est une métaheuristique introduite par Feo et Resende en 1989. 1-définition 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 final. 04 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 Il y a deux phases dans chaque itération GRASP : 1. 2. 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. 1-définition On peut soutenir que cela C'est exactement la manière dont fonctionne une méthode de construction gourmande 05 Les méthodes gourmandes n'effectuent 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. 1-définition 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 finale est renvoyée. 06 1-définition GRASP utilise une liste restreinte de candidats (RCL) qui permet à l'algorithme d'échantillonner différentes solutions à partir de l'espace des solutions et donc d'effectuer une chercher. 07 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. 2-Vue algorithmique s: solution vide ci: élément de solution RCL: liste restreinte de candidats C: l’ensemble des éléments non encore ajoutés Explication des symboles G: une fonction performance 08 Etape 1: commencer avec une solution vide s, c.a.d aucun élément de solution n'est encore fixé. Répetées jusqu'à critère de terminaison soit satisfait, qui est généralement un nombre maximum de solutions construites Etape 2 :répétées jusqu'à ce qu'une solution complète soit construite. 09 Etape 4: 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 5 :Dans cette liste, un élément aléatoire est choisi et ajouté à la solution Etape 3 : 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 10 Etape 7: Chaque solution nouvellement générée est comparée à la meilleure solution trouvée jusqu'à présent Etape 8 :finalement stocké comme meilleure solution si elle dépasse la qualité. Etape 6 : Chaque solution complète est ensuite optimisée à l'aide d'une procédure de recherche locale. 11 2- Principux composants Construction de la solution de la métaheuristique GRASP 12 Au sommet les éléments sont affichés qui restent à ajouter à la solution partielle actuelle (c1,c2,..., cn) 13 2- Principux composants Une fonction d'évaluation détermine l'influence de ces éléments candidats à la solution actuelle. 14 2- Principux composants Ainsi, la solution partiellement construite peut influencer les performances des éléments candidats. Ensuite, le RCL est construit sur la base des résultats de l'évaluation Enfin un élément de la RCL est choisi au hasard et ajouté à la solution partielle. 15 2- Principux composants Évaluation des candidats 01 Construction d'une liste restreinte de candidats 02 Sélecteur d'éléments aléatoires 03 La phase de construction GRASP consiste en 3 élement 2- Principux composants 16 Évaluation des candidats La fonction d’évaluation du candidat détermine le changement dans la qualité de la solution qui est induite par l’élément candidat respectif. Mathématiquement parlant, la fonction g (évaluation du candidat) mappe chaque élément "ci" de l’ensemble des éléments non encore ajoutés C à une valeur réelle, ce qui reflète l’évolution de la fonction de la solution partielle actuelle 17 Évaluation des candidats Pour la construction de la liste, nous devons savoir gmin et gmax, où gmin = min{g(ci)}, ci C et gmax = max{g(ci)}, ci C, Les renseignements sont utilisés pour limiter le nombre de candidats figurant sur la liste restreinte. 18 Nous connaissons donc l’incrémentation minimale et maximale de la qualité de la solution. Construction d'une liste restreinte de candidats Deux façons de construire la RCL sont décrites : cardinalité et basé sur la valeur Note : Si "k = 1" la construction est purement gourmande. Dans le cas où "k" est plus grand que le nombre d’éléments candidats restants la construction est purement aléatoire. 19 La méthode fondée sur la cardinalité comprend les k meilleurs candidats, i. e. si k = 5 les 5 meilleurs éléments sont inclus dans la liste des candidats où k est un paramètre de cette liste un élément est choisi au hasard. La méthode basée sur la valeur utilise le paramètre α ∈ [0,1] pour la construction de liste des candidats restreints Si α = 0, la construction est gourmande et dans le cas α = 1 la construction est purement aléatoire. 20 Construction d'une liste restreinte de candidats Supposons que nous traitons un problème de minimisation, puis tous les éléments candidats ayant une valeur inférieure au seuil µ = gmin +α(gmax −gmin) sont inclus dans la RCL. Construction of the restricted candidate list le coût d’un élément doit être dans l’intervalle g(ci) ∈ [gmin,µ] Cette méthode a été utilisée pour le sac a dos Ligne indique le cas où des composants de solution sont ajoutés selon leur valeur. Avec α = 0,5 nous obtenons l’intervalle µ = gmin +α(gmax- gmin) = 1+0,5*(7- 1) = 4. Cela signifie que nous ajoutons tous les éléments où g est dans l’intervalle [1,4] qui Il y a 5 éléments. 21 Construction d'une liste restreinte de candidats Changing of the restricted candidate list after adding element 7 Considérons maintenant dans les deux cas que la composante 7 a été ajoutée et que g(ci) ne pour les composants restants. 22 Construction d'une liste restreinte de candidats La liste des candidats est donc un élément plus petite qu’avant. Nous voyons que la longueur de la valeur basée sur RCL varie en fonction sur les performances respectives des différentes propriétés de la solution. La longueur de la RCL a une influence cruciale sur la performance du GRASP. 23 Construction d'une liste restreinte de candidats Festa et Resende décrivent trois approches différentes pour choisir α (en si une liste de valeurs est utilisée): 1. choisir α de façon aléatoire à partir d’une probabilité discrète uniforme 2. choisir α parmi une probabilité discrète décroissante non uniforme 3. fixer α à une valeur proche du choix purement gourmand 24 Construction d'une liste restreinte de candidats Selection des éléments aléatoire Le sélecteur d’éléments aléatoires sélectionne simplement au hasard un élément de la RCL,qui est ensuite ajouté à la solution partielle. 2- Exemple d'application 25 Soit TSP à 4 villes suivant E est l'ensemble de tous les arcs Pour chaque e appartient à E : on associe un cout c(e) 2- Exemple d'application 26 Merci pour votre attention uploads/Science et Technologie/ procedure-de-recherche-adaptative-aleatoire-gloutonne.pdf