Intergiciels Heuristiques Contraintes Composants Agile Vivado Agents

M2

Metaheuristiques

• Recuit Simulé
• Simulated annealing

Méthode de Recuit Simulé

• Choisir une solution s ∈ S ainsi qu'une température initiale T
• Tant qu'aucun critère d'arrêt n'est satisfait faire
  • Choisir aléatoirement s' ∈ N(s)
  • Générer un nombre réel aléatoire r dans [0, 1]
  • Si r < p(T, s, s') alors pour s = s'
  • Mettre à jour T

Recherche à voisinnage variable

Soient v₁, v₂, ..., v_{max_k} : ensemble du voisinnage

x0     // Solution initiale
x = x0 // Solutio courante
x* = x // Meilleure solution

tant que non fin faire
  k = 1
  tant que k <= Max_k faire
    x′ ∈ V′k(x) aléatoirement
    x′′ = rehercheLocale(x′, Vk)

    si x′′ est meilleure que x alors
      x = x′′
      k = 1
      x* = x
    sinon
      k = k + 1
    fin
  fin
fin