Propriétés des algorithmes stochastiques

Propriétés des algorithmes stochastiques

Les algorithmes d’optimisation stochastique vérifient certaines de ces propriétés : Evolutionnaires : On peut faire la différence entre les algorithmes d’optimisation stochastique « évolutionnaires » qui s’inspirent de phénomènes naturels et qui sont modélisés par des opérateurs spécifiques. Par contre, les algorithmes « non évolutionnaires » sont ceux qui ne s’inspirent pas de phénomènes naturels.
Trajectoire et population : Les algorithmes d’optimisation stochastique qui possèdent « une structure à population », sont ceux qui manipulent un ensemble de solutions, à chaque itération. Par contre, ceux fondés sur la notion de « trajectoire », ne manipulent qu’une seule solution sur l’espace de recherche, à chaque itération.
Statiques et dynamiques : On peut distinguer entre les algorithmes stochastiques selon leur manière d’utiliser la fonction objectif, « statique » (qui demeure inchangée tout au long de l’optimisation) ou « dynamique » (quand la fonction objectif est modifiée au cours de la recherche). Elles dépendent du temps.
Structures de voisinages : La plupart des algorithmes d’optimisation stochastique utilisent « une seule » structure de voisinage. Cependant, il existe des algorithmes qui permettent de changer de structure de voisinage en cours de recherche.
Mémoire à court et à long terme : Certains algorithmes stochastiques font usage de l’historique de la recherche au cours de l’optimisation, ils sont qualifiés de méthodes à « mémoire à long terme » et à « mémoire à court terme » dans le cas où ils se limitent à considérer l’état de recherche à une itération donnée pour déterminer la prochaine, ces méthodes sont des processus de décision markovienne. Alors que d’autres algorithmes n’ont aucune mémoire du passé.

Files d’attente

La théorie mathématique des files d’attente peut s’appliquer à différentes situations : optimisation des stocks (gestion à flux tendu), gestion des avions au décollage ou à l’atterrissage, attente des clients à un guichet, ou bien encore traitement informatique de données par un serveur.
La modélisation mathématique des files d’attente est un outil de la logistique. Elle relève du calcul des probabilités : les arrivées et départs des clients de la file sont analysés comme un processus stochastique typique d’un processus de naissance et de mort. L’objectif de la modélisation est la recherche des solutions optimales de gestion des files d’attente, ou « queues », telles que la recherche d’une gestion de priorité (ou discipline) donnant le temps d’attente moyen minimum, ou le temps d’attente au pire des cas minimum, etc., en fonction de la loi de probabilité des arrivées et de la loi donnant le temps de traitement. Elle peut aussi permettre d’évaluer la conséquence de la défaillance d’un serveur sur le temps moyen de résidence dans la file et d’apprécier l’impact de la mise en place d’un serveur supplémentaire, etc.
L’analyse des systèmes de files d’attente s’appuie généralement sur les outils de la théorie des chaînes de Markov à temps continu et à temps discret.

Description du phénomène d’attente

Un phénomène d’attente peut être décrit comme un système composé d’un certain nombre (fini ou non) de places d’attente d’un ou plusieurs serveurs et de clients arrivant à des instants aléatoires. Les clients attendent, se font servir selon des règles spécifiées et quittent le système. Ils peuvent être des appels téléphoniques, des machines, …, de même que les serveurs peuvent être un central téléphonique, un processeur,…. Quand les serveurs sont tous occupés, les clients doivent alors patienter dans un espace d’attente (s’il existe) jusqu’à ce qu’un serveur soit disponible. L’identification des systèmes de files d’attente classiques se base principalement sur trois éléments: le processus stochastique décrivant l’arrivée des clients dans le système, le mécanisme de service (le nombre de serveurs et la loi probabiliste décrivant la durée des services) et la discipline d’attente.
Le processus d’arrivée spécifie les instants auxquels les clients arrivent dans le système. Dans la théorie classique des files d’attente, on fait le plus souvent l’hypothèse que les clients arrivent de manière isolée et indépendamment les uns des autres. Sous ces hypothèses, les intervalles de temps entre deux arrivées successives forment une suite de variables aléatoires indépendantes et identiquement distribuées.
La liste qui suit résume les lois de probabilité les plus couramment rencontrées dans la modélisation des systèmes de files d’attente ainsi que les symboles associés.
La lettre M désigne la loi exponentielle. La lettre D correspond à une loi déterministe. Le symbole Ek désigne un processus où les intervalles de temps entre deux arrivées successives sont des variables aléatoires indépendantes et identiquement distribuées suivant une loi d’Erlang d’ordre k.
La lettre G est utilisée lorsqu’aucune hypothèse particulière n’est faite sur le processus d’arrivée, ce dernier étant alors un processus de renouvellement quelconque.
Les temps de service nécessaire au traitement des clients sont supposés être des réalisations de variables aléatoires indépendantes et identiquement distribuées. La description du processus de service revient alors à préciser la loi de probabilité de ces variables aléatoires. Les symboles utilisés pour décrire les processus de service sont les mêmes que ceux introduits pour les processus d’arrivée.

