局所探索

メタ・ヒューリスティックの一番基本的なものは、近傍探索という方法です。これは、最初に1つ解を見つけて、解の評価値（目的関数値、つまり最適化したい値）が良くなるように、解をちょっとずつ変更していき、ちょっとの変更では値が良くならなくなったら、そこで終了、その解を出力しましょう、という簡単なものです。

この「局所探索」という方法では、もっとも良い解、つまり最適解が得られるわけではない、というのは、直感的にすぐに分かると思います。1個加えたり減らしたりしたものの中に、今より良い解がないからといって、全体の中に今の解よりも良いものがない、というのは、性急な結論ですから。しかも、1個しか変更しない解しか見ていませんから、解の精度もそれほどよくありません。

解決策

「1個加える／減らす」という変更を、「1個か2個加える／1個か2個減らす／1個減らして1個増やす」のように、変更の作業を大掛かりにしていく