New variants of simulated annealing for solving a biobjective assignment problem
Le recuit simulé a été appliqué de différentes manières au contexte de l'optimisation multiobjectif pour la détermination d'un ensemble de solutions efficaces. Dans cet article, nous développons trois approches du recuit simulé. Dans la première, qui consiste à agir en amont, la stratégie d'acceptation ou de rejet d'une solution moins bonne est définie à partir d'une relation de dominance qui agit sur le vecteur utilité, en utilisant simultanément toutes les directions de recherche. Dans la deuxième approche, nous considérons la relation de dominance sur le vecteur coût, et gardons l'agrégation dans la règle de Metropolis. Dans la troisième, nous éliminons la notion d'agrégation, et introduisons dans la règle de Metropolis une relation de dominance sur le vecteur des probabilités d'acceptation d'une solution de moindre qualité.
The simulated annealing method (SA) has been applied in many ways to the multiobjective optimization context in order to determinate a set of efficient solutions. In this paper, we develop three approaches of multiobjective simulated annealing. Our first approach consists in acting upstream: the strategy of acceptance or reject of a non improving solution is defined from a dominance relation on the utility vector by simultaneously using all the search directions. In the second approach, we consider the dominance relation, on the cost vector, and we keep the aggregation in the Metropolis's rule. And in the third approach, we eliminate completely the notion of aggregation, by introducing in the Metropolis's rule a dominance relation on the probability vector of acceptance of a lower-quality solution, according to each objective.
C.ADICHE, M.AÏDER
optimisation multiobjectif, métaheuristiques, agrégation, dominance, problème d'affectation, recuit simulé.
multiobjective optimization, metaheuristics, aggregation, dominance, assignment problem, simulated annealing.
Anglais
|
