Search-11d — Descente sous budget : la loi derrière les métaheuristiques

Série : Search / Part1-Foundations — variante -d de Search-11 (métaheuristiques MEALPy) et Search-11c (sélection empirique) Opération attestée : op 11 « Descendre sous budget » — EPIC #12204 (table des opérations), 2ᵉ attestation après mimo_lean/Descent.lean (attestation 1, Lean-formel) Source primaire (lue firsthand) : MyIA.AI.Notebooks/SymbolicAI/Lean/mimo_lean/Descent.lean — descent_flips_le_barrier (confinement + plafond) et descent_target_before_ceiling (terminaison dans la cible avant épuisement du budget), thèse op 11 explicite l.148

Ce que ce notebook fait que Search-11 ne fait pas : Search-11 utilise des métaheuristiques qui améliorent iterativement sous un budget d’évaluations ; il n’énonce ni ne mesure jamais la loi qui garantit qu’elles terminent. Ici, la loi est un objet : énoncée, exercée par des assertions runtime sur des centaines d’exécutions, et surtout cassée où elle doit casser — sa troisième hypothèse est fausse en paysage générique, et le notebook l’exhibe.

Statuts de preuve : [exercée ici] = mesuré/asserted dans ce notebook · [Lean-formel] = prouvé dans Descent.lean · [rapporté] = affirmé sans re-vérification.

Exécution : stdlib uniquement (random, itertools), CPU, ~20 min de lecture, ~5 s d’exécution.

1. La loi, et ce que l’attestation Lean prouve exactement

Descent.lean formalise une descente comme une suite d’états où seuls les flips acceptés comptent, sous trois hypothèses :

Hypothèse	Énoncé	Rôle
`hstrict`	chaque mouvement accepté décroît strictement le coût	interdit les cycles
`hbarrier`	le coût reste confiné sous une borne `B` sur tout le run	majore le nombre de pas
`hnostall`	hors de la cible, un mouvement accepté existe toujours	bloque uniquement sur la cible

Sous ces trois hypothèses, descent_target_before_ceiling démontre : le dernier état est dans la cible, et le run a consommé strictement moins que le plafond M_N dès que B < M_N. C’est la garantie de complexité : terminaison dans la cible avant épuisement du budget.

La question de ce notebook : que reste-t-il de cette loi quand on quitte le cadre Lean — c’est-à-dire sur un paysage combinatoire générique, avec un budget d’évaluations explicite ? Réponse en trois temps : la loi de terminaison tient (§2, exercée), la troisième hypothèse tombe (§3, exhibée), et le budget achète de la qualité à rendement décroissant (§4, mesuré).

import random
import itertools
import statistics

random.seed(20260916)
print("kernel python3, stdlib only")

kernel python3, stdlib only

2. L’objet : une descente sous budget, instrumentée

Le substrat : sac à dos 0/1 (instances synthétiques seedées). Le potentiel Φ = valeur négative de la sélection (décroître Φ = augmenter la valeur). Le voisinage : flips de bit uniques. La barrière de confinement : la relaxation LP du sac à dos (majorant de toute sélection admissible — Φ ne peut pas descendre en dessous).

Chaque exécution est instrumentée : trajectoire de Φ, mouvements acceptés, raison d’arrêt. Les assertions hstrict/hbarrier sont vérifiées au runtime, à chaque mouvement accepté — la loi n’est pas décrite, elle est exercée.

def instance_knapsack(n, seed, ratio_poids=0.5):
    """Instance 0/1 synthetique : n objets, capacite = ratio * somme poids."""
    rng = random.Random(seed)
    poids = [rng.randint(10, 100) for _ in range(n)]
    valeurs = [poids[i] + rng.randint(-5, 20) for i in range(n)]  # correlation valeur/poids
    capacite = int(ratio_poids * sum(poids))
    return poids, valeurs, capacite

def borne_lp(poids, valeurs, capacite):
    """Relaxation fractionnaire (greedy densite) : majorant de l'optimum 0/1."""
    ordre = sorted(range(len(poids)), key=lambda i: valeurs[i] / poids[i], reverse=True)
    reste, total = capacite, 0
    for i in ordre:
        pris = min(poids[i], reste)
        total += valeurs[i] * pris / poids[i]
        reste -= pris
        if reste == 0:
            break
    return total

