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

发布于 2024-10-10 08:18:49 字数 851 浏览 0 评论 0原文

对于遗传算法，通常基因像这样符号化：

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 来表示。

原文

For genetic algorithms usually genes symbolized like this:

PARENT1: 101101010101001001001001110011100110101011101101
PARENT2: 010100111011010101110101001001101011001010010110

so crossover, mutations may be done with this representations as like:

Choose a crossover point:

PARENT1: 1011010101010010 01001001110011100110101011101101
PARENT2: 0101001110110101 01110101001001101011001010010110

Perform crossover to produce a child:

CHILD: 1011010101010010 01110101001001101011001010010110

Which then becomes, a whole new chromosome:

CHILD: 101101010101001001110101001001101011001010010110

My problem is how to represent a weekly schedule gene in Java?

Examples are taken from this article: http://secretgeek.net/content/bambrilg.pdf

I am impelementing this timetabling problem in Java and want to represent

FIGURE 10: An Entire University Timetable

in Java.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

清秋悲枫 2024-10-17 08:18:49

下面的代码可能会让您了解如何解决该问题。一种解决方案（即大学时间表）由一系列单间组成。这些单间每个都有一个二维数组，其中列是天，行是小时。我将时间设置为 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 的？

The code below might give you an idea how to approach the problem. One solution (which would be the university timetable) consists out of an array of single rooms. These single rooms each have a 2dimensional array, where the columns are the days, and the rows are the hours. I set the HOURS to 16, since I think in the night time there will be no classes. So Hour Row 1 would be the first hour of the day... probably from 7 to 8 AM. The values of the array show which class is booked.

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

mutations:

change class mutation - change the class to another random class or to zero = no booking

switch on / off class - if an hour at a day in a specific room is booked, switch it off
if it is not booked, switch it on with a random class
this is to give the algorithm the possibility to not book hours, since in the change class mutation the 0 has a low probability to be chosen

constraints:
after creating your solutions, check against all constraints and keep the solutions that are valid
the new valid solutions have to be inserted into your population (of solutions), if they are better to other solutions already in your population or if they enhance the diversity of your population

But in the document you referred to it is fairly good described how to implement a GA for this problem (starts with page 16).

I wrote a generic java framework for the multi-objective optimisation algorithm mPOEMS (Multiobjective prototype optimization with evolved improvement steps), which is a GA using evolutionary concepts.

You can find the code here, it might give you an idea how to approach your problem:

The solutions which you can find with this algorithm have been compared in a scientific work with state-of-the-art algorithms SPEA-2 and NSGA, and it has been proven that
the algorithm performes comparable or even better, depending on the metrics you take to measure the performance.

You can find it here.

Further resources:
My thesis which applies this framework to the project selection problem:
http://www.ub.tuwien.ac.at/dipl/2008/AC05038968.pdf

The documentation of the framework:
http://thomaskremmel.com/mpoems/mpoems_in_java_documentation.pdf

mPOEMS presentation paper:
http://portal.acm.org/citation.cfm?id=1792634.1792653

Actually with a bit of enthusiasm you could easily adapt the code of the generic framework to your needs.

Do you write this GA in your job or as a student?

回复收藏 0 原文

~没有更多了~