BDD IA Web services Architecture Info. Ubi.

M1

Correction - Sujet de 2016-2017

Partie 1 - Questions de cours

1. Quels sont les différents modes de résolution de problèmes ? Quel est l'intérêt d'utiliser des graphes pour cela ?

Différent modes de résolution de problèmes

L'intérêt d'utiliser des graphes pour cela est qu'on peut appliquer la théorie des graphes à la représentation de nos connaissances / problèmes et que l'on peut appliquer des algorithmes tel que la recherche en profondeur ou la recherche en largeur ; on peut ne représenter qu'une partie du graphe et pas son ensemble.

2. Quelle est la stratégie de recherche ayant une complexité en temps de O(bm) et en espace de O(b*m) ? En quoi consiste-t-elle ?

b = facteur de branchement maximum de l'arbre de recherche m = profondeur maximale de l'arbre

La recherche en profondeur a une complexité temporelle en O(bm) et spatiale de O(b*m).

Elle consiste à placer un noeud dans une file d'attente et tant que la solution n'est pas trouvée de :

3. Expliquez le principe de la recherche par heuristique. Donnez le nom d'un algorithme de recherche par heuritstique.

La recherche par heuritstique consiste à utiliser des heuristiques pour guider le choix des états à tester et les ordonner selon leurs "promesses" de rapprocher d'un but.

A* est un exemple d'algorithme de recherche par heuristique.

4. Le jeu de dames se joue sur un échiquier de 10x10 composés d'alternance de cases noires et blanches. Les joueurs se font face et leurs pions occupent initialement les cases noires des 3 premères rangées. Les pions se déplacent vers l'avant d'une case en diagonale.

Parant de l'état initial (c.f. figure), quelle est la largeur de l'arbre au niveau 2 ?

Au niveau 2, la largeur de l'arbre est de 81 car au premier niveau il y a 9 coups possibles puis 9 coups possibles pour chacun d'entre eux et 9 × 9 = 81.

Est-il nécessaire de développer entièrement l'arbre des états futurs possible pour appliquer un algorithme de type alphaBeta ?

Non car le principe des algorithmes alphaBeta est d'églaguer l'arbre des possibilités en fonction des découvertes qui ont déjà été réalisées.

Partie 2 - Algorithme A*

Lors d'un examen d'intelligence artificielle en master 1 TNSI surveillé par l'enseignant, la disposition initiale des candidats est représenté par la figure ci-dessous (les carrés représentent les tables où se trouvent les candidats A, B ... et I ; les lignes indiquent les possibilités d'échanges de feuilles entre candidats, notamment les feuilles de brouillon).

Il n'y a que trois couleurs possibles de brouillons : blanc, gris et gris-foncé. La répartition initiale des brouillons permettrait un échange facile de feuilles de brouillon. Sur la figure, on voit que C et F ont la même couleur, de même pour D, E et G, ainsi que pour H et I. Ils peuvent donc échanger leurs feuilles.

Le préparateur de salle ne peut effectuer qu'un seul type d'action : l'échange de deux feuilles de brouillon adjacente si l'action ne résout au moins un conflit.

Proposer une heuristique pour l'algorithme A* permettant de faire en sorte qu'aucun(e) candidat(e) ne puisse avoir la même couleur de papier brouillon que son(sa) voisin(e).

Partie 3 - Algorithmes génétiques

Une entreprise a devéllopé des mini drones autonomes, dotés de reconnaissance vocale, dédiés à la gestion / la surveillance de logement. Dans un premier temps pensés pour l'assistance aux séniors, le produit rencontre un succès dans l'ensemble de la population. L'entreprise tente de s'étendre et de créer des points de vente & agences dans 64 villes.

Le problème est le suivant : à partir d'une somme maximale MaxLoc d'euros dédiés à la location de surface par l'ensemble des agences, et d'un nom maximal MaxPers de personnes pouvant être déployées, il s'agit de choisir dans chaque ville : la bonne dimension d'agence, sachant que la location d'espace a un coût différent selon les villes, et le bon nombre d'employés dans chaque agence (qui soit dépendre du nombre de clients potentiels). Un outil de simulation de vente permet à partir de ces données d'estimer le chiffre d'affaire d'une proposition de déploiement d'agence.

