PDC や TechED などの大きなイベントのセッションを計画するためのアルゴリズムが必要な Mike Swanson のビデオを見ました。解決策を表す最良の方法は何かを考えています。彼のアプローチは非常に単純です。インデックスをタイムスロット ルームにマップする配列があり、ソリューションは、これらのインデックスのリストを含む単純な配列であり、各タイムスロット ルーム要素は、選択後に配列から削除されます。
たとえば、3 つのタイムスロットと 3 つの部屋がある場合、これはタイムスロット + ルームをマッピングする配列です:
0: タイムスロット 0、ルーム 0
1: タイムスロット 0、ルーム 1
2: タイムスロット 0、ルーム 2
3: タイムスロット 1、ルーム 0
4:タイムスロット 1、ルーム 1
5: タイムスロット 1、ルーム 2
6: タイムスロット 2、ルーム 0
7: タイムスロット 2、ルーム 1
8: タイムスロット 2、ルーム 2
9 つのセッションがスケジュールされているとします。サンプル ソリューションは 5,5,2,1,2,3,1,1,0 であり、
セッション 0、タイムスロット 1、ルーム 2
セッション 1、タイムスロット 2、ルーム 0
セッション 2、タイムスロット 0、ルーム 2
セッション 3、タイムスロット 0、ルーム 1
セッション 4、タイムスロット 1、ルーム 1
セッション 5、タイムスロット 2、ルーム 2
セッション 6、タイムスロット 1、ルーム 0
セッション 7、タイムスロット 2、ルーム 1
セッション 8、タイムスロット 0、ルーム 0
（はっきりしない場合は、ビデオの25:30で非常に明確に説明しています）
さて、私は遺伝的アルゴリズムの経験が少しあり、間違っていたら訂正しますが、個人を交差させて突然変異させることによって生成されるソリューションは、それを生成したソリューションと似ている必要があると常に思っていましたか? つまり、2 つの解の間でクロスオーバーを行う場合、生成された解は、それを生成した解と非常に似ている必要があります (また、突然変異についても同様です)。これが進化の仕組みではないでしょうか。マーク・スワンソンが解決策を表現する方法は、それを考慮していないようです。
例えばクロスオーバーの場合
親 1: 5,5,2,1,2,3,1,1,0
親 2: 0,0,0,0,4,3,2,1,0
子: 5,5,2,1,4,3,2,1,0 (クロスオーバー インデックスはこの場合 4)
この子には、親 1 と共通する遺伝子が 4 つ、親 2 と共通する遺伝子が 5 つあります。親 2 との共通点はほとんどありません。これは問題ではありませんか?
今回の突然変異の別の例:
突然変異前: 5,5,2,1,2,3,1,1,0
突然変異後: 0,5,2,1,2,3,1,1,0
この小さな変更により、実際の最終ソリューションで 9 つの変更のうち 6 つが発生しました。
私が提起したこれらのことは実際の問題ですか？それとも、遺伝的アルゴリズムがとにかくうまく機能するので、問題ではありませんか? これらが問題である場合、より良い解決策を提案できますか?
もう 1 つの質問は、セッションを複数回スケジュールする必要がある場合はどうすればよいかということです。その場合の解決策をどのように表しますか？
どんな助けでも大歓迎です。
ありがとうございました！