7. TP de C++ n°7 Utilisation de la structure priority_queue et de foncteurs

7.1. Les tas en STL

Les tas sont représentés par la classe priority_queue dans la STL. Cette classe est caractérisée par les éléments suivants :

7.2 Une application sympa : les séquences de Bean

7.2.1 Les séquences de Bean

Les séquences de Bean offrent un codage particulièrement efficace pour la résolution par algorithme génétique du problème du voyageur de commerce (TSP).

Rappelons brièvement que le principe des algorithmes génétiques consiste à disposer d'une population de chromosomes codant différentes solution d'un problème. A chaque itération, ces chromosomes sont croisés par paires pour donner une nouvelle génération.

La plus commune des techniques de croisement imite le processus naturel du cross over. Les deux chromosomes sont coupés en un certain nombre d'endroits et leurs différentes parties sont recopiées. La figure suivante illustres des cross overs à 1 et 2 points.

Utiliser des séquences de villes pour coder un TSP ne convient pas car l'application des cross overs ne donne pas toujours des solutions réalisables (c'est à dire correspondant à une solution du problème). L'exemple suivant illustre ce problème pour un TSP à 6 villes sur un cross over à 1 point.

Bean a eu l'idée d'utiliser un générateur de nombres aléatoires pour pallier cette difficulté. Le principe des séquences de Bean consiste à associer un nombre aléatoire à chaque ville en fonction de sa position dans la tournée.

Voici l'algorithme de codage accompagné d'un exemple :

  1. Générer une séquence de nombres aléatoires de même taille que la tournée
  2. Trier ces nombres
  3. Associer chaque nombre a une ville de la tournée dans l'ordre croissant des positions (i.e. le plus petit nombre correspond à la première ville, le second plus petit nombre à la seconde ville, etc.)
  4. On obtient ainsi une séquence de couples (nombre aléatoire, numéro de ville)
  5. Trier cette séquence de couples par ordre croissant du numéro de ville
  6. On obtient alors une séquence de Bean

Lorsque vous effectuez un cross over sur de telles séquences, vous êtes sur d'obtenir une solution réalisable car chaque ville sera représentée une et une seule fois.

Voici l'algorithme de décodage de la séquence de Beans en une séquence de villes :

  1. Triez la séquence par ordre croissant des nombres aléatoires
  2. La séquence des villes s'obtient alors par simple lecture de la séquence

Séquence de villes n°1

1

3

2

5

4

Nombres aléatoires associés

0.13

0.36

0.56

0.58

0.91

Séquence de Bean après tri par ordre de ville :

1

2

3

4

5

0.13

0.56

0.36

0.91

0.58

Séquence de villes n°2

3

1

4

2

5

Nombres aléatoires associés

0.27

0.41

0.63

0.66

0.88

Séquence de Bean après tri par ordre de ville :

1

2

3

4

5

0.41

0.66

0.27

0.63

0.88

Après application d'un cross over entre les villes 3 et 4

Fils 1

1

2

3

4

5

0.13

0.56

0.36

0.63

0.88

Fils 2

1

2

3

4

5

0.41

0.66

0.27

0.91

0.58

Décodage du Fils 1

0.13

0.36

0.56

0.63

0.88

1

3

2

4

5

Décodage du Fils 2

0.27

0.41

0.58

0.66

0.91

3

1

5

2

4

On obtient donc les 2 solutions :

1

3

2

4

5

3

1

5

2

4

 7.2.2 Travail demandé

On vous demande d'utiliser la STL pour réaliser le codage et le décodage d'une séquence de villes vers une séquence de Bean.