3

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

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

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

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

假设我们有我们的输入（教室及其容量、学科名称、讲师和注册的学生数量）。该应用程序从生成随机时间表开始。然而，我决定在这个阶段实施我的硬约束，一个不容忽视的约束（例如，同一位讲师同时教授多个课程或教室在任何给定时间占用多个科目）。所以基本上我们正在生成随机时间表，但在创建它们时，我们对它们应用硬约束。我想称之为引导式随机生成的时间表。下一阶段是找到最佳的时间表。使用我之前谈到的技术；我们已经知道生成的时间表在硬约束方面是可以接受的，现在使用遗传算法我会找到最好的（最佳）时间表并得到结果。因此，我的 GA 的健身功能将使用软约束（例如在课间休息、避免同一科目每天上不止一节课等）。

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

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

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

  1. 对于我想要应用的约束编程部分，我是否必须使用 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);


}

}

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

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

感谢任何帮助我并希望这也能帮助其他人的人 Hirad

4

1 回答 1

0

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

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

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

您可能还想考虑健身正常化。

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

于 2015-07-28T13:26:16.093 回答