帝国主義の競争アルゴリズム

コンピュータサイエンスにおいて、帝国主​​義的競争アルゴリズムは、さまざまな種類の最適化問題を解決するために使用される計算方法の一種です。 ^{[1] [2]}進化的計算 の分野のほとんどの方法と同様に、ICAは最適化プロセスで関数の勾配を必要としません。特定の観点から、ICAは遺伝的アルゴリズム（GA）の社会的対応物と考えることができます。ICAは人間の社会的進化の数学的モデルとコンピュータシミュレーションであり、GAは種の生物学的進化に基づいています。

図 1 は帝国主義競争アルゴリズムのフローチャートを示しています。このアルゴリズムは、最適化問題の探索空間に候補となるランダムな解のセットを生成することから始まります。生成されたランダムな点は、初期国と呼ばれます。このアルゴリズムにおける国は、GA の染色体や粒子群最適化(PSO)の粒子に相当し、最適化問題の候補解の値の配列です。最適化問題のコスト関数は、各国の力を決定します。その力に基づいて、最良の初期国 (コスト関数値が最小の国) のいくつかは帝国主義国となり、他の国 (植民地と呼ばれる) を支配し始め、初期帝国を形成します。^[1]

このアルゴリズムの2つの主な演算子は、同化と革命です。同化は、各帝国の植民地を社会政治的特性の空間（最適化検索空間）で帝国主義国家に近づけます。革命は、検索空間内のいくつかの国の位置に突然のランダムな変化をもたらします。同化と革命の間、植民地はより良い位置に到達する可能性があり、帝国全体を支配し、帝国の現在の帝国主義国家に取って代わるチャンスがあります。^[3]

帝国主義的競争は、このアルゴリズムのもう一つの部分です。すべての帝国はこのゲームに勝利し、他の帝国の植民地を占領しようとします。アルゴリズムの各ステップでは、その力に基づいて、すべての帝国は最も弱い帝国の植民地の1つ以上を支配するチャンスがあります。^[1]

アルゴリズムは、停止条件が満たされるまで、前述のステップ (同化、革命、競争) を継続します。

上記の手順は以下の疑似コードとしてまとめることができます。^{[2] [3]}

0) 目的関数を定義する:${\displaystyle f(\mathbf {x} ),\quad \mathbf {x} =(x_{1},x_{2},\dots ,x_{d});\,}$
1) アルゴリズムの初期化。検索空間でランダムなソリューションを生成し、初期帝国を作成します。
    2) 同化: 植民地はさまざまな方向から帝国主義国家に向かって進みます。
    3) 革命: 一部の国の特性にランダムな変化が発生します。
    4) 植民地と帝国主義者の間の立場の交換。帝国主義者よりも良い立場にある植民地は、
       既存の帝国主義者を交代させることで帝国の支配権を握るチャンスがある。
    5) 帝国主義的競争: すべての帝国主義者は互いの植民地を占領するために競争します。
    6) 無力な帝国を排除する。弱い帝国は徐々に力を失い、最終的には排除されます。
    7) 停止条件が満たされている場合は停止し、満たされていない場合は 2 に進みます。
8) 終わり

• メタファーベースのメタヒューリスティクスのリスト