ローカル検索とクラシック検索

Question

本の第4章で説明されているように、ローカルの検索 /最適化に関する質問があります。 http://aima.cs.berkeley.edu/

古典的な検索（3章）では、検索は初期ノードから始まり、検索はBFS、DFSなどの戦略に基づいて継続されます。

1. ローカル検索アルゴリズムは、状態空間の1つのノードから始まりますか？制約が満たされているかどうかを確認しますか？はいの場合、これは目標ですか？そうでない場合は、隣人に移動しますか？

2. 州スペース全体が目標状態と見なされていますか？制約を満たさないノードでさえ？

3. 最適化では、検索はすべての制約が満たされているが、より良い解決策を見つけようとする検索スペースの一部で行われます。その場合、検索アルゴリズムが制約を満たさないノードに移動した場合はどうなりますか？

Answer 1

古典的なローカル検索は次のように機能します。いくつかの制約の下でいくつかの機能を最適化しようとしています。実行可能なポイント（すべての制約を満たすポイント）から始めます。各ステップで、（1）それを実行可能に保つ、（2）目的関数を改善する現在のポイントの小さな変更を検討します。このような小さな変更が見つかった場合、それに応じてポイントを変更します。最終的に、私たちはローカルの最適に到達し、グローバルな最適に比べてそれほど悪くないことを願っています。

古典的な例は、線形プログラミングのシンプレックスアルゴリズムです。アルゴリズムは、実行可能なポイントから始まります（それを行う方法はすぐにはわかりません。トリックが必要です）。各ステップで、ポイントを実現可能に保ちながら目的関数を改善する方法で、ある緊密な制約を別のものに切り替えることにより、ポイントを変更しようとします。最終的には、ローカルオプティムに達します。これは、グローバルな最適であることが判明しました（この特定の場合）。

線形プログラミングのインテリアポイントアルゴリズムは異なる方法で機能します。それらはある時点で開始し、（1）ポイントをより実現可能にし、（2）目的関数を改善する方向に移動します。最終的に、あなたは実現可能なローカルの最適に近づきます。これはグローバルな最適であることが判明しました。これはローカル検索ではありませんが、実行可能なソリューションを維持しないアルゴリズムの例です。

非認証ローカル検索は、ローカル検索のテーマに関するバリアントであり、実際の目的関数を最適化しようとする代わりに、補助目的関数を使用してローカル検索を指示します。これにより、ローカルの最適の品質が向上する場合があります。最近ではすべて読むことができます 博士論文 ジャスティン・ウォードによる。

Answer 2

ローカル検索アルゴリズムは、状態空間の1つのノードから始まりますか？制約が満たされているかどうかを確認しますか？はいの場合、これは目標ですか？そうでない場合は、隣人に移動しますか？

通常、ローカル検索は任意のソリューションから開始されます。たとえば、SATの場合、各変数は、独立した等しい1/2の確率を持つ0または1のいずれかを割り当てることができます。あなたが次に説明することは、あなたが始めることとは関係ありません。しかし、はい、あなたはあなたが実行可能な解決策を持っているかどうかをチェックする一般的な戦略に従うことができ、おそらくいくつかの戦略に従って近隣の州に進むことができます。

州スペース全体が目標状態と見なされていますか？制約を満たさないノードでさえ？

目標状態は、あなたの制約を満たす状態です。たとえば、8-Queensの場合、目標状態は、お互いを攻撃しないように女王の配置です。他のすべての州は目標状態ではありません。

最適化では、検索はすべての制約が満たされているが、より良い解決策を見つけようとする検索スペースの一部で行われます。その場合、検索アルゴリズムが制約を満たさないノードに移動した場合はどうなりますか？

一般に、検索はすべての可能な状態を含む検索スペース全体で実施されていると言う方が正確です。あなたの質問の残りは、使用される検索方法に完全に依存します。たとえば、これまでに見つかったソリューションを貪欲に改善しようとすることができます。その後、もはや良くないソリューションに遭遇した場合、または有効な解決策さえ言わないように、最後に既知の最良のソリューションを返します。