•  
  • 欢迎光临软件毕设网,定做作品,包修改,包解答,包通过,100%原创,100%满意.!
  •  
首页 >> 工硕专题 >> 排课常用算法介绍
※ 排课常用算法介绍

遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法,它是有美国Michigan大学J.Holland教授于1975年首先提出来的,并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》,GA这个名称才逐渐为人所知,J.Hilland教授所提出的GA通常为简单遗传算法(SGA)。
    遗传算法是从代表问题可能潜在的解集的一个种群(population)开始的,而一个种群则由经过基因(gene)编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体,即多个基因的集合,其内部表现(即基因型)是某种基因组合,它决定了个体的形状的外部表现,如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此,在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂,我们往往进行简化,如二进制编码,初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代(generation)演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度(fitness)大小挑选(selection)个体,并借助于自然遗传学的遗传算子(genetic operators)进行组合交叉(crossover)和变异(mutation),产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码(decoding),可以作为问题近似最优解。
遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法,与传统的优化算法相比,主要有以下特点:
1、 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际植本身,而遗传算法处理决策变量的某种编码形式,使得我们可以借鉴生物学中的染色体和基因的概念,可以模仿自然界生物的遗传和进化机理,也使得我们能够方便的应用遗传操作算子。
2、 遗传算法直接以适应度作为搜索信息,无需导数等其它辅助信息。
3、 遗传算法使用多个点的搜索信息,具有隐含并行性。
4、 遗传算法使用概率搜索技术,而非确定性规则。

1.3.1贪心算法
贪心法(greedy method)是一种改进了的分级处理方法,逐步构造最优解。它从问题的某一个初始解出发,在一定的标准下做出一系列的贪心选择(选择一旦做出,就不可再更改),即当前状态下看上去最优的选择.逐步逼近给定的目标.以尽可能快的速度求得更好的解 当达到算法中的某一步不能再继续前进时则停止。贪心算法的核心是在所选择的策略中,选一个权值最优的策略作为当前策略。因此贪心算法的好坏主要决定于权值的确定。
在排课系统中,贪心算法是从排课问题的某一初始状态出发.依据给出的贪心策略朝最终排好全部课程这个目标前进一步,判断是否可以求出可行解的一个解元素.如果可以则继续依据贪心策略向给定目标前进.求出下一个解元素。直到前进不能再继续时停止。最后由所有得到的解元素组成问题的一个可行解。此时算法结束。
贪心算法的缺点在于解的效果比较差.而最大优势在于极低的时间复杂度。能做到某种意义上的局部最优。它具有不可后撤性,可以有后效性.一般情况下不满足最优化原理。并且不适用于解决可行性问题.仅适用于较容易得到可行解的最优性问题。为了尽量减小贪心算法带来的副作用。使得最后得到的解更接近最优解。可以在算法尽可能多的地方使用有效的最优化算法(如动态规划)。贪心算法还可以为搜索算法提供较优的初始界值。

1.3.2回溯算法
回溯算法也叫试探法.它是一种系统地搜索问题的解的方法,可以被认为是一个有过剪枝的DFS(深度优先搜索)过程。它按优先条件向前搜索,以达到目标,但当搜索到某一步时.发现原先的选择并不优或达不到目标。就退回一步重新选择。而满足回溯条件的某个状态点称之为回溯点。具体到计算机智能排课系统中,选优条件即为排课数学模型中的约束条件群(需求集中的元素特征与资源集中的元素特征相互作用形成的数学关系)若不满足约束条件群,该选择即为不优或达不到目标 当遍历该步骤的所有可能仍未满足约束条件群.则该状态满足了回溯条件,该状态点即为回溯点。
回溯算法解决排课问题时首先要描述解的形式,定义一个解空间.它包含问题的所有解:其次构造状态空间树,这棵树的每条完整路径都代表了一种解的可能:再次是构造约束函数,通过描述合法解的一般特征用于去除不合法的解,从而避免继续搜索出这个不合法解的剩余部分:然后通过深度优先搜索完成回溯。
①设置初始化的方案(给变量赋初值,读入已知数据等);
②变换方式去试探。若全部试完则转⑦ ;
③ 判断此法是否成功(通过约束函数),不成功则转② ;
④ 试探成功则前进一步再试探;
⑤正确方案还未找到则转② ;
⑥ 已找到一种方案则记录并打印;
⑦退回一步(回溯),若未退到根则转② ;
⑧ 已退到根节点则排课结束或打印无排课结果。
回溯法适用于解的组合数相当大但仍然有限的那一类问题。它的一个有重要的特性是在搜索执行的同时产生解空问。在搜索期间的任何时刻.仅保留从开始节点到当前节点的路径。因此.回溯算法的空间需求为一个常数,即从开始节点起最长路径的长度。这个特性非常重要.因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话。再多的空间也不够用。其缺点是时间复杂度较大.因此在采用时还需要谨慎。最好是和其它的算法结合使用。


友情链接

联系我们