计算智能

"""感知机学习算法：学习 AND 逻辑"""
import numpy as np

class Perceptron:
    def __init__(self, n_features, lr=1.0, epochs=20, seed=0):
        rng = np.random.default_rng(seed)
        self.w = rng.normal(0, 0.1, n_features)
        self.b = 0.0
        self.lr = lr
        self.epochs = epochs

    def forward(self, X):
        z = X @ self.w + self.b
        return np.where(z >= 0, 1, 0)         # 阶跃函数

    def fit(self, X, y):
        for epoch in range(self.epochs):
            errors = 0
            for xi, yi in zip(X, y):
                yi_hat = 1 if xi @ self.w + self.b >= 0 else 0
                delta = yi - yi_hat
                if delta != 0:                 # 仅当预测错误时更新
                    self.w += self.lr * delta * xi
                    self.b += self.lr * delta
                    errors += 1
            if errors == 0:
                print(f"第 {epoch+1} 轮全部正确，收敛！")
                break
        return self

if __name__ == "__main__":
    # AND 真值表（线性可分）
    X = np.array([[0, 0], [0, 1], [1, 0], [1, 1]])
    y = np.array([0, 0, 0, 1])

    model = Perceptron(2).fit(X, y)
    print(f"学到的权重 w = {model.w.round(2)}，偏置 b = {model.b:.2f}")
    print("预测：", model.forward(X).tolist())

    # XOR 真值表（线性不可分）——感知机无法收敛
    y_xor = np.array([0, 1, 1, 0])
    p2 = Perceptron(2, lr=0.5, epochs=20)
    p2.fit(X, y_xor)
    print("XOR 上感知机 20 轮后的预测：", p2.forward(X).tolist(),
          "（无法同时分对——需要多层网络引入非线性）")

"""两层全连接 BP 神经网络（NumPy 手写），在 XOR 上验证"""
import numpy as np

def sigmoid(z):
    return 1.0 / (1.0 + np.exp(-z))

class TwoLayerNet:
    def __init__(self, n_in, n_hidden, n_out, seed=1):
        rng = np.random.default_rng(seed)
        # Xavier 初始化，使各层信号方差稳定
        self.W1 = rng.normal(0, np.sqrt(1 / n_in), (n_in, n_hidden))
        self.b1 = np.zeros(n_hidden)
        self.W2 = rng.normal(0, np.sqrt(1 / n_hidden), (n_hidden, n_out))
        self.b2 = np.zeros(n_out)

    def forward(self, X):
        self.z1 = X @ self.W1 + self.b1
        self.a1 = sigmoid(self.z1)
        self.z2 = self.a1 @ self.W2 + self.b2
        self.a2 = sigmoid(self.z2)          # 输出概率
        return self.a2

    def backward(self, X, y, lr):
        n = len(X)
        # 输出层误差项（sigmoid + MSE 的梯度形式）
        delta2 = (self.a2 - y) * self.a2 * (1 - self.a2)
        dW2 = self.a1.T @ delta2 / n
        db2 = delta2.mean(axis=0)
        # 误差反传到隐层
        delta1 = (delta2 @ self.W2.T) * self.a1 * (1 - self.a1)
        dW1 = X.T @ delta1 / n
        db1 = delta1.mean(axis=0)
        # 梯度下降
        self.W2 -= lr * dW2
        self.b2 -= lr * db2
        self.W1 -= lr * dW1
        self.b1 -= lr * db1

    def fit(self, X, y, epochs=20000, lr=0.8):
        y = y.reshape(-1, 1)
        for ep in range(epochs):
            pred = self.forward(X)
            loss = ((pred - y) ** 2).mean()
            self.backward(X, y, lr)
            if ep % 4000 == 0 or ep == epochs - 1:
                print(f"epoch {ep:5d}  MSE = {loss:.6f}")
        return self

if __name__ == "__main__":
    X = np.array([[0, 0], [0, 1], [1, 0], [1, 1]], dtype=float)
    y = np.array([0, 1, 1, 0], dtype=float)     # XOR

    net = TwoLayerNet(2, 4, 1).fit(X, y)
    prob = net.forward(X).ravel()
    print("\n最终输出概率：", np.round(prob, 3).tolist())
    print("判别结果：", (prob > 0.5).astype(int).tolist(), "（期望 [0, 1, 1, 0]）")

"""遗传算法：二进制编码求 f(x) = x^2 在 [0,31] 上的最大值"""
import random

N_BITS = 5                 # 5 位二进制表示 0~31
POP_SIZE = 8
N_GEN = 30
P_CROSS = 0.9
P_MUT = 0.05

def decode(chrom):
    return int("".join(map(str, chrom)), 2)

def fitness(chrom):
    return decode(chrom) ** 2          # 目标函数即适应度

def select(pop, fits):
    """轮盘赌选择：适应度占比即被抽中概率。"""
    total = sum(fits)
    r = random.uniform(0, total)
    acc = 0
    for ind, f in zip(pop, fits):
        acc += f
        if r <= acc:
            return ind[:]
    return pop[-1][:]

def crossover(p1, p2):
    if random.random() < P_CROSS:
        pt = random.randint(1, N_BITS - 1)          # 单点交叉
        p1[pt:], p2[pt:] = p2[pt:], p1[pt:]
    return p1, p2

def mutate(chrom):
    for i in range(N_BITS):
        if random.random() < P_MUT:
            chrom[i] = 1 - chrom[i]                 # 位翻转
    return chrom

