Embed Size (px)
Citation preview
Analyse de Résultats de Simulation
Cours
Pierre-Yves Gueniffey – Julien Roux
InfoTronique
2
Plan
• Introduction• Techniques de vérification de modèles• Techniques de validation de modèles• Suppression de l’état transitoire• Simulations terminales• Critère de fin : Estimation de la variance• Réduction de la variance• Conclusion
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
3
Introduction
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
La simulation : outil incontournable
Objectifs de la simulation ?
Qu’est-ce qu’on demande à un modèle de simulation ?
Développement d’un modèle de simulation :
• Vérification du modèle de simulation
• Validation du modèle de simulation
4
Introduction
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
Deux questions essentielles :
• Combien de temps la simulation doit-elle fonctionner ?
• Quand est-ce que le modèle a atteint un état stable ?
Efficacité du modèle :
• Estimation de la variance
• Réduction de la variance
5
Plan
• Introduction• Techniques de vérification de modèles• Techniques de validation de modèles• Suppression de l’état transitoire• Simulations terminales• Critère de fin : Estimation de la variance• Réduction de la variance• Conclusion
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
6
Techniques de vérification de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Vérification = débogage
– S’assurer que le modèle fait ce qu’il est censé faire
• Beaucoup de techniques dans la littérature
– Nous allons en décrire quelques unes
7
Techniques de vérification de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Création modulaire et hiérarchique
– Les modèles de simulation sont de très gros programmes
– Modularité : Le modèle doit être constitué de modules qui communiquent entre eux par des interfaces bien définies
– Hiérarchie : Chaque module du programme est divisé récursivement en modules plus petits jusqu’à obtenir des modules faciles à déboguer
8
Techniques de vérification de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Création modulaire et hiérarchique
– Exemple : Etude de congestion d’un réseau
Modèle Système
9
Techniques de vérification de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Création modulaire et hiérarchique
– Exemple : Etude de congestion d’un réseau
10
Techniques de vérification de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Antibugging
– Ajout de vérifications et de messages dans le programme qui détectent les bugs.
– Exemple dans un réseau :
Nb paquets sources = Nb paquets reçus + Nb paquets perdus
11
Techniques de vérification de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Parcours structuré
– Le développeur explique chaque ligne de son code à une autre personne
– Ceci permet souvent de détecter des bugs
12
Techniques de vérification de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Modèles déterministes
– Pas de variables aléatoires
– Permettre à l’utilisateur de spécifier n’importe quelle distribution
– Ainsi il peut calculer les variables de sortie et déboguer
13
Techniques de vérification de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Exécuter des cas simples
– Assez complexes pour être analysés sans simulation
– Exemples dans un réseau :• Un seul paquet
• Une seule source
• Un seul nœud intermédiaire
14
Techniques de vérification de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Trace
– Liste temporelle d’évènements et de variable
– Ajoute des appels processeur
– Doit pouvoir être désactivé
15
Techniques de vérification de modèles
InfoTronique
• Trace– Exemple dans un réseau :
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
16
Techniques de vérification de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Affichage graphique
– Longue durée des simulations
– L’affichage graphique permet à l’utilisateur de savoir où en est le programme
– Plus compréhensible que les traces
17
Techniques de vérification de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Test de continuité
– Exécuter plusieurs fois la simulation avec de petits changements
– Petits changements dans les entrées du modèle
– Impliquent généralement de petits changements dans les sorties
18
Techniques de vérification de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Test de continuité
– Exemple dans un réseau :
Nombre de sources Nombre de sources
Sortie Sortie
Courbe avant vérification Courbe après vérification
19
Techniques de vérification de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Tests de dégénérescence
– Test des cas extrêmes
– Exemples dans un réseau :• Aucune source
• Aucun routeur
• Routeurs avec des temps de service nuls
20
Techniques de vérification de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Tests de consistance
– Test avec des paramètres d’entrée différents qui ont les mêmes effets
– Exemple dans un réseau :• 2 sources avec 100 paquets / s et 4 sources avec 50 paquets / s
21
Techniques de vérification de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Indépendance de « germe »
– Les germes utilisés pour la génération de nombres aléatoires ne doivent pas affecter le résultat final
– Exécuter la simulation avec différentes valeurs de germes
22
Techniques de vérification de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Questions
23
Plan
• Introduction• Techniques de vérification de modèles• Techniques de validation de modèles• Suppression transitoire• Simulations terminales• Critère de fin : Estimation de la variance• Réduction de la variance• Conclusion
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
24
Techniques de validation de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
Qu’est-ce que la validation de modèle ?
Trois aspects essentiels pour valider un modèle :
• la validation des hypothèses émises au départ
• la validation des valeurs mises en entrée
• la validation des valeurs de sortie
25
Techniques de validation de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
Validation des trois aspects par :
• (1) Avis d’experts
• (2) Des mesures effectuées auprès d’un système réel
• (3) Des résultats théoriques
26
Techniques de validation de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(1) Avis d’experts
Principe
Le choix des experts
Comment les experts procèdent ?
27
Techniques de validation de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(2) Mesures effectuées auprès d’un système réel
Principe
Méthode peu utilisée car :
• Souvent le système réel n’existe pas
• Coût élevé des mesures
28
Techniques de validation de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(3) Résultats théoriques
Principe
Les résultats théoriques sont utilisés pour des cas complexes
29
Techniques de validation de modèles
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
Un modèle n’est jamais parfaitement modélisé
30Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Questions
Techniques de validation de modèles
31
Plan
• Introduction• Techniques de vérification de modèles• Techniques de validation de modèles• Suppression de l’état transitoire• Simulations terminales• Critère de fin : Estimation de la variance• Réduction de la variance• Conclusion
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
32
Suppression de l’état transitoire
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Définitions :
– Comportement à l’état uniforme :Comportement lorsque le système a atteint un état stable
– Etat transitoire :Partie initiale de la simulation, avant l’état stable
33
Suppression de l’état transitoire
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Dans la plupart des simulations, on ne s’intéresse qu’au comportement à l’état final
• Dans ce cas l’état transitoire ne doit pas être inclus dans le programme final
• Il faut le supprimer• Méthodes empiriques
– Nous allons les décrire
34
Suppression de l’état transitoire
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Longues exécutions
– Simulations assez longues pour s’assurer que les conditions initiales n’affectent pas les résultats
– Nécessite des ressources
– Difficile de savoir si la durée d’exécution est suffisamment longue
– Méthode non recommandée
35
Suppression de l’état transitoire
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Initialisation appropriée
– Démarrer la simulation dans un état proche de l’état uniforme
– Réduction de la durée de la période transitoire
– Exemple :• Une simulation d’exécution CPU doit démarrée avec des tâches en
attente
36
Suppression de l’état transitoire
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Troncation– n observations
– On ignore les l premières observations
– On calcule le minimum et le maximum des n-l observations restantes
– On répète l’opération jusqu’à ce que l’observation l+1 ne soit ni le maximum ni le minimum
37
Suppression de l’état transitoire
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Troncation– Exemple :
Numéro de l’observation
Valeur
Intervalle transitoire
38
Suppression de l’état transitoire
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Suppression des données initiales
– Réplications : Exécution de la simulation sans changer les paramètres d’entrée mais en changeant les germes des nombres aléatoires
– m réplications de taille n
– xij : la jéme observation de la ième réplication
39
Suppression de l’état transitoire
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Suppression des données initiales1. Calcul de la moyenne :
2. Assigner 1 à l
3. Supposer que l’état transitoire dure seulement l, supprimer les l premières observations
40
Suppression de l’état transitoire
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Suppression des données initiales4. Calcul du changement relatif
Changement relatif =
5. Répéter les actions 3 et 4 en variant l de 1 à n-1. Après une certaine valeur de l, le graphe se stabilise. Cette valeur de l est la durée de l’état transitoire
41
Suppression de l’état transitoire
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Suppression des données initiales– Exemple :
42
Suppression de l’état transitoire
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Déplacer la moyenne de réplications indépendantes
– Similaire à la méthode précédente
– Utilisation d’une fenêtre de temps mouvante
43
Suppression de l’état transitoire
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Lots de Moyennes
– Similaire aussi
– Très longues simulations divisées en parties de durée égale
– Calcul de la variance
44Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Questions
Suppression de l’état transitoire
45
Plan
• Introduction• Techniques de vérification de modèles• Techniques de validation de modèles• Suppression de l’état transitoire• Simulations terminales• Critère de fin : Estimation de la variance• Réduction de la variance• Conclusion
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
46
Simulations terminales
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Cas des simulations qui n’atteignent jamais un état final
• Dans ce cas, étude de l’état transitoire
• Exemples : – Transfert de petits fichiers sur un réseau
– Systèmes qui s’éteignent chaque jour à 17h
47Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Questions
Simulations terminales
48
Plan
• Introduction• Techniques de vérification de modèles• Techniques de validation de modèles• Suppression transitoire• Simulations terminales• Critère de fin : Estimation de la variance• Réduction de la variance• Conclusion
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
49
Critère de fin : Estimation de la variance
x
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
Bien choisir la durée de simulation
Rappel :
• La simulation est découpée en échantillons
• Moyenne d’un échantillon :
• Variance de la moyenne d’un échantillon pour n observations indépendantes :
n
xVarxVar
)()(
50
Critère de fin : Estimation de la variance
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
Trois méthodes pour calculer correctement la variance :
• (1) Réplications indépendantes
• (2) Méthode des sous échantillons
• (3) Méthode de régénération
51
Critère de fin : Estimation de la variance
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(1) Réplications indépendantes
Repose sur la technique de réplication
Le principe :
• m réplications de taille n + n0
(avec n0 la longueur de la phase de transition)
52Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(1) Réplications indépendantes
Calcul de la moyenne pour chaque réplication:
Critère de fin : Estimation de la variance
53Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(1) Réplications indépendantes
Calcul d’une moyenne générale pour toutes les réplications:
Critère de fin : Estimation de la variance
54Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(1) Réplications indépendantes
Calcul de la variance de la moyenne répliquée :
Critère de fin : Estimation de la variance
55Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(1) Réplications indépendantes
Intervalle de confiance pour la réponse moyenne :
Critère de fin : Estimation de la variance
56
Critère de fin : Estimation de la variance
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(2) Méthode des sous échantillons
Le principe :
• simulation de (N + n0) observations
• n0 : nombre d’observations dans la phase de transition
• On ignore les n0 observations
• Les observations restantes sont divisées en m lots :
n
Nm
57Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(2) Méthode des sous échantillons
Calcul de la moyenne pour chaque lot :
Critère de fin : Estimation de la variance
58Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(2) Méthode des sous échantillons
Calcul de la moyenne générale :
Critère de fin : Estimation de la variance
59
Critère de fin : Estimation de la variance
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(2) Méthode des sous échantillons
Calcul de la variance des moyennes du lot :
60
Critère de fin : Estimation de la variance
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(2) Méthode des sous échantillons
Intervalle de confiance pour la réponse moyenne :
61
Critère de fin : Estimation de la variance
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(2) Méthode des sous échantillons
Meilleure méthode que les réplications indépendantes
Calcul de la covariance pour optimiser l’intervalle de confiance :
62
Critère de fin : Estimation de la variance
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(2) Méthode des sous échantillons
Autocovariance et variance pour des tailles de lots différentes
Taille des lots Auto covariance
Variance
63
Critère de fin : Estimation de la variance
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(3) Méthode de régénération
Le principe :
• Simulation régénérative
• Points de régénération :
64
Critère de fin : Estimation de la variance
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(3) Méthode de régénération
Considérons la simulation régénérative suivante :
• m cycles de tailles n1,…,nm
65
Critère de fin : Estimation de la variance
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(3) Méthode de régénération
Moyennes d’un cycle :
66
Critère de fin : Estimation de la variance
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(3) Méthode de régénération
Procédure pour calculer la moyenne générale et son intervalle de confiance :
67
Critère de fin : Estimation de la variance
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(3) Méthode de régénération
Calcul des sommes de cycle :
68
Critère de fin : Estimation de la variance
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(3) Méthode de régénération
Calcul de la moyenne générale :
69
Critère de fin : Estimation de la variance
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(3) Méthode de régénération
Calcul de la différence entre les sommes de cycles attendus et observés :
70
Critère de fin : Estimation de la variance
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(3) Méthode de régénération
Calcul de la variance des différences :
71
Critère de fin : Estimation de la variance
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(3) Méthode de régénération
Calcul de la longueur d’un cycle moyen :
72
Critère de fin : Estimation de la variance
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(3) Méthode de régénération
Intervalle de confiance pour la réponse moyenne :
73
Critère de fin : Estimation de la variance
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
(3) Méthode de régénération
Avantage de cette méthode :
• Tient compte de la phase de transition
Inconvénient de cette méthode :
• Temps de simulation ??
• Point de régénération ??
• Application des méthodes de réduction de variance ??
74Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Questions
Critère de fin : Estimation de la variance
75
Plan
• Introduction• Techniques de vérification de modèles• Techniques de validation de modèles• Suppression transitoire• Simulations terminales• Critère de fin : Estimation de la variance• Réduction de la variance• Conclusion
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
76
Réduction de la variance
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
77Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
• Questions
Réduction de la variance
78
Conclusion
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
Réaliser une simulation c’est déjà bien…
Mais ce n’est pas tout…
Il faut aussi la valider et l’analyser.
Nous avons vu plusieurs méthodes pour cela
Pour être sûr de s’approcher des cas réels
Il faut les appliquer toutes
Bon courage …
79
Questions
Cours - Analyse de Résultats de Simulation – P.Y. Gueniffey, J. Roux
InfoTronique
