最適化 解析的手法と数値的手法.

Presentation on theme: "最適化 解析的手法と数値的手法."— Presentation transcript:

1 最適化 解析的手法と数値的手法

2 最大値（最小値）を求める 解析的 手法 数値的 手法 すでに知られている関数の性質を使って解く 制約条件がない場合 制約条件がある場合
極値では，微分係数 が０である性質を利用 制約条件がある場合 ラグランジュの未定乗数法 数値的 手法 実際に数値を当てはめ，計算により解く 山登り 法（hill climbing）もしくは最急勾配法 模擬アニーリング (simulated annealing) 遺伝子アルゴリズム (genetic algorithm)

3 解析的手法 極値を求めるには微分 微分：曲線に接する直線の傾きを求める 最大，最小の極値では接線は水平
Δx を0に近づけると 接線 の傾きに 最大，最小の極値では接線は水平 傾きは 0

4 多次元でも同じ http://handa.blog19.fc2.com/blog-entry-69.htmlより
x, yの法線ベクトル 偏微分の結果=0 を解けばよい [すぐ後に出てくる全微分] 任意の接ベクトルは　　と　　に より張られるので，　　　　　と書ける 全微分 曲面のある点における接平面 dx, dyはこの点からのxおよびyの誤差 zの誤差dzは赤線で近似可能

5 最小二乗法 すべての観測値から もっとも近い 位置に線を引く
最小二乗法 すべての観測値から　もっとも近い　位置に線を引く 観測値 xi, yi (i=1,2,..,n)がある xiの値でyiの値を予測．予測値を とする 誤差の2乗　　　　　　　　　　 を最小化 予測式を　　　　　　　　　　とすると a, bでの微分を0とした連立方程式をとく ※ 解き方は回帰の週で説明

6 ラグランジュの未定乗数法 与えられた条件下での極値の探索
関数: f (P1,P2,P3･･･,Pn) が最大となる点を， 制約条件: g(P1,P2,P3･･･,Pn)=0 の条件下で探せ 最大値（あるいは最小値）の点では微分して０になる 山の頂上か谷の底に相当 制約条件のため単純に f を Pi(i=1…n) で微分してもダメ． 制約条件のため，答は必ずしも山の頂上ではなく，斜面の途中にあるかもしれない [ラグランジュの未定乗数法] 新しい変数 λ を用意して式　f + λ・g = 0　を作る これの Pi(i=1…n)とλでの偏微分結果=0とした連立方程式を解くと，目的の f の最大値（最小値）が得られる． f + λ・g = 0 が3変数の場合

7 簡単な例 http://d.hatena.ne.jp/rikunora/20110210/p1より抜粋
関数:　 　　　　　　　　が最大となる点を 制約：　 　　　　　　　　　が0という条件の下で探し出せ [従来方式] 直線　　　　　　　が半径1の円に接する点 （Lを変動させ）直線を上下に動かし円と接する点を探す [ラグランジュの未定乗数法] 式　　　　　　　　　　　　　　　　を x,yで偏微分 制約 これらを解いて，x,y,λ が求まる λを変動させることは，何を動かすこと? L

8 まずはイメージで - 3次元に増やす - 式 の (x,y,g)空間での3D図 関数 も表現 では f と g を足し合わせると
まずはイメージで　- 3次元に増やす - 式　　　　　　　　の (x,y,g)空間での3D図 水平に切れば円 垂直に切れば放物線 関数 　 も表現 では f と g を足し合わせると 平面 f の分だけ（斜めに平行移動して） 放物面の中心が原点からずれる 真上から みたとき

9 λで窪みが変化 λg という項でλを変化させると， 窪みの深さが変化
λ=0 ならまったくの平面 λが小さい：少しだけ窪んだ「お皿」形 λが大きい：深く窪んだ「おわん」形 窪みの深さを変化させ， ちょうどxy平面上のところで 放物面λg と平面 f の傾斜を ぴったり一致させることが可能

10 放物線をずらす f +λg を足し合わせると （斜めに平行移動して） 傾斜がぴったり一致した点が， もっとも低い谷底に降りてくる
３Ｄグラフを真横から切った図で解説 放物線の中心がずれて解の点が一番底へ 目的の関数と傾斜がぴったり一致するように制約条件を適当に調整して重ね合わせる 重ね合わせた関数=0とすると，傾斜が一致した点である目的の点が谷底に来る 一番下に来た点は微分で探しだせる 解の位置が移動

