遺伝的アルゴリズム（GA）の基礎とPython実装

import numpy as np

L = 20          # 個体の長さ l
O_H = 4         # スキーマHの次数 o(H): 固定ビット数
DELTA_H = 3     # スキーマHの定義長 delta(H): 先頭4ビット(位置0-3)なので3
N = 200         # 個体数
PC = 0.7        # 交叉率
PM = 0.01       # 突然変異率
GENERATIONS = 30
TRIALS = 200    # 期待値評価のための試行回数

def matches_schema(pop):
    """スキーマ H = 1111************** (先頭4ビットが1) にマッチするか"""
    return np.all(pop[:, :O_H] == 1, axis=1)

def run_trial(seed):
    rng = np.random.default_rng(seed)
    pop = rng.integers(0, 2, size=(N, L))

    m_actual = []
    rhs_bound = []

    for t in range(GENERATIONS):
        fitness = pop.sum(axis=1).astype(float)
        f_bar = fitness.mean()

        match = matches_schema(pop)
        m_t = match.sum()
        m_actual.append(m_t)
        f_H = fitness[match].mean() if m_t > 0 else 0.0

        selection_term = (f_H / f_bar) if f_bar > 0 else 0.0
        disruption_term = max(1 - PC * DELTA_H / (L - 1) - O_H * PM, 0.0)
        rhs_bound.append(m_t * selection_term * disruption_term)

        # --- 世代交代: ルーレット選択 -> 一点交叉 -> 突然変異 ---
        probs = fitness / fitness.sum() if fitness.sum() > 0 else np.ones(N) / N
        parent_idx = rng.choice(N, size=N, p=probs)
        parents = pop[parent_idx]

        children = parents.copy()
        for i in range(0, N - 1, 2):
            if rng.random() < PC:
                point = rng.integers(1, L)
                children[i, point:], children[i + 1, point:] = (
                    parents[i + 1, point:].copy(),
                    parents[i, point:].copy(),
                )

        mutate_mask = rng.random((N, L)) < PM
        children = np.where(mutate_mask, 1 - children, children)
        pop = children

    match = matches_schema(pop)
    m_actual.append(match.sum())
    return np.array(m_actual), np.array(rhs_bound)

all_m, all_rhs = [], []
for trial in range(TRIALS):
    m_actual, rhs_bound = run_trial(seed=trial)
    all_m.append(m_actual)
    all_rhs.append(rhs_bound)

all_m, all_rhs = np.array(all_m), np.array(all_rhs)
mean_m, mean_rhs = all_m.mean(axis=0), all_rhs.mean(axis=0)

print(f"m(H,0) 平均 = {mean_m[0]:.3f} (理論値 N*0.5^{O_H} = {N*0.5**O_H:.3f})")
print(f"m(H,{GENERATIONS}) 平均 = {mean_m[-1]:.3f}")
print(f"下界を下回った世代数(平均ベース): {np.sum(mean_m[1:] < mean_rhs)}/{GENERATIONS}")
violations = np.sum(all_m[:, 1:] < all_rhs)
print(f"個別試行での下界違反率: {violations}/{all_m[:,1:].size} = {violations/all_m[:,1:].size*100:.2f}%")

import numpy as np
import matplotlib.pyplot as plt

def rastrigin(x):
    """Rastrigin関数（バッチ評価対応: 定数項は x.shape[-1]（次元数）で計算する）"""
    return 10 * x.shape[-1] + np.sum(x**2 - 10 * np.cos(2 * np.pi * x), axis=-1)

