Dynamiques recuites de type Feynman-Kac : résultats précis et conjectures

Del Moral, Pierre  ; Miclo, Laurent 

ESAIM: Probability and Statistics, Tome 10 (2006), pp. 76-140

Résumé (VO)

Soit $U$ une fonction définie sur un ensemble fini $E$ muni d’un noyau markovien irréductible $M$. L’objectif du papier est de comparer théoriquement deux procédures stochastiques de minimisation globale de $U$ : le recuit simulé et un algorithme génétique. Pour ceci on se placera dans la situation idéalisée d’une infinité de particules disponibles et nous ferons une hypothèse commode d’existence de suffisamment de symétries du cadre $(E,M,U)$. On verra notamment que contrairement au recuit simulé, toute évolution logarithmique de l’inverse de la température conduit asymptotiquement à concentrer les dynamiques de Feynman-Kac recuites sur certains minima globaux de $U$ (du moins si $M$ ne fait pas sortir de leur ensemble en un temps presque immédiat). Par contre, ces dernières ont tendance à oublier plus difficilement leur condition initiale et on quantifiera précisément cette propriété. Enfin on présentera les conjectures correspondantes dans une situation plus générale.

Abstract

Let $U$ be a function defined on a finite set $E$ which is endowed with an irreducible Markov kernel $M$. The main purpose of this paper is to theoretically compare two stochastic procedures for the global minimization of $U$: simulated annealing and a genetic algorithm. For the latter we simplify the analysis by considering an infinite number of particles. Furthermore, we assume that the setting $(E,M,U)$ is sufficiently symmetrical and that $M$ does not force particles to get out of $𝒰$ in bounded time, where $𝒰$ is the set of global minima of $U$. Contrarily to simulated annealing, for all logarithmic inverse temperature evolutions, the considered genetic algorithms concentrate in large time on some particular elements of $𝒰$ that we will describe. But it is more difficult for these genetic algorithms to forget their initial condition and we will quantify this property. Corresponding conjectures for more general situations will also be pointed out.

Détail

DOI : 10.1051/ps:2006003

Classification : 37A30, 46E39, 47D08, 60F10, 60J10, 70K20, 90C27
Keywords: optimisation stochastique, dynamique de Feynman-Kac recuite, recuit simulé généralisé, ergodicité faible, valeur et vecteur propre de Perron-Frobenius, équation de Poisson, temps de retour, probabilité invariante ou fixe, grandes déviations, mesures empiriques, basse température, couplage et inégalités stochastiques, inégalité de Sobolev logarithmique modifiée