def dp_exact(poids, valeurs, capacite):
    """Optimum 0/1 exact par programmation dynamique (temoin de verite)."""
    best = [0] * (capacite + 1)
    for p, v in zip(poids, valeurs):
        for c in range(capacite, p - 1, -1):
            if best[c - p] + v > best[c]:
                best[c] = best[c - p] + v
    return best[capacite]

def admissible(x, poids, capacite):
    return sum(p for p, xi in zip(poids, x) if xi) <= capacite

def valeur(x, valeurs):
    return sum(v for v, xi in zip(valeurs, x) if xi)

def descente_sous_budget(x0, poids, valeurs, capacite, budget, collect=True):
    """Hill-climbing a stricte amelioration, plafonne a `budget` evaluations.

    Retourne un dict : etat final, trajectoire du potentiel, nombre de pas,
    raison d'arret ('budget' | 'blocage'), et compteurs de violation des
    hypotheses hstrict/hbarrier (assertions runtime de la loi, section 2).
    """
    lp = borne_lp(poids, valeurs, capacite)
    x = list(x0)
    phi = -valeur(x, valeurs)          # potentiel : decroitre = s'ameliorer
    trajectoire = [phi] if collect else []
    hstrict_viol, hbarrier_viol = 0, 0
    evaluations, pas = 0, 0
    ameliorant_final = None
    while evaluations < budget:
        best_delta, best_i = 0, None
        for i in range(len(x)):
            if evaluations >= budget:
                break
            y = list(x); y[i] = 1 - y[i]
            if not admissible(y, poids, capacite):
                evaluations += 1
                continue
            evaluations += 1
            d = valeur(y, valeurs) - valeur(x, valeurs)
            if d > best_delta:
                best_delta, best_i = d, i
        if best_i is None:
            ameliorant_final = False   # aucun voisin ameliorant : blocage
            break
        y = list(x); y[best_i] = 1 - y[best_i]
        phi_new = -valeur(y, valeurs)
        if phi_new >= phi:             # hstrict : mouvement accepté doit decroitre strictement
            hstrict_viol += 1
        if -phi_new > lp + 1e-9:       # hbarrier : confinement sous le majorant LP
            hbarrier_viol += 1
        x, phi = y, phi_new
        pas += 1
        if collect:
            trajectoire.append(phi)
    else:
        ameliorant_final = None        # budget epuise avant balayage complet du voisinage
    if ameliorant_final is None:
        # le dernier balayage incomplet peut cacher un ameliorant : le noter honnetement
        raison = 'budget'
    else:
        raison = 'blocage'
    return {'x': x, 'valeur': -phi, 'trajectoire': trajectoire, 'pas': pas,
            'evaluations': evaluations, 'raison': raison,
            'hstrict_viol': hstrict_viol, 'hbarrier_viol': hbarrier_viol,
            'lp': lp}

Lecture de l’instrumentation

raison distingue budget atteint (le plafond d’évaluations a interrompu la recherche alors qu’un améliorant pouvait exister) de blocage (un balayage complet du voisinage n’a trouvé aucun mouvement améliorant) — la dissociation que Descent.lean érige en objet.
hstrict_viol / hbarrier_viol comptent les violations des deux premières hypothèses sur les mouvements réellement acceptés : ils doivent rester à zéro, et la cellule suivante le vérifie en série.
lp est le majorant LP : la barrière de confinement. Aucun état admissible ne peut dépasser cette valeur — Φ reste confiné au-dessus de −lp.

# LA LOI, EXERCICEE : hstrict + hbarrier + plafond, sur 60 executions
random.seed(20260916)
runs = []
for n in (16, 24, 32):
    for seed in range(20):
        poids, valeurs, capacite = instance_knapsack(n, seed)
        x0 = [0] * n
        budget = 8 * n * n            # generosite : budget >> longueur typique d'un run
        r = descente_sous_budget(x0, poids, valeurs, capacite, budget)
        runs.append((n, seed, r))

v_strict = sum(r['hstrict_viol'] for _, _, r in runs)
v_barrier = sum(r['hbarrier_viol'] for _, _, r in runs)
depassements = sum(1 for (n, _, r) in runs if r['evaluations'] > 8 * n * n)

print(f"executions              : {len(runs)}")
print(f"violations hstrict      : {v_strict}   (mouvements acceptes sans decroissance stricte)")
print(f"violations hbarrier     : {v_barrier}   (etat au-dela du majorant LP)")
print(f"depassements de plafond : {depassements}   (evaluations > budget)")
assert v_strict == 0 and v_barrier == 0 and depassements == 0
print("=> *[exercee ici]* la loi de terminaison tient : strictement decroissant, confine, plafonne.")

