検索しましたが、答えが見つかりませんでした。
Java で実装されたシミュレーテッド アニーリング (SA) アルゴリズムを使用して 8 クイーン パズル (具体的には N クイーン パズル) を解こうとしていますが、目的関数に関してはちょっと行き詰まっています。目標 (最適解) に近づいているかどうかはどうすればわかりますか?
試行に「ポイント」を与える方法を 2 つ思いつきました (より多くのポイントが試行をより良いものにします)。
合法的にボードにいるクイーンの数
合法的にボード上にあるクイーンの数 + 次のクイーンを合法的に配置するための利用可能なスポットの量
しかし、これらが良いかどうかは判断できません。ヒントやその他の情報を提供していただけますか? :)
ソリューションからの距離は、通常、互いに攻撃しているクイーンの数として定義されます。
シミュレーテッド アニーリングで採用される 1 つのアプローチは、すべてのクイーンをランダムに配置してから、攻撃されているランダムなクイーンを選択し、同じ行のランダムな列に移動することです。
それらを1つずつ配置しようとするのではなく。
これはランダム解と同じではありませんか？
いいえ。
私たちはランダムな動きを選びますが、この動きが実際に起こる確率は、その動きがどれだけ優れているか、解決策にどれだけ近づいているかによって異なります。
良い動きは常に起こりますが、それが悪い動きである場合、その動きが実際に起こる確率は最初は高くなりますが、解決策に近づくにつれてどんどん低くなります。したがって、悪い動きをする可能性はまだあるので、最終的には悪い場所から抜け出しますが、全体としては、主に良い動きをしようとします。
これはシミュレーテッド アニーリングの背後にある基本的な考え方です。「温度」(解までの距離に関連する) の考え方があります。温度が低くなる (解に近づく) と、悪い動きをする確率が減少します。
解決策に近づくにつれて、最善の手を選択しないのはなぜですか?
悪い動きを選択する可能性がまだある限り、これも機能します (ただし、これがまだシミュレートされたアニーリングとして分類されるかどうか、またはこれがパフォーマンスの高いソリューションにつながるかどうかはわかりません-各ステップですべての動きを分析することはかなり高価です）。
場合によっては、2 つのクイーンのみが互いに攻撃しているなどの局所最適から離れる必要があるため、悪い動きの可能性がある必要がありますが、そこからソリューションに直接到達することはできません。最良の動きは、次のステップでの最良の動きになります。