問題タブ [simulated-annealing]

現在、以下の機能を最小限に抑えるために、Simulated Annealing パッケージ GenSA を使用しようとしています。

ここで、Cov_Mat は 4 つのアセットから取得された共分散行列で、v は次元 4 の重みベクトルです。

この方法でマーコウィッツの資産配分アプローチを解決しようとしています。すべての係数の合計が 1 に等しくなければならないなどの数学的制約を導入する方法を知りたいです。

さらに、GenSA関数に依存するつもりなので、制約で次のようなものを使用したいと思います:

私はこの論文で見つけました：http ://citeseerx.ist.psu.edu/viewdoc/download ?doi=10.1.1.97.6091&rep=rep1&type=pdfシミュレーテッドアニーリングアルゴリズム内でそのような制約を処理する方法ですが、わかりませんRでどのように実装できますか。

アドバイスをいただければ幸いです。SO を使用するのは初めてなので、質問の仕方が間違っている場合は遠慮なく教えてください。

私はシミュレーテッド アニーリング (SA) と TSP の解決におけるその有効性に関する多くの文献を読んできました。これにより、SA を使用してsourcetodestinationパス検索だけを最適化できるかどうかを考えるようになります。

基本的な SA 疑似コード (wiki から)

これは解決策を表していますs0(つまり、私の場合は既にソース - 宛先パスを意味します)。私の質問は、最大フロー アルゴリズムまたはダイクストラを使用する以外に、これらの「解決策」をどのように生成するかです。

単純な重み付けニューラル ネットワークのコスト関数を解決するためにシミュレーテッド アニーリングを実装しましたが、奇妙な結果が得られます。

論理：

• Forward prop : f(W*x+b)、ここで、f = tanh、W = 重み行列、x = 入力データ、b = バイアス
• 重みとバイアスは、rnd ガウス重みを使用してランダムに初期化されます
• 重みとバイアスは W/norm2(W) & b/norm2(b) で正規化されます
• W を perturb as: W +/- rnd_unif[0,1] & b に対して同じことを行う
• MSE < 前の MSE が受け入れられる場合は、再び前方プロップ、そうでない場合はアニーリング基準を使用します
• n 番目の受け入れごとに温度を更新します。一般的な T=T*0.9 を使用

発生しているように見えるのは、ネットワークが予想どおりにコストを削減するということですが、一部のエラー予測では、MSE が「通常の」状態の MSE よりも低くなります。backprop では、エラーの MSE が常に高いことがわかります。他の誰かが同じ問題に遭遇したのではないかと思っていました。

問題:サイズ m*n の 2D グリッドをセット S の文字で埋めて、結果のグリッド内の個別のサブマトリックスの数が特定の数 k に近くなるようにする必要があります。この質問はhttp://www.codechef.com/JULY14/problems/GERALD09
から派生したものです

制限:
1<=n,m<16
1<=k <=m*n*m*n
|S|=4
制限時間=0.1 秒

仮定: 2 つのサブマトリックスは、次元が同じでない場合、または対応する位置の少なくとも 1 組の文字が一致しない場合、区別されます。

私のアプローチ:許容可能な解決策が見つかっている間、ランダムなグリッドとループから開始し、各反復で、現在の状態に応じてランダム性を増減できます (ただし、局所最適状態にとどまる可能性があります)。

しかし、問題は、サブグリッド内の異なるサブマトリックスの数を計算する効率的な方法がわからないことです。かなり高速なカウントのためにハッシュを試みました ( O(n ² m ² ) *生成/検索のコストサブグリッドのハッシュ値)。しかし、このアプローチはハッシュ値の衝突のために正確な答えを与えません.@Vaughn Catoのコメントを使用して修正した後でも、最適な状態を見つけるために15〜25回の反復を実行できますが、それでは十分ではありません.

最近、シミュレーテッド アニーリングを使用して、この種の問題を解決できることを知りました。
http://www.theprojectspot.com/tutorial-post/simulated-annealing-algorithm-for-beginners/6
この最適化問題を解決するための効率的なアプローチを探しています。

前もって感謝します。

巡回セールスマン問題などの問題を解決するためにシミュレーテッド アニーリングを使用しています。満足のいく解決策が得られましたが、解決策空間内のパス (つまり、アルゴリズムが解決策に到達するために取ったステップ) を知りたいと思います。 、最適な旅程から、かなり最適な旅程まで。

つまり、巡回セールスマン問題の場合は次のようになります。

• 都市間のランダムな旅程から始めます
• ステップ 1: 都市 AC と EF の間のパスが交換されました
• ステップ 2: 都市 GU と SQ の間のパスがスワップされました
• ...
• 都市間のかなり最適な旅程で終わる

シミュレーテッド アニーリングを使用して、最適化プロセスの各ステップを保存し、システムに加えられた各変更を 1 つずつたどって、最終的にその特定のソリューションにつながった方法はありますか? それとも、これはシミュレーテッド アニーリングの仕組みに反しますか?

これは、巡回セールスマンの例を使用してhttps://github.com/perrygeo/simanneal/blob/master/simanneal/anneal.pyから非常にわずかに変更された、@perrygeo による優れたシミュレーテッド アニーリング アルゴリズムです: https://github.com /perrygeo/simanneal/blob/master/examples/salesman.py (すべての変更の後に、""" で始まる 1 行のコメントが続きます)

移動が行われるたびに保存すると、実際に追跡可能なステップの膨大なリストが作成されます。ただし、特に高温で、アルゴリズムが解空間内のさまざまな位置を探索してジャンプする方法を明らかに模倣しています。

よりまっすぐに収束するステップを取得するには、ステップ節約ラインを移動できます。

下

これまでに見つかった最良のソリューションを実際に改善する手順のみが保存されます。ただし、ステップの最終的なリストは、旅程を再構築するのに役立ちません (ステップが欠落しています)。

この問題は絶望的で、シミュレーテッド アニーリングの仕組みに固有のものですか? それとも、ランダムから準最適への収束ステップ リストを構築できる希望はありますか?

私が解決しようとしたTSPに基づいて、Rubyにシミュレートされたアニーリングを実装しようとしています(このコードをJavaから変換しました)。しかし、アニーリングが私の結果を最悪にしていることが判明しました! (PlayerPath は、シミュレートされたアニーリングを実行するパスを提供します - 貪欲なアルゴリズム 1 を実行してパスを取得しました)。誰かがコードをチェックして、何か問題があるかどうかを確認するのを手伝ってもらえますか?それとも、シミュレートされたアニーリングが常に改善するとは限らないのですか?