使用遗传算法的大学时间表调度项目（JAVA）

Question

个人信息： 大家好，我是一名计算机科学专业的学生；谁（不幸的是）必须为我的毕业设计解决这个 NP-Complete 问题。除了我的作业和我在大学学到的东西之外，我在编程方面没有那么丰富的经验。所以对于我可能会问的任何无知的问题，我深表歉意。

使用遗传算法的大学时间表计划项目：

这是我大学Final year Project的题目。我已经收集了所需的信息并撰写了我的提案和进度报告，因此我完全意识到这个主题是 NP-Complete。然而，我的项目的目标不是创建黄金时间表、完全最优且没有问题，而是我只需要确保它是可以接受的并且不会违反我的一些规则。

关于我的方法论和我想要创建这个应用程序的方式，我决定使用两种主要的人工智能技术来解决这个问题；遗传算法和约束满足。我想出了一些规则并将它们分为两个主要组；软约束和硬约束。所以算法应该这样工作：

假设我们有我们的输入（class房间及其容量、学科名称、讲师和注册他们的学生数量）。该应用程序从生成随机时间表开始。然而，我决定实施我的硬性约束，这是一个不容忽视的约束（例如让同一位讲师同时教授一门以上的 class 课，或者 class 房间在任何时候都被不止一门学科占据时间）在这个阶段。所以基本上我们是在生成随机时间表，但在创建它们时，我们对它们应用了硬约束。我想称它为引导随机生成的时间表。下一阶段是找到最佳时间表。使用我之前谈到的技术；我们已经知道生成的时间表在硬约束方面是可以接受的，现在使用遗传算法我将找到最好的（最优化的）时间表并将其作为结果。因此，软约束（例如在 class 之间休息，避免同一主题每天有多个 class 等）将用于我的 GA 的适应度函数。

在我开始编程之前，所有这些都是解决问题的好方法。嗯，它们在纸面上看起来不错，但我的编程技能阻碍了我完成项目。

我有一些关于编码部分的问题，如果你们能帮助我，我将不胜感激。

问题： 1. java 中的遗传算法库有什么好的教程和指南、手册吗？我决定使用 Jgap，根据人们对其他线程的建议，但我真的无法在互联网上找到任何关于它的好教程，不幸的是，在我们查看 Jgap 库中提供的一些示例之后，我仍然无法弄清楚那里发生了什么。

对于我想应用的约束编程部分，我是否必须在 Java 上使用任何特定的库，或者我可以使用 If/Else 或 switch 语句来完成？如果是这样，请告诉我名称和详细信息。

最重要的问题： 1.如何创建时间表？好的，正如我所说，我不是一个好的程序员。所以你可以假设我停留在我项目的第一步，创建时间表。我必须把它当作一个对象吗？你们通常使用什么样的数据结构来创建时间表？数组、链表、队列？

这是我创建时间表的尝试：

                              **UPDATED**

在这个项目上工作了一段时间之后。我设法创建了时间表。这是我之前分享的 classes 的更新。

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);


}

}

请记住，上面显示的代码只是一个原型（我尝试创建时间表）。

如果有人愿意帮助我，我可以提供到目前为止我在这个项目中所做的工作的完整文档。

感谢所有帮助过我的人，希望这也能帮助到其他人希拉德

Answer 1

我已经使用遗传算法解决了生产应用程序中的大学时间表安排问题。

不要太担心要使用的库，那里有很多很棒的 java GA 库。

您应该关注的是您对候选时间表进行编码的方式。通常您会使用数字表示，例如 ['math', 'chemistry', physics] = [1, 4, 6] 每个数字代表一个唯一的 class，而该数字的索引代表将提供 class 的时间。然后，适应度函数将采用表示候选时间表总体的多维值数组，然后将此总体与学生列表进行比较，并应用约束，例如冲突和计算可能的适应度。

您可能还想 fitness normalization .

最重要的是不要使用对象来存储您的时间表信息，而是使用简单的整数数组，这将显着提高您的通用算法的速度。

使用遗传算法的大学时间表调度项目（JAVA）

University Timetable Scheduling Project using Genetic Algorithm (JAVA)

java

scheduling

genetic-algorithm

timetable