0

学生とプロジェクトの特定の割り当てを最適化するために、シミュレーテッド アニーリング アルゴリズムを実行しています。

これは、Wikipedia の言語に依存しない疑似コードです。

s ← s0; e ← E(s)                                // Initial state, energy.
sbest ← s; ebest ← e                            // Initial "best" solution
k ← 0                                           // Energy evaluation count.
while k < kmax and e > emax                     // While time left & not good enough:
  snew ← neighbour(s)                           // Pick some neighbour.
  enew ← E(snew)                                // Compute its energy.
  if enew < ebest then                          // Is this a new best?
    sbest ← snew; ebest ← enew                  // Save 'new neighbour' to 'best found'.
  if P(e, enew, temp(k/kmax)) > random() then   // Should we move to it?
    s ← snew; e ← enew                          // Yes, change state.
  k ← k + 1                                     // One more evaluation done
return sbest                                    // Return the best solution found.

以下は、テクニックの適応です。私の上司は、そのアイデアは理論的には問題ないと言いました。

最初に、ランダム化された割り当てのセット全体からいくつかの割り当て (つまり、プロジェクトのランクを含む、学生と割り当てられたプロジェクトの辞書全体) を取得し、それをコピーして関数に渡します。この割り当てを呼び出しましょうaOld(辞書です)。aOldと呼ばれるそれに関連する重みがありwOldます。重み付けについては後述します。

この関数は次のことを行います。

  • この割り当てaOldをbest_node
  • すべての生徒からランダムな数の生徒を選び、リストに貼り付けます
  • それらのプロジェクトを削除 (DEALLOCATE) ++ プロジェクト (allocatedパラメーターは now False) と講師の変更を反映 (1 つ以上のプロジェクトが割り当てられなくなった場合はスロットを解放)
  • そのリストをランダム化する
  • そのリスト プロジェクトの全員を再度割り当て (REALLOCATE) してください。
  • 重みを計算します (ランクを合計します。ランク 1 = 1、ランク 2 = 2... およびプロジェクトなしのランク = 101)。
  • この新しい割り当てaNewでは、重みが最初に選択しwNewた割り当ての重みよりも小さい場合、これは (上記のアルゴリズムで定義された) です。アルゴリズムを適用して続行します。wOldbest_nodeSimulated AnnealingaNew
  • の場合wOld < wNew、アルゴリズムをaOld再度適用して続行します。

割り当て/データポイントは、「ノード」として表現されます。node = (weight, allocation_dict, projects_dict, lecturers_dict)

現時点では、このアルゴリズムは 1 回しか実行できませんが、数値 N (kmaxウィキペディアのスニペットでは で示されています) を試して、以前nodeの とbest_node.

元の辞書 (リセットしたいかもしれません) を変更しないように、辞書の浅いコピーを作成しました。ドキュメントで読んだことから、参照をコピーするだけのようで、辞書にはオブジェクトが含まれているため、コピーされた辞書を変更するとオブジェクトが変更されます。copy.deepcopy()これらの辞書は、SQLA でマップされたオブジェクトを参照します。

Questions:

私は直面している問題に対していくつかの解決策を与えられてきましたが、Python を使用することに対する私の環境への配慮のせいで、それらはすべて私にはやや不可解に聞こえます。

  1. Deepcopy は SQLA とうまく連携していません。ORM オブジェクトのディープコピーにはおそらく問題があり、期待どおりに動作しないと言われています。どうやら、「コピー コンストラクター、つまり def copy(self): return FooBar(....) を作成する」ほうがよいようです。誰かがそれが何を意味するのか説明してもらえますか?

  2. deepcopySQLAlchemy がオブジェクトに余分な情報を配置するため、問題があることがわかりました。つまり_sa_instance_state、コピーには入れたくないが、オブジェクトに必要な属性です。「古いものを手動で吹き飛ばして_sa_instance_state新しいものをオブジェクトに付ける方法はありますが、最も簡単なのは、新しいオブジェクトを作成して、__init__()重要な属性を設定することです。ディープコピー。」それは正確にはどういう意味ですか？古いマップされたクラスに似た、マップされていない新しいクラスを作成する必要がありますか?

  3. 別の解決策は、「オブジェクトに実装__deepcopy__()し、新しい _sa_instance_state が設定されていることを確認する必要があります。それを支援できる関数が sqlalchemy.orm.attributes にあります。」繰り返しますが、これは私を超えているので、誰かが親切にそれが何を意味するのか説明できますか?

  4. より一般的な質問：上記の情報が与えられた場合、best_node（whileループを通じて常に持続する必要がある）およびprevious_node実際のオブジェクト（辞書によって参照されるため、ノードの場合）の情報/状態を維持する方法に関する提案はありますか) が行われているため、割り当て解除/再割り当てが変更されていますか? つまり、コピーを使用せずに？

4

2 に答える 2

2

別の可能な解決策があります。トランザクションを使用します。これはおそらくまだ最善の解決策ではありませんが、実装はより高速になるはずです。

まず、次のようにセッションを作成します。

# transactional session
Session = sessionmaker(transactional=True)
sess = Session()

そうすればトランザクションになります。トランザクションが機能sess.commit()する方法は、変更を永続的にし、sess.rollback()元に戻すことです。

シミュレーテッド アニーリングの場合、新しい最適解を見つけたらコミットします。後でいつでも rollback() を呼び出して、ステータスをその位置に戻すことができます。

于 2010-06-07T05:49:29.963 に答える
0

そのようなsqlalchemyオブジェクトをコピーしたくありません。コピーを簡単に作成できる独自のメソッドを実装することもできますが、それはおそらく望ましくありません。データベースに学生やプロジェクトのコピーが必要ではありませんか？したがって、そのデータをコピーしないでください。

つまり、割り当てを保持する辞書があります。プロセス中は、SQLAlchemyオブジェクトを変更しないでください。変更できるすべての情報は、それらの辞書に保存する必要があります。それを考慮してオブジェクトを変更する必要がある場合は、最後にデータをコピーして戻します。

于 2010-06-06T07:24:41.920 に答える