遺伝的アルゴリズムとタイムテーブルのシミュレーテッドアニーリング

Question

私はタイムテーブルアプリケーションを開発しています。遺伝的アルゴリズムとシミュレーテッドアニーリングの相対的な利点は何ですか？

---

私は私の状況に固有のこれらのポイントがあります。一度に

1. を、我々は （X 6時間3人の教師）の最大値を割り当てているX（3クラスX週35時間労働制）を一度に実行すると、が反復的にタイムテーブルを構築しています。私たちは、このアプリケーションは、それの限界にプッシュされることを期待

2. は不可能の状態があるでしょうし、どんな不可能時刻表は、アプリケーションがstuck-取得せずに通知しなければなりません。

3. 結果はの定数であるに戻り、失敗したことを報告する必要があります。

Answer 1

まず、かなり小さなソリューションスペースのように思えます。あなたはブルートフォースがあなたの最も簡単な方法ではないと確信していますか？

第二に、あなたは、いくつかの一定の時間に「かなり良い」結果を必要としていることか、アルゴリズムはO（1）である必要があると言うことを意味しますか？私はそれが不可能だとは言わないが...まあ、私はそれが不可能だと確信しています。

具体的には、SAは、ソリューション空間の最後の点から「外側」を探索するヒルクライミングアルゴリズムであり、GAは確率論的であり、ソリューション内の探索超平面であるスペース。

あなたは私を作る二つのSAは、あなたの問題のためのより良いフィット感だと思うと言う：「不可能の状態」「反復的に構築する」とGAsはソリューション空間の超平面全体で「かなり良い」ソリューションを再結合するため、ソリューション空間内のデッドゾーンを「再発見」する傾向があります。あなたが良い解決策からより良い解決策が繰り返し構築できると確信しているなら、あなたは山登りの領域にあり、SAはより良く適合することができます。

非常に一般的に、GAの相対的な利点は、非常に大量のソリューションスペースをすばやく処理することですが、ソリューションスペース内に短くエンコードされた「良いアイデア」があることに依存しています。 SAの相対的な利点は、局所的な解決策を効率的に見つける傾向がある初期解決策の「周辺」において、局所的な解決策空間を探索することである。欠点は、SAがランダムにシードされるため、大きな解空間を探索する上で効率的ではないことです。