Intergiciels Heuristiques Contraintes Composants Agile Vivado Agents

M2

Heuristiques

• Heuristiques qui vient du verbe heuriskein en grec qui signifie "trouver"
• meta qui est un suffixe qui signifie "au dela", "dans un niveau supérieur"

Heuristique constructive

Principe: On comence par une solution nulle et à chaque itération on ajoute un élément (sommet, arc, job, tâche, etc) jusqu'à l'obtention d'une solution complète

Exemple 1 : Arbre couvrant de coût minimal

Problème : soit G = <S, A> un graphe non orienté

∀ (i, j) ∈ C(i, j) coût de l'arrête

Trouver un arbre couvrant de coût minimal

Début de l'algorithme :

T = O
T = {(1,2)}
T = T U (4,6)
T = T U (2,5)
T = T U (5,7)
T = T U (3,4)
stop

On ne prend pas la (3,6) parce que ca fait un cycle. On arrête car tous les somets sont couverts.

C(T) = 2 + 7 + 8 + 8 + 10 + 3

Remarque : T est un arbre optimal

Exemple 2 : Problème du voyageur de commerce

Trouver un cycle Hamiltonien de coût

Heuristique constructive du plus proche voisin. π = < 1 >

π = <1>

i = 1, z = 0

tant que π != S faire
  C(i, j) = min { C(i, k) : k ∈ S - π}
  z = z + C(i, j)
  π = π U {j}
  j = i
fin

z = z + c(i, 1)

Exemple 3 : Problème du sac à dos

max z = ∑ Cj xj
  s.c.  ∑ aj xj <= b
        xj ∈ {0, 1}  j = 1, ..., n

Trier les objets j selon un ordre

x_j ∀j = 1, ..., n

z = 0
j = 1
Δ = b

tant que (j <= n) faire
  si aj <= Δ alors
    xj = 1
    z = z + Cj
    Δ = Δ - aj
  fin

  j++
fin

Remarque : En général pour les problèmes NP-difficiles les heuristiques constructives ne garantissent ni l'optimalité ni la réalisabilité de la solution finale

Heuristique destructive

On commence par une solution irréalisabe et à chaque itération on retire un élément jusqu'à l'obtention éventuelle d'une solution réalisable.

Remarque : stratégie d'oscillation alterné entre les phases constructives et destructives

Heuristiques basées sur la programmation mathématique

1. Arrêter un algo exacte après :
   • Une certaine itération
   • à ε près
   • un temps limité
2. Basés sur les relaxations
3. Basés sur la décomposition

Heuristique d'amélioration

Principe : on commence par une solution initiale x⁰ et on essaye d'améliorer la qualité de cette dernière

Il y a 2 cas :

Cas 1: x⁰ est réalisable et ƒ0 = ƒ(x⁰), x⁰ → x^k tel que ƒ(x^k) ≤ ƒ(x⁰)

Cas 2 : x⁰ irréalisable Δ⁰ : violation de la réalisabilité, x⁰ -> x^k tel que Δ^k ≤ Δ⁰

Simplexe :

x⁰ -> x¹ -> ... -> x^k

c_x⁰ ≤ c_x¹ ... ≤ c_x^k

Problème : min ƒ(x) s.c. x ∈ X ⊆ E

Voisinnage : v : E → P(E)

x ∼> V(x) ⊆ E

Méthode de descente

x⁰ : Solution initiale

x = x0
Fin = faux

tant que non Fin faire
  selectionner x ∈ V(x) tel que f(x') < f(x)

  si x' existe alors
    x = x'
  sinon
    Fin = vrai
  fin
fin

retourner x

Remarque : les méthodes de descente sont appelées aussi méthodes de recherche locale.

Elles dépendent de :

- La solution initiale.

=> La solution finale est une optimisation locale.

- Du voisinnage V

La taille de | V(x) | dépend du problème.

- Choix de l'améliorant

• 1er améliorant lors de l'exploration de V(x)
• Meilleur améliorant f(x') = min { f(y) : y ∈ V(x) }

Ici 14.

Evaluation d'un voisin

Δ = ƒ(x) - ƒ(x')

Exemple : Problème du sac à dos x ∈ { 0, 1 }ⁿ.

ƒ(x) = ∑ C_j x_j

ƒ(x') → O(n)

V(x) = { x' : ∑ | x'_i - x_i | }

x^j ∈ V(x)

Δ_j = ƒ(x) - ƒ(x^j) = c₁x₁ + ... + c_nx_n
- c₁x^j₁ + ... + c_nx^j_n
= c_jx_j - c_jx^j_j
= c_j(2x_j - 1)

Problème du voyageur de commerce

Voisinnage 2 - 0

π' ∈ V(π)

Δ = C(π) - C(π')

Complexité en O(1).

Méthode de Monte Carlo

x⁰ : Solution initiale

x = x0
x* = x // Meilleure solution
Fin = faux

tant que non Fin faire
  selectionner aleatoirement x' ∈ V(x)

  si f(x') < f(x*) alors
    x* = x'
  fin

  x = x'

  MAJ Fin
fin

Test d'arrêt :

• Maximum d'aléatoire
• Maximisation CPU
• Gap = écart ≤ ε