問題タブ [simulated-annealing]

これまでに質問されたことがある場合は申し訳ありませんが、何を探しているのかよくわかりません。また、質問を正しく組み立てるためのドメイン知識が不足しているため、回答を見つけるのがかなり難しくなります。

とにかく、私はPythonで論文からシミュレーテッドアニーリングアルゴリズムを実装しようとしています（IBM J. Res。Dev。、2001; 45（3/4）; 545）。著者は、C ++で実装したアルゴリズムの概要を明確に示していますが、定義の最後に次のように述べています。

「繰り返される潜在的に高価なメモリ割り当てを回避するために、SとS *は、好ましくない突然変異の後に初期状態に戻ることができる単一のオブジェクトとして実装されます。」

（SおよびS *は、最適化されているものの元の状態と段階的に変更された状態を表します）。

以前のより単純なバージョンでは、各状態を保持するために2つのリストを使用しましたが、彼のコメントは、そのようなアプローチはメモリ効率が悪いことを示唆しているようです。したがって、私の質問は次のとおりです。

1. 彼のコメントはC++固有であり、Pythonでは引き続きリストを使用でき、心配する必要はありませんか？
2. それについて心配する必要がある場合、どのPythonデータ構造を使用する必要がありますか？元の属性と変更された属性、および変更を行うためのメソッドを使用してクラスを定義するだけですか、それとも他に何か足りないものがありますか？
3. 私はまだ2つの状態が必要なので、クラスでそれをラップすると、クラス表現をよりコンパクトにするためにメモリが割り当てられる方法が変わりますか？

以下の質問は、特にバイオテクノロジーアプリケーションに適用されますが、他の分野での同様の問題の一般的な原則を示している場合があります。これは巡回セールスマン問題に関連する可能性のあるNP困難な問題であり、解決策に到達するためにどのアルゴリズムを使用できるのか興味があります。

簡単な生物学的背景：タンパク質は20個のアミノ酸で構成されています。DNAは4つの塩基（A、C、G、T）で構成されています。タンパク質のDNA配列によって、アミノ酸の配列が決まります。3つのDNA塩基（単位はコドンと呼ばれます）の連続する各配列は、1つのアミノ酸をコードします。単一のアミノ酸は複数のコドンでコード化できます。たとえば、バリンには4つのコード化方法があります。

すべてのコドンが等しくなるわけではありません-それらのいくつかは他より速く処理されます。また、すべてのコドンペアが等しくなるわけではありません-いくつかのペアは他のペアよりも遅いです。

これは、100アミノ酸（300 DNA塩基）の特定の遺伝子について、同じアミノ酸配列をコード化する多くの方法がありますが、処理速度などの非常に異なる特性を持つことを意味します。

対応する速度値を持つコドンペアのテーブルが与えられた場合、希望する速度のシーケンス、たとえば可能な限り速いシーケンスと最も遅いシーケンス、およびその間の勾配を出力できるアルゴリズムを記述したいと思います。入力は、遺伝子をコードするDNA配列、およびコドンペアとそれぞれの速度スコア（-1から1）の辞書です。出力は、最適化されたDNA配列とその全体の速度スコア（すべてのコドンペアスコアの合計として表すことができます）です。アミノ酸配列は同じままでなければなりません。

例：3つのアミノ酸をコードする配列AAATTTGGGがあり、スコアのあるコドンペアがある場合：

AAATTT = -0.5

TTTGGG = -0.5

この場合、このシーケンスのスコアは-1になる可能性があります。

ペアの選択肢もある場合は、さまざまな可能性を評価できます。

AAATTG = -0.7 AAATTC = -0.3

TTGGGC = +0.2 TTCGGA = -1.0

この情報に基づく最適なシーケンスは、全体の値が-1.3になるため、AAATTCGGAであることがわかります。

もちろん、この問題の複雑さは、周囲のすべてのコドンペアに対するコドンペアの影響にあります。

完全なコドンペアチャートには61*61のエントリがあります（3つのコドンが遺伝子の読み取りを停止するため）。

====

質問

これはNP困難な問題であり、TSPと関係があると思います。シミュレーテッドアニーリングアルゴリズムを使用するアプローチを見てきました。この問題とそれに対応するアルゴリズムおよびヒューリスティックを考慮して目的の出力を生成する他の洞察に満ちた方法があるかどうか知りたいです。