class GeneticAlgorithm:
    def __init__(self, dim, pop_size=100, bounds=(-5.12, 5.12),
                 crossover_rate=0.8, mutation_rate=0.1, mutation_sigma=0.5,
                 tournament_size=3):
        self.dim = dim
        self.pop_size = pop_size
        self.bounds = bounds
        self.crossover_rate = crossover_rate
        self.mutation_rate = mutation_rate
        self.mutation_sigma = mutation_sigma
        self.tournament_size = tournament_size

    def initialize(self):
        """ランダムな初期集団を生成"""
        low, high = self.bounds
        return np.random.uniform(low, high, (self.pop_size, self.dim))

    def tournament_selection(self, population, fitness):
        """トーナメント選択"""
        indices = np.random.randint(0, self.pop_size, size=self.tournament_size)
        best = indices[np.argmin(fitness[indices])]
        return population[best]

    def blx_alpha_crossover(self, parent1, parent2, alpha=0.5):
        """BLX-α交叉"""
        low = np.minimum(parent1, parent2) - alpha * np.abs(parent1 - parent2)
        high = np.maximum(parent1, parent2) + alpha * np.abs(parent1 - parent2)
        child = np.random.uniform(low, high)
        return np.clip(child, *self.bounds)

    def gaussian_mutation(self, individual):
        """ガウス突然変異"""
        mask = np.random.random(self.dim) < self.mutation_rate
        noise = np.random.normal(0, self.mutation_sigma, self.dim)
        individual[mask] += noise[mask]
        return np.clip(individual, *self.bounds)

    def run(self, objective, max_generations=200):
        """GAの実行"""
        population = self.initialize()
        best_history = []

        for gen in range(max_generations):
            fitness = objective(population)
            best_idx = np.argmin(fitness)
            best_history.append(fitness[best_idx])

            # 次世代の生成
            new_population = [population[best_idx].copy()]  # エリート保存
            while len(new_population) < self.pop_size:
                p1 = self.tournament_selection(population, fitness)
                p2 = self.tournament_selection(population, fitness)
                if np.random.random() < self.crossover_rate:
                    child = self.blx_alpha_crossover(p1, p2)
                else:
                    child = p1.copy()
                child = self.gaussian_mutation(child)
                new_population.append(child)

            population = np.array(new_population[:self.pop_size])

        fitness = objective(population)
        best_idx = np.argmin(fitness)
        return population[best_idx], fitness[best_idx], best_history

# --- 実行 ---
np.random.seed(42)
ga = GeneticAlgorithm(dim=10, pop_size=200)
best_solution, best_fitness, history = ga.run(rastrigin, max_generations=300)

print(f"最良解の適応度: {best_fitness:.6f}")
print(f"最良解: {best_solution[:3]}... (最初の3次元)")

# --- 収束曲線のプロット ---
plt.figure(figsize=(10, 5))
plt.plot(history, color="#2a78d6", linewidth=2)
plt.xlabel('Generation')
plt.ylabel('Best Fitness')
plt.title('GA Convergence on Rastrigin Function (10D)')
plt.yscale('log')
plt.grid(True, alpha=0.25)
plt.gca().spines[["top", "right"]].set_visible(False)
plt.tight_layout()
plt.savefig("ga_convergence.png", dpi=150)
plt.show()

import numpy as np

N = 200
GENERATIONS = 40
TRIALS = 100
BOUNDS = (-5.12, 5.12)

def rastrigin_1d(x):
    return 10 + x**2 - 10 * np.cos(2 * np.pi * x)

def roulette_select(pop, fitness, rng):
    """ルーレット選択(最小化問題なので f' = fmax - f で適応度変換)"""
    f_prime = fitness.max() - fitness
    total = f_prime.sum()
    probs = f_prime / total if total > 0 else np.ones(N) / N
    idx = rng.choice(N, size=N, p=probs)
    return pop[idx]

def tournament_select(pop, fitness, rng, k):
    """トーナメント選択(トーナメントサイズk)"""
    idx = rng.integers(0, N, size=(N, k))
    best = idx[np.arange(N), np.argmin(fitness[idx], axis=1)]
    return pop[best]

def run_trial(method, seed, k=None):
    rng = np.random.default_rng(seed)
    pop = rng.uniform(*BOUNDS, size=N)
    stds = [pop.std()]
    for gen in range(GENERATIONS):
        fitness = rastrigin_1d(pop)
        pop = roulette_select(pop, fitness, rng) if method == "roulette" \
            else tournament_select(pop, fitness, rng, k)
        stds.append(pop.std())
    return np.array(stds)

methods = [("roulette", None), ("tournament", 2), ("tournament", 3),
           ("tournament", 5), ("tournament", 10)]