Types de modèles

Modèles markoviens : Les modèles markoviens caractérisent les systèmes dans lesquels les deux quantités stochastiques principales, qui sont le temps inter-arrivées et la durée de service, sont des variables aléatoires indépendantes et exponentiellement distribuées. La propriété d’absence de mémoire de la loi exponentielle facilite l’étude de ces modèles. L’étude mathématique de tels systèmes se fait par l’introduction d’un processus stochastique approprié. Ce processus est souvent le processus {N (t), t ≥ 0} défini comme étant le nombre de clients dans le système à l’instant t. L’évolution temporelle du processus markovien est complètement définie grâce à la propriété d’absence de mémoire.
Modèles non markoviens : En l’absence de l’exponentialité ou lorsque l’on s’écarte de l’hypothèse d’exponentialité de l’une des deux quantités stochastiques : le temps des inter-arrivées et la durée de service, ou en prenant en compte certaines spécificités des problèmes par introduction de paramètres supplémentaires, on aboutit à un modèle non markovien.

Table des matières

Introduction
1 Modélisation stochastique
1.1 Introduction
1.2 Propriétés des algorithmes stochastiques
1.3 Algorithmes génétiques
1.3.1 Modélisation par chaîne de Markov
1.4 Recuit simulé
1.4.1 Convergence du recuit simulé
1.5 Files d’attente
1.5.1 Modélisation des systèmes de files d’attente par chaînes de Markov
Conclusion
2 Systèmes de files d’attente classiques
2.1 Description du phénomène d’attente
2.2 Analyse mathématique d’un système de files d’attente
2.3 Types de modèles
2.3.1 Modèles markoviens
2.3.2 Modèles non markoviens
2.4 Caractéristiques d’un système de files d’attente
2.5 Modèle d’attente M/G/1
2.5.1 Description du modèle
2.5.2 Chaîne de Markov induite
2.5.3 Mesures de performance
2.6 Modèle d’attente MX/G/1
2.6.1 Description du modèle
2.6.2 Analyse du modèle
2.6.3 Chaîne de Markov induite
2.6.4 Approche alternative à l’analyse du modèle MX/G/1
2.6.5 Mesures de performance
Conclusion
3 Systèmes de files d’attente avec rappels
3.1 Introduction
3.2 Modèle d’attente M/G/1 avec rappels
3.2.1 Description du modèle
3.2.2 Chaîne de Markov induite
3.2.3 Distribution stationnaire de l’état du système
3.2.4 Mesures de performance
3.3 Modélisation de l’impatience
3.3.1 Description du modèle à un serveur
3.3.2 Distribution stationnaire de l’état du système
3.3.3 Mesures de performance
3.4 Systèmes de files d’attente MX/G/1 avec rappels et groupes impatients
3.4.1 Description du modèle
3.4.2 Chaîne de Markov induite
3.4.3 Distribution stationnaire de l’état du système
3.4.4 Mesures de performance
3.4.5 Exemples d’application
Conclusion
4 Propriété de décomposition stochastique pour le nombre de clients dans le système
4.1 Introduction
4.2 Propriété de décomposition stochastique
4.2.1 Modèles d’attente avec vacances
4.2.2 Modèles d’attente avec rappels
4.3 Propriété de décomposition stochastique du modèle MX/G/1 avec rappels et impatience
Conclusion
5 Comportement asymptotique du nombre de clients dans le modèle MX/G/1 avec rappels et clients impatients
5.1 Introduction
5.2 Comportement asymptotique du nombre de clients en orbite sous un taux de trafic intense
5.3 Comportement asymptotique du nombre de clients en orbite sous un taux de rappels faible
5.4 Comportement asymptotique du système sous un taux de rappels élevé
5.5 Application numérique
Conclusion
Conclusion générale
Bibliographie