如何表示遗传算法中的时间表问题的时间表？

Question

对于遗传算法,通常基因符号如下:

PARENT1: 101101010101001001001001110011100110101011101101
PARENT2: 010100111011010101110101001001101011001010010110

如此交叉,突变可以通过这种表示来完成,如:

选择一个交叉点:

PARENT1: 1011010101010010 01001001110011100110101011101101
PARENT2: 0101001110110101 01110101001001101011001010010110

执行交叉生成孩子:

CHILD: 1011010101010010 01110101001001101011001010010110

然后变成一条全新的染色体:

CHILD: 101101010101001001110101001001101011001010010110

我的问题是如何在Java中表示每周计划基因？

示例来自本文:http://secretgeek.net/content/bambrilg.pdf

我正在克服Java中的这个时间表问题,并希望代表

FIGURE 10: An Entire University Timetable

在Java中.

Answer 1

下面的代码可能会让您了解如何解决该问题。一种解决方案（即大学时间表）由一系列单间组成。这些单间每个都有一个二维数组，其中列是天，行是小时。我将时间设置为 16 点，因为我认为晚上不会有课。因此，第 1 行时间将是一天中的第一个小时……可能是早上 7 点到 8 点。数组的值显示预订的舱位。

public class SingleRoom {
    static final int DAYS  = 7;
    static final int HOURS = 16;
    . . .
    private int[][] timetable = new int[DAYS][HOURS];   //0 would say room is not booked, >0 indicates the booked class (english advanced (12), object oriented programming (139), etc..)
}

public class Solution {
    static final int AVAILABLE_ROOMS = 26;
    . . .
    private SingleRoom[] university_timetable = new SingleRoom[AVAILABLE_ROOMS];    
}

突变：

更改类别突变 - 将类别更改为另一个随机类别或为零 = 不预订

打开/关闭课程 - 如果预订了特定房间每天的一个小时，如果没有预订，则将其关闭，使用随机课程打开它，这是为了让算法有可能不预订时间，因为在变化类突变 0 被选择的概率很低

约束：创建解决方案后，检查所有约束并保留有效的解决方案。新的有效解决方案必须插入到您的总体（解决方案）中，如果它们比您总体中已有的其他解决方案更好，或者它们是否增强了人口的多样性

但在您提到的文档中，它很好地描述了如何针对此问题实施 GA（从第 16 页开始）。

我为多目标优化算法mPOEMS（具有进化改进步骤的多目标原型优化）编写了一个通用的java框架，这是一个使用进化概念的GA。

您可以在这里找到代码，它可能会让您了解如何解决您的问题：

您可以使用该算法找到的解决方案已在科学工作中与最先进的算法 SPEA-2 和 NSGA 进行了比较，并且已证明该算法的性能相当甚至更好，具体取决于您的指标来衡量性能。

你可以在这里找到它。

更多资源：我的论文将该框架应用于项目选择问题： http://www.ub.tuwien.ac.at/dipl/2008/AC05038968.pdf

该框架的文档： http://thomaskremmel.com/mpoems/mpoems_in_java_documentation.pdf

mPOEMS 演示文稿： http://portal.acm.org/itation.cfm? id=1792634.1792653

实际上，只要有一点热情，您就可以轻松地根据您的需要调整通用框架的代码。

你是在工作中还是在学生的时候写这个 GA 的？