Une méthode de planification qui explore l'arbre des décisions possibles en simulant des milliers de fins au hasard. Elle concentre ses efforts sur les branches prometteuses, sans jamais tout énumérer. Associée à des réseaux de neurones, elle est au cœur d'AlphaGo, vainqueur en 2016 du champion de go Lee Sedol.
Un joueur d'échecs pressé ne calcule pas tous les coups. Il joue mentalement beaucoup de parties rapides à partir des coups qui lui semblent bons, et revient plus souvent sur ceux qui mènent à des victoires.
On descend dans l'arbre des décisions déjà explorées en choisissant à chaque niveau la branche qui combine un bon score moyen et peu de visites (règle UCT).
Arrivé à une branche jamais essayée, on l'ajoute à l'arbre : ici, placer une commande de plus dans le planning.
On termine le scénario au hasard, en plaçant les commandes restantes dans un ordre aléatoire, et on calcule le résultat.
Le résultat remonte le long du chemin parcouru : chaque branche met à jour son nombre de visites et son score cumulé. Au bout du budget, on retient la branche la plus visitée.
Chaque commande a une durée, une heure de livraison promise et un poids : une heure de retard chez un client clé coûte trois fois plus. Il existe plus de 40 000 ordres de passage possibles.
MCTS construit le planning commande après commande, en suivant les branches les plus visitées. Le résultat est un ordre de passage directement utilisable par l'atelier.
Dans l'exemple Python, après 20 000 simulations, MCTS obtient un retard pondéré de 28 contre 33 pour la règle classique « la plus urgente d'abord », qui ignore l'importance des clients.
MCTS se programme sans package dédié. Trois choix pèsent sur la qualité du plan.
Nombre d'itérations avant de décider (20 000 dans l'exemple). Plus il est grand, meilleur est le plan, avec des rendements décroissants.
Dans la règle UCT, elle arbitre entre creuser les branches qui marchent et visiter les autres. Elle doit être à l'échelle des scores : 30 dans l'exemple, pour des retards pondérés de quelques dizaines d'heures.
Finir les scénarios au hasard est le plus simple. Une heuristique métier, comme « la plus urgente d'abord », rend chaque simulation plus informative et accélère la convergence.
# Ordonnancement d'atelier : Monte Carlo Tree Search en R
set.seed(42)
durees <- sample(2:9, 8, replace = TRUE) # 8 commandes : durée en heures
echeances <- sample(5:39, 8, replace = TRUE) # heure de livraison promise
poids <- sample(1:3, 8, replace = TRUE) # pénalité par heure de retard (3 = client clé)
cout <- function(o) sum(poids[o] * pmax(cumsum(durees[o]) - echeances[o], 0))
cle <- function(debut) paste0("p", paste(debut, collapse = "-"))
S <- new.env() # pour chaque début de planning : c(visites, score cumulé)
lire <- function(k) if (is.null(S[[k]])) c(0, 0) else S[[k]]
explorer <- function(debut) {
reste <- setdiff(1:8, debut)
if (length(reste) == 0) return(-cout(debut)) # planning complet
j <- Filter(function(j) is.null(S[[cle(c(debut, j))]]), reste[sample.int(length(reste))])[1]
if (!is.na(j)) { # expansion d'une branche jamais vue, puis fin de planning tirée au hasard
score <- -cout(c(debut, j, setdiff(reste, j)[order(runif(length(reste) - 1))]))
S[[cle(c(debut, j))]] <- c(1, score)
} else { # sélection UCT : bon score moyen ou branche peu explorée
uct <- sapply(reste, function(j) { s <- S[[cle(c(debut, j))]]; s[2] / s[1] + 30 * sqrt(log(S[[cle(debut)]][1]) / s[1]) })
score <- explorer(c(debut, reste[which.max(uct)]))
}
S[[cle(debut)]] <- lire(cle(debut)) + c(1, score)
score
}
for (iteration in 1:20000) explorer(integer(0))
plan <- integer(0)
while (length(plan) < 8) { # on suit la branche la plus visitée
reste <- setdiff(1:8, plan)
plan <- c(plan, reste[which.max(sapply(reste, function(j) lire(cle(c(plan, j)))[1]))])
}
cat("Planning MCTS :", plan, "| retard pondéré :", cout(plan), "| tri par échéance :", cout(order(echeances)), "\n")# Ordonnancement d'atelier : Monte Carlo Tree Search en Python
import math
import numpy as np
rng = np.random.default_rng(42)
durees = rng.integers(2, 10, size=8) # 8 commandes : durée en heures
echeances = rng.integers(5, 40, size=8) # heure de livraison promise
poids = rng.integers(1, 4, size=8) # pénalité par heure de retard (3 = client clé)
def cout(ordre): # retard pondéré total d'un planning complet
o = list(ordre)
return int((poids[o] * np.maximum(np.cumsum(durees[o]) - echeances[o], 0)).sum())
N, W = {}, {} # visites et score cumulé de chaque début de planning
def explorer(debut):
reste = [j for j in range(8) if j not in debut]
nouveaux = [debut + (j,) for j in reste if debut + (j,) not in N]
if not reste:
score = -cout(debut)
elif nouveaux: # expansion d'une branche, puis fin de planning tirée au hasard
e = nouveaux[rng.integers(len(nouveaux))]
N[e], W[e] = 1, -cout(e + tuple(j for j in rng.permutation(reste) if j != e[-1]))
score = W[e]
else: # sélection UCT : bon score moyen ou branche encore peu explorée
score = explorer(max([debut + (j,) for j in reste], key=lambda c: W[c] / N[c] + 30 * math.sqrt(math.log(N[debut]) / N[c])))
N[debut], W[debut] = N.get(debut, 0) + 1, W.get(debut, 0) + score
return score
for iteration in range(20000):
explorer(())
plan = ()
while len(plan) < 8: # on suit la branche la plus visitée
plan = max([plan + (j,) for j in range(8) if j not in plan], key=lambda c: N.get(c, 0))
print("Planning MCTS :", plan, "| retard pondéré :", cout(plan), "| tri par échéance :", cout(np.argsort(echeances)))AlphaGo combine MCTS avec deux réseaux de neurones : l'un propose les coups prometteurs, l'autre évalue les positions. Les réseaux rendent la recherche bien plus ciblée que des simulations au hasard. En 2016, AlphaGo a remporté 4 parties sur 5 contre Lee Sedol.
UCT (Upper Confidence bounds applied to Trees) choisit la branche qui maximise son score moyen plus un bonus d'exploration. Ce bonus est grand pour les branches peu visitées et diminue à mesure qu'on les explore. Aucune branche prometteuse n'est ainsi abandonnée trop tôt.
Non, dans sa version de base. Il suffit de pouvoir simuler le problème : connaître les actions possibles et calculer le résultat final. C'est un atout quand l'historique est pauvre, et une limite quand le problème est mal connu.
Tirer des milliers de scénarios au hasard pour estimer un résultat. MCTS organise ces tirages en arbre pour décider.
Voir la fiche → l'alternative en optimisationAméliore une solution complète par petites modifications. Souvent plus simple pour un planning de grande taille.
Voir la fiche → apprendre une fois pour toutesApprend une politique réutilisable, là où MCTS recalcule à chaque décision.
Voir la fiche →Dataistudio forme les équipes au machine learning et à l'IA, sur des cas concrets.
Nous utilisons des cookies de mesure d'audience et de suivi publicitaire pour comprendre la fréquentation du site et l'efficacité de nos annonces. Rien n'est déposé sans votre accord. En savoir plus