1前書き

この記事では、Multi-swarm最適化アルゴリズムについて説明します。同じクラスの他のアルゴリズムと同様に、その目的は、適応度関数と呼ばれる特定の関数を最大化または最小化することによって、問題に対する最良の解決策を見つけることです。

いくつかの理論から始めましょう。


2マルチスウォーム最適化の仕組み

マルチスウォームはhttps://en.wikipedia.org/wiki/Particle

swarm

optimization[Swarm]アルゴリズムの変形です。その名前が示すように、

Swarmアルゴリズムは、可能な解決策の空間内でのオブジェクトのグループの動きをシミュレートすることによって問題を解決します

マルチスウォームバージョンでは、1つだけではなく複数のSwarmがあります。

スウォームの基本構成要素はパーティクルと呼ばれます。パーティクルは、実際の位置(これも私たちの問題を解決する可能性があります)と次の位置を計算するために使用される速度によって定義されます。

粒子の速度は絶えず変化し、覆われた空間の量を増やすために、ある程度のランダム性をもってすべての群れの中のすべての粒子の間で見つけられる最良の位置に傾いています。

これにより、最終的に、ほとんどの粒子は、最小化または最大化を試みているかどうかに応じて、フィットネス関数の極小値または最大値である点の有限集合になります。

求められる点は常に関数の極小値または極大値ですが、アルゴリズムが完全に解の空間を探索したという保証はないため、必ずしも大域的なものとは限りません。

このため、マルチスウォームはメタヒューリスティックであると言われています。


3実装

これでマルチスウォームとは何か、そしてそれがどのように機能するのかがわかったので、それを実装する方法を見てみましょう。

この例では、https://matheducators.stackexchange.com/questions/1550/optimization-problems-that-todays-students-might-actually-encounter/1561#1561[この実生活最適化問題]に対処しますStackExchangeに投稿された]:

League of Legendsにおいて、物理的ダメージから防御するときのプレイヤーの有効ヘルスは、

E = H(100 A)/100

で与えられます。

ヘルスは1ユニットにつき2.5ゴールド、アーマーは1ユニットにつき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);
}

発見された結果が問題の制約に従って有効であると仮定すると、適合度を測定することは、我々が最大化したい計算された有効健康状態を返すことの問題である。

私たちの問題のために、私たちは以下の特定の検証の制約があります:

  • 解は正の整数のみでなければならない

  • 解決策は提供された金の量で実行可能でなければなりません

これらの制約のいずれかに違反した場合は、妥当性の境界からどれだけ離れているかを示す負の数を返します。

これは前者の場合に見られる数か後者の場合に利用できない金の量のどちらかです:

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結論

このチュートリアルでは、群アルゴリズムの理論と実装について説明しました。また、特定の問題に応じてフィットネス関数を設計する方法も見ました。

このトピックについて詳しく知りたい場合は、https://books.google.it/books?id = Xl9uCQAAQBAJ[この本]およびhttps://msdn.microsoft.com/ja-jp/magazine/をご覧ください。この記事の情報源としても使用されているdn385711.aspx[この記事]。

いつものように、この例のすべてのコードはhttps://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-1[GitHubプロジェクトについて]で利用可能です。