1 ランダム探索の概観
1.1 定義と基本的な考え方
ランダム探索とは、状態や候補を決定論的な順序で逐次調べるのではなく、確率的な選択規則に従って探索を進める手法群の総称である。基本の考え方は、探索空間全体を網羅することよりも、乱数によるサンプリングと繰り返しによって、目標に近い領域へ到達する確率を高めることにある。
探索の進行は、(1) どの状態を次に選ぶかを確率で決める部分、(2) その状態の良さを判定する基準、(3) いつ探索を止めるか、に分解できる。これらは必ずしも独立ではなく、確率選択と評価指標が相互に影響し合う設計が一般的である。
1.2 どのような問題に適するか
1.2.1 探索空間が大きい問題
探索空間のサイズが膨大な場合、決定論的な網羅探索は計算資源の制約により現実的でないことが多い。ランダム探索は、全体を系統的に列挙する代わりに、確率的に「有望な部分」に探索を集中させることで実行可能性を得やすい。
特に、局所的な手掛かりが不完全でも、繰り返しにより十分に多くのサンプルを集めれば、平均的には改善方向へ進むことが期待される問題で適性が高い。
1.2.2 目標関数が不確実または高コストな問題
目標関数の評価が高コスト、あるいはノイズを含む場合、すべての候補を精密に評価する戦略は難しい。ランダム探索では、少数の評価で得られる情報をもとに確率的に次の候補を選ぶため、評価回数を節約しやすい。
さらに、評価が不確実でも、確率的推定の枠組みによって期待値や信頼区間の形で性能を扱える場合がある。これにより、「測定が高価な問題」や「実験的評価に近い問題」で利用しやすくなる。
1.3 決定論的探索との対比
決定論的探索は、状態の展開順序や選択を固定規則で決めるため、同じ入力では同じ挙動を示しやすい。対してランダム探索は、同一条件でも乱数により経路が変わるため、探索の品質は分布として表れることが多い。
この違いは性能評価に直結する。決定論的手法は「必ずこの計算量で到達する」といった形式になりやすいのに対し、ランダム探索は「期待計算量」や「成功確率」「分散」といった統計的指標で議論されることが多い。設計者は性能保証の種類を明確にする必要がある。
2 モデル化と要素
2.1 探索空間と状態表現
2.1.1 グラフ・状態遷移としての定式化
問題は、状態集合と遷移関係を持つグラフ、あるいはマルコフ的な状態遷移としてモデル化できる。各状態は候補解や状況を表し、辺は「ある状態から次の状態へ遷移し得る」ことを意味する。
ランダム探索では、遷移の実際の選択に確率が入る。例えば、各状態から取り得る遷移先の中で、確率分布に従って次の状態がサンプルされる設計になる。このとき、遷移確率が探索の性質（到達のしやすさ、停滞のしやすさ、推定の安定性）を左右する。
2.1.2 探索木としての定式化
探索木モデルでは、ルートからの展開により候補列を木構造として表す。木の各ノードは部分状態（あるいは行動列）を表し、子ノードはその拡張を表す。
確率的探索木では、ノードごとに「どの子をどれだけ調べるか」の配分が確率で与えられる。結果として、探索が木の一部に偏る現象が起きるが、適切な確率設計により価値の高い枝をより多く訪れることが可能になる。
2.2 近傍生成と遷移確率
近傍生成は、ある状態から近い候補を列挙（または確率的に生成）する機構である。全近傍を明示列挙する必要がなく、乱数でサンプルするだけでよい場合も多い。
遷移確率は、近傍内の候補に対してどの確率を割り当てるかを規定する。均等に選ぶ方式もあるが、評価情報を反映して偏らせることで探索効率が改善することがある。一方で偏りが強すぎると、探索が局所領域に固定されて多様性が失われるため、設計にはトレードオフがある。
2.3 目標判定と評価指標
2.3.1 成功条件（到達・最適化・満足）
成功条件は問題設定に応じて複数の形を取る。到達問題では、目標状態集合に一度でも入れば成功とする。最適化では、最良値を求める、あるいは既知の最適値へ近づくことが目標になる。
満足（satisficing）では、最適性よりも「許容基準を満たす」ことを成功とみなす。ランダム探索では、満足条件にすると比較的達成しやすい基準を設定でき、実運用上の要請に合わせやすい。
2.3.2 評価関数の役割
評価関数は、状態（または候補）にスコアを付け、探索の確率選択や更新の判断材料となる。評価は必ずしも真の目的関数と一致しない場合があるが、設計者はそのズレが探索品質へ与える影響を理解する必要がある。
評価関数は、(1) 確率選択の重み付け、(2) 学習（方策更新）の信号、(3) 終了判定の根拠、の複数役割を担うことが多い。ノイズを含む評価では、評価回数の増加によって推定精度を高める戦略が組み合わされる。
2.4 乱数生成と確率モデル
2.4.1 乱数品質の影響
乱数生成器の品質は、探索の再現性や推定の安定性に関わる。特定の欠陥（周期性、偏り、相関）があると、理論上の確率モデルと実際の挙動が乖離し、性能が劣化する可能性がある。
一般に、暗号学的強度が必要というよりも、探索で要求される統計特性（分布の正しさ、相関の扱い、十分な状態空間）を満たすことが重要である。実験では同一条件の比較のため、乱数系列を固定する運用がよく採用される。
2.4.2 確率分布の選び方
確率分布の選定は、ランダム探索の核となる。例えば一様分布は単純だが、探索効率は低くなり得る。重み付き分布は評価情報を取り込む一方で、推定の偏りや探索の多様性低下が起き得る。
分布の設計には、(1) サンプルが探索空間のどの部分をどの頻度で訪れるか、(2) 評価情報がどの程度反映されるか、(3) 理論的な保証（条件付き期待値、収束）を成立させる前提があるか、を考慮する必要がある。
3 主要な手法クラス
3.1 モンテカルロ型の探索
3.1.1 ランダムサンプリングによる推定
モンテカルロ型の探索では、確率的にサンプルした複数の経路や候補に基づいて期待値や最良度合いを推定する。推定の対象は、例えば到達確率、期待評価、将来報酬の近似などである。
サンプリングは局所的な情報だけで全体像を完全に知ることはできないという状況に対応する。多数の試行を行うことで統計的に推定が安定し、平均的な性能が改善する。
3.1.2 反復による信頼性向上
単発のサンプルはばらつきが大きいが、反復を重ねることで推定誤差は縮小し得る。ここで重要なのは、分布に対する仮定と、試行回数と誤差の関係をどう扱うかである。
誤差の評価には、分散、信頼区間、あるいは集中不等式に基づく見積りが使われる。実務では「どれだけ試行すれば十分か」を決めるために、事前の実験による較正も行われる。
3.2 確率的最適化
3.2.1 近傍探索と確率的受理
確率的最適化では、現在の候補の近傍から新候補を生成し、確率的に受理することで探索を進める。受理規則は改善を優先しつつ、劣化方向にも一定確率で進む仕組みを含み得る。
この「受理の確率性」により、局所最適に閉じ込められるリスクを低減し、より広い領域を探索しやすくなる。受理確率の設計は探索の温度や緩和の強さ、評価関数のスケールに依存し、調整パラメータが性能を左右する。
3.2.2 探索と活用のバランス
探索（新しい領域へ移ること）と活用（高いスコアの領域を深掘りすること）の両立は、確率的最適化における中心課題である。完全な活用は局所探索に偏り、完全な探索は良い領域での改善を逃しやすい。
このバランスは、受理規則の確率、近傍の広がり、更新頻度といった要素で調整される。多くの設計では、初期は探索寄りにし、反復が進むにつれて活用寄りに移行することで安定化を図る。
3.3 確率的探索木手法
3.3.1 ランダムロールアウトの考え方
探索木において、各ノードで価値を直接計算せず、ランダムに展開した先（ロールアウト）での結果から見積もる方法がある。ロールアウトは、そのノードから先の挙動を簡易に模した試行であり、計算量を抑えつつ将来の見通しを得る目的がある。
ロールアウトの方針が単純すぎると価値推定が粗くなる一方、複雑にすると試行コストが増えるため、試行の作り方と予算の配分が重要になる。
3.3.2 価値推定と方策の更新
探索木手法では、訪れた頻度と評価結果に基づいて価値推定を更新し、次に探索すべき枝の確率や優先度を調整する。更新の手法は、平均値の更新、上置信界に基づく方策、あるいは学習則に基づく方策改善などに分かれる。
この枠組みの利点は、試行を重ねるほど「良さ」と「不確かさ」を同時に反映しやすい点にある。結果として、限られた計算予算のもとで探索木が効率良く伸びるように設計できる。
3.4 エージェントベースの確率探索
3.4.1 方策による行動選択
エージェントベースの確率探索では、状態に対して行動を選ぶ方策（ポリシー）を持ち、確率的に行動が決定される。方策により、同じ状態でも異なる行動が選ばれ得るため、多様な経験を集められる。
方策は固定の確率表としても、パラメータ付きモデルとしても表現できる。更新される場合、より高い報酬が見込まれる行動ほど選ばれやすくなるように調整される。
3.4.2 報酬に基づく学習
報酬（スコア、利益、ペナルティ）に基づいて方策や価値の推定を改善する学習手法が、確率探索と結び付けられる。学習では、経験の系列から将来の期待を見積もり、その差をもとに更新を行う。
ノイズを含む報酬や遅延報酬がある場合、信用割当ての難しさが増す。したがって、学習率、割引率、バッチ化やターゲットの使い方など、安定性を高める工夫が必要になりやすい。
4 性能評価と理論的側面
4.1 計算量（期待値・分布）
ランダム探索の計算量は、単一の実行時間としてではなく確率変数として扱うのが自然である。典型的には、期待計算量、分位点、あるいは分布の裾（最悪に近い挙動）を評価対象にする。
期待値だけを見ると稀な失敗や長時間の事例が隠れることがあるため、分散や上側の尾を追加で確認する実務がある。理論的には、遷移確率や評価の更新則に依存して分布形が変わり得る。
4.2 成功確率と停止条件
4.2.1 有限時間での到達可能性
停止までの時間が有限であるとき、成功がどの程度の確率で起きるかが問題になる。到達可能性は、目標集合へ繋がる経路がどれだけ探索されやすいか、そしてその経路に必要な試行の回数がどの程度かで決まる。
理論では、初期状態分布、探索戦略、遷移の偏りに関する条件を明示し、成功確率の下界や期待される達成時間を示すことがある。実験では、それらを検証するために試行回数を揃える設計が重要になる。
4.2.2 反復上限と打ち切り
探索は通常、計算予算を超えないように反復上限や打ち切り規則が設定される。打ち切りがあると成功確率が低下し得るが、実用上は計算量の制約を満たす必要がある。
打ち切り時の指標として、最良到達値、達成度、あるいは平均スコアなどを用いることで、完全到達に限らない評価が可能になる。これにより、目的が「最適解発見」だけでなく「良質解の獲得」である状況に適応できる。
4.3 分散・再現性・統計的検定
4.3.1 推定誤差の扱い
モンテカルロ型では推定が本質的に統計誤差を含む。したがって、サンプル数に応じた標準誤差や信頼区間を見積もり、比較の妥当性を担保する必要がある。
推定誤差は、試行の独立性、分散の大きさ、重み付けの分布によって変化する。設計段階では、推定対象と分散要因を切り分け、必要な試行数を見積もることが求められる。
4.3.2 実験設計とベンチマーク
ベンチマークでは、乱数の影響を制御しつつ公正な比較を行う必要がある。具体的には、同じデータセットや初期条件、同じ予算（反復回数、評価回数）をそろえることが基本になる。
統計的検定や効果量の報告を行うことで、偶然の差を過大評価しない。さらに、複数のシードにわたる平均とばらつきを示すことで、頑健性を評価しやすくなる。
4.4 復元性と乱数依存の制御
4.4.1 シード管理
再現性を確保するために、乱数シードの管理が重要である。同一シードに対して同一挙動が得られることは、バグ調査や性能比較に役立つ。
また、複数シードでの結果を収集することで、特定の乱数系列に依存した結論を避けられる。ログに乱数状態を記録する運用は、追試可能性を高める。
4.4.2 検証可能な評価手順
検証可能な評価手順とは、入力、実行環境、予算設定、打ち切り規則、乱数制御、集計方法を明確にし、第三者が同じ条件で再実行できる形に整えることである。
評価指標の定義（成功の定義、スコアの集計方法、外れ値処理）も手順に含める必要がある。これにより、ランダム要因による偶然性を区別しつつ、手法の実力を測定できる。