III – Convergence Asymptotique

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