java如何在遗传算法中表示时间表问题的时间表?
对于遗传算法而言,通常基因符号如下:
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中
# 1 楼答案
下面的代码可能会让您了解如何解决这个问题。一种解决方案(即大学时间表)由一系列单人房间组成。这些单人房间都有一个二维数组,其中的列是天,行是小时。我把时间设置为16小时,因为我认为在晚上不会上课。所以第1排的小时数将是一天中的第一个小时。。。可能是早上7点到8点。数组的值显示预订了哪个类
突变:
更改类别-将类别更改为另一个随机类别或更改为零=无预订
打开/关闭课堂-如果每天在特定房间预订了一个小时,请将其关闭 如果没有预订,则随机打开一节课 这是为了给算法提供不预定小时数的可能性,因为在变更类变异中,选择0的概率很低
限制条件: 创建解决方案后,检查所有约束并保留有效的解决方案 如果新的有效解决方案比您的人群中已有的其他解决方案更好,或者如果它们增强了您人群的多样性,则必须将新的有效解决方案插入到您的人群中
但是在您提到的文档中,它很好地描述了如何为这个问题实现GA(从第16页开始)
我为多目标优化算法mPOEMS(具有进化改进步骤的多目标原型优化)编写了一个通用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
实际上,只要有一点热情,您就可以轻松地根据需要调整通用框架的代码
你是在工作中还是在学生时期写的