executions              : 60
violations hstrict      : 0   (mouvements acceptes sans decroissance stricte)
violations hbarrier     : 0   (etat au-dela du majorant LP)
depassements de plafond : 0   (evaluations > budget)
=> *[exercee ici]* la loi de terminaison tient : strictement decroissant, confine, plafonne.

Interprétation

Sur 60 exécutions (3 tailles × 20 graines), zéro violation : chaque mouvement accepté décroît strictement Φ, aucun état ne franchit la barrière LP, aucune exécution ne dépasse son plafond d’évaluations. La partie inconditionnelle de la loi de Descent.lean — descent_flips_le_barrier — se transporte intacte du cadre Lean au paysage combinatoire : la descente sous budget termine toujours. Ce n’est pas une propriété de MEALPy ou d’un algorithme particulier : c’est la conséquence arithmétique de « strictement décroissant + confiné ».

3. Le contre-claim : `hnostall` ne survit pas au paysage générique

Le théorème Lean conclut « le dernier état est dans la cible » — mais seulement sous hnostall : hors de la cible, un mouvement accepté existe toujours. Cette hypothèse est gratuite en paysage générique. Ce qui suit l’exhibe : on classe chaque arrêt en budget atteint vs blocage, puis on demande aux blocages s’ils sont sur la cible (optimum global, connu par DP exacte) ou hors cible — des optima locaux, la négation exacte de hnostall.

# LA DISSOCIATION, EXERCICEE : budget-atteint vs blocage, et blocage-hors-cible
random.seed(20260916)
budgets_serre = 4 * 24 * 24           # budget volontairement serre pour rendre 'budget' observable
stats = {'budget': 0, 'blocage_cible': 0, 'blocage_hors_cible': 0}
gaps_hors_cible = []
n = 24
for seed in range(60):
    poids, valeurs, capacite = instance_knapsack(n, seed)
    opt = dp_exact(poids, valeurs, capacite)
    x0 = [random.Random(seed).randint(0, 1) for _ in range(n)]
    if not admissible(x0, poids, capacite):
        x0 = [0] * n
    r = descente_sous_budget(x0, poids, valeurs, capacite, budgets_serre, collect=False)
    if r['raison'] == 'budget':
        stats['budget'] += 1
        gap = 1 - r['valeur'] / opt
        gaps_hors_cible.append(gap)   # budget epuise : gap quelconque
    else:
        if r['valeur'] == opt:
            stats['blocage_cible'] += 1
        else:
            stats['blocage_hors_cible'] += 1
            gaps_hors_cible.append(1 - r['valeur'] / opt)

total = sum(stats.values())
print(f"runs                        : {total}")
print(f"budget atteint              : {stats['budget']:3d}  ({stats['budget']/total:.0%})")
print(f"blocage SUR la cible        : {stats['blocage_cible']:3d}  ({stats['blocage_cible']/total:.0%})")
print(f"blocage HORS cible (optimum local) : {stats['blocage_hors_cible']:3d}  ({stats['blocage_hors_cible']/total:.0%})")
print(f"gap final median            : {statistics.median(gaps_hors_cible):.1%}")
print(f"gap final max               : {max(gaps_hors_cible):.1%}")
print()
print("=> *[exercee ici]* hnostall est fausse :", end=" ")
if stats['blocage_hors_cible'] > 0:
    print(f"{stats['blocage_hors_cible']} runs se bloquent sur un optimum local :")
    print("   le theoreme 'dernier etat dans la cible' ne se transporte PAS ;")
    print("   sa conclusion devient : dernier etat = minimum LOCAL, atteint sous budget.")
else:
    print("aucun optimum local observe sur cet echantillon (a confronter a un voisinage plus pauvre).")

# Regime budget SERRE (~2 balayages) : la cause d'arret 'budget' existe aussi
stats_tight = {'budget': 0, 'blocage': 0}
for seed in range(30):
    poids, valeurs, capacite = instance_knapsack(n, seed)
    x0 = [random.Random(seed).randint(0, 1) for _ in range(n)]
    if not admissible(x0, poids, capacite):
        x0 = [0] * n
    r = descente_sous_budget(x0, poids, valeurs, capacite, 48, collect=False)
    stats_tight[r['raison']] += 1
