コメントでこれを回答にするように依頼したので、以前の回答も自由に要約して、すべてを 1 か所にまとめました。「ペナルティ用語とは」という特定の質問に対する答えは、以下の項目 3 にあります。
標準的な遺伝的アルゴリズムの仕組みは、各「染色体」が問題の完全な解決策になるというものです。あなたの場合、提出されるジョブの注文。混乱は、そのスケジュール内の特定の仕事によるフィットネスへの個々の貢献がスケジュールの残りの部分によって異なるため、「動的」なものが必要であるという考えに集中していると思います. それは本当ではありません。GA の観点からは、適合性を持つ唯一のものはソリューション全体です。したがって、動的な問題とは、スケジュール全体の適合性が時間の経過とともに変化する可能性がある問題です。TSP に話を戻すと、動的問題とは、A、B、C、D、E の順に都市を巡って、実際に試行するたびに距離が異なるというものです。B を通るツアーの費用は、ツアーで B の前後にある都市によって異なりますが、それを決定すると、費用は静的であり、GA はツアー全体の費用しか受け取ることができないため、わかっているのは [ A,B,C,D,E] の適合度は一定です。動的な策略は必要ありません。
2 番目の質問は、TSP の例のように、セールスマンが特定の時間までにパリに着くようにする必要がある場合、どのように制約を処理するかということでした。通常、これを処理するには 3 つの方法があります。
彼が 2:00 より前に到着しないような解決策が生成されることを決して許可しないでください。これは簡単な場合もあれば、非常に難しい場合もあります。たとえば、制約が「彼は都市 X から始めることはできない」であった場合、X で始まらないソリューションを生成しないようにするのはかなり簡単です。ただし、多くの場合、有効なソリューションを単に見つけることは難しい場合があるため、このアプローチはそうではありません。本当にうまくいきます。
制約違反を許可しますが、後で修正します。TSP の例では、クロスオーバーとミューテーションによって可能性のあるツアーが生成されますが、それをスキャンして、彼がパリに到着するのが遅すぎないかどうかを確認します。もしそうなら、パリの位置をツアーの前の都市と交換してください。繰り返しになりますが、違反を修復する良い方法を見つけるのが難しい場合があります。
実行不可能な解の適合性にペナルティを課します。ここでの考え方は、彼がパリに遅すぎるのを防ぐことができず、もしそうならそれを直すことができないとしても、少なくともフィットネスを恣意的に悪化させることができるということです. TSP の場合、フィットネスはツアーの長さです。したがって、ツアーで彼がパリに到着するのが遅すぎる場合、フィットネスはツアーの長さ + 100 であると言うかもしれません。それで、解を母集団にとどめましょう (それ以外の場合は非常に良い可能性があるため、チャンスを与えたいと考えています)。その遺伝子の一部を渡すため)、しかし、選択と置換の方法により、適合度の値がより高い個体が選択されるため、選択される可能性が低くなります。
JSP の問題では、通常、makespan を最小限に抑えようとします。何らかの制約がある場合は、同じ 3 つのオプションを使用できます。しかし、私が知る限り、実際にはそのような制約はありません。進化的アルゴリズムが独自に考え出すのではなく、プロセスにあまりにも多くの知識を注入しようとしていると思います. つまり、ある仕事の配置が他の配置よりも優れていることを GA に伝えることについて、必ずしも心配する必要はありません。より良いフィットネスに高いフィットネスを割り当て、プロセスを収束させます。
とはいえ、このような情報を注入することは、多くの場合非常に良いことですが、最初に基本的なアルゴリズムをよく理解しておく必要があります。TSP の場合、適切なソリューションは、互いに近い都市を接続する可能性が高いことがわかっているとしましょう。GA内でその情報を使用する方法は、ランダムなソリューションを不均一に（おそらく貪欲なヒューリスティックで）生成することです。また、標準の交差アルゴリズムと突然変異アルゴリズムをカスタマイズしたものに置き換えることもできます。ミューテーションは通常、クロスオーバーよりも簡単にこれを行うことができます。TSP ソリューションを変更するには、接続されている 2 つの都市を選択し、接続を切断してから、それらを「より近い」再接続する方法を探す場合があります。つまり、ツアーが [A,B,C,D,E,F,G,H] の場合、エッジ [B,C] をランダムに選択してから、[F,G] などの別のエッジを探すことができます。 ]、[A、B、G、D、E、F、C、H]を取得するためにそれらを交差して接続すると、ツアー全体の長さが短くなるように。その突然変異を 1 ステップを超えて拡張することもできます。短いツアーが見つからなくなるまで、エッジを切断して再接続しようとするループを作成します。これは、ローカル検索とハイブリッド化された GA であるため、通常ハイブリッド GA と呼ばれるものにつながります。Memetic Algorithm と呼ばれることもあります。これらの種類のアルゴリズムは通常、ブラックボックス GA よりも優れています。これは、アルゴリズムに「ヒント」を与えて、良いと期待されることを試すようにバイアスをかけるためです。これは、ローカル検索とハイブリッド化された GA であるため、通常ハイブリッド GA と呼ばれるものにつながります。Memetic Algorithm と呼ばれることもあります。これらの種類のアルゴリズムは通常、ブラックボックス GA よりも優れています。これは、アルゴリズムに「ヒント」を与えて、良いと期待されることを試すようにバイアスをかけるためです。これは、ローカル検索とハイブリッド化された GA であるため、通常ハイブリッド GA と呼ばれるものにつながります。Memetic Algorithm と呼ばれることもあります。これらの種類のアルゴリズムは通常、ブラックボックス GA よりも優れています。これは、アルゴリズムに「ヒント」を与えて、良いと期待されることを試すようにバイアスをかけるためです。
このミームアルゴリズムのアイデアは、特定の仕事からのフィットネスへの貢献が他の仕事がスケジュールのどこにあるかに依存するという事実にどのように対処するかという最初の質問であなたが思いついたものにかなり近いと思います. ここでの唯一の障害は、これを「動的」と考えるのがやや不運だったことです。「動的」とは実際にはまったく異なるものを意味するためです。
まとめると、あなたの問題には「動的」なものは何もないので、動的な問題に対して人々が GA で行うことはまったく役に立たないでしょう。標準的な GA は、派手なトリックなしで機能します。ただし、どのスケジュールがより適切に機能するかについての情報を使用するというアイデアは、遺伝的演算子に導入することができ、おそらく大幅に優れた全体的なアルゴリズムになります。