4

私は大学のスケジューリング問題に取り組んでおり、これには単純な遺伝的アルゴリズムを使用しています。実際には、それはうまく機能し、0％から90％（約）まで1時間の目的関数値を最適化します。しかし、その後、プロセスは劇的に遅くなり、最良の解決策を得るのに数日かかります。他のアルゴとジェネティックアルゴを混ぜるのが合理的であるという論文をたくさん見ました。どのアルゴリズムを遺伝的アルゴリズムと混合できるか、そしてこのアルゴリズムをどのように適用して解決プロセスをスピードアップできるかについて、アドバイスをお願いします。主な問題は、このような複雑な構造の問題にヒューリスティックをどのように適用できるかということです。たとえば、貪欲なヒューリスティックなど、そこでどのように適用できるかわかりません。

よろしくお願いします！本当にあなたの助けに感謝します！

問題の説明：

  1. 私は持っています：

    • ScheduleSlotオブジェクトで埋められた配列
    • レッスンオブジェクトで埋められた配列

  2. そうです：

    • スタンダート2点クロスオーバー
    • 突然変異（ランダムなレッスンをランダムな位置に移動する）
    • 大まかな選択（次の母集団に対してn人の最良の個人のみを選択）

@Dougalと@izomorphiusの追加情報：
私は大学のスケジュールを作成しようとしています。これにより、グループや教授向けのレッスン、重複、地理的に分散したレッスンの間に休憩がなくなります。
適応度関数は本当に単純です：fitness = -1000 * numberOfOverlaps-1000 * numberOfDistrebutedLessons-20*numberOfBreaks。（またはそのようなもので、変数の前の係数を単純に変更できます）
非常に最初に、ランダムな部屋、時間、曜日にレッスンを配置するだけで個人を生成します。
上記のように、突然変異とクロスオーバーは本当に些細なことです。

  1. クロスオーバー-親のスケジュールを取得し、クロスオーバーのポイントと範囲をランダムに選択し、親のスケジュールの一部を交換するだけで、2つの子のスケジュールが生成されます。
  2. 突然変異-子のスケジュールを取り、n個のランダムなレッスンをランダムな位置に移動します。
4

2 に答える 2

4

私の最初の観察：あなたはの前の係数をnumberOfOverlaps、numberOfDistrebutedLessonsそしてnumberOfBreaksいくぶんランダムに選択しました。私の経験では、通常、これらの選択肢は最善ではないため、コンピューターに選択させる方がよいでしょう。私はそれらを選択するために2番目のアルゴリズムを書くことを提案します-ニューラルネットワーク、2番目の遺伝的アルゴリズムまたは山登り法である可能性があります。アイデアは-一定の時間が経過した後にどれだけ良い結果が得られるかを計算し、これら3つの値の選択を最適化しようとすることです。

別のアイデア：結果を取得した後、ブルートフォースで最適化しようとする場合があります。つまり、最初の問題が発生した場合、「愚かな」解決策はすべての可能性をチェックするバックトラックであり、これは通常dfsを使用して行われます。これは非常に遅くなりますが、反復深化を伴う深さ優先探索、または単に深さ制限されたDFSを使用してみてください。

于 2012-04-30T06:41:05.900 に答える
0

多くの問題について、ローカル検索を GA アルゴリズムに組み合わせたラマルク式の GA がうまく機能することがわかりました。

あなたの場合、ローカル検索として部分的な系統的検索を導入しようと思います。これを行うには 2 つの明白な方法があり、おそらく両方を試す必要があります。

  1. GA の反復とローカル検索の反復。たとえば、ローカル検索では、他のすべてを変更せずに、1 日に割り当てられたすべてのレッスンをブルート フォースすることができます。もう 1 つの可能性は、ランダムに選択されたレッスンをすべての空きスロットに移動して、最適な選択を見つけることです。重要なのは、ブルートサーチのコストを最小限に抑えながら、局所的な改善を見つける機会を維持することです。

  2. ローカル検索を実行するミューテーションとクロスオーバーに加えて、新しい演算子を追加します。(突然変異演算子はハイブリッド スキームではあまり役に立たないことがわかるかもしれません。そのため、それを置き換えるだけで実行可能になる可能性があります。)

本質的に、GA のグローバル探索と効率的なローカル検索を組み合わせます。いくつかの GA フレームワークには、この組み合わせを支援する機能が含まれています。たとえば、GAULは上記の代替スキーム 1 を実装し、反復ごとに完全な母集団または新しい子孫のみを使用します。

于 2012-12-19T10:38:51.453 に答える