print(f"a budget serre (48 evals ~ 2 balayages) : budget {stats_tight['budget']}/30, blocage {stats_tight['blocage']}/30")

runs                        : 60
budget atteint              :   0  (0%)
blocage SUR la cible        :   0  (0%)
blocage HORS cible (optimum local) :  60  (100%)
gap final median            : 10.4%
gap final max               : 16.9%

=> *[exercee ici]* hnostall est fausse : 60 runs se bloquent sur un optimum local :
   le theoreme 'dernier etat dans la cible' ne se transporte PAS ;
   sa conclusion devient : dernier etat = minimum LOCAL, atteint sous budget.
a budget serre (48 evals ~ 2 balayages) : budget 30/30, blocage 0/30

Interprétation — le défaut comme dissociation

Les deux causes d’arrêt existent, chacune dans son régime de budget : à budget serré (~2 balayages), l’arrêt est « budget atteint » — on ne sait pas, un améliorant pouvait exister au-delà du plafond ; à budget généreux (96 balayages), l’arrêt est « blocage » — on sait, aucun voisin n’améliore. Et sur ce régime généreux, tous les blocages observés sont hors cible : hnostall y est littéralement fausse — un état non-cible sans mouvement accepté, gap médian ~10 %. C’est la dette que Descent.lean consigne dans son propre fichier (« un échec de décroissance n’est pas un échec d’expérience à écarter, c’est une dissociation à exhiber ») : transportée hors du cadre Lean, la garantie de cible dégénère en garantie de minimum local sous budget. La loi forte (terminaison) tient ; la loi faible (qualité de l’atteint) ne tient que hypothèse par hypothèse.

4. Ce que le budget achète : courbe qualité-budget

La descente est un algorithme anytime : à chaque plafond correspond une qualité atteignable. La mesure : gap final vs optimum DP exact, à budget croissant, 30 graines par point — la courbe de rendement du budget.

# COURBE QUALITE-BUDGET (anytime) : gap median vs budget, multi-seed
random.seed(20260916)
n = 24
echantillons = []
for B in (20, 50, 100, 200, 400, 800):
    gaps = []
    for seed in range(30):
        poids, valeurs, capacite = instance_knapsack(n, 1000 + seed)
        opt = dp_exact(poids, valeurs, capacite)
        rng = random.Random(2000 + seed)
        x0 = [rng.randint(0, 1) for _ in range(n)]
        if not admissible(x0, poids, capacite):
            x0 = [0] * n
        r = descente_sous_budget(x0, poids, valeurs, capacite, B, collect=False)
        gaps.append(1 - r['valeur'] / opt)
    echantillons.append((B, gaps))
    q = sorted(gaps)
    print(f"budget {B:4d} evaluations | gap median {statistics.median(gaps):6.1%} | "
          f"IQR [{q[7]:.1%}, {q[22]:.1%}] | pire {max(gaps):.1%}")

g_med = [statistics.median(g) for _, g in echantillons]
ameliorations = [g_med[i] - g_med[i + 1] for i in range(len(g_med) - 1)]
print()
print("rendement marginal (gain de gap par doubling de budget) :", )
for i, a in enumerate(ameliorations):
    print(f"  {echantillons[i][0]:4d} -> {echantillons[i+1][0]:4d} : {a:+.1%}")

budget   20 evaluations | gap median  86.3% | IQR [18.4%, 87.1%] | pire 89.0%
budget   50 evaluations | gap median  63.8% | IQR [12.2%, 66.4%] | pire 72.6%
budget  100 evaluations | gap median  39.3% | IQR [12.2%, 42.8%] | pire 48.0%
budget  200 evaluations | gap median  10.8% | IQR [7.9%, 12.7%] | pire 17.0%
budget  400 evaluations | gap median   8.9% | IQR [7.0%, 12.2%] | pire 17.0%
budget  800 evaluations | gap median   8.9% | IQR [7.0%, 12.2%] | pire 17.0%

rendement marginal (gain de gap par doubling de budget) :
    20 ->   50 : +22.4%
    50 ->  100 : +24.5%
   100 ->  200 : +28.5%
   200 ->  400 : +1.9%
   400 ->  800 : +0.0%

Interprétation

Le gap médian s’effondre aux petits budgets puis se plateaute : doubler le budget rapporte de moins en moins, et le plateau restant est exactement la part des optima locaux que §3 a exhibée — le budget n’achète plus rien quand tous les runs restants sont bloqués, pas interrompus. C’est la frontière opérationnelle de l’op 11 : au-delà du budget de saturation, la seule monnaie est le changement de voisinage ou les restarts (exercice 1), pas plus d’évaluations.

