Multi-Swarm Optimization Algorithm in Java – Java中的多群优化算法

最后修改: 2018年 3月 3日

中文/混合/英文(键盘快捷键：t)

 

1. Introduction

1.介绍

In this article, we’ll take a look at a Multi-swarm optimization algorithm. Like other algorithms of the same class, its purpose is to find the best solution to a problem by maximizing or minimizing a specific function, called a fitness function.

在这篇文章中，我们将看一下多群优化算法。与其他同类算法一样，它的目的是通过最大化或最小化一个特定的函数（称为健身函数）来找到问题的最佳解决方案。

Let’s start with some theory.

让我们从一些理论开始。

2. How Multi-Swarm Optimization Works

2.多群优化是如何工作的

The Multi-swarm is a variation of the Swarm algorithm. As the name suggests, the Swarm algorithm solves a problem by simulating the movement of a group of objects in the space of possible solutions. In the multi-swarm version, there are multiple swarms instead of just one.

多群算法是Swarm算法的一个变体。顾名思义，蜂群算法通过模拟一群物体在可能的解决方案空间中的运动来解决问题。在多蜂群版本中，有多个蜂群而不是只有一个。

The basic component of a swarm is called a particle. The particle is defined by its actual position, which is also a possible solution to our problem, and its speed, which is used to calculate the next position.

蜂群的基本组成部分被称为粒子。粒子由其实际位置（也是我们问题的可能解决方案）和其速度（用于计算下一个位置）来定义。

The speed of the particle constantly changes, leaning towards the best position found among all the particles in all the swarms with a certain degree of randomness to increase the amount of space covered.

粒子的速度不断变化，倾向于在所有粒子群中发现的最佳位置，具有一定程度的随机性，以增加覆盖的空间量。

This ultimately leads most particles to a finite set of points which are local minima or maxima in the fitness function, depending on whether we’re trying to minimize or maximize it.

这最终将大多数粒子引向一个有限的点集合，这些点是健身函数的局部最小值或最大值，这取决于我们是试图最小化还是最大化。

Although the point found is always a local minimum or maximum of the function, it’s not necessarily a global one since there’s no guarantee that the algorithm has completely explored the space of solutions.

虽然找到的点总是函数的局部最小或最大，但它不一定是全局的，因为不能保证算法已经完全探索了解决方案的空间。

For this reason, the multi-swarm is said to be a metaheuristic – the solutions it finds are among the best, but they may not be the absolute best.

由于这个原因，多群组被说成是一种元启发式算法—它找到的解决方案是最好的，但它们可能不是绝对最好的。。

3. Implementation

3.实施

Now that we know what a multi-swarm is and how it works let’s take a look at how to implement it.

现在我们知道什么是多群，以及它是如何工作的，让我们来看看如何实现它。

For our example, we’ll try to address this real-life optimization problem posted on StackExchange:

对于我们的例子，我们将尝试解决StackExchange上发布的这个现实生活中的优化问题。

In League of Legends, a player’s Effective Health when defending against physical damage is given by E=H(100+A)/100, where H is health and A is armor.

在《英雄联盟》中，玩家在防御物理伤害时的有效生命值由E=H(100+A)/100给出，其中H是健康值，A是护甲。

Health costs 2.5 gold per unit, and Armor costs 18 gold per unit. You have 3600 gold, and you need to optimize the effectiveness E of your health and armor to survive as long as possible against the enemy team’s attacks. How much of each should you buy?

健康值每单位需要2.5金，护甲每单位需要18金。你有3600金，你需要优化你的健康和盔甲的有效性E，以尽可能长时间地抵御敌方队伍的攻击。你应该各买多少？

3.1. Particle

3.1.粒子

We start off by modeling our base construct, a particle. The state of a particle includes its current position, which is a pair of health and armor values that solve the problem, the speed of the particle on both axes and the particle fitness score.

我们首先对我们的基本结构进行建模，即粒子。粒子的状态包括它的当前位置，这是一对解决了问题的健康值和装甲值，粒子在两个轴上的速度和粒子的健身得分。

We’ll also store the best position and fitness score we find since we’ll need them to update the particle speed:

我们还将存储我们找到的最佳位置和健身分数，因为我们需要它们来更新粒子速度。

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

    // constructors and other methods
}

We choose to use long arrays to represent both speed and position because we can deduce from the problem statement that we can’t buy fractions of armor or health, hence the solution must be in the integer domain.

我们选择使用长数组来表示速度和位置，因为我们可以从问题陈述中推断出，我们不能购买零头的盔甲或健康，因此解决方案必须是在整数域中。

We don’t want to use int because that can cause overflow problems during calculations.

我们不希望使用int ，因为这可能会在计算过程中引起溢出问题。

3.2. Swarm

3.2 蜂群

Next up, let’s define a swarm as a collection of particles. Once again we’ll also store the historical best position and score for later computation.

