Contrôle d'heuristiques par poursuite ou utilisation d'objectifs flexibles

摘要

La plupart des méthodes connues pour résoudre des problèmes de satisfaction de contraintes ou d'optimisation sont basées sur le pilotage d'un point courant dans un certain domaine. Les déplacements de ce point sont alors décidés de façon à minimiser une certaine quantité objectif, combinaison d'un critère de qualité et d'une mesure de satisfaction des contraintes. Très souvent, la structure du domaine considéré ne permet pas d'établir un lien fort entre les notions d'optimalité locale et d'optimalité globale. De ce fait, divers artifices de contrôle existent, qui visent à éviter au point courant de s'enfermer sur un optimum local de mauvaise qualité. Ces artifices de contrôle tendent à autoriser des déplacements dégradant temporairement le point courant, moyennant un tirage au sort (Recuit simulé) ou bien une mémorisation des positions déjà rencontrées (Tabou). Dans l'approche que nous décrivons ici, l'attention est portée non plus sur l'objet primai mais sur les paramètres d'un objectif de contrôle flexible qui conditionnent les déplacements de cet objet. Cette approche peut s'avérer efficace, principalement lorsque la structure de l'objet primai est complexe. Nous en présentons ici les grandes lignes, puis en discutons les modalités d'implémentation, les performances et les limites au travers d'un cadre d'expérimentation lié à la programmation linéaire entière, et en proposons enfin diverses possibilités d'extension.%Most of the usual methods in optimization and constraint satisfaction involve driving some current object inside a given domain. The successive moves of this object are decided in relation to an economic criterion which has to be minimized. Unhappily, local optimality scarcely implies global optimality. Several techniques exist, which make possible to deal with the problem of getting out of a bad local optimum (Tabu search, Simulated Annealing,...). The idea which we develop here consists in rewriting the initial problem in such a way that its new formulation depends on some parameters, and in focusing on adjusting these parameters in order to make a simple algorithmic process yield the global solution of the problem. This approach may prove itself to be efficient when the structure of the unknown primal object is complex. We first present the general framework which makes its description possible, and next discuss its efficiency along with with experimental results.