5. Expérience ICT candidate, limites, exercices

Expérience ICT candidate : le protocole qualité-budget de §4, appliqué à une descente multi-regards (op 12) — budget partagé entre deux potentiels différents, courbe comparée au budget intégrairement alloué au regard le plus performant en isolation. La dissociation §3 prédit que le partage ne peut pas battre le meilleur regard seul sur les instances où il se bloque ; la mesurer dirait si le plateau de saturation est un invariant ou un artefact du voisinage.

Limites (bornes explicites) : (1) substrat sac à dos 0/1 seul — voisinage bit-flip unimodal par objet ; (2) hill-climbing déterministe — pas de recuit, pas de restarts (c’est l’exercice 1, pas le corps) ; (3) la comparaison MEALPy reste le territoire de Search-11 — ce notebook énonce la loi, il ne refait pas le tour d’horizon.

Exercices — les stubs s’exécutent sans erreur (politique du dépôt : compléter, pas débloquer).

# Exercice 1 — restarts strategiques : mesurer l'effet sur les blocages hors cible
# Indice : repartir d'un x0 aleatoire a chaque blocage, budget global constant a repartir.
# Etape 1 : encapsuler la boucle (descente + tirage) dans budget_restarts().
# Etape 2 : recompter stats['blocage_hors_cible'] a budget global egal.
def descente_restart(x0_gen, poids, valeurs, capacite, budget_global, k_restarts):
    # TODO etudiant : k_restarts descentes, budget_global // k_restarts chacune, garder la meilleure
    return None

# Exercice 2 — barriere : LP fractionnaire vs borne triviale 0
# Indice : hbarrier est une HYPOTHESE ; une barriere plus serree raccourcit le plafond theorique.
# Etape 1 : recalculer le majorant de flips de descent_flips_le_barrier avec lp vs valeur initiale.
# Etape 2 : comparer au pas reellement observe.
def plafond_theorique(x0, lp):
    # TODO etudiant : majorant du nombre de pas acceptes selon la barriere choisie
    return None

# Exercice 3 — voisinage 2-flip : le plateau de saturation recule-t-il ?
# Indice : le voisinage 2-flip contient le 1-flip ; un optimum 1-flip n'est pas optimum 2-flip.
# Etape 1 : etendre le balayage aux paires (i, j). Etape 2 : retracer la courbe de la section 4.
def descente_2flip(x0, poids, valeurs, capacite, budget):
    # TODO etudiant : meme schema, voisins = paires de bits
    return None

print("Exercices a completer : 1 (restarts), 2 (barriere), 3 (voisinage 2-flip).")

Exercices a completer : 1 (restarts), 2 (barriere), 3 (voisinage 2-flip).

Conclusion

Exigence de distillation	Où elle vit
Source primaire firsthand	`mimo_lean/Descent.lean` — `descent_flips_le_barrier` l.110, `descent_target_before_ceiling` l.144, thèse op 11 l.148
Objet formel	`descente_sous_budget` : potentiel strictement décroissant, barrière LP, plafond d’évaluations
Claim exact, exercé	§2 : 60 exécutions, 0 violation `hstrict`, 0 violation `hbarrier`, 0 dépassement de plafond — [exercée ici]
Contre-claim, exhibé	§3 : `hnostall` fausse — 100 % des blocages hors cible à budget généreux (gap médian 10,4 %), arrêts « budget » exhibés à budget serré
Expérience ICT candidate	§5 : qualité-budget d’une descente multi-regards (op 12)

Attestation : 2ᵉ attestation de l’opération 11 « Descendre sous budget » (EPIC #12204), sur substrat indépendant de l’attestation Lean — empirique-notebook, stdout réels committés. La promotion en TABLE appartient à la relecture froide (A7).

Retour au sommet

1. La loi, et ce que l’attestation Lean prouve exactement

2. L’objet : une descente sous budget, instrumentée

Lecture de l’instrumentation

Interprétation

3. Le contre-claim : hnostall ne survit pas au paysage générique

Interprétation — le défaut comme dissociation

4. Ce que le budget achète : courbe qualité-budget

Interprétation

5. Expérience ICT candidate, limites, exercices

Conclusion

3. Le contre-claim : `hnostall` ne survit pas au paysage générique