私は、学生向けのこの一般的な割り当てアルゴリズムに取り組んできました。
その擬似コード (Python 実装) は次のとおりです。
for a student in a dictionary of students:
for student preference in a set of preferences (ordered from 1 to 10):
let temp_project be the first preferred project
check if temp_project is available
if so, allocate it to him and make the project unavailable to others
break
簡単に言えば、これは最も優先度の高いものから始めてプロジェクトを割り当てようとします。仕組みとしては、たとえば 100 個のプロジェクトのセットから、やりたいことを 10 個挙げます。したがって、10 番目のプロジェクトは「全体的に最も好ましくない」ものではなく、選択したセットの中で最も好ましくないものであり、それほど悪くはありません。
明らかに、プロジェクトを割り当てることができない場合、学生はランク 11 のなしの割り当てである基本ケースに戻ります。
私がやっているのは、ランクの加重合計に基づいて割り当ての「品質」を計算することです。したがって、数値が低いほど (つまり、優先度の高いプロジェクト)、割り当ての質が高くなります (つまり、より多くの学生が優先度の高いプロジェクトを持っています)。
それは基本的に私が現在持っているものです。シンプルで機能します。
現在、割り当ての重みをローカルで最小化しようとするこのアルゴリズムに取り組んでいます (この疑似コードは少し面倒です。申し訳ありません)。
これがおそらく機能する唯一の理由は、私の「検索スペース」がそのままでは特に大きくないためです (非常に一般的で、逸話的な観察にすぎません)。プロジェクトは私の部門にのみ固有のものであるため、独自の制限が課せられています。したがって、学生の数は 100 人を超えることはできず、好みの数は 10 を超えることはありません。
for student in a dictionary/list/whatever of students:
where i = 0
take the (i)st student, (i+1)nd student
for their ranks:
allocate the projects
and set local_weighting(N) to be sum(student_i.alloc_proj_rank, student_i+1.alloc_proj_rank)
these are the cases:
if N is 2 (i.e. both ranks are 1):
then i += 1 and
and continue above
if N > 2 (i.e. one or more ranks are greater than 1):
let temp_N be N:
pick student with lowest rank
and then move him to his next rank
and pick the other student and reallocate his project
temp_N is sum of the the ranks
if temp_N is < N:
then allocate those projects to the students
i += 1
and move on for the rest of the students
コメントに関して更新：
私がやろうとしていること:
一度に 2 人の生徒のグループ間 (つまり、ローカル) で「最小の重みの割り当て」を達成しようとしています。
重み付けの割り当ては、学生によって割り当てられたランクの合計です。生徒には、全体で最高ランクのプロジェクトを取得してもらいたいと考えています。したがって、学生 A がランク 1 のプロジェクトを取得し、学生 B がランク 5 のプロジェクトを取得した場合、ローカル割り当ての重みは 6 になります。学生 A をランク 2 のプロジェクトに移動すると、結果として学生 B は彼女のランクに移動します3 プロジェクトの場合、重みは 5 になりました。5 < 6 で、全体的に優れています。
したがって、私は学生のコレクションから始めて、それらを反復し始めます
1 人目と 2 人目の生徒から始めて、プロジェクトを割り当てます
次に、上記のように重量を計算します。重みがランキングに等しいとすると、両方がランク 1 の場合、重みは 2 です。
ここで、重みが 2 より大きい場合、1 つまたは複数のプロジェクトが 2 より大きいランク付けされていることを示し、より良いバージョンを取得しようとします。
したがって、ランクが最も低い生徒を取り上げて、その生徒を 1 ランク下げます (その生徒がランク 1 だった場合、ランク 2 に移動します)。
そして、他の学生を別のランクに再割り当てしようとします。
重みが以前の重みよりも優れている場合は、それを新しい重みとし、それらのプロジェクトを彼らに持たせます。それより悪いか等しい場合は、次の学生のデュオに進みます.
地元では、学生の場合、このことは最小重量に達し、それ以上うまくいかなくなるまで試行を続けます.
これで私がやろうとしていることを説明できますか？
だから、質問：
これはシミュレートされたアニーリングの一種の修正ですが、これに関するあらゆる種類のコメントをいただければ幸いです。
どの生徒が (i) で、どの生徒が (i+1) であるかを追跡するにはどうすればよいですか?
学生の全体的なリストが 100 である場合、(i+1) = 101 は何もないため、混乱します。どうすればそれを回避できますか?
すぐに発見できる欠陥はありますか?
追加情報:
私の学生辞書は次のように設計されています。
students[student_id] = Student(student_id, student_name, alloc_proj, alloc_proj_rank, preferences)
where preferences is in the form of a dictionary such that
preferences[rank] = {project_id}