III – Convergence Asymptotique

1 – Chaînes de Markov2 – Conditions de convergence

Chaînes de Markov

– Une variable aléatoire X est dite chaîne de Markov si :

– Une Chaîne de Markov est dite homogène si :

Conditions de convergence

– Chaque chaîne de Markov homogène est de longueur fini– Les chaînes de Markov sont irréductibles et apériodiques– Seules les configurations d’énergie minimale ont une

probabilité d’existence non nulle quand T tend vers 0

-> Convergence vers des solutions optimales globales asymptotique

V - Amélioration du recuit simulé

1 - Recuit simulé parallèle2 - Recuit simulé distribué

Recuit simulé parallèle

• Plusieurs solutions sont possibles :

– Architecture « Fermier/Travailleurs » proposée par

Baiardi et Orlando

– Architecture « Une-chaîne » proposée par Aarts

– Architecture « Chaînes-Parallèles » proposée par

Aarts

Architecture « Fermier/Travailleurs »

Processeurfermier

Processeurtravailleur

ProcesseurtravailleurProcesseur

travailleur

Génération de configurations voisines par le processeur Fermer

Architecture « Fermier/Travailleurs »

Processeurfermier

Processeurtravailleur

ProcesseurtravailleurProcesseur

travailleur

Un processeur détecte une configuration acceptable il en informe le processeur fermier. Le processeur fermier effectue la mise à jour globale du système.

Recuit simulé distribué

• Subdiviser l’espace de recherche en sous-

espaces

• Dégager des tâches ou des rôles bien

déterminés

VI - Applications

1 - Voyageur de commerce2 - Autres applications

Problème du voyageur de commerce

Il faut définir :

– L’état initial– La fonction de coût– L’évolution de T°– Une modification élémentaire.

X 3 0,8 2,5 0,8 3 1,5 1,6 2,2 0,3 3

Y 0,3 1 1,8 2,3 3 1,8 1,6 0,9 0,4 0,3

Etat initial aléatoire

- Coût initiale : 33,1

Problème du voyageur de commerce

X 3 0,8 2,5 0,8 3 1,5 1,6 2,2 0,3 3

Y 0,3 1 1,8 2,3 3 1,8 1,6 0,9 0,4 0,3

Chainage des sommets

X 3 0,3 0,8 2,5 0,8 3 1,5 1,6 2,2 3

Y 0,3 0,4 1 1,8 2,3 3 1,8 1,6 0,9 0,3

1ère étape

- On sélectionne une transformation.

- On calcule le coût associé C = 25,5

- Comme le nouveau coût est plus petit, on applique la transformation.

Problème du voyageur de commerce

X 3 0,8 2,5 0,8 3 1,5 1,6 2,2 0,3 3

Y 0,3 1 1,8 2,3 3 1,8 1,6 0,9 0,4 0,3

Nouvel état obtenue

- Coût à l’étape 1 : 25,5

Problème du voyageur de commerce

X 3 0,3 0,8 2,5 0,8 3 1,5 1,6 2,2 3

Y 0,3 0,4 1 1,8 2,3 3 1,8 1,6 0,9 0,3

X 3 0,3 0,8 0,8 3 1,5 1,6 2,5 2,2 3

Y 0,3 0,4 1 2,3 3 1,8 1,6 1,8 0,9 0,3

2ème étape

- On sélectionne une autre transformation.

- On calcule le coût associé C = 21,42

- Comme le nouveau coût est plus petit, on applique la transformation.

Problème du voyageur de commerce

X 3 0,3 0,8 2,5 0,8 3 1,5 1,6 2,2 3

Y 0,3 0,4 1 1,8 2,3 3 1,8 1,6 0,9 0,3

Nouvel état obtenue

- Coût à l’étape 2 : 21,42

Problème du voyageur de commerce

X 3 0,3 0,8 0,8 3 1,5 1,6 2,5 2,2 3

Y 0,3 0,4 1 2,3 3 1,8 1,6 1,8 0,9 0,3

X 3 0,3 0,8 1,6 0,8 3 1,5 2,5 2,2 3

Y 0,3 0,4 1 1,6 2,3 3 1,8 1,8 0,9 0,3

3ème étape

- On sélectionne une autre transformation.

- On calcule le coût associé C = 21,96

- Le nouveau coût est plus grand. On applique la transformation avec une certaine P(T°,E)

Problème du voyageur de commerce

X 3 0,3 0,8 0,8 3 1,5 1,6 2,5 2,2 3

Y 0,3 0,4 1 2,3 3 1,8 1,6 1,8 0,9 0,3

Nouvel état obtenue

- Coût à l’étape 3 : 21,96

Problème du voyageur de commerce

X 3 0,3 0,8 1,6 0,8 3 1,5 2,5 2,2 3

Y 0,3 0,4 1 1,6 2,3 3 1,8 1,8 0,9 0,3

X 3 0,3 0,8 1,6 1,5 0,8 3 2,5 2,2 3

Y 0,3 0,4 1 1,6 1,8 2,3 3 1,8 0,9 0,3

4ème étape

- On sélectionne une autre transformation.

- On calcule le coût associé C = 18,62

- Comme le nouveau coût est plus petit, on applique la transformation.

Problème du voyageur de commerce

X 3 0,3 0,8 1,6 0,8 3 1,5 2,5 2,2 3

Y 0,3 0,4 1 1,6 2,3 3 1,8 1,8 0,9 0,3

Nouvel état obtenue

- Coût à l’étape 4 : 18,62

Problème du voyageur de commerce

X 3 0,3 0,8 1,6 1,5 0,8 3 2,5 2,2 3

Y 0,3 0,4 1 1,6 1,8 2,3 3 1,8 0,9 0,3

Problème du voyageur de commerce (2)

Problème du voyageur de commerce (2)

Autres applications

• Placement des composants sur une carte électronique

• K-partitionnement de graphes• Truc• Bidule• Construction d’images

Exemple.avi