Mécanique statistique et théorie des systèmes : utilisation de méthodes de mécanique statistique pour étudier des systèmes de télécommunication et traiter des problèmes de recherche opérationnelle
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
The aim of this work is to use· statistical mechanics ideas for studying engineering problems. First we analyze the performance of a class of connecting networks: Clos connecting Networks with 2 k + 1 stages. We show that these networks, like physical systems, exhibit the thermodynamical limit property. We deduce analytical expressions which give values of macroscopic system performance parameters (system with loss, system with rearrangement or system with queueing) in terms of the offered traffic. In particular, we estimate probability distribution of the number of rearrangements and the waiting time distribution using the maximum entropy principle. All these analytical results give good agreements with numerical simulations. We then apply the simulated annealing procedure to some combinatorial optimization problems (travelling salesman problem, minimum weighted matching problem, quadratic sum assignment problem). In fact, we use the Metropolis algorithm to determine a quasi-optimal solution to the problem we consider. We deduce a good heuristic with better performances than other classical methods, especially for large problems. For example we obtain a "good" solution for a 10000-city travelling salesman problem. Using statistical mechanics formalism, we also estimate the asymptotic behaviour of the optimal solution.
Abstract FR:
L'objectif de ce travail est d'utiliser les concepts issus de la mécanique statistique pour étudier les problèmes d'ingénierie. Dans une première partie, nous analysons les performances de réseaux de connexion: réseaux de CLOS à 2k+1 étages. Nous montrons que ces réseaux, comme les systèmes physiques admettent une limite thermodynamique. Nous en déduisons alors, analytiquement, les valeurs de certaines grandeurs macroscopiques décrivant leurs divers modes de fonctionnement (systèmes avec perte des appels bloqués, avec réarrangement ou mise en attente de ces derniers) en fonction de la charge. Nous estimons en particulier certaines lois de distribution de probabilité d'événement (loi du nombre de réarrangements, loi des temps d'attente) grâce au principe du maximum d'entropie. Tous ces résultats analytiques sont comparés avec succès à des résultats de simulation numérique. Dans une deuxième partie, nous appliquons la procédure dite d· recuit simulé à des problèmes d'optimisation combinatoire (voyageur de commerce, couplage parfait de points de poids minimum, affectation à coût quadratique minimum). En fait nous utilisons l'algorithme de Metropolis pour déterminer la solution "optimale" des problèmes considérés. Nous obtenons ainsi une heuristique dont les performances sont favorablement comparées à celles d'autres méthodes classiques. Nous en profitons pour traiter des problèmes de grande taille (voyageur de commerce avec 10000 villes). De plus utilisant le formalisme des ensembles statistiques, nous estimons le comportement asymptotique des solutions optimales des problèmes étudiés.