本研究は、動的線形環境における(1+1)-進化戦略(EA)の性能を理論的に分析したものです。動的環境とは、毎世代ごとに正の重みを持つ線形関数が新たにサンプリングされる環境を意味します。 研究対象となるのは2つのモデルです。第1に「Dynamic Binary Value問題」では、各世代で1, 2, 4, ..., 2^(n-1)の均一ランダムな並べ替えを使用します。第2に「Uniform weight variant」では、重みが[0,1]の一様分布から独立にサンプリングされます。両モデルはIOHprofilerプラットフォームに組み込まれており、実験的な検証も行われています。 この研究の主な貢献は、突然変異パラメータχに対する明確な閾値を証明したことです。突然変異率をχ/nとすると、閾値より下では最適化に要する期待時間がO(n log n)である一方、閾値より上では実行時間が2^(Ω(n))に急激に増加します。このような相転移現象は、アルゴリズム設計においてパラメータ調整がいかに重要であるかを示しています。 Dynamic Binary Value問題の指数領域では、さらに詳細な分析が行われました。研究者らは最適解からの距離に関する第2の閾値を特定し、効率的に到達できる距離と指数時間を要する距離を定量的に区別しました。この結果は、従来の実験的知見を理論的に立証し、動的環境における進化的アルゴリズムの挙動をより深く理解する手がかりを提供します。