動的計画法の場合、どのようなアプローチが適切でしょうか？

また、アルゴリズムを使用して、最大値と最小値だけでなく、速度スコアの勾配を作成するにはどうすればよいですか？

C++ でアルゴリズムを作成して、モンテカルロ法を使用して球面上の相互に反発する点をシミュレートする必要があります。これまでのところ、私が持っているのはこれです:

私は大丈夫だと思います（私は基本的にエネルギー関数を最小化しようとしていることに注意してください）が、より正確にしたり、より速く実行したりしたいと考えています。そのためには、p の値、while ループ条件、またはコードの最後で p を変更する方法を変更する必要があると思います。(これらはすべて * ... *に含まれています。これは、私が意味するところを明確にするためにそれらを大胆にしようとしていたためです。コードの約 3/4 まで)。私はこれらの条件を変えようと何時間も座っていましたが、何も機能していません. n=12 (球上の 12 ポイント) の場合、私のエネルギーは 49.16525306 になるはずですが、実際には 50.5 から 54.0 の間しか得られません。これが比較的良いことはわかっていますが、もっと正確にしたいです (時間がかかるとしても)。また、可能であれば成功率を上げたいと思っています (私の全体的な成功率は絶対に恐ろしいものです)。

誰かが何かアイデアを持っているなら、私はあなたの助けにとても感謝しています!

ありがとう、A.

(注: コードを実行する場合は、二重の * を削除する必要があります。二重の * で囲まれた 4 つのセクションがあります)。

「数値レシピ」の著者は、Ch。図１０は、「古典的な」シミュレートされたアニーリングをネルダー・ミードダウンヒルシンプレックス法と組み合わせたシミュレートされたアニーリングアルゴリズムの実装である。

このアルゴリズムで私が本当に気に入っているのは、アニーリング温度が 0 に達すると、古典的な下り坂の検索に収束する方法です。ただし、このアルゴリズムに関する他のリファレンスは見つかりませんでした。それは、シミュレーテッド アニーリング アルゴリズムの安全で成熟した変種 (すなわち、生産準備完了) ですか、それとも本に投げ込まれた実験的なアイデアと見なすべきですか?

私は、特定の条件下では正常に再帰し、他の条件下では確率e ^（E / Temperature）で再帰する必要がある再帰検索関数を設計しています。特定の確率で何かを実行する方法がわからないため、再帰的な手順を除いてすべてのコードが実行されます

n クイーン問題を解決するためのシミュレーテッド アニーリング アルゴリズムに問題があります。基本的に、私はもっと良いものを探すようにしていますが、それは問題なく機能しますが、式を実行して、「悪い」動きをするべきかどうかを確認します。私の理解では、式は e^(ボード状態の計算の変化)/CurrentTemperature です。この数値は、ランダムな double または float と比較する必要があります。乱数が方程式よりも大きい場合、アルゴリズムは「悪い」動きを取る必要があります。私が得ている問題は、式が常に1に近いか1を超えていることです。ここに私のコードの一部を示します(さらに提供する必要がある場合はお知らせください):

調べる変数を負にしたり、ボードの状態間の差の絶対値を取得したりするなど、多くのことを試しました。また、呼び出されている計算関数は基本的にボードをスキャンし、競合しているクイーンの数を int で返します。さらに説明が必要な場合はお知らせください。ありがとう

シミュレーテッド アニーリング アルゴリズムでエネルギー変数は何を表しますか? GAのフィットネス変数に似ていると思いますか？

私は暗号解読の問題を解決するためにシミュレーテッドアニーリングを使用していますが、レンガの壁にぶつかりました。私は一生の間、確率関数を正しく動作させることができません。それは、より悪い解を頻繁に取るか（0.03と0.2のスコアで跳ね返る）、または十分に頻繁にかかりません（したがって、行き詰まります）。 0.35）。私はインターネットを見回しましたが、問題が最小値を見つけることを含む例にしか出くわしません....私の問題は最大値を見つける必要があります。最低スコアは0、最高は1です。

温度と使用する確率関数についてアドバイスが必要です。

TSP のコスト関数はどのように機能しますか? 距離が 100 のツアーがあり、元のツアーに 4 つの変更を加えてツアーをわずかに変更し、距離が 50 になったとします。

変更の数なので、コスト関数は 4 を返します。または50、距離の変化のため？それとも、何かが欠けていて、どちらでもないのでしょうか?