Making a Class Schedule Using a Genetic Algorithm 中的fitness函数的解析

2024-04-19 14:32
文章标签 函数 解析 using class algorithm schedule genetic making fitness

本文主要是介绍Making a Class Schedule Using a Genetic Algorithm 中的fitness函数的解析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

genetic algotithm 排课

排课过程中的一些硬条件：

  • A class can be placed only in a spare classroom
  • No professor or student group can have more then one class at a time.
  • A classroom must have enough seats to accommodate all students.
  • To place a class in a classroom, the classroom must have laboratory equipment (computers, in our case) if the class requires it。

Fitness函数积分规则：

  • Each class can have 0 to 5 points
  • If a class uses a spare classroom, we increment its score.
  • If a class requires computers and it is located in the classroom with them, or it doesn't require them, we increment the score of the class.
  • If a class is located in a classroom with enough available seats, guess what, we increment its score.
  • If a professor has no other classes at the time, we increment the class's score once again.
  • The last thing that we check is if any of the student groups that attend the class has any other class at the same time, and if they don't, we increment the score of the class.
  • If a class breaks a rule at any time-space slot that it occupies, its score is not incremented for that rule.
  • The total score of a class schedule is the sum of points of all classes.
  • The fitness value is calculated as schedule_score/maximum_score, and maximum_score is number_of_classes*5.

这之间的联系可以这样：


这些限制条件关联了不同的对象，有课程对教室的要求，有学生或教授对课程的要求，有课程对课程表的要求（时间唯一性）。现在有个问题，有了这些限制条件，问题的解空间该怎么定义？怎么初始化一个初代的课程表?这分为两个步骤，一个是课程已经安排好了（一个课程指的是，确定好了上什么课，哪个老师上，哪些班级的学生去上，教室选在哪里），这时候上课的时间是不定的，也就是只有时间安排这一个变量，这时候把安排好的课程输入排课系统里进行优化排序。怎么安排课程呢？也就是统筹学生，老师，地点这些信息。上面这种思考方式有点偏离问题，教室和一周的时间都是可配置资源，应该是一起安排的，并不是先安排教室，然后在安排时间。

按照上面的资源分配来看，教师也可以看做一种分配资源，不过因为教师一般只教授一门课或者两门课，变化比较小，所以很多课表设计时，把这个部分是定死了。问题有点远了，后续在思考这部分问题，先解析下C++中的fitness源码。

Fitness源码部分c++

// Calculates fitness value of chromosome
void Schedule::CalculateFitness()
{// chromosome's scoreint score = 0;int numberOfRooms = Configuration::GetInstance().GetNumberOfRooms();int daySize = DAY_HOURS * numberOfRooms;int ci = 0;// check criterias and calculate scores for each class in schedulefor( hash_map<CourseClass*, int>::const_iterator it = _classes.begin(); it != _classes.end(); ++it, ci += 5 ){// coordinate of time-space slotint p = ( *it ).second;int day = p / daySize;int time = p % daySize;int room = time / DAY_HOURS;time = time % DAY_HOURS;int dur = ( *it ).first->GetDuration();// check for room overlapping of classesbool ro = false;for( int i = dur - 1; i >= 0; i-- ){if( _slots[ p + i ].size() > 1 ){ro = true;break;}}// on room overlapingif( !ro )score++;_criteria[ ci + 0 ] = !ro;CourseClass* cc = ( *it ).first;Room* r = Configuration::GetInstance().GetRoomById( room );// does current room have enough seats_criteria[ ci + 1 ] = r->GetNumberOfSeats() >= cc->GetNumberOfSeats();if( _criteria[ ci + 1 ] )score++;// does current room have computers if they are required_criteria[ ci + 2 ] = !cc->IsLabRequired() || ( cc->IsLabRequired() && r->IsLab() );if( _criteria[ ci + 2 ] )score++;bool po = false, go = false;// check overlapping of classes for professors and student groupsfor( int i = numberOfRooms, t = day * daySize + time; i > 0; i--, t += DAY_HOURS ){// for each hour of classfor( int i = dur - 1; i >= 0; i-- ){// check for overlapping with other classes at same timeconst list<CourseClass*>& cl = _slots[ t + i ];for( list<CourseClass*>::const_iterator it = cl.begin(); it != cl.end(); it++ ){if( cc != *it ){// professor overlaps?if( !po && cc->ProfessorOverlaps( **it ) )po = true;// student group overlaps?if( !go && cc->GroupsOverlap( **it ) )go = true;// both type of overlapping? no need to check moreif( po && go )goto total_overlap;}}}}total_overlap:// professors have no overlaping classes?if( !po )score++;_criteria[ ci + 3 ] = !po;// student groups has no overlaping classes?if( !go )score++;_criteria[ ci + 4 ] = !go;}// calculate fitess value based on score_fitness = (float)score / ( Configuration::GetInstance().GetNumberOfCourseClasses() * DAYS_NUM );
}


