近傍探索#

読み: きんぼうたんさく
英名: Neighborhood Search

ヒューリスティックアルゴリズムの基本的な枠組みのこと．ある解に対して定義された近傍に存在するより好ましい解を探索し，解を更新する．「近傍」および「好ましさ」の定義により様々なアルゴリズムが構成できる．典型的な近傍の例としては，「0-1 変数の一つを逆転させた状態すべて」，「経路を構成する点を一つ変更した状態すべて」，がある．「好ましさ」は目的関数の値や制約式の違反分を加味して決定するが，局所最適解からの脱出のために，近傍においてはあえて改悪となる点へと更新することもある．