問題タブ [simulated-annealing]

私は現在プロジェクト（TSP）に取り組んでおり、シミュレーテッドアニーリング擬似コードをJavaに変換しようとしています。私は過去に擬似コードをJavaコードに変換することに成功しましたが、これを正常に変換することはできません。

擬似コードは次のとおりです。

誰かがJavaでこれの基本的なマークアップを見せてくれたら、私は非常に感謝するでしょう-私はそれを理解できないようです！

私はいくつかの関数を使用して複数のクラスにまたがって作業しています（これは私が求めているものとは無関係であるため、リストしません）。私はすでにsmallChange()メソッドとfitness関数を持っています-上記のメソッドのさまざまなバージョンを作成する必要がある可能性はありますか？たとえば、私は次のようなものを持っています：

異なるパラメーターを受け入れるこのメソッドの別のバージョンが必要になる可能性がありますか？次のようなもの：

必要なのは、Javaで記述した場合にこれがどのように見えるかについての基本的な考え方です。正しい構文でどのように表示されるかがわかれば、コードに適応させることができますが、この特定のハードルを乗り越えることはできないようです。 。

私はシミュレートされたアニーリング プログラムの実装に取り​​組んでおり、その一部には、私の Java プログラムが読み取る .txt ファイルからスコアを計算することが含まれます。

1) 入力文字列がユーザーから読み取られます。入力文字列が長いほど、以下の例外が発生する可能性が高くなります

2) 計算されるスコアは、基本的に多くの 10 進数を追加するものであり、それを「double」変数に格納します。

なぜそのような例外が発生するのか、誰か教えてもらえますか?

Hill Swap のスコア: 0.24874990000000005 スワップ後... スレッド "main" での例外 java.lang.NumberFormatException: For input string: "7.92066E-" at sun.misc.FloatingDecimal.readJavaFormatString(FloatingDecimal.java:1224)

どうもありがとう！

この実際的な問題についてコメントをいただければ幸いです。

簡単な説明。 特定のベルト幅を構成するために使用できる可変数のリンクがあります。問題は、各リンクの数です。選択基準: より長いアイテムを使用することをお勧めします。

例。 ベルト幅 W = 1024.0 を作成したいとします。モデルの 1 つは、次のリンクの長さを持っています: L = [34.0, 65.0, 96.0, 126.0]

問題は、幅を作るために各リンクの数です。

ここに私が試したいくつかのアプローチがあります。

1. 貪欲 (条件を満たすために最長の最初のものを選択) c = [0,0,0,8] ここで、c は各項目のカウントです。これは 16.0 のギャップを残し、最小のアイテムの 1 つでも収まりません。貪欲は簡単ですが、良くありません。

2.選択ループ 簡単すぎず、難しい問題だと思います。私は多くの戦略を試しました。小さなアイテムを詰めてから、次のサイズに合わせて順番に削除します。

3. ナップザック方式 これはアイテム数が決まっているためあまり適切ではありません。

4. 部分和問題 これは Knapsack のサブクラスですが、私はそれを機能させることができませんでした。

5. Bin Packing problem 似ているように聞こえますが、私の問題には当てはまりませんでした。

6. ブルート フォース (ランダム選択) 奇妙なことに、これは多くの正確な一致を見つけます。カウントの単純な多項式を評価として使用します。rating = n[0] + n[1]* 2 + n[2] *3 + n[4]**4 + ... ブルート フォースからの解の 1 つは [4, 0, 4, 4] です。正確には 1024 です。問題は、この方法では異なる選択が行われることが多いため、理想的ではないことです。

7. 網羅的検索 選択肢が多すぎるため実用的ではありません。

8. シミュレーテッド アニーリング ブルート フォースの成功からすると、これは良い代替手段のように見えます。誰かが簡単な例を教えてくれませんか (別の巡回セールスマンはやめてください)。

9. 遺伝子群と粒子群 これらについては不明です。

今、私は立ち往生してイライラしています。この問題に使用できる直接アルゴリズムはありますか?

