1. Введение
В этой статье мы рассмотрим алгоритм оптимизации Multi-swarm. Как и другие алгоритмы того же класса, его цель — найти наилучшее решение проблемы путем максимизации или минимизации определенной функции, называемой фитнес-функцией.
Начнем с теории.
2. Как работает оптимизация Multi-Swarm
Multi-swarm — это разновидность алгоритма Swarm. Как следует из названия, алгоритм Swarm решает задачу, моделируя движение группы объектов в пространстве возможных решений. В версии с несколькими роями существует несколько роев, а не один.
Основной компонент роя называется частицей. Частица определяется ее фактическим положением, которое также является возможным решением нашей проблемы, и ее скоростью, которая используется для вычисления следующей позиции.
Скорость частицы постоянно меняется, склоняясь к наилучшему положению, найденному среди всех частиц во всех роях с определенной степенью случайности, чтобы увеличить количество охватываемого пространства.
Это в конечном итоге приводит большинство частиц к конечному набору точек, которые являются локальными минимумами или максимумами в функции пригодности, в зависимости от того, пытаемся ли мы минимизировать или максимизировать ее.
Хотя найденная точка всегда является локальным минимумом или максимумом функции, она не обязательно является глобальной, поскольку нет гарантии, что алгоритм полностью исследовал пространство решений.
По этой причине множественный рой считается метаэвристическим — решения, которые он находит, являются одними из лучших, но они не могут быть абсолютно лучшими.
3. Реализация
Теперь, когда мы знаем, что такое мультирой и как он работает, давайте посмотрим, как его реализовать.
В нашем примере мы попытаемся решить эту реальную проблему оптимизации, опубликованную на StackExchange:
3.1. Частица
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.
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?
Мы начинаем с моделирования нашей базовой конструкции, частицы. Состояние частицы включает ее текущую позицию, которая представляет собой пару значений здоровья и брони, решающих проблему, скорость частицы по обеим осям и оценку пригодности частицы.
Мы также сохраним лучшее положение и оценку пригодности, которые мы найдем, поскольку они понадобятся нам для обновления скорости частиц:
Мы решили использовать длинные массивы для представления как скорости, так и положения, потому что мы можем вывести из постановки задачи, что мы не можем купить фракции брони или здоровья, следовательно, решение должно быть в целочисленной области.
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
}Мы не хотим использовать int, потому что это может вызвать проблемы с переполнением во время вычислений.
3.2. Рой
Далее, давайте определим рой как набор частиц. Еще раз мы также сохраним историческую лучшую позицию и оценку для последующих вычислений.
Рой также должен будет позаботиться об инициализации своих частиц, назначив каждой из них случайное начальное положение и скорость.
Мы можем приблизительно оценить границу решения, поэтому добавляем этот предел в генератор случайных чисел.
Это уменьшит вычислительную мощность и время, необходимое для запуска алгоритма:
3.3. Multiswarm
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
}Наконец, давайте завершим нашу модель созданием класса Multiswarm.
Как и в случае с роем, мы будем отслеживать набор роев, а также лучшее положение частиц и пригодность среди всех роев.
Мы также сохраним ссылку на фитнес-функцию для дальнейшего использования:
3.4. Фитнес-функция
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
}Давайте теперь реализуем фитнес-функцию.
Чтобы отделить логику алгоритма от этой конкретной проблемы, мы представим интерфейс с одним методом.
Этот метод принимает позицию частицы в качестве аргумента и возвращает значение, указывающее, насколько она хороша:
При условии, что найденный результат действителен в соответствии с ограничениями задачи, измерение пригодности — это просто вопрос возврата рассчитанное эффективное здоровье, которое мы хотим максимизировать.
public interface FitnessFunction {
public double getFitness(long[] particlePosition);
}Для нашей задачи у нас есть следующие конкретные ограничения проверки:
«решения должны быть только положительными целыми числами решения должны быть осуществимы с предоставленным количеством золота
-
Когда одно из этих ограничений нарушается, мы возвращаем отрицательное число, которое говорит, как далеко мы находимся от границы допустимости.
Это либо число, найденное в первом случае, либо количество недоступного золота во втором:
3.5. Основной цикл
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.6. Обновление скорости
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);
}
}
}Для частицы важно изменить свою скорость, поскольку именно так ей удается исследовать различные возможные решения.
Скорость частицы должна будет заставить частицу двигаться к лучшей позиции, найденной ею самой, ее роем и всеми роями, присваивая каждому из них определенный вес. Мы будем называть эти веса когнитивным весом, социальным весом и глобальным весом соответственно.
Чтобы внести некоторую вариативность, мы умножим каждый из этих весов на случайное число от 0 до 1. Мы также добавим в формулу коэффициент инерции, который побуждает частицу не замедляться слишком сильно:
Принятые значения инерционных, когнитивных, социальных и глобальных весов: 0,729, 1,49445, 1,49445 и 0,3645 соответственно.
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])));
}4. Заключение
В этом уроке мы рассмотрели теорию и реализацию алгоритма роя. Мы также увидели, как разработать фитнес-функцию в соответствии с конкретной проблемой.
Если вы хотите узнать больше об этой теме, взгляните на эту книгу и эту статью, которые также использовались в качестве источников информации для этой статьи.
Как всегда, весь код примера доступен в проекте GitHub.
«