论文部分内容阅读
摘要：高校教务管理工作中，排课问题是一项重要而又复杂的工作。遗传算法是一种借鉴于生物界自然选择规律和进化机制体系发展起来的自适应随机搜索算法。具有良好的并行性、通用性、穩定性，是一种非有效的解决NP完全问题的方法。
关键词：智能排课；遗传算法；改进
1遗传算法概述
遗传算法是一种通过借鉴达尔文的生物进化率而得来的进化规律演化而来的智能排课方法。它的主要特点是直接对结构对象进行操作，不存在求导和函数连续性等条件的限定；具有更好的全局寻优能力；另外，其通过采用概率化的寻优方法，能够自动的获取并且指导优化的搜索空间，根据自身条件适应地、有选择的调整搜索方向，不需要确定的规则。正是因为遗传算法的这些性质和优点，所以遗传算法已经广泛的被人们应用于机器学习、组合优化、人工生命、信号处理、和自适应控制等领域。是智能计算排课系统中的关键技术。另外，遗传算法作为因生物进化思想而受到启发得出的一种全局优化算法，在本质上是一种不依赖具体问题的直接搜索方法。
1.1遗传算法的基本原理
遗传算法是类似于生物进化的一个智能排课算法。将其主要载体比喻为染色体，换句话说也就是多个基因的组合。我们通过这些多个基因的组合来决定个体的形状以及外在的表现。因此，我们首先需要实现从表现型到基因型的转化，也就是编码工作。在第一代种群产生后，经过选择、交叉、变异等具体方法来进行改革优化，直到满足优化标准为止。
1.2遗传算法的基本步骤
第一步：确定编码的方案，将参数进行结合（又称可行解的集合转化成染色体的结构空间）。
第二步：为了方便计算适应值，所以要定义具体的适应度函数。
第三步：确定遗传方案，通过对第一代种群进行相关操作，也就是通过选择、交叉、变异的方法，来确定交叉和变异的概率等对应遗传参数。
第四步：确定随机产生对应的初始化群体。
第五步：主要计算种群里面的个体以及染色体解码后，所产生的对应适应值。
第六步：参照先前确定好的遗传的策略，在进行选择，并选出交叉和变异算子等方法作用于群体，最终形成下一代的群体。
第七步：主要用于判别群体的性能是否能够满足其中具体的某一项指标，是否完成事先约定的迭代次数，假如不能够完成的话，需要返回到第五步或者通过修改具体遗传方案后再返回第六步。
1.3遗传算法的演化过程
遗传算法采用类似基因演化的循环过程，其演算过程如下：
（1）随机产生一定数目的初始种群
（2）对个体适应度进行评估，如果个体的适应度符合优化准则，则输出最佳个体及其代表的最优解，并结束计算，否则转向第3步
（3）依据适应度选择再生个体
（4）按照一定的交叉概率和交叉方法生成新的个体
（5）按照一定的变异概率和变异方法生成新的个体
（6）由交叉和变异产生新一代的种群，然后返回第2步
2遗传算法解决排课问题的优势
（1）遗传算法是高效智能算法。遗传算法在已经确定了编码方案、适应度函数和遗传算子之后，又利用演化过程中所获得的信息进行自行组织搜索，通过选择来看，适应度大的个体通常具有比较高的生存概率，而适应度小的个体则具有比较低的生存概率。遗传算法是具有“潜在学习能力”的自适应搜索技术。
（2）遗传算法具有群体搜索策略。群体中各个个体之间的信息交换是单独存在的，并不依赖于初始参数的特点，并具有较好的通用性、稳定性。
（3）遗传算法具有并行性。由于遗传算法是采用种群的方式来进行搜索的，因此它具备可以同时搜索空间内的多个区域的能力，并且相互之间可以进行信息交流。这种搜索方式虽然每次只能够执行与种群规模互成比例的计算，但实际上，根据 Goldberg DE 的推算，以及他进行的 O（N3）次的有效搜索之后，这才使得遗传算法能够用较少的计算来获取较大的收益。
（4）遗传算法在解决排课问题这类具有多重约束的组合优化问题时，几乎能够得到基本满足各种需求的课表。
（5）遗传算法解法之所以能够被各级各类的学校所认可，是因为它能够较好地解决并能满足各类学校对课表编排的其他特殊要求，通过评价函数值、适应度函数值的方式使复杂的排课约束条件能够得以量化，这有利于解决类似于排课这种模糊不清并且不确定的问题。
3遗传算法的改进
3.1遗传算法的不足
我们在利用遗传算法解决实际问题的过程中，发现出现了一些现象，例如：种群发散和早熟现象，换句话说，也就是会有不收敛或者过早收敛的现象。一方面，我们利用数学概率知识来分析遗传算法知识，同时认为收敛的过程是一个无限逼近的过程，但是计算过程却属于有限自动机，并且在数学概率运算的作用下，种群的产生、遗传和变异都是随机抽取的，而在算法进化的过程中可能由于概率的随机性而丢失优势个体，容易造成种群的适应能力下降，从而导致不收敛或过早收敛现象。另一方面，由于优势个体的优势作用，导致它会优先进行繁殖，从而致使劣势个体的淘汰，因此会造成部分基因的丢失，降低了种群的多样性，正是由于这些原因，这才会产生早熟现象或容易造成局部最优现象。所以，通常情况下运用基本遗传算法在解决实际问题时所求得的最终结果通常存在一定局限现象，并不是最佳结果；除此之外，采用简单遗传算法具有不可避免多次对某一个可行解的搜索，因此会造成另外的负面效应，会导致那只是选择了局部的最优解，而并非整体最优解，这也是影响运行效率的一个因素。
3.2遗传算法的改进方法
鉴于上述两类情况，本文给出了两类对策：首先是最优个体替换，其次是对淘汰的个体进行有限的回收。经过改进的遗传算法更能满足现实需要，具有更为良好的性能。
最优个体保留原则 ：改进的遗传算法在排课过程中的应用与实现由于遗传算法具有随机性的特点，如果采用简单遗传算法，在种群进化过程中难免出现适应度最高的个体丢失现象，若采用最优个体保留原则即可降低此类现象出现的概率。最优个体保留原则，即对每代中的最优个体进行选择，使其进入子代，而对子代中具有最差适应度个体进行剔除，以此维持整个种群的规模的稳定。规定种群数量是对种群中具有最大适应度的个体进行记录，进而进行母体的交叉、变异操作。从中得到个个体，并加上在上一代群体中具有最高适用度的个体，以此维持整个种群的规模的恒定。通过这种方式的修订可以确保种群序列适应值具有单调不减性的特征。
关键词：智能排课；遗传算法；改进
1遗传算法概述
遗传算法是一种通过借鉴达尔文的生物进化率而得来的进化规律演化而来的智能排课方法。它的主要特点是直接对结构对象进行操作，不存在求导和函数连续性等条件的限定；具有更好的全局寻优能力；另外，其通过采用概率化的寻优方法，能够自动的获取并且指导优化的搜索空间，根据自身条件适应地、有选择的调整搜索方向，不需要确定的规则。正是因为遗传算法的这些性质和优点，所以遗传算法已经广泛的被人们应用于机器学习、组合优化、人工生命、信号处理、和自适应控制等领域。是智能计算排课系统中的关键技术。另外，遗传算法作为因生物进化思想而受到启发得出的一种全局优化算法，在本质上是一种不依赖具体问题的直接搜索方法。
1.1遗传算法的基本原理
遗传算法是类似于生物进化的一个智能排课算法。将其主要载体比喻为染色体，换句话说也就是多个基因的组合。我们通过这些多个基因的组合来决定个体的形状以及外在的表现。因此，我们首先需要实现从表现型到基因型的转化，也就是编码工作。在第一代种群产生后，经过选择、交叉、变异等具体方法来进行改革优化，直到满足优化标准为止。
1.2遗传算法的基本步骤
第一步：确定编码的方案，将参数进行结合（又称可行解的集合转化成染色体的结构空间）。
第二步：为了方便计算适应值，所以要定义具体的适应度函数。
第三步：确定遗传方案，通过对第一代种群进行相关操作，也就是通过选择、交叉、变异的方法，来确定交叉和变异的概率等对应遗传参数。
第四步：确定随机产生对应的初始化群体。
第五步：主要计算种群里面的个体以及染色体解码后，所产生的对应适应值。
第六步：参照先前确定好的遗传的策略，在进行选择，并选出交叉和变异算子等方法作用于群体，最终形成下一代的群体。
第七步：主要用于判别群体的性能是否能够满足其中具体的某一项指标，是否完成事先约定的迭代次数，假如不能够完成的话，需要返回到第五步或者通过修改具体遗传方案后再返回第六步。
1.3遗传算法的演化过程
遗传算法采用类似基因演化的循环过程，其演算过程如下：
（1）随机产生一定数目的初始种群
（2）对个体适应度进行评估，如果个体的适应度符合优化准则，则输出最佳个体及其代表的最优解，并结束计算，否则转向第3步
（3）依据适应度选择再生个体
（4）按照一定的交叉概率和交叉方法生成新的个体
（5）按照一定的变异概率和变异方法生成新的个体
（6）由交叉和变异产生新一代的种群，然后返回第2步
2遗传算法解决排课问题的优势
（1）遗传算法是高效智能算法。遗传算法在已经确定了编码方案、适应度函数和遗传算子之后，又利用演化过程中所获得的信息进行自行组织搜索，通过选择来看，适应度大的个体通常具有比较高的生存概率，而适应度小的个体则具有比较低的生存概率。遗传算法是具有“潜在学习能力”的自适应搜索技术。
（2）遗传算法具有群体搜索策略。群体中各个个体之间的信息交换是单独存在的，并不依赖于初始参数的特点，并具有较好的通用性、稳定性。
（3）遗传算法具有并行性。由于遗传算法是采用种群的方式来进行搜索的，因此它具备可以同时搜索空间内的多个区域的能力，并且相互之间可以进行信息交流。这种搜索方式虽然每次只能够执行与种群规模互成比例的计算，但实际上，根据 Goldberg DE 的推算，以及他进行的 O（N3）次的有效搜索之后，这才使得遗传算法能够用较少的计算来获取较大的收益。
（4）遗传算法在解决排课问题这类具有多重约束的组合优化问题时，几乎能够得到基本满足各种需求的课表。
（5）遗传算法解法之所以能够被各级各类的学校所认可，是因为它能够较好地解决并能满足各类学校对课表编排的其他特殊要求，通过评价函数值、适应度函数值的方式使复杂的排课约束条件能够得以量化，这有利于解决类似于排课这种模糊不清并且不确定的问题。
3遗传算法的改进
3.1遗传算法的不足
我们在利用遗传算法解决实际问题的过程中，发现出现了一些现象，例如：种群发散和早熟现象，换句话说，也就是会有不收敛或者过早收敛的现象。一方面，我们利用数学概率知识来分析遗传算法知识，同时认为收敛的过程是一个无限逼近的过程，但是计算过程却属于有限自动机，并且在数学概率运算的作用下，种群的产生、遗传和变异都是随机抽取的，而在算法进化的过程中可能由于概率的随机性而丢失优势个体，容易造成种群的适应能力下降，从而导致不收敛或过早收敛现象。另一方面，由于优势个体的优势作用，导致它会优先进行繁殖，从而致使劣势个体的淘汰，因此会造成部分基因的丢失，降低了种群的多样性，正是由于这些原因，这才会产生早熟现象或容易造成局部最优现象。所以，通常情况下运用基本遗传算法在解决实际问题时所求得的最终结果通常存在一定局限现象，并不是最佳结果；除此之外，采用简单遗传算法具有不可避免多次对某一个可行解的搜索，因此会造成另外的负面效应，会导致那只是选择了局部的最优解，而并非整体最优解，这也是影响运行效率的一个因素。
3.2遗传算法的改进方法
鉴于上述两类情况，本文给出了两类对策：首先是最优个体替换，其次是对淘汰的个体进行有限的回收。经过改进的遗传算法更能满足现实需要，具有更为良好的性能。
最优个体保留原则 ：改进的遗传算法在排课过程中的应用与实现由于遗传算法具有随机性的特点，如果采用简单遗传算法，在种群进化过程中难免出现适应度最高的个体丢失现象，若采用最优个体保留原则即可降低此类现象出现的概率。最优个体保留原则，即对每代中的最优个体进行选择，使其进入子代，而对子代中具有最差适应度个体进行剔除，以此维持整个种群的规模的稳定。规定种群数量是对种群中具有最大适应度的个体进行记录，进而进行母体的交叉、变异操作。从中得到个个体，并加上在上一代群体中具有最高适用度的个体，以此维持整个种群的规模的恒定。通过这种方式的修订可以确保种群序列适应值具有单调不减性的特征。