Java中的多群优化算法 | Baeldung中文网

1. 引言

本文将探讨多群优化算法（Multi-Swarm Optimization）。与同类算法类似，其核心目标是通过最大化或最小化特定函数（称为适应度函数）来寻找问题的最优解。

让我们从理论基础开始讲起。

2. 多群优化算法的工作原理

多群算法是群算法（Swarm Algorithm）的一种变体。顾名思义，群算法通过模拟一群对象在解空间中的移动来解决问题。在多群版本中，我们使用多个群而非单个群。

群的基本单元称为粒子（Particle）。粒子由以下要素定义：

当前位置（即问题的一个可能解）
速度（用于计算下一个位置）

粒子的速度会持续变化，倾向于朝向所有群中所有粒子发现的最优位置移动，同时引入一定随机性以扩大探索范围。这最终使大多数粒子汇聚到适应度函数的局部极值点（最小值或最大值，取决于优化目标）。

⚠️ 需要注意：虽然算法总能找到局部最优解，但不保证是全局最优解，因为无法确保完全探索整个解空间。因此多群算法属于元启发式算法（metaheuristic）——其找到的解是较优解，但不一定是绝对最优解。

3. 算法实现

理解了多群算法的原理后，我们来看具体实现。本文将解决一个实际问题（源自StackExchange）：

在英雄联盟中，玩家防御物理伤害的有效生命值公式为：E = H(100 + A)/100，其中H是生命值，A是护甲。

生命值单价2.5金币，护甲单价18金币。现有3600金币，如何分配购买生命值和护甲，使有效生命值E最大化？

3.1 粒子实现

首先建模基础组件——粒子。粒子状态包含：

当前位置（生命值和护甲的组合解）
速度向量
适应度评分
历史最佳位置及评分（用于速度更新）

public class Particle {
    private long[] position;
    private long[] speed;
    private double fitness;
    private long[] bestPosition;    
    private double bestFitness = Double.NEGATIVE_INFINITY;

    // 构造函数和其他方法
}

✅ 使用long数组而非int：因为问题要求整数解（不能购买部分生命值/护甲），且计算过程可能超出int范围。

3.2 群实现

群（Swarm）是粒子的集合。需要维护：

粒子数组
群历史最佳位置及评分
粒子初始化逻辑（随机位置和速度）

public class Swarm {
    private Particle[] particles;
    private long[] bestPosition;
    private double bestFitness = Double.NEGATIVE_INFINITY;
    
    public Swarm(int numParticles) {
        particles = new Particle[numParticles];
        for (int i = 0; i < numParticles; i++) {
            long[] initialParticlePosition = { 
              random.nextInt(Constants.PARTICLE_UPPER_BOUND),
              random.nextInt(Constants.PARTICLE_UPPER_BOUND) 
            };
            long[] initialParticleSpeed = { 
              random.nextInt(Constants.PARTICLE_UPPER_BOUND),
              random.nextInt(Constants.PARTICLE_UPPER_BOUND) 
            };
            particles[i] = new Particle(
              initialParticlePosition, initialParticleSpeed);
        }
    }

    // 省略其他方法
}

💡 随机初始化边界：通过PARTICLE_UPPER_BOUND限制解空间范围，减少计算量。

3.3 多群实现

多群（Multiswarm）是群的集合，需维护：

群数组
全局最佳位置及评分
适应度函数引用

public class Multiswarm {
    private Swarm[] swarms;
    private long[] bestPosition;
    private double bestFitness = Double.NEGATIVE_INFINITY;
    private FitnessFunction fitnessFunction;

    public Multiswarm(
      int numSwarms, int particlesPerSwarm, FitnessFunction fitnessFunction) {
        this.fitnessFunction = fitnessFunction;
        this.swarms = new Swarm[numSwarms];
        for (int i = 0; i < numSwarms; i++) {
            swarms[i] = new Swarm(particlesPerSwarm);
        }
    }