接下来，让我们把蜂群定义为一个粒子的集合。再一次，我们还将存储历史上的最佳位置和分数，以便以后计算。

The swarm will also need to take care of its particles’ initialization by assigning a random initial position and speed to each one.

粒子群还需要通过为每个粒子分配一个随机的初始位置和速度来处理其初始化问题。

We can roughly estimate a boundary for the solution, so we add this limit to the random number generator.

我们可以粗略地估计出解决方案的边界，因此我们将这个极限添加到随机数发生器中。

This will reduce the computational power and time needed to run the algorithm:

这将减少运行该算法所需的计算能力和时间。

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);
        }
    }

    // methods omitted
}

3.3. Multiswarm

3.3.多重温暖

Finally, let’s conclude our model by creating a Multiswarm class.

最后，让我们通过创建一个Multiswarm类来结束我们的模型。

Similarly to the swarm, we’ll keep track of a collection of swarms and the best particle position and fitness found among all the swarms.

与蜂群类似，我们将跟踪蜂群的集合以及在所有蜂群中发现的最佳粒子位置和适配性。

We’ll also store a reference to the fitness function for later use:

我们还将存储一个对健身函数的引用，供以后使用。

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);
        }
    }

    // methods omitted
}

3.4. Fitness Function

3.4.健身函数

Let’s now implement the fitness function.

现在让我们来实现健身功能。

To decouple the algorithm logic from this specific problem, we’ll introduce an interface with a single method.

为了将算法逻辑与这个具体问题解耦，我们将引入一个具有单一方法的接口。

This method takes a particle position as an argument and returns a value indicating how good it is:

这个方法将一个粒子的位置作为参数，并返回一个表示它有多好的值。

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

Provided that the found result is valid according to the problem constraints, measuring the fitness is just a matter of returning the computed effective health which we want to maximize.

只要找到的结果根据问题的约束条件是有效的，衡量适配度只是一个返回我们想要最大化的计算出的有效健康的问题。

For our problem, we have the following specific validation constraints:

对于我们的问题，我们有以下具体的验证约束。

  • solutions must only be positive integers
  • solutions must be feasible with the provided amount of gold

When one of these constraints is violated, we return a negative number that tells how far away we’re from the validity boundary.

当这些约束之一被违反时，我们返回一个负数，告诉我们离有效性边界有多远。

This is either the number found in the former case or the amount of unavailable gold in the latter:

在前一种情况下，这是发现的数字，在后一种情况下，这是不可用的黄金数量。

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. Main Loop

3.5.主环路

The main program will iterate between all particles in all swarms and do the following:

主程序将在所有粒子群中的所有粒子之间进行迭代，并做以下工作。

  • compute the particle fitness
  • if a new best position has been found, update the particle, swarm and multiswarm history
  • compute the new particle position by adding the current speed to each dimension
  • compute the new particle speed

For the moment, we’ll leave the speed updating to the next section by creating a dedicated method:

目前，我们将通过创建一个专门的方法，把速度更新留给下一节。

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. Speed Update

3.6.速度更新

It’s essential for the particle to change its speed since that’s how it manages to explore different possible solutions.

粒子必须改变其速度，因为这是它探索不同可能解决方案的方式。

The speed of the particle will need to make the particle move towards the best position found by itself, by its swarm and by all the swarms, assigning a certain weight to each of these. We’ll call these weights, cognitive weight, social weight and global weight, respectively.

粒子的速度将需要使粒子向它自己、它的蜂群和所有的蜂群所发现的最佳位置移动，给每一个粒子分配一定的权重。我们将这些权重分别称为：认知权重、社会权重和全局权重。

To add some variation, we’ll multiply each of these weights with a random number between 0 and 1. We’ll also add an inertia factor to the formula which incentivizes the particle not to slow down too much:

为了增加一些变化，我们将把这些权重中的每一个都乘以一个0到1之间的随机数。我们还将在公式中加入一个惯性因素，以激励粒子不要太慢。

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])));
}

Accepted values for inertia, cognitive, social and global weights are 0.729, 1.49445, 1.49445 and 0.3645, respectively.

惯性、认知、社会和全球权重的接受值分别为0.729、1.49445、1.49445和0.3645。

4. Conclusion

4.结论

In this tutorial, we went through the theory and the implementation of a swarm algorithm. We also saw how to design a fitness function according to a specific problem.

在本教程中，我们了解了蜂群算法的理论和实现。我们还看到了如何根据一个具体问题设计一个健身函数。

If you want to read more about this topic, have a look at this book and this article which were also used as information sources for this article.

如果你想阅读更多关于这个主题的内容，请看看这本书和这篇文章，它们也被作为本文的信息来源。

As always, all the code of the example is available over on the GitHub project.

一如既往，该示例的所有代码都可以在GitHub项目上找到。