for method, k in methods:
    all_stds = np.array([run_trial(method, seed=t, k=k) for t in range(TRIALS)])
    mean_stds = all_stds.mean(axis=0)
    half = mean_stds[0] / 2
    gen_half = next((t + (mean_stds[t] - half) / (mean_stds[t] - mean_stds[t + 1])
                      for t in range(len(mean_stds) - 1)
                      if mean_stds[t] >= half > mean_stds[t + 1]), None)
    gen_1pct = next((t for t, s in enumerate(mean_stds) if s < mean_stds[0] * 0.01), None)
    label = f"{method}(k={k})" if k else method
    print(f"{label:20s} 半減期(世代)={gen_half}  1%到達世代={gen_1pct}")

import numpy as np

def rastrigin(x):
    """Rastrigin関数(バッチ評価対応: 定数項は x.shape[-1](次元数)で計算する)"""
    return 10 * x.shape[-1] + np.sum(x**2 - 10 * np.cos(2 * np.pi * x), axis=-1)

class GeneticAlgorithm:
    def __init__(self, dim, pop_size=100, bounds=(-5.12, 5.12),
                 crossover_rate=0.8, mutation_rate=0.1, mutation_sigma=0.5,
                 tournament_size=3, rng=None):
        self.dim = dim
        self.pop_size = pop_size
        self.bounds = bounds
        self.crossover_rate = crossover_rate
        self.mutation_rate = mutation_rate
        self.mutation_sigma = mutation_sigma
        self.tournament_size = tournament_size
        self.rng = rng if rng is not None else np.random.default_rng()

    def initialize(self):
        low, high = self.bounds
        return self.rng.uniform(low, high, (self.pop_size, self.dim))

    def tournament_selection(self, population, fitness):
        indices = self.rng.integers(0, self.pop_size, size=self.tournament_size)
        best = indices[np.argmin(fitness[indices])]
        return population[best]

    def blx_alpha_crossover(self, parent1, parent2, alpha=0.5):
        low = np.minimum(parent1, parent2) - alpha * np.abs(parent1 - parent2)
        high = np.maximum(parent1, parent2) + alpha * np.abs(parent1 - parent2)
        child = self.rng.uniform(low, high)
        return np.clip(child, *self.bounds)

    def gaussian_mutation(self, individual):
        mask = self.rng.random(self.dim) < self.mutation_rate
        noise = self.rng.normal(0, self.mutation_sigma, self.dim)
        individual[mask] += noise[mask]
        return np.clip(individual, *self.bounds)

    def run(self, objective, max_generations=150):
        population = self.initialize()
        best_history = []
        diversity_history = []

        for gen in range(max_generations):
            fitness = objective(population)
            best_idx = np.argmin(fitness)
            best_history.append(fitness[best_idx])
            diversity_history.append(population.std())

            new_population = [population[best_idx].copy()]  # エリート保存
            while len(new_population) < self.pop_size:
                p1 = self.tournament_selection(population, fitness)
                p2 = self.tournament_selection(population, fitness)
                if self.rng.random() < self.crossover_rate:
                    child = self.blx_alpha_crossover(p1, p2)
                else:
                    child = p1.copy()
                child = self.gaussian_mutation(child)
                new_population.append(child)

            population = np.array(new_population[:self.pop_size])

        fitness = objective(population)
        best_idx = np.argmin(fitness)
        return population[best_idx], fitness[best_idx], best_history, diversity_history

mutation_rates = [0.0, 0.01, 0.05, 0.1, 0.2, 0.4, 0.6, 0.8, 1.0]
DIM, POP, GENS, SEEDS = 5, 100, 150, 30

for mr in mutation_rates:
    finals, diversities = [], []
    for seed in range(SEEDS):
        rng = np.random.default_rng(seed * 1000 + int(mr * 100))
        ga = GeneticAlgorithm(dim=DIM, pop_size=POP, mutation_rate=mr, rng=rng)
        _, best_fitness, history, div_history = ga.run(rastrigin, max_generations=GENS)
        finals.append(best_fitness)
        diversities.append(div_history[-1])
    finals = np.array(finals)
    print(f"mutation_rate={mr:.2f}  最終最良適応度(平均)={finals.mean():.5f}  "
          f"(std={finals.std():.5f})  最終多様性(平均)={np.mean(diversities):.5f}")