引言
捣蛋猪（Bad Piggies）是一款由Rovio开发的物理建造游戏：玩家利用木板、轮子、发动机、气球等零件组装载具，帮助小猪穿越地形障碍并收集星星。设计一辆稳定且高效的载具本质上是一个复杂的组合优化问题——零件类型、连接位置和角度共同决定了载具的通过能力。本文将用Java实现基于免疫算法（Immune Algorithm, IA）的车辆结构自动进化系统，讲解抗体编码、亲和力计算与克隆选择机制，通过模拟生物免疫系统的学习过程自动搜索最优车辆设计。
核心算法设计
1. 抗体编码（车辆结构表示）
将载具设计编码为抗体（Antibody），采用基于邻接表的图结构表示：
– 每个节点代表一个零件（轮子/发动机/木板/气球/火箭等）
– 节点属性：零件类型、坐标(x,y)、旋转角度θ
– 边表示零件之间的物理连接关系
– 抗体长度 = 零件数量（5~15个零件为合理范围）
为简化实现，采用固定最大零件数的实数向量编码：
X = [type₁, x₁, y₁, θ₁, type₂, x₂, y₂, θ₂, …, typeₙ, xₙ, yₙ, θₙ]
2. 亲和力函数（适应度评估）
亲和力衡量抗体（车辆）解决问题的优劣：
Affinity(X) = w₁×Distance(X) + w₂×Stability(X) + w₃×Stars(X) – w₄×PartsCost(X)
- Distance：载具从起点前进的水平距离（越远越好）
- Stability：模拟运行中倾覆次数的倒数（越稳越好）
- Stars：收集到的星星数量
- PartsCost：使用零件的总成本（越少越好）
3. 免疫算法核心机制
克隆选择：对高亲和力抗体进行克隆扩增，克隆数量与亲和力成正比。
超变异：克隆体经历高频变异（变异率与亲和力成反比），低亲和力抗体允许更大探索步长。
免疫网络抑制：若两个抗体相似度过高（欧氏距离小于阈值），低亲和力者被抑制（淘汰），维持种群多样性。
新生成：每代随机生成少量全新抗体，补充种群多样性。
Java实现
import java.util.*;
/**
* 捣蛋猪车辆结构进化系统
* 核心算法：免疫算法（Immune Algorithm）
*/
public class BadPiggiesOptimizer {
// ==================== 零件类型与车辆模型 ====================
enum PartType {
WOOD_BOX(1.0, 0.5), // 木箱：基础结构，中等重量
WHEEL(0.3, 0.8), // 轮子：低重量，提供移动能力
ENGINE(2.0, 0.0), // 发动机：重，提供动力
BALLOON(0.1, -0.5), // 气球：极轻，提供升力
ROCKET(1.5, 0.0), // 火箭：一次性推进
SPRING(0.5, 0.3), // 弹簧：减震，提升稳定性
TNT(0.8, 0.0); // TNT：爆炸推进
final double weight; // 重量
final double lift; // 升力（负值表示下压力）
PartType(double weight, double lift) {
this.weight = weight;
this.lift = lift;
}
}
static final PartType[] PART_TYPES = PartType.values();
static final int MAX_PARTS = 10; // 最大零件数
static final int GENE_SIZE = 4; // 每个零件的编码维度：type, x, y, angle
/** 车辆抗体：实数向量编码 */
static class Antibody {
double[] genes; // [type1, x1, y1, ang1, type2, x2, y2, ang2, ...]
double affinity;
int cloneCount;
Antibody() {
this.genes = new double[MAX_PARTS * GENE_SIZE];
}
/** 将基因解码为零件列表 */
List<Part> decode() {
List<Part> parts = new ArrayList<>();
for (int i = 0; i < MAX_PARTS; i++) {
int idx = i * GENE_SIZE;
int typeIdx = (int) Math.abs(genes[idx]) % PART_TYPES.length;
double x = genes[idx + 1];
double y = genes[idx + 2];
double angle = genes[idx + 3];
// 只保留在合理范围内的零件
if (x >= 0 && x <= 20 && y >= 0 && y <= 10) {
parts.add(new Part(PART_TYPES[typeIdx], x, y, angle));
}
}
return parts;
}
@Override
public String toString() {
List<Part> parts = decode();
return "Antibody{零件数=" + parts.size() + ", 亲和力=" + String.format("%.2f", affinity) + "}";
}
}
static class Part {
PartType type;
double x, y, angle;
Part(PartType type, double x, double y, double angle) {
this.type = type; this.x = x; this.y = y; this.angle = angle;
}
}
// ==================== 物理模拟与适应度评估 ====================
static class PhysicsSimulator {
double gravity = 9.8;
double groundY = 0.0;
/**
* 简化物理模拟：计算车辆在给定地形上的行驶表现
* @param parts 车辆零件列表
* @param terrain 地形高度数组
* @return 模拟结果 [距离, 稳定性, 星星数]
*/
double[] simulate(List<Part> parts, double[] terrain) {
if (parts.isEmpty()) return new double[]{0, 0, 0};
double totalWeight = parts.stream().mapToDouble(p -> p.type.weight).sum();
double totalLift = parts.stream().mapToDouble(p -> p.type.lift).sum();
double enginePower = parts.stream()
.filter(p -> p.type == PartType.ENGINE).count() * 5.0;
double wheelCount = parts.stream()
.filter(p -> p.type == PartType.WHEEL).count();
double springCount = parts.stream()
.filter(p -> p.type == PartType.SPRING).count();
double rocketCount = parts.stream()
.filter(p -> p.type == PartType.ROCKET).count();
double tntCount = parts.stream()
.filter(p -> p.type == PartType.TNT).count();
// 无轮子且无升力/推进 = 无法移动
if (wheelCount == 0 && totalLift <= 0 && enginePower == 0 && rocketCount == 0) {
return new double[]{0, 0, 0};
}
// 简化的运动学模拟
double netForce = enginePower + rocketCount * 15 + tntCount * 10;
double friction = totalWeight * 0.3;
if (wheelCount > 0) friction *= 0.6; // 轮子降低摩擦
double acceleration = Math.max(0, (netForce - friction) / Math.max(totalWeight, 0.1));
// 稳定性：重心越低、弹簧越多越稳
double avgY = parts.stream().mapToDouble(p -> p.y).average().orElse(0);
double stability = 1.0 / (1.0 + avgY) + springCount * 0.2;
stability = Math.min(1.0, stability);
// 行驶距离
double simTime = 5.0; // 模拟5秒
double distance = 0.5 * acceleration * simTime * simTime;
// 气球提供额外空中距离
if (totalLift > 0) {
distance += totalLift * 3.0;
}
// 星星收集（简化：行驶越远收集越多，最多3颗）
int stars = Math.min(3, (int)(distance / 15.0));
return new double[]{distance, stability, stars};
}
}
static class FitnessEvaluator {
PhysicsSimulator simulator = new PhysicsSimulator();
double[] terrain;
FitnessEvaluator(double[] terrain) {
this.terrain = terrain;
}
double evaluate(Antibody ab) {
List<Part> parts = ab.decode();
double[] result = simulator.simulate(parts, terrain);
double distance = result[0];
double stability = result[1];
double stars = result[2];
double cost = parts.size(); // 零件成本
// 综合适应度
return distance * 0.5 + stability * 30 + stars * 20 - cost * 2;
}
}
// ==================== 免疫算法核心 ====================
static class ImmuneAlgorithm {
int popSize;
int maxGen;
double cloneFactor; // 克隆基数
double mutationBase; // 基础变异率
double suppressionThreshold; // 相似度抑制阈值
Random rand = new Random(123);
FitnessEvaluator evaluator;
ImmuneAlgorithm(int popSize, int maxGen, double cloneFactor,
double mutationBase, double suppressionThreshold,
FitnessEvaluator evaluator) {
this.popSize = popSize;
this.maxGen = maxGen;
this.cloneFactor = cloneFactor;
this.mutationBase = mutationBase;
this.suppressionThreshold = suppressionThreshold;
this.evaluator = evaluator;
}
/** 随机初始化抗体 */
Antibody randomAntibody() {
Antibody ab = new Antibody();
for (int i = 0; i < MAX_PARTS; i++) {
int idx = i * GENE_SIZE;
ab.genes[idx] = rand.nextInt(PART_TYPES.length); // type
ab.genes[idx + 1] = rand.nextDouble() * 20; // x
ab.genes[idx + 2] = rand.nextDouble() * 5; // y (较低重心更稳)
ab.genes[idx + 3] = rand.nextDouble() * 360; // angle
}
ab.affinity = evaluator.evaluate(ab);
return ab;
}
/** 计算两个抗体的欧氏距离 */
double distance(Antibody a, Antibody b) {
double sum = 0;
for (int i = 0; i < a.genes.length; i++) {
double diff = a.genes[i] - b.genes[i];
sum += diff * diff;
}
return Math.sqrt(sum);
}
/** 克隆选择：高亲和力抗体产生更多克隆 */
List<Antibody> cloneAndMutate(List<Antibody> population) {
List<Antibody> clones = new ArrayList<>();
// 按亲和力排序
population.sort((a, b) -> Double.compare(b.affinity, a.affinity));
for (int i = 0; i < population.size(); i++) {
Antibody parent = population.get(i);
// 克隆数量与亲和力成正比，与排名成反比
int nClones = (int) Math.max(1, cloneFactor * parent.affinity / (i + 1));
parent.cloneCount = nClones;
for (int c = 0; c < nClones; c++) {
Antibody clone = new Antibody();
System.arraycopy(parent.genes, 0, clone.genes, 0, parent.genes.length);
// 超变异：亲和力越低（排名越后），变异率越高
double mutateRate = mutationBase / (1 + parent.affinity * 0.1);
for (int g = 0; g < clone.genes.length; g++) {
if (rand.nextDouble() < mutateRate) {
// 高斯变异
clone.genes[g] += rand.nextGaussian() * 2.0;
// type索引取整并归一化
if (g % GENE_SIZE == 0) {
clone.genes[g] = Math.abs(clone.genes[g]) % PART_TYPES.length;
}
}
}
clone.affinity = evaluator.evaluate(clone);
clones.add(clone);
}
}
return clones;
}
/** 免疫网络抑制：消除相似度过高的低亲和力抗体 */
List<Antibody> suppress(List<Antibody> population) {
List<Antibody> survivors = new ArrayList<>();
population.sort((a, b) -> Double.compare(b.affinity, a.affinity));
for (Antibody ab : population) {
boolean tooSimilar = false;
for (Antibody kept : survivors) {
if (distance(ab, kept) < suppressionThreshold) {
// 相似度过高，保留亲和力更高的
tooSimilar = true;
break;
}
}
if (!tooSimilar) {
survivors.add(ab);
}
}
return survivors;
}
/** 执行免疫优化 */
Antibody optimize() {
// 初始化种群
List<Antibody> pop = new ArrayList<>();
for (int i = 0; i < popSize; i++) {
pop.add(randomAntibody());
}
Antibody best = null;
for (int g = 0; g < maxGen; g++) {
// 克隆与超变异
List<Antibody> clones = cloneAndMutate(pop);
// 合并原种群与克隆体
List<Antibody> combined = new ArrayList<>(pop);
combined.addAll(clones);
// 免疫抑制
combined = suppress(combined);
// 选择 top popSize
combined.sort((a, b) -> Double.compare(b.affinity, a.affinity));
pop = combined.subList(0, Math.min(popSize, combined.size()));
// 补充新生抗体（维持多样性）
while (pop.size() < popSize) {
pop.add(randomAntibody());
}
// 更新最优
Antibody genBest = pop.get(0);
if (best == null || genBest.affinity > best.affinity) {
best = new Antibody();
System.arraycopy(genBest.genes, 0, best.genes, 0, genBest.genes.length);
best.affinity = genBest.affinity;
}
if ((g + 1) % 20 == 0) {
System.out.println(" 第" + (g + 1) + "代, 最优亲和力=" + String.format("%.2f", best.affinity));
}
}
return best;
}
}
// ==================== 主程序与测试 ====================
public static void main(String[] args) {
System.out.println("===== 捣蛋猪车辆结构进化系统 =====\n");
System.out.println("核心算法：免疫算法（Immune Algorithm）");
System.out.println("优化目标：最大化行驶距离、稳定性与星星收集\n");
// 定义一个简单起伏地形
double[] terrain = new double[100];
for (int i = 0; i < 100; i++) {
terrain[i] = Math.sin(i * 0.2) * 0.5 + Math.cos(i * 0.5) * 0.3;
}
FitnessEvaluator evaluator = new FitnessEvaluator(terrain);
// 免疫算法参数
int popSize = 40;
int maxGen = 150;
double cloneFactor = 3.0;
double mutationBase = 0.3;
double suppressionThreshold = 5.0;
ImmuneAlgorithm ia = new ImmuneAlgorithm(
popSize, maxGen, cloneFactor, mutationBase, suppressionThreshold, evaluator);
long start = System.currentTimeMillis();
Antibody best = ia.optimize();
long elapsed = System.currentTimeMillis() - start;
System.out.println("\n===== 最优车辆设计 =====");
List<Part> bestParts = best.decode();
System.out.println("最优抗体: " + best);
System.out.println("零件清单:");
for (int i = 0; i < bestParts.size(); i++) {
Part p = bestParts.get(i);
System.out.println(" [" + i + "] " + p.type +
" 位置=(" + String.format("%.1f", p.x) + "," + String.format("%.1f", p.y) + ")" +
" 角度=" + String.format("%.0f", p.angle) + "°");
}
double[] simResult = ia.evaluator.simulator.simulate(bestParts, terrain);
System.out.println("\n模拟结果:");
System.out.println(" 行驶距离: " + String.format("%.2f", simResult[0]) + "m");
System.out.println(" 稳定性评分: " + String.format("%.2f", simResult[1]));
System.out.println(" 收集星星: " + (int)simResult[2] + "/3");
System.out.println(" 进化耗时: " + elapsed + "ms");
}
}
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 抗体解码 | O(P) | O(P) | P为最大零件数 |
| 物理模拟 | O(P) | O(1) | 简化模拟为线性计算 |
| 适应度评估 | O(P) | O(1) | 调用模拟器 |
| 克隆操作 | O(N×C×G) | O(N×C×G) | N种群大小，C平均克隆数，G基因长度 |
| 变异操作 | O(N×C×G) | O(G) | 逐基因判断变异 |
| 免疫抑制 | O(M²×G) | O(M) | M为合并后种群数，两两比较 |
| 整体优化 | O(Gen×N²×P) | O(N×P) | Gen为迭代代数 |
算法扩展思路
- 物理引擎集成：将简化模拟替换为Box2D等真实物理引擎，在精确碰撞检测和刚体动力学中评估车辆性能。
- 图神经网络编码：将车辆结构表示为图，使用GNN编码结构特征，提升相似度计算的语义准确性。
- 多目标免疫算法：将距离、稳定性、成本作为独立的帕累托目标，使用MOIA算法求解散布均匀的解集。
总结
本文将捣蛋猪的载具设计问题建模为组合优化问题，通过免疫算法的克隆选择、超变异和免疫网络抑制机制，自动进化出高性能的车辆结构。免疫算法通过抗体间的相似度抑制维持种群多样性，避免早熟收敛，是求解结构优化和组合设计问题的有效仿生智能方法。