L'entreprise souhaite utiliser un algorithme génértique pour trouver une très bonne solution.

1. Rappelez le principe d'un algorithme génétique

Le principe d'un algorithme génétique est de partir d'une population d'individus, de ne conserver que les meilleurs (c'est-à-dire les individus avec le caractère qui nous intéresse le plus pour le problème rencontré) et de les croiser ensemble puis de répéter l'opération en boucle, jusqu'à obtenir un résultat satisfaisant.

2. Supposons qu'une séquence codant le déploiement dans 64 villes soit composée de 128 valeurs : pour une ville i, sequence[2i] contient la taille de l'agence, sequence[2i+1] contient la taille du personnel.

Sachant que tailleMax est la taille maximale d'une agence, persoMax le nombre maximal de personnes par agence, cout(sequence[2i]) calcul le coût de location d'une surface dans la ville i et que simu(sequence) est l'outil de simulation de vente qui retourne le chiffre d'affaire d'une séquence, définissez une fonction d'utilisé d'une séquence.

u(sequence) = 0 si la séquence est faible ou irréaliste, u(sequence) = 1 s'il s'agit de la meilleure séquence (CA visé = 400 k€)

// Bon en principe il demande une méthode `u` avec uniquement
// `sequence` en paramètre mais du coup elle ferait juste une
// boucle pour créer ("crier") un tableau avec l'utilité par
// ville mais du coup osef.
public double u(Sequence sequence, int ville) {
  double taille = sequence[2 * ville];
  int personnel = sequence[2 * ville + 1];

  double ca_estime = simu(sequence);

  if (taille > tailleMax)
    return 0.0;

  if (personnel > persoMax)
    return 0.0;

  if (ca_estime >= 400000)
    return 1.0;

  // Si le coût est supérieur au chiffre d'affaire, ça pue
  // certainement la raie du coup le max permet d'éviter les
  // valeurs négatives mais je sais pas si je me trompe
  // ou pas  ¯\_(ツ)_/¯
  return Math.max(
    0.0,
    simu(sequence) - cout(sequence[2 * ville]) / 400000 * 100.0
  );
}

3. Supposons que le point de croisement soit unique et au centre d'une séquence. La méthode élitiste consiste à prendre les p (p=2, 3 ou 4) premières séquences pour les faire se reproduire entre elles.

- Les séquences résultant de la reproduction doivent-elles toujours remplacer les pires de la population ?

Pas forcément car si le p est suffisament grand, certaines séquences résultant de la reproduction peuvent être pires que les pires précédemment générées.

- Si on utilise la méthode de sélection par rand (les candidat à la reproduction sont triés au hasard, mais ayant d'autant plus de chance d'être tirés que le rang dans la population est elevé), quels seraient les avantages et les inconvénients ?

Les avantages seraient que l'on pourrait avoir des croisement qui n'auraient pas lieux avec le système élitiste et ces croisements sont peut être intéressants.

L'inconvénient est qu'on peut également ne pas générer certains croisements qui auraient eu lieu avec le système élitiste et peut être passer à côté des meilleurs croisements possibles.

4. t % de la population mute à chaque étape et pour chaque mutant, m % des gènes mutent. Ici la surface et la quantité de personnel peuvent varier d'au plus 10%. Définissez la fonction mutation(sequence) qui permet à une séquence de muter

public void mutation(Sequence sequence, int ville) {
  Gene surface   = sequence[2 * ville];
  Gene personnel = sequence[2 * ville + 1];

  // La fonction `pourcentage` permet de générer
  // un pourcentage aléatoire compris entre 0 et 10%
  // de la taille du gène à faire muter.
  int tauxSurface   = pourcentage(surface.length);
  int tauxPersonnel = pourcentage(personnel.length);

  // On fait muter les gènes liés à la surface
  for (int i = 0; i < Math.round(tauxSurface*100); i++) {
    int index_gene = Math.random() * (surface.length + 1);

    surface[index_gene] = surface[index_gene] == 0 ? 1 : 0;
  }

  // On fait muter les gènes liés au personnel
  for (int i = 0; i < Math.round(tauxPersonnel*100); i++) {
    int index_gene = Math.random() * (personnel.length + 1);

    personnel[index_gene] = personnel[index_gene] == 0 ? 1 : 0;
  }
}