局所探索法と局所最適解

局所最適解 ＝ 悪い解?

局所探索法は，組合せ最適化問題を実践的に解くツールとしてとても強力です． 現実問題を実践的に解決することが目的であるような多くの場面で， メタ戦略のようなより高度な手法を用いなくても， 局所探索法によって満足のいく解が得られることは多いと思います． それにもかかわらず，
「局所最適解 ＝ 悪い解」
という誤った印象を持ち，
「局所探索法は局所最適解で止まってしまうからダメな手法」
と勘違いしてしまっている人が少なからずいるように思います． これはおそらく，以下のような理由のよるものであろうと思います．

メタ戦略アルゴリズムを解説あるいは提案する論文や講演において，

「局所探索法は局所最適解に到達すると止まってしまう． そこで改悪解への移動を許容することで局所最適解に留まらないような工夫を加える．」
というような説明がしばしばなされます． また，メタ戦略アルゴリズムを提案する研究発表などでは
「この方法では探索が局所最適解に捕まってしまってうまくいかなかったので」
というような表現をしばしば聞きます． このような表現をあまり深く考えずに見ると， 「局所最適解 ＝ 悪者」という印象を持ってしまっても仕方ないのかなとも思います．

しかし，上述の1つ目の説明は，もう少し詳しく丁寧に書くと， 以下のようなことを言おうとしています．

「局所探索法は局所最適解に到達すると止まってしまう． しかし，局所最適解は大抵の場合結構良い解で， 良い解の近くにはより良い解が潜んでいることが多いから， 探索をやめてしまうのはとてももったいない． そこで改悪解への移動を許容することで局所最適解に留まらないような工夫を加え， 局所最適解からさらに探索を続けてその付近を詳しく調べることで， より良い解を得ることを狙う．」
このような探索を実現しようとするとき， 局所最適解からその近傍内の解に移動したのち， 新たな解の近傍を探索すると， 近傍が対称であれば， 直前の局所最適解は改善解の1つなので， 探索がそこに逆戻りする可能性があります． 直前の解に戻ることを避けるのは容易ですが， いくつかの解を辿ったのち逆戻りしてしまうのを避けるのは意外に難しいものです． これがうまくいかない時に，
「この方法では探索済みの局所最適解に探索が逆戻りするという無駄がしばしば起こってしまってうまくいかなかったので」
ということを言いたいために，上述の2つ目のような言い方をすることがあるのです． これらを理解すれば，上述のような表現は， 「局所最適解は質の悪い解である」と言いたいわけではないことが理解できると思います．

局所最適解は良い解であることが多いのですが， 中にはそれほど質の良くない局所最適解もあり， 局所探索がそのような解を得て止まってしまうこともあります． また，応用によっては， 解の精度をほんの1%改善するだけでもコストや利益に大きく影響する場合もあり， そのような場合には，探索に多少時間を多く割いても， より精度の高い解を得る工夫を加えたくなります． メタ戦略はそのような時に用いられますが， その多くは局所探索をベースにしています． 局所探索法が本当にダメな手法なら， それを捨てて他の手法に頼れば良いわけですが， そうすることはせずに， 局所探索をベースにより良いアルゴリズムを作ろうという試みが多いことからも， 局所探索法が強力な手法として広く認知されていることがわかると思います．

当たり前のことなのにしばしば見過ごされがちなこととして，

ある解が局所最適解であるか否かは， 近傍と解の評価基準（2つの解のどちらが良いかを定める基準）を定義しないと判断できない
ことが挙げられます． 連続変数に対する最適化問題なら， 変数ベクトル間の距離として多くの人が自然に思い浮かべるものがあり， その距離の意味での「近傍」を連想できるのでまだいいのですが， 組合せ最適化の場合は，そうはいきません． 従って，近傍や評価基準を定義していない状況とか， そもそも局所探索に基づく手法ではないものについて議論している時に， 局所最適という表現はそもそも使えないはずなのですが， そういう状況であるにもかかわらず， 探索があまり良くない解に留まっている状況を表現するのに 局所最適解という言葉を使う人を時々見かけます． 「局所最適解 ＝ 悪い解」と勘違いして， 局所最適解にネガティブな印象を持っていて， あまり深く考えずに使ってしまうのであろうと思います．

そういう使い方のときによく耳にする言い方に， 「局所解」というものがあります． 局所最適解を端折った言い方かなと思いますが， だいたいここに書いたような， ちょっとネガティブな， しかも本来この表現を使えない状況で使われることが多いように思います． そういうこともあって，個人的にはこの表現はあまり好きではありません．

英語では，局所最適解を locally optimal solutions あるいは local optima （いずれも複数形を記した）と言いますが， 後者は上述のネガティブな意味に誤って使われることが多い気がするのと， 上述の「局所解」を連想してどうも好きになれず， （以前はあまり気にしていませんでしたが）最近の自分の書き物では前者を使うようにしています．

用語

局所探索法(local search): 適当な初期解からはじめ，現在の解xの近傍N(x)内にxより良い解x'があればxをx'に置き換える操作を， そのような解がN(x)内に存在しなくなるまで反復する方法． 組合せ最適化問題に対する基本的な発見的解法のひとつ．

近傍(neighborhood) N(x): 解に小さな変形を加えることで得られる解の集合．

局所最適解(locally optimal solution): 近傍N(x)内にxより良い解が存在しないような解x.

メタ戦略(metaheuristics, メタヒューリスティクス，メタ解法): アニーリング法，遺伝アルゴリズム，進化計算，タブー探索法，GRASP法， 反復局所探索法など， 主に組合せ最適化問題に対する反復改善形の手法の総称． 局所探索法をベースにしたものが多い．

近傍Nが対称: x' ∈ N(x) ⇔ x ∈ N(x').

柳浦のホームページ