基本的なヒューリスティック・アルゴリズム
続いて、遺伝的アルゴリズム以外のヒューリスティック・アルゴリズムを紹介しましょう。
山登り法 Hill Climbing
ヒューリスティック・アルゴリズムの中でもっとも単純なアルゴリズムです。
「山登り法」という名前が、単純にその内容を物語っています。
たとえばこういうことです。あなたは目隠しをされ、ヘリコプターでとある山地のど真ん中に降ろされます。地図も何も渡されません。そしてこう言われます。「とりあえず一番高いところまで登って」と。
そう言われたらできることはひとつしかありません。斜面を見つけては登り、見つけては登り……を続けることです。そして、もうそれ以上登れないところまで行けば、そこが「一番高いところ」です。
このように、目標が掲げられており、値を少しずつずらして、目標に近づけば採用、遠ざかれば破棄して、目標に近づく値を探索していく手法が「山登り法」です。
単純なだけに、この手法には問題点もあります。「局所最適解におちいりやすい」という問題です。
上の例で言えば、とりあえず今いる場所からどんどん登っていき、頂上まで行きますが、それがそのエリアで一番高い山であるとは限りません。たまたまヘリコプターを降ろされた地点から一番近い高所であって、実はすぐ隣の山の方が高いかもしれないわけです。
「たまたま手近にあった最適値」を解と見なしてしまうことを「局所最適解におちいる」と言います。
山登り法では、これを回避する方法がありません。頂上ではなく下山道を探索する問題の場合は、深くくぼんだ穴に落ち込んで抜け出せなくなることもありえますし、迷路脱出問題では、ゴール方向から大きく遠ざかる迂回ルートが正解だと、解けなくなります。
焼きなまし法 Simulated Annealing
「局所最適解におちいる」のを回避する仕組みを加えたアルゴリズムに「焼きなまし法」や「タブー探索法」があります。
「焼きなまし法」は、金属の熱処理方法になぞらえた呼び名がつけられたアルゴリズムです。「最初は高温で、ゆっくりゆっくり冷えていく」ような流れで実行されます。
山地の例でいうと、ヘリコプターから降ろされて最初のうちは自力で数キロもジャンプできる（ジャンプできる距離はだんだん減っていく）……という非現実的な話になります。
そこで、「結婚相談所に入会したAI子さん」で説明しましょう。
まだ若いながら、結婚したいAI子さんは、ある結婚相談所のドアをたたきます。カウンセリングを受け、趣味嗜好や希望をプロフィール化してもらい、お金を払って入会。すると、相手を紹介してもらえたり、お見合いパーティーに参加できたりします。
あるとき、素敵な人と出会います。ルックスは好みだし、話も合うし、価値観も似通っていて、ココロときめきます。
「この人ならいいかも！」と思いました。
しかし少し付き合ううちに、
「この人は局所最適解かもしれないわ！」
という思いも浮かんでくるのです。つまり、「今まで会った中では最高の人だけれど、本当のウンメイの人（大域最適解）はもっと別にいるのかも！」という話です。
AI子さんはまだ若い（まだ「高温」なんです）。そこでAI子さんは、思い切ってその人と別れ、思い切って海を越え、米国カリフォルニア州の結婚相談所に入会します。そしてそこで、また素敵な人と出会います。もう、なんだかんだいろいろと、最高でした。
しかしAI子さんは思います。
「この人は局所最適解かもしれないわ！」（パート2）
そして思い切ってその人と別れ、思い切ってアメリカ東海岸に転じ、ニューヨークの大手結婚相談所に入会します。そしてそこで、またまた素敵な人と出会うのです。いやもう、うまく説明できませんけれど、なんだかんだいろいろと、とにかく最高でした。
しかし、真実の愛を求めるAI子さんのココロは叫んでしまうのです。
「この人は局所（以下省略）」（パート3）
このように、「この人は局（以下省略）」をパートｎまで繰り返したAI子さんですが、だんだんと年を取ってきます。大西洋を越え、ヨーロッパを横断し、中東に入ってアラブの石油王を狙いイスラム教（スンニ派）に改宗し、トンカツに永遠の別れを告げたあたりで、いい加減くたびれてきました（少しずつ「冷えて」きたわけです）。
こうなってくると、AI子さんもこれまでのような大ジャンプはしなくなります。結局、紫禁城クラスの宮殿に住み50台ほどの乗用車を保有し100人ほどの使用人を雇う大富豪で妥協しました。
「ほかに3人奥さんがいるけど、まいっか」と。
「焼きなまし法」とはつまり、このように最適解を探索しながらも、ある確率であえて大きく外れる別方向に解を探しに行くステップを、「山登り法」に加えたものです。そのことによって局所最適解におちいる危険を避けようとしています。
そしてその確率が、最初は高く、だんだん低くなっていくように設定されているので「焼きなまし法」と呼ばれます。
タブー探索法 Tabu Search
タブー探索法は、やはり局所最適解におちいる危険性を回避する仕組みをそなえたアルゴリズムです。
引き続き、結婚相談所で説明してみましょう。ただし今度は海を越えるような大スケールの話ではなく、せいぜい都道府県くらいの現実的な話でまいりましょう。
結婚相談所におけるタブー探索法のキモは、「一度見た人はしばらく見ない」です。以下のような流れで素敵な人を探します。
① とりあえず何でもいいから「お相手データファイル」を開ける（初期状態）
② 職業・年収、学歴、ルックス、身長、趣味嗜好などを点数化、数値化して把握（「S₀さん」とします）
③ S₀さんと似たような「お相手データファイル」をいくつか開き、数値化して評価（S₀さんに比べ、「勤務先だけ少し良い」とか、「ルックスだけちょっと残念」とか、「学歴だけはすごい」とか、微妙にちがうだけのファイルを複数）
④ それらの中で、タブーリストになく（ファイルを見たことがなく）、かつもっともスコアが高い人（S₁さん）を選び、S₀さんと比較
④－1 スコアがS₁さん＞S₀さんなら、S₀さんを捨て、S₁さんのファイルをホールド
タブーリストに「S₀さん→S₁さん」との記載がすでにあれば、最新の欄に移動
④－2 スコアがS₁さん＜S₀さんなら、タブーリストに「S₀さん→S₁さん」という記載があるか確認し、なければ「S₀さん→S₁さん」と記載（タブーリストのサイズを超えてしまうようならリストから一番古い記録を削除して記載）・そのうえで、S₀さんを捨て、S₁さんのファイルをホールド（結局S₀さんのファイルは捨てている点に注意）
⑤ ③のステップに戻る（S₁さんと微妙にちがうスペックの別人のファイルをいくつか開けます）
このプロセスを図示すると、次のようなイメージになります。近似ファイルを4つずつ開けるケースです。
①で4つのファイルを開け、②を選びます。②でも4つ新たなファイルを開けます（そうすると本当はもう一本矢印が必要になりますが、省略します）。次は③が最高でした。ここでも新しいファイルを4つ開き、そのうちひとつを選びますが、一度参照したファイルは選びません（①の上の丸印）。
こうすると、「一度通った道は（しばらくの間は）通らない」形で次々に最適な「お相手データファイル」を探索できるわけです。「タブー探索法」では、このようにして局所最適解におちいる可能性を回避しています。
ただ、「しばらくの間は」と書いたように、ある程度探索が進んだあとでは再び一度見たことがあるファイルに戻る可能性も残してあります。そのためにも、タブーリストのデータサイズは大きくしすぎないようにすることが重要です。
まとめ
「焼きなまし法」にしても「タブー探索法」にしても、けっこう似たようなことを私たちは日頃やっているものです。結婚相談所を例に挙げましたが、そういう場に参加していて「本当にこの人でいいのかな」という思いをいだいてしまうことがあるのは、男女いずれも同じではないかと思います。「この人は局所最適解かもしれないわ！」というのは、それを数理学の用語で言い換えただけです。
ほかにも、ランチをとりにフードコートに行きまして、あれにしようかこれにしようかといろいろ悩むことがあります。悩んだ末に、「ピリ辛ガパオライス半熟目玉焼きのせ」を選択し、作ってもらったガパオライスをトレーにのせてテーブルに戻る途中、目に入ってくるほかの人たちが食べている料理の方が、なんともいえず自分が選択したガパオライスよりもおいしそうに見えてしまう……ということもしょっちゅうあるわけです。
「となりの芝生は青く見える」ものなんですね。
おそらく、リアルな人生には局所最適解しかないんです。「大域最適解」なんてものの探求は、人生においては無理、かつ無意味。そんなものは限定的なつまらない問題について、マシンにやらせておきましょう。
「局所最適解だけが人生さ」――そんな感じで気楽に行った方が幸せになれると思います。
