８メタヒューリスティックあなたは真夜中に山の頂上を目指す登山者です８メタヒューリスティックあなたのいる山にはいくつもの小高い丘があり、周りを見ただけではそこが頂上か分かりません８メタヒューリスティックさて、なるべく早く頂上に登るにはどのような戦略を用いれば良いのでしょうか？メタヒューリスティックの代表的な解法局所探索法（Local Search)  模擬焼き鈍し法(Simulated Annealing Method)  タブーサーチ(Tabu Search)  遺伝的アルゴリズム(Genetic Algorithm)  局所探索法(Local Search)  適当な初期実行可能解を定め、近傍の中に、現在の解を改良する解があれば、それに移ることを繰り返して解を改善していく方法近傍実行可能解山頂を目指す夜の登山者  明かりの照らせる範囲に現在地点より高い場所が周りにあればその方向へ移動する山頂を目指す夜の登山者  照らした範囲に現在地点よりも標高が高い地点が見つからなくなった時点で終了 →いつも最も高い地点に到達できるとは限らないココが頂上？本当の頂上模擬焼き鈍し法 (Simulated Annealing Method) 解を改悪することを確率的に許したメタヒューリスティック  焼き鈍し現象にアナロジーを持つ  温度Tが高い徐々に冷却温度T=0 模擬焼き鈍し法 (Simulated Annealing Method)  改悪を許す確率を徐々に小さくすることによって、非常に長い時間をかけて最適解を得る保証を持つ低温高温山頂を目指す夜の登山者   照らした場所の標高と現在地点の標高差Δを測定する現在の地点より高い地点(Δ≧０)があれば、その場所に移動する山頂を目指す夜の登山者照らした地点の標高が現在地点よりも低ければ(Δ< ０)、寒暖計によって現在の気温Tを測定する  乱数表により[０，１]の一様乱数を得て、その値が eーΔ/Tより小さかったら、その場所に移動。大きかったらその場にとどまり、再び適当な場所を懐中電灯で照らす →局所検索法と違い、現在地点より低い場所へ移動することもある →局所検索法よりも歩く時間は長くなるが、到着した丘は局所検索法よりも高いことが期待できる  タブーサーチ(Tabu Search)  探索の過去の記憶を利用したメタヒューリスティック？山頂を目指す夜の登山者同じ場所を巡回しないように、記憶を頼りに、常に最も高い方向を目指して進む  周りに標高の高い地点がなくなったときでも、なるべく下り坂の勾配が小さいほうへ歩き続ける  元の道に戻らないための目印として、属性をタブーリストに記憶する。但し、タブーリストにはタブー長だけしか記憶できず、古いものから順に忘れていく  山頂を目指す夜の登山者タブー長は２属性山頂を目指す夜の登山者に戻らないよう高いほうへ進む山頂を目指す夜の登山者タブー長は２山頂を目指す夜の登山者に戻らないように高いほうへ進む遺伝的アルゴリズム (Genetic Algorithm)    複数の実行可能解を保持し、それら解を進化のアナロジーを用いて改善していく方法２つの解から新たな解を合成する交叉(crossover) ランダムに解の一部を変化させる突然変異 (mutation) 遺伝的アルゴリズム (Genetic Algorithm)  交叉や突然変異は実行可能性を破壊してしまう、という問題点もある山頂を目指す夜の登山者複数の人がばらばらに登りの方向を目指して進む  標高の高い位置にいる２人の間に１番低い所にいる人を移動させる  １番高い２番目に高い１番低い移動後おわり