タイムテーブルアプリケーションを開発しています。遺伝的アルゴリズムとシミュレーテッドアニーリングの相対的な利点は何ですか？

私の状況に固有のポイントは次のとおりです。

1. 一度に最大（3人の教師×6時間）×（3クラス×週35時間労働）を割り当て、タイムテーブルを繰り返し作成しています。

2. 不可能な状態が発生し、アプリケーションがスタックすることなく、不可能なタイムテーブルを通知する必要があります。このアプリケーションは限界に達すると予想されます。

3. 一定時間で結果を返すか、失敗したことを報告する必要があります。

「Drools Planner」パッケージを使用して、部分的に初期化された数独パズル (新聞に掲載されているようなもの) を解こうとしていました。3 秒でゼロから(ランダムな) パズルを生成できますが、部分的に初期化されたパズルを解くループに陥ります。

質問: タブー検索やシミュレートされたアニーリングなどのヒューリスティックは、数独にとって基本的に悪い選択ですか? 私が話しているのは、完全性 (解決策に到達するかどうか) と効率性 (やり過ぎかどうか) です。

私の疑問は、数独パズルには常に正確で単一の解決策があり、ヒューリスティックアルゴリズムは（AFAIK）「それらに到達する」ように設計されていないという事実から来ています。

焼きなまし法の基本的な考え方は理解できたと思います。基本的には、最初に検索スペースのより良い領域をカバーするためにランダムなソリューションを追加し、アルゴリズムの実行を継続するにつれてランダム性を徐々に減らします。

これを遺伝的アルゴリズムに実装する方法について少し混乱しています。

誰かが私がする必要があることの簡単な説明を私に与えて、シミュレーテッドアニーリングがどのように機能するかについての私の理解が正しいことを明確にすることができますか？

Javaで実装されたGSATおよびSA-SATアルゴリズムを探しています。誰かがそれについて知っていますか？ありがとうございました。

私が取り組んでいるプロジェクトの一部としてランダム突然変異山登りアルゴリズムを使用しましたが、局所最適点でスタックする可能性を最小限に抑えるためにシミュレーテッドアニーリングを使用する方がよいかどうか疑問に思いました。

私が持っている質問は、あなたの経験から一般的にどちらが速い傾向があるかということです。明らかに、両方のアルゴリズムには非常に豊富なアプリケーションがあります。必要に応じて、これはより一般化された熟考です。

ありがとうございました。

シミュレーテッドアニーリングアルゴリズム（Java）を、作業中の個人プロジェクトに適用しましたが、別の言語（C ++、Pythonなど）で記述した場合、SAアルゴリズムのパフォーマンスが同じデータセットでわずかに向上するかどうか疑問に思いました。

私が作成したダミーのデータセットは、5,000人のユーザーの名前、郵便番号、生年月日で構成されています。

SAアルゴリズムは、さまざまな情報を抽出するためにデータセットに適用されます。

現在、私の最新のテストでは、SAアルゴリズムを取得して、生年月日が互いに1週間以内（任意の年）にあるすべてのユーザーを検出しようとしています。現在、SAアルゴリズムは実際に非常にうまく機能します。しかし、私は完璧主義者なので、少し速い結果を達成したいと思います。同じサイズのデータ​​セットで優れた結果を生成するが、他の言語で書かれたSAで良い経験をした人がいるかどうか知りたいですか？

現時点では、SAアルゴリズムが検索を成功させるのに5秒弱かかります。

ソリューションをランダムに生成し、そのソリューションをコピーして少し変更して、最終的により良いソリューションになるかどうかを確認するヒル クライミング アルゴリズムを作成しました。その場合、新しいソリューションを保持し、古いソリューションを破棄します。

このアルゴリズムにシミュレートされたアニーリングを追加したい場合は、高い突然変異率から始めて、新しいソリューションが作成されるたびに突然変異率を少しずつ下げることはできますか?

その場合、突然変異率はシミュレーテッド アニーリング アルゴリズムの温度として機能すると思いますが、それは正しいですか?