ALGORITHMES GÉNÉTIQUES.

# Sélection de projets sous budget : algorithme génétique en R
library(GA)

# 40 projets simulés : coût et gain attendu (k€), budget de 1 000 k€
set.seed(42)
cout <- sample(20:119, 40, replace = TRUE)
gain <- round(cout * runif(40, 0.8, 2))
budget <- 1000

# Fitness : gain total, pénalisé si le budget est dépassé (x = vecteur de 0 et de 1)
fitness <- function(x) sum(x * gain) - 10 * max(sum(x * cout) - budget, 0)

# 100 portefeuilles par génération, 300 générations : sélection, croisement, mutation, élitisme
res <- ga(type = "binary", fitness = fitness, nBits = 40, popSize = 100, maxiter = 300,
          pcrossover = 0.8, pmutation = 0.1, elitism = 2, seed = 42, monitor = FALSE)

meilleur <- res@solution[1, ]
cat("Projets retenus :", which(meilleur == 1), "\n")
cat("Coût :", sum(meilleur * cout), "k€ | gain :", sum(meilleur * gain), "k€\n")
cat("Budget total si l'on prenait tout :", sum(cout), "k€\n")

# Sélection de projets sous budget : algorithme génétique en Python
import numpy as np

# 40 projets simulés : coût et gain attendu (k€), budget de 1 000 k€
rng = np.random.default_rng(42)
cout = rng.integers(20, 120, 40)
gain = np.round(cout * rng.uniform(0.8, 2.0, 40))
budget = 1000
fitness = lambda pop: pop @ gain - 10 * np.maximum(pop @ cout - budget, 0)   # pénalité si hors budget

pop = rng.integers(0, 2, (100, 40))                # 100 portefeuilles au hasard (1 = projet retenu)
for generation in range(300):
    score = fitness(pop)
    a, b = rng.integers(0, 100, (2, 100))          # sélection par tournoi entre 2 portefeuilles
    parents = np.where((score[a] > score[b])[:, None], pop[a], pop[b])
    enfants = parents.copy()
    for i, c in enumerate(rng.integers(1, 40, 50)):   # croisement en un point, par paires
        enfants[2 * i, c:], enfants[2 * i + 1, c:] = parents[2 * i + 1, c:], parents[2 * i, c:]
    enfants ^= (rng.uniform(size=enfants.shape) < 1 / 40).astype(enfants.dtype)   # mutation
    enfants[0] = pop[score.argmax()]               # élitisme : le meilleur passe toujours
    pop = enfants

meilleur = pop[fitness(pop).argmax()]
print("Projets retenus :", np.flatnonzero(meilleur).tolist())
print("Coût :", meilleur @ cout, "k€ | gain :", meilleur @ gain, "k€")

# Contrôle : optimum exact par programmation dynamique (faisable ici car le problème est petit)
optimum = np.zeros(budget + 1)
for c, g in zip(cout, gain):
    optimum[c:] = np.maximum(optimum[c:], optimum[:budget + 1 - c] + g)
print("Optimum exact :", optimum[budget], "k€")