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