Monte Carlo

ARMOR a développé de nouvelles méthodologies de simulation, pour pallier certaines limitations des techniques existantes. Les travaux ont participé au deux axes majeurs sur ce thème:

- L'échantillonnage préférentiel est le premier axe de recherche (voir les travaux de Nakayama, Nicola, Heidelberger ou Shahabuddin). Il s'agit ici de simuler le processus non pas à l'aide des lois des variables réelles, mais à utiliser des lois accélérant les défaillances. L'estimateur devenant alors biaisé, on utilise une fonction appelée fonction de vraisemblance permettant de supprimer ce biais. Tout le jeu est donc ici de pousser vers la défaillance, mais sans trop forcer car dans ce cas la variance de l'estimateur deviendrait trop importante. Nous avons travaillé dans le cadre de l'évaluation de mesures de sureté de fonctionnement de systèmes multi-composants réparables, à partir de modèles markoviens. En considérant le cas des mesures stationnaires ou encore de la MTTF, nous avons étudié les méthodes de Monte Carlo existantes, appartenant toutes au cadre de l'échantillonnage préférentiel. Nous avons proposé des améliorations de certaines de ces méthodes, et nous avons comparé les performances obtenues. Nous avons aussi proposé une méthode basé sur le conditionnement des évolutions du système a partir des "pathsets", ensembles de composants qui assurent le bon fonctionnement du système, qui est adapté pour l'évaluation de mesures transitoires telle la fiabilité ou la disponibilité dans un intervalle. Une autre contribution apportée à la simulation des systèmes markoviens hautement fiables est l'introduction par Tuffin d'un nouveau concept, l'approximation normale bornée qui valide l'utilisation, parfois abusive, de la loi normale pour des fiabilités proches de 1 (i.e. quand $\varepsilon\rightarrow 0$ ), ainsi qu'une condition nécessaire pour obtenir cette propriété. En effet, la littérature s'était focalisée sur la notion d'erreur relative bornée (déterminant si la taille relative de l'intervalle de confiance est bornée quand $\varepsilon\rightarrow 0$ ), indépendamment de savoir si la loi normale, dont dépend l'intervalle de confiance, est bien approchée. La propriété d'approximation normale bornée est basée sur le théorème de Berry-Esseen déterminant la vitesse de convergence de la distribution empirique centrée et normée vers la loi normale centrée et réduite en fonction des moments absolus d'ordre deux et trois de la variable aléatoire considérée et de la taille de l'échantillon. Une condition nécessaire et suffisante pour obtenir la propriété est donc une condition sur chaque cycle régénératif de la chaîne de Markov pour que cette convergence reste vérifiée quand la fiabilité augmente. Il a été possible, grâce à la mise en évidence de cette condition, de déterminer les techniques, parmi toutes celles existantes, vérifiant la propriété et de démontrer que l'approximation normale bornée impliquait l'erreur relative bornée. Ce dernier résultat montre que la propriété importante à vérifier est celle d'approximation normale bornée.

- Une autre démarche est celle dite de ramification de trajectoires (importance splitting ou splitting) (voir les travaux de Glasserman et Villen-Altamirano) dans le cadre général de la simulation à événements discrets. L'idée est d'étudier ce qui se passe lorsque cette approche est suivie pour accélérer l'exécution d'un logiciel générique de simulation événementiel. L'idée de base de la technique de ramification de trajectoires est qu'il existe des états intermédiaires bien identifiés qui, partant de l'état initial, sont visités beaucoup plus fréquemment que l'état de l'événement recherché. La méthode cherche à optimiser le temps de calcul en évitant de simuler quand certains chemins s'éloignent de la région que l'on veut atteindre. En effet, on essaye de maintenir le simulateur dans les états les plus ``proches'', dans un certain sens, de la région d'intérêt et ceci aussi longtemps que possible. Ceci permet aux trajectoires d'arriver plus fréquemment à la zone de rareté de l'espace d'état du système. Nous avons travaille sur ces méthodes alternatives dans de nombreux contextes, pour lesquels l'optimalité est prouvée, moyennant certains paramètres. Cette méthode est en général bien plus facile à manipuler que celle de l'échantillonnage préférentiel.

Ces techniques de simulation ont été en partie implantées dans différents logiciels. Le premier est B&B, pour Balls and Buskets, développé par H. Cancela lors de sa thèse, qui implante les techniques d'échantillonnage préférentiel précédemment citées. De même, ARMOR a collaboré avec l'université de Duke (états-Unis) sur le développement du logiciel SPNP (Stochastic Petri Net Package), un outil permettant l'évaluation de performances par réseau de Petri et implanté sur près de 200 sites. Les contributions concernent le développement de méthodes de simulation à événements discrets et leur analyse par diverses méthodes de Monte Carlo, comme l'échantillonnage préférentiel et l'importance splitting.

Dans le cadre du projet, les équipes souhaitent travailler ensemble sur les problèmes suivants:

beaucoup de problèmes théoriques et pratiques se posent encore sur la détermination des paramètres optimaux ou quasi-optimaux dans le cas de l'échatillonnage préférentiel et de la méthode de ramification de trajectoires.
Une technique prometteuse très récente et demandant à être développée est celle de l'entropie croisée imaginée par Rubinstein où les paramètres de la simulation sont estimés puis rafinés de manière dynamique.
Un autre point très important est que la plupart des études ont été réalisées dans un cadre Markovien. Cependant, étudier le comportement pratique des méthodes dans le cadre général non-Markovien est primordial pour leur validation.
l'emploi des ressource GRID pour effectuer des simulations distribuées, en particulier la simulation rapide de RAS pour obtenir des informations sur les transitoires.