Question 1

Qu'est-ce qu'un algorithme génétique ?

Accepted Answer

Un algorithme génétique (AG) est une heuristique de recherche inspirée de la sélection naturelle. Plutôt que de dériver une solution analytiquement, un AG maintient une population de solutions candidates — ici, des itinéraires de livraison complets — et applique de façon répétée sélection, croisement et mutation pour engendrer de nouveaux candidats. Les individus les plus adaptés (itinéraires plus courts) ont plus de chances de transmettre leur structure à la génération suivante. Sur de nombreuses générations, la qualité moyenne de la population augmente même si aucun itinéraire individuel n'a jamais été résolu directement, car la recherche explore en parallèle de nombreuses régions de l'espace des solutions et recombine sans cesse ce qui fonctionne.

Question 2

Que font réellement le croisement et la mutation ici ?

Accepted Answer

Chaque itinéraire est une permutation des arrêts clients, donc un croisement ordinaire produirait des itinéraires invalides avec des clients répétés ou manquants. Cette simulation utilise le croisement par ordre (OX) : une tranche contiguë d'arrêts est copiée du parent A aux mêmes positions, et les arrêts restants sont remplis à partir du parent B dans l'ordre où ils apparaissent, en sautant tout arrêt déjà placé. Cela garantit une permutation valide. La mutation est une mutation par échange : avec une probabilité égale au taux de mutation, deux arrêts choisis au hasard dans un itinéraire échangent leur place, écartant légèrement l'itinéraire de sa forme actuelle sans jamais créer de tournée invalide.

Question 3

Pourquoi l'élitisme est-il important ?

Accepted Answer

La sélection, le croisement et la mutation sont tous stochastiques, donc une génération peut par hasard produire une population qui est, en moyenne, pire que la précédente — le croisement peut briser un bon itinéraire et la mutation peut endommager un itinéraire presque optimal. L'élitisme copie le seul meilleur itinéraire de la génération actuelle directement dans la génération suivante, totalement inchangé. Cela garantit que la meilleure distance trouvée jusqu'ici ne peut jamais empirer d'une génération à l'autre, ce qui explique pourquoi la courbe de « meilleure distance » du graphique est toujours plate ou décroissante, jamais croissante.

Question 4

Quel est le rapport avec le véritable problème du voyageur de commerce ?

Accepted Answer

Il s'agit d'une petite variante de tournées de véhicules du problème du voyageur de commerce (TSP) : trouver la tournée fermée la plus courte, commençant et finissant à un dépôt, qui visite chaque client exactement une fois. Le TSP est NP-difficile — le nombre d'itinéraires possibles pour N clients est (N-1)!/2, ce qui pour seulement 16 clients dépasse 650 milliards. Les algorithmes exacts (branch-and-bound, programmation dynamique) peuvent résoudre des instances modestes mais passent mal à l'échelle. Les algorithmes génétiques, avec d'autres métaheuristiques comme le recuit simulé et l'optimisation par colonies de fourmis, échangent une garantie d'optimalité contre un itinéraire généralement très bon et trouvé en une fraction du temps — exactement le compromis que fait le vrai logiciel logistique pour des flottes comptant des dizaines ou des centaines d'arrêts.

Question 5

Pourquoi l'itinéraire reste-t-il parfois bloqué à un optimum local ?

Accepted Answer

Si toute la population converge vers des itinéraires partageant la même structure de base, le croisement entre deux parents similaires reproduit surtout cette même structure, et de petites mutations par échange suffisent rarement à échapper à une boucle localement bonne mais globalement sous-optimale — par exemple un itinéraire avec une arête de croisement évitable. C'est ce qu'on appelle la convergence prématurée : la diversité de la population s'effondre avant que la meilleure tournée possible ne soit trouvée. Augmenter le taux de mutation, accroître la taille de la population, ou utiliser une nouvelle carte pour comparer les exécutions sont des façons d'observer ce compromis entre exploration (diversité) et exploitation (affiner ce qui fonctionne déjà).

Question 6

Qu'est-ce que la sélection par tournoi et pourquoi l'utiliser ?

Accepted Answer

La sélection par tournoi choisit un petit sous-ensemble aléatoire de la population (un tournoi, ici de taille 3) et retient le membre le plus adapté de ce sous-ensemble comme parent. Elle est simple, rapide, et sa pression de sélection est facile à régler via la taille du tournoi : un tournoi plus grand augmente la probabilité qu'un seul meilleur individu domine la reproduction (convergence plus rapide, risque accru de convergence prématurée), tandis qu'un tournoi plus petit préserve davantage de diversité. Cela évite certains écueils de la sélection proportionnelle à l'aptitude (roulette), où un itinéraire inhabituellement court peut dominer immédiatement toute la population.

Question 7

Comment la taille de la population et le taux de mutation affectent-ils la vitesse de convergence ?

Accepted Answer

Une population plus grande explore davantage l'espace des permutations d'itinéraires par génération et risque moins de perdre une diversité utile par dérive aléatoire, mais chaque génération coûte plus d'évaluations de distance. Un taux de mutation plus élevé injecte plus d'aléa, aidant à échapper aux optima locaux mais perturbant aussi plus souvent les bons itinéraires, ce qui peut ralentir la convergence ou même dégrader temporairement la moyenne de la population (l'élitisme protège quand même le seul meilleur itinéraire). En pratique, il existe un point optimal — des tailles de population de l'ordre de la dizaine à quelques centaines et des taux de mutation de quelques pourcents par gène tendent à converger le plus vite pour des problèmes de cette taille.

🚚 Optimiseur d'Itinéraires de Chaîne d'Approvisionnement — Un Algorithme Génétique à l'Œuvre

À propos de l'Optimiseur d'Itinéraires de Chaîne d'Approvisionnement

Questions fréquentes

Qu'avez-vous trouvé ?