Simulation distribuée et continue. Simulation distribuée et simulation continue2 Simulation distribuée (Section 1.6; LAW & KELTON, 90) Des processeurs

Simulation distribuée et continue

Simulation distribuée et simulation continue

2

Simulation distribuéeSimulation distribuée(Section 1.6; LAW & KELTON, 90)

Des processeurs spécialisés s’acquittent de fonctions spécialisées.

Décomposition du modèle en plusieurs sous-modèles lesquels sont assignés à desprocesseurs différents.

Les processeurs communiquent entre eux à l’aide d’un système de messagerie.Cela permet de synchroniser l’ensemble des opérations du modèle.

Une autre approche est telle que les processeurs sont autonomes ou encore, lessous-modèles sont indépendants (File d’attente M/M/s ou s files M/M/1).

La réception d’un message par un sous-modèle où l’instant courant du récepteur> l’instant courant du transmetteur entraîne la reprise d’une partie de la simulationpropre à ce sous-modèle.


3

Simulation continueSimulation continueIl s’agit de modéliser un système dont l’état change continûment en fonction du temps.

Le modèle est représenté en général par un système d’équations différentielles àvaleurs initiales.

Elle est très utilisée dans tous les domaines : physique, chimie, biologie, génie,informatique, sociologie, économie, gestion, etc.

Langages spécialisés en simulation continue:ACSL, CSSL-IV, DYNAMO, CSMP, DSL/VS, etc.

Langages de simulation à événements discrets possédant des outils permettant lasimulation continue :

SIMAN, SIMSCRIPT II.5, SLAM II.


4

Résolution numérique d’équations Résolution numérique d’équations différentielles à valeurs initialesdifférentielles à valeurs initiales

On cherche une approximation à la solution y(t) du problème:

y'(t) = dy/dt (t) = f(t, y(t)), a ≤ t ≤ b

y (a) = y0

En général, y(t) = (y1(t), ..., yn(t)) est un vecteur qui désigne l’état du système.

Note: - En pratique, on ne peut pas calculer y(t)pour tout t.- On choisit un maillage de points t0 < t1 < ... < tN sur [a, b].- On calcule pour tout ti, une approximation Wi de y(ti).- Maillage régulier: h = (b - a)/N (le pas d’intégration)

ti = a + i h

Il existe plusieurs façons d’obtenir les Wi.


5


La plus simple est: LA MÉTHODE D’EULER.

- On suppose qu’on connaît y(ti) (approximé par Wi) et on veut approximer y(ti + 1).- On se base sur la formule de TAYLOR:

y(ti + 1) = y(ti) + h y'(ti) + h2/2 y''(ti + i h) (avec 0 < i < 1)

ERREUR y(ti) + h f(ti , y (ti)) car h est très petit.LOCALEERREUR Wi + h f(ti, y(ti)) =Wi +1

GLOBALE

On pose W0 := y0 et on évalue

Wi + 1 := Wi + h f(ti, Wi) pour tout i = 1, 2, 3,...


6


h h t

W i

y(t)

W i+1

h f(t ,W )i i

droite de pente

i if(t ,W )

droite de pente

i+1 i+1f(t ,W )

ti

ti+1

ti+2

y(t )i

y(t )i+1 y(t)


7

Algorithme (méthode d ’EULER)Algorithme (méthode d ’EULER)

Lire les paramètres a, b, N et y0;h = (b - a)/N; // h = pas d’intégrationt = a; // t = instant courantw = y0; // w = approximation de y(t)

Écrire la valeur de (t, w);

for (i = 1; i <= N; i++){

w = w + h * f (t, w);t = a + i h;Écrire (t, w)

}Note : - Si N est assez grand, on suppose que l’erreur est négligeable.- La méthode d’EULER est simple, mais faible numériquement.


8

Un système proie-prédateurUn système proie-prédateurexempleexemple

Il y a 2 types d’animaux : les proies sont la nourriture des prédateurs.

x(t) : # proies au temps ty(t) : # prédateurs au temps t

Le modèle est le suivant :

x'(t) = taux de variation du nombre de proies= r x(t) - c x(t) y(t)

y'(t) = taux de variation du # de prédateurs= - s y(t) + d x(t) y(t)

Taux de croissance naturelen l’absence de prédateurs

Taux de mortalitédû à la prédation

Tauxd’extinction

naturel

Taux de croissancedû à la prédation


9

Un système proie-prédateurUn système proie-prédateurexempleexemple

La population initiale est x(0) = x0 > 0 et y(0) = y0 > 0.

Il s’agit d’un système (déterministe) discret approximé par un modèle continu.

Il est possible de le résoudre analytiquement:toutes les solutions (x(t), y(t)) pour x0 0, y0 0 sont périodiques autour du point (x, y) (s/d, r/c).

