最適化手法の整理（AHC用）

AHC用にまとめた自分用の備忘録です。誤っている箇所があればご指摘ください

• 組合せ最適化の解法
  • 厳密解法
    • 分枝限定法
    • 動的計画法
    • 整数計画法
  • 近似解法
    • ヒューリスティック：経験則や直感に基づいてある程度の正解に近い解を見つけ出す発見的手法（特定の問題に特化した手法のこと）
      • 貪欲法：局所的に最適な選択を積み重ねる手法
      • ビームサーチ：貪欲法において、各段階で評価値の高い上位n件を保持しておく（幅優先探索の一種）
      • 局所探索
        • 山登り法
          • ある解を少しずつ変更しながらより良い解を探索。
    • メタヒューリスティック：特定の問題に依存しないヒューリスティック解法
      • 焼きなまし法（Simulated Annealing, SA）
        • 山登り法の発展で、局所最適解に陥るのを防ぐため、確率的に悪化を許容しながら最適解を探索。温度パラメーターにより探索範囲を狭めて局所最適化に移行する
      • 遺伝的アルゴリズム：個体の集合（集団）を進化させながら最適解を探索。交叉や突然変異により多様性を確保する。焼きなましよりも局所最適解に陥りにくい
  • 乱択アルゴリズム：シミュレーションや数値計算を乱数を用いて行う手法
    • モンテカルロ法
  • その他（学習・統計的手法）
    • 強化学習
    • ベイズ最適化