Speeding Up the NSGA-II via Dynamic Population Sizes

技術要約：動的な集団サイズによるNSGA-IIの高速化

問題提起
多目的進化アルゴリズム（MOEA）、特に非劣ソート遺伝的アルゴリズムII（NSGA-II）は、多目的最適化問題を解くために広く用いられている。その適用における中心的な課題は、集団サイズ（$N$）の管理である。パレートフロント（最適なトレードオフの集合）を効果的に表現するためには、集団は十分に大きくなければならない。しかし、集団が大きいと、NSGA-IIは反復ごとに$N$個の解を評価するため、アルゴリズムの速度が低下する。これは設計上のジレンマを生み出す。集団が小さすぎるとパレートフロントを効率的にカバーできず、大きすぎると不必要な計算コストが発生する。近年の数学的解析によれば、最適な固定集団サイズを持つ静的なNSGA-IIの実行時間は、OneMinMax（OMM）ベンチマークにおいて$\Theta(n^2 \log n)$であり、これは特定のクラスのアルゴリズムに対する理論的な下限と比較して最適ではないと考えられている。

手法
著者らは、初期の小さな集団から開始し、時間の経過とともに集団を増加させることで、集団サイズのジレンマに対処する、古典的なアルゴリズムの変種であるDynamic NSGA-IIを提案している。

• アルゴリズムの構造: アルゴリズムは集団サイズ$N=4$から始まる。ユーザーが指定するパラメータ$\tau$に相当する固定数の関数評価を実行した後、集団サイズを倍増させる試みを行う。この倍増は、ユーザー定義の最大集団サイズ$N_{max}$に達するまで繰り返される。重要な点は、倍増が反復回数ではなく「関数評価数」によってトリガーされることであり、これにより、現在の集団サイズに関わらず、各「フェーズ」がほぼ等しい計算予算を受け取ることが保証される。
• 選択メカニズム: 著者らは、タイブレーク（同順位の決定）に**現在の混雑距離（current crowding distance）**を用いる特定のNSGA-IIの変種を利用している。このメカニズムは、以前に解の分布を改善することが示されており、混雑距離が最小の個体を反復的に削除して距離を再計算することで、解のより等間隔な広がりを実現する。
• 変種:
  1. 標準的Dynamic NSGA-II: $\tau$回の評価ごとに集団を倍増させる。
  2. 初期フェーズを延長したDynamic NSGA-II: 初期フェーズ（$N=4$の期間）の継続時間を、その後のすべてのフェーズの合計計算予算に一致するように延長する。これにより、漸近的な実行時間のオーダーを増大させることなく、極めて効率的な初期段階により多くの時間を割くことができる。
  3. パラメータレス戦略（アルゴリズム3）: $\tau$の手動チューニングの必要性を排除するため、著者らは並行実行戦略を提案している。このフレームワークは、異なる$\tau$値（2のべき乗）を持つ複数のDynamic NSGA-IIのインスタンスを起動し、これまでに費やした総計算努力が最も少ないインスタンスにリソースを動的に割り当てる。

主な貢献と結果
本論文は、2つの標準的なベンチマークである**OneMinMax (OMM)およびOneJumpZeroJump (OJZJ$_k$)**に対する提案アルゴリズムの厳密な数学的実行時間解析を提供している。

1. OMMベンチマーク:

   • 最適な$\tau$を持つ標準的なDynamic NSGA-IIは、高い確率で$O(n \log^2 n)$の関数評価による実行時間を達成する。これは、静的なNSGA-IIの$\Theta(n^2 \log n)$の実行時間に対する大幅な改善である。
   • 初期フェーズを延長した変種は、$O(n \log n)$の実行時間を達成する。これは、偏りのないブラックボックスアルゴリズムの広範なクラスに対して漸近的に最適であり、全オールワン文字列を見つけるための理論的な下限と一致する。
   • パラメータレスな並行戦略（アルゴリズム3）は、$O(n \log^3 n)$（標準）および$O(n \log(N_{max}) \log(n \log N_{max}))$（初期フェーズ延長版）の実行時間を達成し、最適に調整されたバージョンと比較して対数因子程度のペナルティのみを課す。

2. OJZJ$_k$ベンチマーク（ギャップサイズ$k$）:

   • 標準的なDynamic NSGA-IIは、$O(nk \log^2 n)$の実行時間を達成し、静的なNSGA-IIの既知の$\Theta(nk+1)$の実行時間を改善する。
   • 初期フェーズを延長した変種は、$O(nk \log n)$を達成する。
   • パラメータレス戦略は、それぞれ$O(kn^k \log^3 n)$および$O(kn^k \log(N_{max}) \log(nk \log N_{max}))$の実行量をもたらす。

3. 堅牢性とパラメータ独立性:

   • 動的な変種の実行時間の保証は、$N_{max}$がパレートフロントのサイズよりもわずかに大きい場合（例：$N_{max} \ge n+4$）、$N_{max}$にほとんど依存しない。
   • $\tau$が不適切に（小さすぎると）選択された場合、アルゴリズムは集団サイズ$N_{max}$を持つ静的なNSGA-IIの性能へと回帰するため、不適切なパラメータ選択が致命的な結果を招くことはない。
   • 並行実行戦略は、集団サイズのダイナミクスに関する$\tau$の選択というユーザーの負担を事実上排除し、「パラメータレス」なアルゴリズムを実現する。

意義と主張
著者らは、本研究が動的なパラメータを持つMOEAを数学的に分析した最初の事例であり、多目的問題の性質によって集団増加戦略を通じた大幅な高速化が可能であることを示したと主張している。

• 理論的進展: 本論文は、Dynamic NSGA-IIがOMMにおける$\Theta(n^2 \log n)$の壁を打破できることを確立しており、初期フェーズを延長した場合、実行時間はほぼ最適（$O(n \log n)$）となる。
• 実用的含意: シンプルな並行実行戦略を用いることで、手動のパラメータチューニングなしに近似的に最適な性能を達成できることを示すことで、著者らはより堅牢な「パラメータレス」なMOEAへの道筋を提示している。
• アーカイブとの比較: 著者らは、解を保存するためにアーカイブを使用し、より小さな集団を許容する他の研究についても言及しているが、彼らの動的なアプローチは（特にクロスのないビット単位の突然変異に関して）、集団がパレートフロント上の新しい解を生成するのに不十分になるリスクを回避できるため、特定の文脈において理論的に好ましいと述べている。

結論として、Dynamic NSGA-IIは静的なNSGA-IIに対して$\tilde{\Omega}(n)$の証明可能な高速化を提供し、初期フェーズをさらに延長することで、偏りのないブラックボックス最適化の理論的限界まで性能が向上することを述べている。今後の課題として、これらの利点がLOTZベンチマークのような他の一般的なシナリオにおいても保持されるかどうかを調査することが提案されている。