個人情報: みなさん、こんにちは。私はコンピュータ サイエンスの学生です。誰が (残念ながら) 私の最終年度プロジェクトでこの NP 完全問題に取り組まなければなりません。私は自分の課題や大学で学んだことを超えて、プログラミングの経験があまりありません。ですので、無知な質問で申し訳ありません。
遺伝的アルゴリズムを使用した大学の時間割スケジュール プロジェクト:
これは、大学の最終年度のプロジェクトの私のトピックです。私はすでに必要な情報を収集し、提案と進捗レポートを作成しているので、このトピックが NP-Complete であるという事実を十分に認識しています。ただし、私のプロジェクトの目標は、完全に最適で問題のないゴールデン タイムテーブルを作成することではありません。代わりに、それが受け入れられ、私のルールに違反しないことを確認する必要があります。
私の方法論とこのアプリケーションを作成する方法に関して、問題を解決するために 2 つの主要な人工知能技術を使用することにしました。遺伝的アルゴリズムと制約の充足。私はいくつかのルールを考え出し、それらを 2 つの主要なグループに分けました。ソフト制約とハード制約。したがって、アルゴリズムは次のように機能するはずです。
入力があると仮定します (教室とその定員、科目名、講師、およびそれらに登録した学生の数)。アプリケーションは、ランダムな時刻表を生成することから始めます。ただし、この段階で、無視できない厳しい制約 (同じ講師が同時に複数のクラスを教える、教室が常に複数の科目で占有されているなど) を実装することにしました。したがって、基本的にはランダムなタイムテーブルを生成していますが、それらを作成する際にハード制約を適用します。私はこれをガイド付きランダム生成時刻表と呼びたいと思います。次の段階は、可能な限り最適な時刻表を見つけることです。私が話した前のテクニックを使用して; 生成された timetable が厳密な制約に関して許容できることは既にわかっています。現在、遺伝的アルゴリズムを使用して、可能な限り最良の (最適な) timetable を見つけ、結果としてそれを取得します。そのため、GA のフィットネス機能では、ソフトな制約 (クラス間で休憩を取る、同じ科目が毎日複数のクラスを持つことを避けるなど) が使用されます。
私がプログラミングを始めるまで、これらはすべて問題を解決するための良いアプローチでした。紙の上では良さそうに見えましたが、私のプログラミング スキルのせいで、プロジェクトを完成させることができませんでした。
コーディング部分についていくつか質問があります。助けていただければ幸いです。
質問: 1. Java の遺伝的アルゴリズム ライブラリの適切なチュートリアルとガイドライン、マニュアルはありますか? 他のスレッドの人々の提案からJgapを使用することにしましたが、インターネット上でそれについての良いチュートリアルを実際に見つけることができず、残念ながらJgapライブラリで提供されているいくつかの例を見た後でも、そこで何が起こっているのか理解できません.
- 適用したい制約プログラミングの部分については、Java で特定のライブラリを使用する必要がありますか、それとも If/Else または switch ステートメントで実行できますか? もしよろしければ、名前と詳細を教えてください。
最も重要な質問: 1. 時刻表の作成方法は? わかりました、私が言ったように、私は良いプログラマーではありません。つまり、私はプロジェクトの最初のステップであるタイムテーブルの作成で行き詰まっていると推測できます。オブジェクトとして扱う必要がありますか？また、時刻表などを作成するために通常どのようなデータ構造を使用していますか? 配列、リンクリスト、キュー ?
時刻表を作成する私の試みは次のとおりです。
**UPDATED**
このプロジェクトで時々働いた後。タイムテーブルを作成することができました。これは、以前に共有したクラスの更新です。
public class Subject {
public String name;
public int Students;
public String NameOfLecturer;
public ClassVenu addVenues;
public Subject(String argName, String argNameofLecturer, int argStudents)
{ name = argName; NameOfLecturer=argNameofLecturer; Students=argStudents;
}
public String toString() { return name;}}
public class ClassVenu {
public String ClassName;
public int ClassCapacity;
public ClassVenu(int argClassCapacity, String argClassName)
{ ClassName = argClassName; ClassCapacity = argClassCapacity; }
}
public class Days extends Hours{
public Days(Subject a, Subject b,Subject c, Subject d,Subject e, Subject f,Subject g,Subject h, Subject j)
{int i=0;
TimeSlot[i]=a;
TimeSlot[i+1]=b;
TimeSlot[i+2]=c;
TimeSlot[i+3]=d;
TimeSlot[i+4]=e;
TimeSlot[i+5]=f;
TimeSlot[i+6]=g;
TimeSlot[i+7]=h;
TimeSlot[i+8]=j;
}
package fyp_small_timetable;
public class Hours {
public Subject [] TimeSlot = new Subject[9];
}
package fyp_small_timetable;
public static void main(String[] args) {
//creating Subjects
Subject A = new Subject("Human Computer Interaction", "Batman" , 49);
Subject B = new Subject("Artificial Intelligence", "Batman" , 95);
Subject C = new Subject("Human Computer Interaction", "Batman" ,180);
Subject D = new Subject("Human Computer Interaction", "Batman" , 20);
Subject E = new Subject("Empty", "No-One", 0);
//Creating Class Venue
ClassVenu Class1 = new ClassVenu(100,"LecturerTheater1");
ClassVenu Class2 = new ClassVenu(50,"LecturerTheater2");
ClassVenu Class3 = new ClassVenu(200,"LecturerTheater3");
//Creating Days
Days Day1 =new Days(A, A, E, B, B, E, E, A, A);
Days Day2 =new Days(C, C, E, D, D, E, E, A, A);
Days Day3 =new Days(E, E, E, B, B, E, E, A, A);
Days Day4 =new Days(C, C, E, C, C, E, E, A, A);
Days Day5 =new Days(A, A, E, B, B, E, E, A, A);
//creating Timetable
TimeTable T1 = new TimeTable(Day1, Day2, Day3, Day4, Day5);
List<Subject> answer = T1.ShowTimetable(T1);
System.out.println(answer);
}
}
上記のコードは単なるプロトタイプ (タイムテーブルを作成するための私の試み) であることに注意してください。
誰かが私を助けてくれるなら、このプロジェクトでこれまでに行ったことの完全なドキュメントを提供できます。
私を助けてくれた人に感謝し、これが他の人にも役立つことを願っています