11 数式による説明 せっかくだから, ひとつ変数を増やし3変数の場合で
関数 f は極値近傍で次の式を満たす(全微分) 　　　　　　　　　　　　　　　　　　　　　　　　[意味] f は極値をもつ 関数 g = 0 が成立するので，全微分すると 　　　　　　　　　　　　　　　　　　　　 [意味] g=0 のため x,y,zは勝手に動けない 第２式を第１式に代入する形でdzを消去．　　　　　　　(*) とおくと， この式にはもう拘束条件がなく，x と y は独立な変数 dx と dy がそれぞれ勝手に動けるので，右辺 が成立するなら， 中辺に含まれる（）内の式は それぞれ恒等的に0, 　(*)の式も追加して

12 数値的手法 目的関数の勾配情報を基に最適解を探索
最大化問題では，関数値のもっとも高い地点 最小化問題では最も低い地点 にたどり着く ちなみにラグランジュの未定乗数法は山をある条件を満たした道で登ったときの，もっとも高い点を探す

13 コスト関数，もしくは，効用関数 コスト関数 効用関数 最適化 以下，効用の最大化に絞って説明 目的を達成するためのコストを表わす関数
達成によって得られる価値を表わす関数 最適化 コスト関数を最小化する 効用関数を最大化する 以下，効用の最大化に絞って説明 コスト c が得られれば，効用 u は などでの式で表現できる

14 旅行プラン検索の例 お正月に，3兄弟が家族を連れ，そろって旅行 全体の効用を最大にしたい 多様な属性に重みづけ，ひとつの尺度で表現
楽しみとして，名所観光，グルメ，温泉, etc 手段として飛行機，新幹線，マイカー, etc 考慮すべき属性 行ってみたい度，有名度，美味しさ，運賃，疲労度, etc 全体の効用を最大にしたい 多様な属性に重みづけ，ひとつの尺度で表現 若い頃は楽しさ重視，年を取ってくると疲労度重視 属性の効用（コストの場合もあり）の数値化により 正しい要素の組合せを選んで効用を最大化すること が目標であることが明確になる

15 ランダム探索 ランダムに手段の組合せを複数選び， 最大のものを解とする 過去の経験 を活かせていない 効用関数は 連続 であることがほとんど
右の図で，１が解となる 過去の経験　を活かせていない 効用関数は　連続　であることがほとんど 最大化の場合 価値が最高の解は，他の価値の高い解の　近く　にあるはず

16 山登り法（最急勾配法） もっとも急な勾配を登る（下る） 利点 欠点 現在のノードよりも評価値が高い（低い）継続ノードへ進む．
次のノードの評価値と現在の評価値の差が小さい場合，そこで終了する 利点 簡単 欠点 局所解　に留まる可能性

17 模擬アニーリングsimulated annealing
アニーリング：焼きなまし 温度が高い間は激しく動く ゆっくり冷やしていくうちに，動きが小さくなる ランダムな解から開始 解の候補を取得 改善する場合は受理(確率 p=1) 改悪の場合も，計算される確率 p で受理 所定の回数2.を試行したら温度を下げる 温度が下がりきるまで2-3を繰り返す 温度を T ,現在の解と（改悪となる）新しい解候補との効用差を△E として，改悪を受け入れる確率 温度が高い間は指数部が 0 に近く確率は　1　に近い． 低温や大差になると，指数部の絶対値が大きくなり，確率は　0　に近い p 1.0 ΔE/T

18 遺伝子アルゴリズム genetic algorithm
生物が環境に適応し進化する過程を模倣(菊川玲の研究テーマ) 個体群という無作為解の集団を生成 最適化のステップごとに，個体群の全メンバに対して効用を計算し，解を順位付ける 新しい個体群（次の世代）を生成 選択 (selection)： 生物の適者生存の模倣 交叉 (crossover): 生物の有性生殖を模倣 突然変異 (mutation)： 自然界におけるDNA複写の際に起こるミスに相当 上記を，次世代で改善が見られなくなるまで繰り返す

19 新生代の個体の生成法 選択(selection)： 適者生存 現在の優れた解のいくつかを，そのまま次世代に入れる
交叉(crossover):　有性生殖 解を優れたほうから2個体とり，その一部分を個体同士で交叉 突然変異(mutation)： DNA複写ミス 最良の解に単純な変更 （例）子Aに対し，マスクパターンが 0 の位置では親Aの遺伝子を 1 の位置では親Bの遺伝子を 　　　複製 　　　子Bに関しては，これの逆

20 特徴 選択，交叉，突然変異の確率を変動させる
初期集団から選択と交叉の組合せにより並列的に山登り探索を実施，かつ，突然変異により，ときどきランダムな変化 [長所] 複数の解について並列的に調べるので山登り法のような局所安定には陥りにくい．たとえ，局所安定に近づいても突然変異により脱出 [短所] 個体数，交叉，突然変異の確率の一般的手法が未確立 必ず最適解を求めなくてはならないという場合には使えない．（基準以上の解を少ない計算量で求めたい場合に適す）