Note : Il existe plusieurs raffinements possibles: plusieurs espèces,perturbations aléatoires,etc.

Paramètres d’entrée : r = 0.005 s = 0.01 c = 0.00001d = 0.000005 x0 = 2000 y0 = 150durée de la simulation = 5000


10

Un système proie-prédateurUn système proie-prédateurexemple (N = 1000)exemple (N = 1000)

ÉVOLUTION DES PROIES ET DES

PRÉDATEURS EN FONCTION DU TEMPS

0100020003000400050006000

50

450

850

1250

1650

2050

2450

2850

3250

3650

4050

4450

4850

Temps

No

mb

re d

'ind

ivid

us

Proies

Prédateurs


11

Un système proie-prédateurUn système proie-prédateurexemple (N = 1000)exemple (N = 1000)

ÉVOLUTION DU NOMBRE DE PRÉDATEURS

EN FONCTION DU NOMBRE DE PROIES

0

500

1000

1500

2000

0 2000 4000 6000

Proies

Pré

dat

eurs

Prédateurs


12

Un système proie-prédateurUn système proie-prédateurexemple (N = 100 000)exemple (N = 100 000)

ÉVOLUTION DES PROIES ET DES

PRÉDATEURS EN FONCTION DU TEMPS

0

1000

2000

3000

4000

50

350

650

950

1250

1550

1850

2150

2450

2750

3050

3350

3650

3950

4250

4550

4850

Temps

No

mb

re d

'ind

ivid

us

Proies

Prédateurs


13

Un système proie-prédateurUn système proie-prédateurexemple (N = 100 000)exemple (N = 100 000)

ÉVOLUTION DU NOMBRE DE PRÉDATEURS

EN FONCTION DU NOMBRE DE PROIES

0

500

1000

1500

0 1000 2000 3000 4000

Proies

Pré

dat

eurs

Prédateurs


14

Exemple : N = 100 000Exemple : N = 100 000(x0, y0) = (2000, 150) et (2000, 300)(x0, y0) = (2000, 150) et (2000, 300)

Toutes les solutions (x(t), y(t)) sont

périodiques autour de (s/d, r/c)

0

200

400

600

800

1000

1200

1400

0 1000 2000 3000 4000

Proies

Pré

da

teu

rs

Prédateurs

(2000, 500)


15


La méthode d’Euler n’est pas très efficace. Il faut trouver mieux.La méthode d’Euler est basée sur la formule de Taylor en retenant 2 termes seulement.Une approche consisterait à utiliser n > 2 termes.

MÉTHODE DE TAYLOR D’ORDRE n

y(ti+1) y(ti) + h y'(ti) + h2/2 y''(ti) + … + hn/n! y(n)(ti) wi + h f(ti, wi) + h2/2 f'(ti, wi) + … + hn/n! f(n-1)(ti , wi)

où y'(t) = dy/dt (t) = f(t, y(t)).Pour n > 2, nous avons en général une meilleure approximation qu’avec la méthode d’Euler, pourvu que la dérivée || f(n) || soit suffisamment petite en valeur absolue.Toutefois, il faut connaître les dérivées de f d’ordre 1 à n-1, ce qui n’est pas le cas en pratique. Les méthodes les plus utilisées n’exigent que des évaluations de f et non de sa dérivée.


16

Évaluation de fonctionsÉvaluation de fonctions

I = g(x) dxa

b

où

g(x) = esin x ln (1 + x2 )

On veut évaluer

g(x)

a b

c

x

0

MÉTHODE SIMPLISTE[GORDON, p. 40]

Tirer des couples (X, Y) dans cerectangle où

X : U[a, b], Y : U[0, c]

Estimer I comme suit:

II = p. c. (b - a) où E[II] = I un estimateur sans biais et Var [II] élevée.

p = # y g x

# couples générés


17

Méthode suggérée parMéthode suggérée parLaw & KeltonLaw & Kelton

Soient X : U[a, b], Z : g(X), E Z = E g x = g xa

b

. 1b - a

dx = I/ b - a

1˚) Générer X1, X2,..., Xn i.i.d. U(a, b)

2˚) Yi = (b - a) g(Xi )

et E[Y] = I ety = 1n yi

i = 1

n

Var (Y) = 1n Var (Yi) 0 lor sque n

LA SIMULATION (MONTE-CARLO) ESTSOUVENT LE SEUL RECOURS.

Intégrales simples: Il existe des méthodes numériques plus efficaces que la simulation.Intégrales multiples :

Documents

Simulation distribuée et continue. Simulation distribuée et simulation continue2 Simulation distribuée (Section 1.6; LAW & KELTON, 90) Des processeurs