Javaのマルチスウォーム最適化アルゴリズム
1. 序章
この記事では、マルチスウォーム最適化アルゴリズムについて見ていきます。 同じクラスの他のアルゴリズムと同様に、その目的は、適応度関数と呼ばれる特定の関数を最大化または最小化することにより、問題の最良の解決策を見つけることです。
いくつかの理論から始めましょう。
2. マルチスウォーム最適化の仕組み
マルチスウォームは、スウォームアルゴリズムのバリエーションです。 名前が示すように、 Swarmアルゴリズムは、可能な解決策の空間でオブジェクトのグループの動きをシミュレートすることによって問題を解決します。マルチスウォームバージョンでは、1つではなく複数のスウォームがあります。
群れの基本的な構成要素は粒子と呼ばれます。 パーティクルは、問題の解決策としても考えられる実際の位置と、次の位置を計算するために使用される速度によって定義されます。
パーティクルの速度は絶えず変化し、カバーされるスペースの量を増やすために、ある程度のランダム性ですべての群れのすべてのパーティクルの中で見つかった最適な位置に傾いています。
これにより、ほとんどのパーティクルは、最小化または最大化するかどうかに応じて、適応度関数の極小値または極大値である有限の点のセットになります。
見つかったポイントは常に関数の極小値または極大値ですが、アルゴリズムが解の空間を完全に探索したという保証はないため、必ずしもグローバルなポイントである必要はありません。
このため、マルチスウォームはメタヒューリスティック – であると言われていますが、最高のソリューションの1つですが、絶対的に最高ではない場合があります。
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;
// constructors and other methods
}速度と位置の両方を表すためにlong配列を使用することを選択します。これは、問題の説明から鎧や体力の一部を購入できないため、解決策は整数領域でなければならないためです。
計算中にオーバーフローの問題が発生する可能性があるため、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);
}見つかった結果が問題の制約に従って有効である場合、適合度の測定は、最大化したい計算された有効なヘルスを返すだけの問題です。
この問題には、次の特定の検証制約があります。
- 解は正の整数でなければなりません
- ソリューションは、提供された量の金で実行可能でなければなりません
これらの制約の1つに違反すると、有効性の境界からどれだけ離れているかを示す負の数が返されます。
これは、前者の場合に見つかった数、または後者の場合に利用できない金の量のいずれかです。
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プロジェクトで利用できます。