    // 省略其他方法
}

3.4 适应度函数

为解耦算法与具体问题，定义适应度函数接口：

public interface FitnessFunction {
    public double getFitness(long[] particlePosition);
}

针对英雄联盟问题的实现需满足约束：

解必须为正整数
总花费≤3600金币

public class LolFitnessFunction implements FitnessFunction {

    @Override
    public double getFitness(long[] particlePosition) {
        long health = particlePosition[0];
        long armor = particlePosition[1];

        // 处理负值解（无效解）
        if (health < 0 && armor < 0) {
            return -(health * armor);
        } else if (health < 0) {
            return health;
        } else if (armor < 0) {
            return armor;
        }

        // 检查预算约束
        double cost = (health * 2.5) + (armor * 18);
        if (cost > 3600) {
            return 3600 - cost; // 返回超支金额的负数
        } else {
            // 计算有效生命值（目标函数）
            long fitness = (health * (100 + armor)) / 100;
            return fitness;
        }
    }
}

❌ 无效解处理：返回负值表示偏离约束的程度，算法会自动规避这些区域。

3.5 主循环

主程序迭代所有粒子，执行：

计算适应度
更新粒子/群/多群历史最优
更新粒子位置
更新粒子速度

public void mainLoop() {
    for (Swarm swarm : swarms) {
        for (Particle particle : swarm.getParticles()) {
            long[] particleOldPosition = particle.getPosition().clone();
            particle.setFitness(fitnessFunction.getFitness(particleOldPosition));
       
            // 更新历史最优
            if (particle.getFitness() > particle.getBestFitness()) {
                particle.setBestFitness(particle.getFitness());                
                particle.setBestPosition(particleOldPosition);
                if (particle.getFitness() > swarm.getBestFitness()) {                        
                    swarm.setBestFitness(particle.getFitness());
                    swarm.setBestPosition(particleOldPosition);
                    if (swarm.getBestFitness() > bestFitness) {
                        bestFitness = swarm.getBestFitness();
                        bestPosition = swarm.getBestPosition().clone();
                    }
                }
            }

            // 更新位置和速度
            long[] position = particle.getPosition();
            long[] speed = particle.getSpeed();
            position[0] += speed[0];
            position[1] += speed[1];
            speed[0] = getNewParticleSpeedForIndex(particle, swarm, 0);
            speed[1] = getNewParticleSpeedForIndex(particle, swarm, 1);
        }
    }
}

3.6 速度更新

速度更新是算法核心，需平衡以下因素：

粒子自身历史最优（认知权重）
群历史最优（社会权重）
全局历史最优（全局权重）
惯性因子（防止过早收敛）

private int getNewParticleSpeedForIndex(
  Particle particle, Swarm swarm, int index) {
 
    return (int) ((Constants.INERTIA_FACTOR * particle.getSpeed()[index])
      + (randomizePercentage(Constants.COGNITIVE_WEIGHT)
      * (particle.getBestPosition()[index] - particle.getPosition()[index]))
      + (randomizePercentage(Constants.SOCIAL_WEIGHT) 
      * (swarm.getBestPosition()[index] - particle.getPosition()[index]))
      + (randomizePercentage(Constants.GLOBAL_WEIGHT) 
      * (bestPosition[index] - particle.getPosition()[index])));
}

📌 推荐参数值：

惯性因子：0.729
认知权重：1.49445
社会权重：1.49445
全局权重：0.3645

4. 总结

本文介绍了多群优化算法的理论与实现，并展示了如何设计特定问题的适应度函数。关键点包括：

✅ 算法优势：

通过多群并行探索提升全局搜索能力
适合处理高维度、非线性优化问题

⚠️ 注意事项：

属于元启发式算法，不保证全局最优
参数调优对性能影响显著

如需深入学习，推荐参考：

完整代码示例可在GitHub项目获取。

Persistence

REST

Security