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

Question

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

PARENT1: 101101010101001001001001110011100110101011101101
PARENT2: 010100111011010101110101001001101011001010010110

所以交叉，突变可以像这样用这种表示来完成:

选择交叉点:

PARENT1: 1011010101010010 01001001110011100110101011101101
PARENT2: 0101001110110101 01110101001001101011001010010110

执行交叉产生一个 child :

CHILD: 1011010101010010 01110101001001101011001010010110

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

CHILD: 101101010101001001110101001001101011001010010110

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

例子取自这篇文章:http://secretgeek.net/content/bambrilg.pdf

我正在用 Java 实现这个时间表问题并想表示

FIGURE 10: An Entire University Timetable

在 Java 中。

Answer 1

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

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];    
}

突变:

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

打开/关闭类(class) - 如果在特定房间每天预定一个小时，则将其关闭 如果未预订，请使用随机类(class)打开它 这是为了让算法有可能不预订小时数，因为在更改类突变中，0 被选中的概率很低

约束: 创建解决方案后，检查所有约束并保留有效的解决方案 必须将新的有效解决方案插入到您的(解决方案)种群中，如果它们比您种群中已有的其他解决方案更好，或者如果它们增强了种群的多样性

但是在您提到的文档中，它很好地描述了如何针对这个问题实现 GA(从第 16 页开始)。

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

您可以找到代码 here ，它可能会让您了解如何解决您的问题:

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

你可以找到它here .

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

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

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

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

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