这篇关于Making a Class Schedule Using a Genetic Algorithm 中的fitness函数的解析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/917804。

相关文章

网页解析 lxml 库--实战

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库，完全使用 Python 语言编写，它对 XPath表达式提供了良好的支 持，因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块，该模块专门用来解析 HTML/XML 文档，下面来介绍一下 lxml 库
阅读更多...
hdu1171（母函数或多重背包）

hdu1171（母函数或多重背包）

题意：把物品分成两份，使得价值最接近 可以用背包，或者是母函数来解，母函数（1 + x^v+x^2v+.....+x^num*v）（1 + x^v+x^2v+.....+x^num*v）（1 + x^v+x^2v+.....+x^num*v） 其中指数为价值，每一项的数目为（该物品数+1）个 代码如下： #include<iostream>#include<algorithm>
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
C++操作符重载实例(独立函数)

C++操作符重载实例(独立函数)

C++操作符重载实例，我们把坐标值CVector的加法进行重载，计算c3=c1+c2时，也就是计算x3=x1+x2，y3=y1+y2，今天我们以独立函数的方式重载操作符+（加号），以下是C++代码： c1802.cpp源代码： D:\YcjWork\CppTour>vim c1802.cpp #include <iostream>using namespace std;/*** 以独立函数
阅读更多...
OWASP十大安全漏洞解析

OWASP十大安全漏洞解析

OWASP（开放式Web应用程序安全项目）发布的“十大安全漏洞”列表是Web应用程序安全领域的权威指南，它总结了Web应用程序中最常见、最危险的安全隐患。以下是对OWASP十大安全漏洞的详细解析： 1. 注入漏洞（Injection） 描述：攻击者通过在应用程序的输入数据中插入恶意代码，从而控制应用程序的行为。常见的注入类型包括SQL注入、OS命令注入、LDAP注入等。 影响：可能导致数据泄
阅读更多...
从状态管理到性能优化：全面解析 Android Compose

从状态管理到性能优化：全面解析 Android Compose

文章目录 引言一、Android Compose基本概念1.1 什么是Android Compose?1.2 Compose的优势1.3 如何在项目中使用Compose 二、Compose中的状态管理2.1 状态管理的重要性2.2 Compose中的状态和数据流2.3 使用State和MutableState处理状态2.4 通过ViewModel进行状态管理 三、Compose中的列表和滚动
阅读更多...
Spring 源码解读：自定义实现Bean定义的注册与解析

Spring 源码解读：自定义实现Bean定义的注册与解析

引言 在Spring框架中，Bean的注册与解析是整个依赖注入流程的核心步骤。通过Bean定义，Spring容器知道如何创建、配置和管理每个Bean实例。本篇文章将通过实现一个简化版的Bean定义注册与解析机制，帮助你理解Spring框架背后的设计逻辑。我们还将对比Spring中的BeanDefinition和BeanDefinitionRegistry，以全面掌握Bean注册和解析的核心原理。
阅读更多...
CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 （最大值之和）给定整数序列 a0,⋯,an−1，求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr（其中0≤l≤r<n0≤l≤r<n）表示，对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同，当且仅当下标不同。 例如，当原序列为 [1,2,1,2] 时，要计算子序列 [
阅读更多...
函数式编程思想

函数式编程思想

我们经常会用到各种各样的编程思想，例如面向过程、面向对象。不过笔者在该博客简单介绍一下函数式编程思想. 如果对函数式编程思想进行概括，就是f(x) = na(x) , y=uf(x)…至于其他的编程思想，可能是y=a(x)+b(x)+c(x)…，也有可能是y=f(x)=f(x)/a + f(x)/b+f(x)/c… 面向过程的指令式编程 面向过程，简单理解就是y=a(x)+b(x)+c(x)
阅读更多...
多线程解析报表

多线程解析报表

假如有这样一个需求，当我们需要解析一个Excel里多个sheet的数据时，可以考虑使用多线程，每个线程解析一个sheet里的数据，等到所有的sheet都解析完之后，程序需要提示解析完成。 Way1 join import java.time.LocalTime;public class Main {public static void main(String[] args) thro
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2