Corrigé Mines-Ponts 2025 Informatique commune MP-PC-PSI — Partie 7 (Q18 à Q23) : Colonie de fourmis : phéromones, meilleure fourmi, probabilités de choix

Sujet officiel du concours Mines-Ponts, session 2025, épreuve Informatique commune MP-PC-PSI. Corrigé rédigé par Ibrahim Alame.

Sujet officiel (PDF, site du concours)

Énoncé

Algorithme ACO. Chaque objet $o_{i}$ porte une trace de phéromone $τ (o_{i})$ , initialisée à $τ_{m a x}$ ; $S_{b es tO f A l l}$ et $P_{b es tO f A l l} = 0$ mémorisent le meilleur résultat. À chacune des $n b_{i t}$ itérations :

b) chaque fourmi $k \in [[0, n b_{A n t s} - 1]]$ construit une solution $S_{k}$ : premier objet $o_{0}$ tiré uniformément, ressource mise à jour, puis, tant qu'il reste des candidats (objets non pris qui tiennent dans la ressource restante $b$ ), choix de $o_{i}$ avec la probabilité

$p r o b (o_{i}) = \frac{τ ( o _{i} ) ^{α} η ( o _{i} ) ^{β}}{\sum _{o_{j} \in c an d i d a t s} τ ( o _{j} ) ^{α} η ( o _{j} ) ^{β}}, η (o_{i}) = b \times \frac{p _{i}}{r _{i}},$

mise à jour de $b$ et retrait des candidats devenus trop lourds ;

c) i. évaporation : toutes les traces sont multipliées par $ρ \in [0, 1]$ ; ii. on détermine la meilleure fourmi $k_{m a x}$ de l'itération, de profit $P_{m a x}$ ; iii. mise à jour de $S_{b es tO f A l l}$ et $P_{b es tO f A l l}$ ; iv. $k_{m a x}$ ajoute $1/ (1 + P_{b es tO f A l l} - P_{m a x})$ à la trace de chaque objet de sa solution ; v et vi. les traces sont ramenées dans $[τ_{m i n}, τ_{m a x}]$ .

Implémentation. Variables globales alpha, beta, rho, Tmax, Tmin, SbestOfAll, PbestOfAll ; liste T des traces ; S liste des $n b_{A n t s}$ solutions (listes de $0$ et $1$ ) ; candidats liste d'indices d'objets ; prob dictionnaire indice $\mapsto$ probabilité. mettreAjourTetSolution(obj, T, S) réalise l'étape c), dont l'étape iii est donnée (si Pmax>PbestOfAll, mise à jour de PbestOfAll et de SbestOfAll=S[kmax]). Le programme principal initialise T, puis pour chaque itération et chaque fourmi : b2=b, lignes 15, 17, 18 à écrire, candidats privée de o0 et filtrée par miseAjourCandidats(obj, candidats, b2), puis while b2>0 and candidats!=[]: (lignes 24 et suivantes) ; enfin mettreAjourTetSolution(obj, T, S). On dispose de randint(a, b) (bornes incluses), de L.remove(x) et de choixCandidat(candidats, prob), qui renvoie le candidat tiré.

Q18. Écrire l'étape c)i.
Q19. Écrire l'étape c)ii (kmax et Pmax).
Q20. Écrire les étapes c)iv, v et vi.
Q21. Écrire les lignes 15, 17 et 18 (tirage de o0, ajout à S[k], mise à jour de b2).
Q22. Compléter les lignes 3, 5, 6, 9 et 10 de construitProb(obj, candidats, b, T), qui renvoie prob (la ligne 7 calcule s=sum(prob.values())).
Q23. Écrire le corps de la boucle while (lignes 24 et suivantes).

Corrigé

Remarque préalable. La ligne 2 de mettreAjourTetSolution déclare global SbestOfAll, PbestOffAll (deux f) : c'est une coquille. Telle quelle, l'affectation de PbestOfAll en ligne 11 ferait de ce nom une variable locale, et sa lecture en ligne 10 lèverait UnboundLocalError. On lit global SbestOfAll, PbestOfAll.

Q18. T est une liste, donc mutable : on la modifie en place, par ses indices.


    # 2)c)i.
    for i in range(len(T)):
        T[i] = rho * T[i]

Ce que le correcteur attend : pas de for t in T: t = t * rho, qui ne réaffecte que la variable locale t et laisse T inchangée (erreur relevée par le jury) ; pas non plus de T = [rho * t for t in T], qui crée une nouvelle liste locale sans modifier celle de l'appelant.

Q19. Recherche de l'indice du maximum d'une liste de profits, en un seul parcours.


    # 2)c)ii.
    kmax = 0
    Pmax = profit(obj, S[0])
    for k in range(1, len(S)):
        P = profit(obj, S[k])
        if P > Pmax:
            Pmax = P
            kmax = k

Les noms kmax et Pmax sont imposés par les lignes 10 à 12. Coût : $n b_{A n t s}$ appels à profit, soit $O (n b_{A n t s} n)$ .

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →