遺伝的アルゴリズム:リクエスト最適化
-
10-10-2019 - |
質問
私は遺伝的アルゴリズムを初めて使用しており、薬局の平日のリクエストの順序を最適化するために遺伝的アルゴリズムを実装するように割り当てられています。まず第一に、問題を説明させてください:
週(月曜日から金曜日)の任意の日に出席するリクエストを発行する9つの家族がいます。薬局は1日あたり1〜3家族しか参加できず、これも同じ週に家族を繰り返すことができません。主な目標は、各家族が参加するのに最適な日を最適化することです。そのようにして、薬局は問題に課された制約を伴う週あたりの最大要求に参加することです。最適化アルゴリズムへの入力は、各ファミリが発行したリクエストの各数の年間平均です。例えば:
(例を簡素化するために、3つの家族のみと協力しましょう):
入力:
|月|火|水|木|金
f1 | 10 | 20 | 2 | 0 | 7
f2 | 20 | 12 | 0 | 1 | 2
f3 | 2 | 0 | 0 | 19 | 3
可能な解決策:
|月|火|水|木|金
| | f2 | f1 | f3 |
これまでのところ、私は遺伝学と遺伝的アルゴリズムの概念全体を研究してきました。私は粒子の群れの最適化を調べましたが、私の時間はかなり短いので、フレームワークを使用することにしました。私はJGAPを使用していますが、私の主な問題は、潜在的なソリューションをどのように提示するかということです。つまり、交尾、繁殖などに使用されるクロモッサム上の遺伝子をどのように組織する必要がありますか...?私はすでにフィットネス関数を開発しましたが、私が望む方法で遺伝子をエンコードすることはできません。助言がありますか?
解決
どのように潜在的なソリューションを提示しますか?
すべての家族は1日にスケジュールされるべきです。そのため、各家族が予定されている日に保管できます。遺伝子は5日間の1つであり、クロムはこれらの9つ、家族ごとに1つあります
1 2 3 4 5 6 7 8 9
Chrome M T T F W H T M T
そのため、月曜日の家族1、火曜日に家族2と3など。他のすべての制約を課す必要があります(The pharmacy can only attend 1 to 3 families per day
)フィットネス関数。
別のエンコーディングはそうかもしれません
M1 M2 M3 T1 T2 T3 W1 W2 W3 ... F2 F3
1 2 - - 5 - 9 - 3 ... 4 -
したがって、可能なすべての予定を取り、家族を埋めるか、それらを空にしておくでしょう。この場合、フィットネス関数は、すべての家族がちょうど1つの予約を持っていることを確認する必要があります。