def main():
    random.seed(7)
    pop = [[random.randint(0, 1) for _ in range(N_BITS)] for _ in range(POP_SIZE)]
    for gen in range(N_GEN):
        fits = [fitness(c) for c in pop]
        best = max(pop, key=fitness)
        if gen % 5 == 0 or gen == N_GEN - 1:
            print(f"第 {gen:2d} 代 | 最优 x={decode(best):2d} | f={fitness(best):4d} | "
                  f"种群均值={sum(fits)/len(fits):7.1f}")
        if decode(best) == 31:
            print(f"第 {gen} 代已找到全局最优 x=31，f=961，提前停止")
            break
        new_pop = []
        while len(new_pop) < POP_SIZE:
            c1, c2 = crossover(select(pop, fits), select(pop, fits))
            new_pop.append(mutate(c1))
            if len(new_pop) < POP_SIZE:
                new_pop.append(mutate(c2))
        # 精英保留：最优个体直接进入下一代
        new_pop[0] = best[:]
        pop = new_pop

if __name__ == "__main__":
    main()

"""粒子群优化：最小化 Sphere 函数 f(x) = sum(x_i^2)"""
import numpy as np

def sphere(x):
    return np.sum(x ** 2)

class PSO:
    def __init__(self, n_dim, n_particles=30, w=0.7, c1=1.5, c2=1.5,
                 bounds=(-5, 5), seed=42):
        rng = np.random.default_rng(seed)
        self.low, self.high = bounds
        self.X = rng.uniform(self.low, self.high, (n_particles, n_dim))
        self.V = rng.uniform(-1, 1, (n_particles, n_dim))
        self.pbest = self.X.copy()
        self.pbest_val = np.array([sphere(x) for x in self.X])
        g = np.argmin(self.pbest_val)
        self.gbest, self.gbest_val = self.X[g].copy(), self.pbest_val[g]
        self.w, self.c1, self.c2 = w, c1, c2

    def step(self):
        r1, r2 = np.random.rand(len(self.X), 1), np.random.rand(len(self.X), 1)
        self.V = (self.w * self.V
                  + self.c1 * r1 * (self.pbest - self.X)
                  + self.c2 * r2 * (self.gbest - self.X))
        self.X = np.clip(self.X + self.V, self.low, self.high)
        for i, x in enumerate(self.X):
            val = sphere(x)
            if val < self.pbest_val[i]:
                self.pbest_val[i], self.pbest[i] = val, x.copy()
                if val < self.gbest_val:
                    self.gbest_val, self.gbest = val, x.copy()

    def run(self, iters=100):
        for it in range(iters):
            self.step()
            if it % 20 == 0 or it == iters - 1:
                print(f"迭代 {it:3d} | 群体最优 f = {self.gbest_val:.6f}")
        return self.gbest, self.gbest_val

if __name__ == "__main__":
    best_x, best_val = PSO(n_dim=10).run()
    print(f"\n最优解位置（前5维）：{np.round(best_x[:5], 4)}")
    print(f"最优值：{best_val:.2e}（理论最小为 0，位于全 0 向量）")

"""蚁群算法求解 4 城市 TSP"""
import numpy as np

# 对称距离矩阵
DIST = np.array([
    [0,  2,  9, 10],
    [2,  0,  6,  4],
    [9,  6,  0,  8],
    [10, 4,  8,  0],
], dtype=float)

N_CITY = len(DIST)
N_ANT = 10
N_ITER = 80
ALPHA, BETA, RHO = 1.0, 5.0, 0.5
ETA = np.where(DIST > 0, 1.0 / DIST, 0.0)

def tour_length(tour):
    return sum(DIST[tour[i], tour[(i + 1) % N_CITY]] for i in range(N_CITY))

def ant_walk(tau, rng):
    start = rng.integers(N_CITY)
    tour, unvisited = [start], set(range(N_CITY)) - {start}
    cur = start
    while unvisited:
        nxt_list = list(unvisited)
        weights = np.array([
            tau[cur, j] ** ALPHA * ETA[cur, j] ** BETA for j in nxt_list
        ])
        probs = weights / weights.sum()
        cur = nxt_list[rng.choice(len(nxt_list), p=probs)]
        tour.append(cur)
        unvisited.remove(cur)
    return tour

def main():
    rng = np.random.default_rng(1)
    tau = np.ones((N_CITY, N_CITY))
    best_tour, best_len = None, float("inf")

    for it in range(N_ITER):
        tours = [ant_walk(tau, rng) for _ in range(N_ANT)]
        delta = np.zeros_like(tau)
        for tour in tours:
            length = tour_length(tour)
            if length < best_len:
                best_len, best_tour = length, tour[:]
            q = 1.0 / length
            for i in range(N_CITY):
                a, b = tour[i], tour[(i + 1) % N_CITY]
                delta[a, b] += q
                delta[b, a] += q
        tau = (1 - RHO) * tau + delta          # 挥发 + 沉积
        tau[tau < 1e-6] = 1e-6
        if it % 20 == 0 or it == N_ITER - 1:
            print(f"第 {it:3d} 轮 | 当前最优长度 {best_len:.1f}")

    print(f"\n最短环路：{' → '.join(map(str, best_tour))} → {best_tour[0]}")
    print(f"最短长度：{best_len:.1f}")

if __name__ == "__main__":
    main()