Key points are not available for this paper at this time.
本研究では、目的関数にノイズが存在する場合の古典的なベンチマークに対するシンプルな多目的進化アルゴリズム (MOEA) の初の数学的実行時間分析を行います。ビット単位の事前ノイズが存在する場合、適切な定数が関与し、ノイズに対処するための調整を行わないシンプルな進化的多目的最適化アルゴリズム (SEMO) が、ノイズのない場合と同様に、OneMinMaxベンチマークのパレートフロントを時間 (2 log) で見つけることを証明します。ここでの問題は、パレートフロントを目撃する + 1 個体の集団に到達することですが、これはノイズに対する驚くべき強いロバスト性を示しています（比較的単純な進化的アルゴリズムは、 = (log()/) の場合に単一目的のOneMax問題を多項式時間で最適化できません）。我々の証明は、MOEAの強いロバスト性が、パレートフロント全体をカバーする集団を計算するために設計された暗黙の多様性メカニズムに起因していることを示唆しています。興味深いことに、この結果は解の目的値が一度だけ決定され、その後アルゴリズムがこの可能性のあるノイズがある目的値で動作する場合にのみ有効です。我々は、各反復で全ての解を再評価する場合、ノイズ率が = (log()/ 2) であると超多項式実行時間につながることを証明します。これは、一般的にフィットネスが重要なときに解を再評価することが好ましい単一目的最適化とは大きく異なり、解を再評価しないことが致命的なパフォーマンス損失につながることが知られている例もあります。この論文は、
Dinot et al. (Sun,) がこの問題を研究しました。