問題タブ [hill-climbing]

水差しの問題でヒルクライミングアルゴリズムに問題があります:

Xリットルの水とYリットルの水を入れることができる2つの水差しが与えられた場合、一方の水差しで正確にDリットルの水を得るために必要なステップ数を決定します.

開始状態 (X,Y) = (0,0) から、いくつかの状態を生成できます。

• (X,Y) = (0,Y)
  または
• (X,Y) = (X,0)

そして、これらの状態から、(X,D) または (D,Y) のいずれかである最終状態まで、他の状態を生成できます。

では、この問題のヒューリスティック関数を推定できますか? どの州が他の州よりも優れているかを知る方法は?

みんなありがとう。

単純な山登りアルゴリズムを探しています

これは大規模なシミュレーション用です。これは、「CurrentLocation」がどのように変化しているかの例です。

私が提示したアルゴリズムは機能していますが、もっと効果的なものがあると思います...何かアドバイスはありますか?

ありがとうございました

I am writing code to address the Nurse Restoring Problem

I have implemented Simulated Annealing and I am interested in comparing the results to Late Acceptance Hill Climbing

I have found some pseudo code for Late Acceptance but need a little help to write it in Java:

I really don't get this bit: For all k in ( 0.. L-1 ) C_hat[k]=C(s)

The pseudo code is from http://www.yuribykov.com/LAHC/LAHC_wonders.pdf

2 つのクイーンが同じ行または列にならないようにボードにクイーンをランダムに配置し、列内のクイーンを最も少ない数で攻撃されている行に移動することにより、Scheme の N-Queens 問題を解決しようとしています。女王の。

私のアルゴリズムは、6 未満の任意のサイズのボードで機能します。6 以上のボード サイズがパラメーターとして使用される場合、プログラムは無限に再帰するように見えます。

すべてのコードを追加しますが、無限再帰が発生すると思われる部分は次のとおりです。

最初の if ステートメントは、ボード上のすべてのクイーンが移動されたかどうかを確認します。競合がある場合は、競合があるかどうかを確認します ((move i) は、競合がない場合は 0 を返します)。競合がある場合、フラグが立てられ、プログラムはクイーンの移動を続行します。

ここで問題です。パズルは最初のパスで解決されるか、まったく解決されません。最初のパスの後にボードが合法である場合、明らかに問題はなく、すべて問題ありません。ただし、そうでない場合は、同じボードが何度も試行され続けます。これは、コードの (ディスプレイ ボード) チェックのおかげでわかります。

ボード サイズが 6 を超えると、最初のパスでパズルが解ける可能性が低いため、コードは機能しないと思います。新しいランダム ボードを作成する行を追加しようとしましたが、その時点で実行時間が最悪で、役に立ちません。

以下にプログラムのコードを示します。ご不明な点がございましたら、お気軽にお問い合わせください。

編集:おそらく問題は、私の(解決)関数が列を反復する方法であると考えています。常に昇順で行けば、最初の数列の競合がゼロであるが、合法的な解決策にならない場所にある場合、残りの列は競合が最も少ない場所に移動されますが、競合がゼロになることはありません。

CPU のプリフェッチャーをシミュレートするコードを c++ で記述しています。コードには、次のような定義がいくつかあります

シミュレーションの最後に、シミュレーターは平均アクセス時間を出力します。これは、プリフェッチャーがどの程度うまく機能したかを示す指標です。プリフェッチャーのパフォーマンスは、x およびその他の同様の定義に依存します。

x を変更し、新しいコードを再コンパイルして実行し、値を調べ、シミュレートされたアクセス時間の変化に基づいてプロセスを繰り返すプログラムが必要です。

手動で値を変更しない簡単な方法を知っている人はいますか?

編集：私は学習アルゴリズムをプログラムする必要がないことを明確にする必要があると思います.

Java で確率的ヒル クライミングを実装しようとしています。このアルゴリズムがランダムに選択された新しいソリューションを作成し、それがどれほど悪い/良いかに基づいてソリューションを受け入れることを理解しています. たとえば、非常に悪い場合はわずかな可能性があり、わずかに悪い場合は選択される可能性が高くなりますが、この確率を Java で実装する方法がわかりません。

Googleでブラウジングしているときに、この方程式に出くわしました。

• f は古いフィットネスを表します
• f' は新しい適応度を表す
• T はパラメーターです

この等式をどのように解釈すればよいか、私にはよくわかりません。

Javaでこれを実装する方法について誰か助けてもらえますか?

ニューラル ネットワークを作成してトレーニングする小さなプロジェクトを C# で作成しました。詳細については、こちらの以前の質問を参照してください: ( https://scicomp.stackexchange.com/questions/19481 )。

十分なトレーニングを行った後、ニューラル ネットワークは適切に機能しますが、自分で作成したヒル クライミング アルゴリズムが完全ではない可能性があることに気づき、改善のための提案を探しています。特に、適応度評価関数の呼び出しを少なくして局所最適に到達できるでしょうか?

C# での単純なヒル クライミング アルゴリズムの例は Web にあまりないようです。.NET Math Library がありますが、何かにお金を払う必要はありません。

ヒル クライミング アルゴリズムは、ネットワーク内のすべての重みとすべてのバイアスに対して実行され、ネットワークをトレーニングします。複数のパスを実行します。バックプロパゲーションを調べましたが、これは 1 つのトレーニング例にのみ適用されるようです。トレーニング データには約 7000 の例があり、フィットネス関数はそれらすべてのネットワークの平均パフォーマンスを評価し、連続 (ダブル）スコア。

これが私の現在のコードです：

フィットネス関数は非常にコストがかかるため、できるだけ呼び出さないようにする必要があります。フィットネス関数の呼び出しを減らして局所最適に到達するための改善を探しています。局所最適に行き詰まることはあまり問題ではありません。ネットワーク内のさまざまな重みとバイアスの値に対してフィットネス関数をグラフ化しました。通常、グラフには 1 ～ 3 個の局所最適があるように見えます。ネットワークが数回のパスで同じ適合性を維持している場合は、この関数にパラメーターを追加して、ランダムな値からヒル クライミングを再開することを試みることができます。