問題タブ [simulated-annealing]

シミュレーテッド アニーリングを使用して、また力ずくで TSP を解決する簡単な作業を行いました。ブルート フォースによる TSP は、考えられるすべてのパスをチェックすることで O(n!) ステップを実行することがわかっているため、シミュレーテッド アニーリング アルゴリズムを使用してこれらの多くのステップを許可した場合、正しい解にたどり着くことができるかどうかを尋ねたいと思います。(反復回数が少ないと次善の解が得られることが保証されていますが、私の質問は、n! 回実行すると最適な解が得られるかどうかです。ここで、n は都市の数です)

(x-2)^2+(y-1)^2ある範囲で最小化するために、C++ でシミュレートされたアニーリングを実装しました。

このタイプのヒューリスティック手法では受け入れられないさまざまな出力が得られます。解は収束しているように見えますが、解に完全に近づくことはありません。

私のコード:

どうすれば解決にたどり着くことができますか？

次のリソース割り当て/スケジューリングの問題に適した決定論的アルゴリズムはどれですか?

P1、P2、P3、および P4 のプレーヤーのセットを考えてみましょう。各プレーヤーは、携帯電話基地局からデータを受信します (ワイヤレス ネットワークなど)。タワーは 1 秒のブロックでデータを送信します。5ブロックあります。各プレーヤーは、任意の数のブロックでデータを受信するようにスケジュールできます。

ここで、各ブロックで受信されるデータの量は、定数 (C) を同じブロックでスケジュールされている他のプレイヤーの数で割ったものになります (帯域幅を共有する必要があるため)。貪欲なアプローチでは、各プレーヤーを各ブロックに割り当てますが、ブロックごとに受信されるデータは減少します。

ネットワークによって配信されるデータの量が最大になるように、プレーヤーの時間ブロックへの割り当てをどのように見つけることができますか? 私はこの問題に対していくつかのヒューリスティックな方法 (遺伝的アルゴリズム、Sim Anneal) を試しましたが、うまくいきました。ただし、最適なスケジュールを解決したいと考えています。

この問題に取り組むための新しい方法として、シミュレーテッド アニーリングを学ぶことにしました。基本的に、各行と列の合計が一意になるように、グリッドを -1、0、または 1 で埋める方法を尋ねます。テスト ケースとして、6x6 グリッドを使用しました。これには、Neil によって与えられた最適なソリューションが確実に存在します。

私のコードは通常、実行の大部分で最適なケースに到達せず、間違ったグリッド コストを返します (old_cost一致する必要がありますcount_conflict(grid))。パラメーターが正しく設定されていないか、実装が間違っているか、またはシミュレートされたアニーリングが実行可能な方法ではない可能性がありますか?

遺伝的アルゴリズムの作成に成功したので、現在、 GA と比較するためのシミュレートされたアニーリング プログラムを作成していますが、グローバルなものを気にせず、どのような種類の最適化にも到達できないようです。

少しテストした後、問題は変数を while ループに戻すことだと思います。テストの目的で、基本的に前のソリューションよりもエネルギー デルタが低いソリューションのみを受け入れるようにコードを変更したので、最適なソリューションを格納する変数はより低い数値しか表示しないことを期待する必要がありますが、実際には変動し、常に最も多くの値を返します。それが良いかどうかにかかわらず、最近の解決策。どんな助けでも大歓迎です。

Python(2.7)のデフォルト(Mersenne Twister)のrandom()関数をKernighan–Linアルゴリズムの乱数ジェネレータとして使用することは(生成される数値の品質と必要なCPU時間の観点から)良い考えですか? それを行うより良い方法はありますか？

また、同じコンテキストで、random() 関数は、シミュレーテッド アニーリング アルゴリズムで 0 から 1 の間の数値を生成するためにどのように機能しますか?

この質問は、Encog リポジトリで取得したC# の Lunar Lander Exampleを参照したものです。例が示すように、NeuralSimulatedAnnealing を使用して多層フィードフォワード ネットワーク (50 エポック) をトレーニングしています。

_

この例はうまく機能し、ニューラル パイロットは与えられた条件で宇宙船を着陸させる方法を正確に学習しますが、私はそれをさらに活用したいと考えています。

そのために、以下のようなグローバル クラスを作成し、LanderSimulator クラスの行も変更しました。

_

これで、 fuelConsumption変数に応じて、推力ごとに燃料が消費されます。次に、fuelConsumption の 3 つの異なる値を試してみました。以下は、個々のネットワークのそれぞれの最高スコアです。

これらのネットワークを相互にテストしたところ、結果は期待外れでした。

• ネットワーク 1 は、fuelConsumed がそれぞれ 5 と 10 のときに -39591 と -39661 のスコアを示しました。
• ネットワーク 2 は、fuelConsumed が 1 と 10 の場合、それぞれ -8832 と -35671 のスコアを示しました。
• ネットワーク 3 は、fuelConsumed が 1 と 5 の場合、それぞれ -24510 と -19697 のスコアを示しました。

そこで、以下のように 3 つのシナリオすべてに対して 1 つのネットワークをトレーニングしようとしました。

しかし、結果は再び同じです

3 つのシナリオすべてで最高のスコアを提供するニューラル パイロットを作成するにはどうすればよいですか?

編集：これはここですでに回答されているようです

正しい命名法を知らなかったため、検索に表示されませんでした。制約のために誰かがここに到着した場合に備えて、ここで質問を残しておきます。

ほとんどすべてのポイントでフラットな関数を最適化しようとしています(「ステップ関数」ですが、より高い次元にあります)。

目的は、合計が 1 になる必要がある一連の重みを最適化することであり、最小化する必要がある関数のパラメーターです。

問題は、関数がほとんどの点でフラットであるため、勾配法は最初の「推測」にすぐに収束するため失敗することです。

私の仮説は、これは (a) アニーリングまたは (b) 遺伝的アルゴリズムで解決できるというものです。Scipy は私をbasinhoppingに送ります。ただし、scipy を使用して制約 (重みの合計が 1 になる必要があります) または範囲 (重みは 0 から 1 の間でなければなりません) を使用する方法が見つかりません。

実際の質問: 最小化問題を勾配なしで解き、入力変数に制約と範囲を使用するにはどうすればよいですか?

以下はおもちゃの例です (明らかに、これは勾配を使用して解決できます)。

[ http://www.cleveralgorithms.com/nature-inspired/physical/simulated_annealing.html][1]で与えられた Ruby コードを変換して、シミュレーテッド アニーリングを使用して巡回セールスマン問題を解決しようとしましたが、どちらのコードも問題なく実行されました。バグ。ただし、同じ問題のインスタンス (TSPLIB の berlin52) では、両者のパフォーマンスが異なることがわかりました。通常、Ruby コードは 9000 から 10000 の間で最適な解を得ますが、Java コードは 16000 から 17000 の間で最良の解を得ます。調べてみましたが、ありませんでした！前もって感謝します。

ルビーコード:

Java コード: