genetic-algorithm - ヒューリスティックのバランスをとる (時刻表問題用)

Question

タイムテーブルを生成するための遺伝的アルゴリズムを書いています。

現時点では、次の 2 つのヒューリスティックを使用しています。

1. 1 日のレクチャー間のホール数 (関連) (ホール数が少ない -> スコアが大きい)
2. 各時間には何らかの値があるため、時間割ごとに、講義が行われている時間の値を合計します。(より適切な時間に講義 -> より高いスコア)

これら 2 つのヒューリスティックのバランスをとりたいので、アルゴリズムはどちらも優先しません。これを達成するための最良の方法は何ですか？

Answer 1

非常に単純なアプローチは、単純にスコアを加算することです。結局のところ、いずれかの独立したスコアが上昇したときに上昇する混合スコアが必要です。乗算も使用できます (スコアのサイズによっては、数値のオーバーフローに注意してください)。どちらのアプローチでも、個々のスコアに重みを付けることができます。

total_score = 0.4 * hours_score + 0.7 * holes_score

重みをユーザーが構成できるようにすることもできます。

Answer 2

1. 生成された時刻表の品質を評価するためのスコアリング関数を開発します。2 つのヒューリスティックでそのアイデアが得られます。

2. いくつかのランダム timetable 問題を生成します。

3. いくつかの値を選択して 2 つのヒューリスティックのバランスを取り、ソリューションを生成し、どちらが最もよく見えるかを評価します (スコアリング関数を思いつかない場合は、目で見てください)。

4. バランスの重み付けの新しいセットを選択し (つまり、前回からの最良の選択の近傍)、繰り返します。