时间：2023-11-30 11:23:11
Abstract： The course scheduling system is very important in academic management of college. The improved adaptive genetic algorithm was discussed firstly, and then the design scheme of course scheduling system based on improved adaptive genetic algorithm was expounded through studying influence factors and main constraint condition in course scheduling problem in this thesis.
关键词： 自适应遗传算法；排课系统；应用
Key words： adaptive genetic algorithm；course scheduling system；application
中图分类号：G47文献标识码：A文章编号：1006-4311（2011）04-0170-02
1对自适应遗传算法进行改进
1.1 采用三维编码方法个体的编码方法对交叉、变异等遗传算子的运算方法及程序实现的复杂度都有很大影响。遗传算法最常用的编码方法是二进制编码，结合实际应用需求，均衡考虑制约学校排课系统的各因素，采用了三维编码。它具有以下优点：可方便地利用三维数组保存排课相关信息；编码和解码直观；进行交叉和变异运算时方便进行冲突检测和适应度计算以及程序实现复杂度低等。
一个采用三维编码表示的染色体可以直观地被看作是一个立方体，X轴表示时间轴，X轴上的每个时间坐标对应一个单位时间的间隔，根据学校实际情况，一个单位时间为一节大课的时间（两个课时），假如一周五个工作日、每个工作日三个时间段，那么X轴共有15个坐标值。Y轴每一坐标间隔代表一间教室，Z轴每一坐标间隔代表一个授课事件。其中，Z轴坐标（授课事件）又可以被分为Za（教师）、Zb（课程）和Zc（班级)三个分量。这样由三维坐标唯一地确定的那个小方块被称作个体的基因。在染色体全部基因块被赋值后，染色体就代表了一个课表编排方案。
1.2 采用基于符号函数的自适应遗传算法为了避免染色体早熟，改善了交叉与变异概率。采用基于符号函数的自适应遗传算法。将遗传的进化过程分成两部分：前期和后期分别取值。在前期，变异概率指定的区间内逐渐增大，变异概率逐渐减低，当适应度的值超过平均适应度值时，交叉概率下降，变异概率增加，从而能够很好地防止早熟现象的发生。基于符号函数的优化遗传算法，算法描述如下：①利用三维编码，进行编码／解码设计，组成初始群体；②定义适应度函数，计算各个个体的适应度；③以交叉概率Pc和变异概率Pm进行；
Pc=sinarcsin■-SGN■-1■■arcsin■
Pm=sinarcsin■-SGN■-1■■arcsin■
④若满足终止条件则退出算法，输出最优解。终止条件可以设定为指定最大代数或指定若干代无法取得更好的最优个体；⑤否则回到第2步。
2排课问题中的基本原则以及需要考虑的教学因素
课程表的编排工作就是要根据学校具体的教学资源情况，按照教学计划的要求，将课程、教师、学生在时间与空间上进行科学合理的排列组合。为了使编排的课程表更加符合教学规律，需要遵循以下原则：①某门课程只能为某一专业的学生安排一次；②同一位教师在同一时间段内只能安排一门课程；③在一个时间段内某专业的学生只能上一门课程；④教室的类型和容量要与学生人数和课程的需求相匹配；⑤同一教室在同一时间段只能安排一门课程。
要想使每一次教学活动都能够顺利进行，那么编排课程表时就必须满足以上五条原则，否则就会出现教学冲突，比如：同一位教师在同一时间段内被安排两门课程等。为了使排出的课程表更优化、合理，需要手工调整的内容较少，根据学院的具体实际情况排课时还应考虑以下因素：①同一门课程不能连续上，应该尽量分散在一个星期中，即某天上完某一门课后，要隔一天以上再上这门课。②尽量上午第一节课不安排自习课。③课程表中的上课时间不能过分集中，应该尽量避免一天课程很满而另一天却没有课的情况。④给两个或者三个教学班上同一门课程的老师，应尽量能上连续课程。比如一个老师给两个教学班上同一门课程，应尽量安排这位老师上完第一个班的课，在这一天内立即上第二个班的课，以保持两个班的教学进度一致。⑤尽可能满足个别教师的特殊上课时间要求。⑥尽量不使某一个教师在一周内总是上上午的第一节课。
3把改进的自适应遗传算法应用于排课系统，排课系统的设计方案
遗传算法可定义为一个8元组：GA=（C，P0，M，Φ，Γ，N，E，T）
式中，C―个体编码方法；Po―初始种群；M―种群规模；Φ―选择算子；Γ―交叉算子；N―变异算子；E―个体适应度评价函数；T―遗传运算终止条件。除了以上8元组之外，还有两个与遗传操作相关的参数：Pc交叉概率，Pm变异概率。
3.1 采用三维编码方法一个采用三维编码表示的染色体可直观地看作一个立方体。采用三维数组来分别表示X、Y、Z轴上的数据。
3.2 确定初始种群与种群规模在遗传算法中要产生初始种群，就必须进行种群群体的初始化处理，在初始种群产生的过程中，种群规模大小的确定非常重要。种群规模的大小会直接对遗传算法的执行效率和问题求解的最终结果产生影响。经过理论研究和实践证明，一般种群规模确定在20到100之间。本论文中优化后的排课系统经过测试，种群规模确定为35。
3.3 设计遗传算子
3.3.1 选择算子的具体实现过程如下：第一步：累加当前代种群中所有染色体的适应度函数值，得到总的适应度函数值；第二步：用每一个染色体的适应度函数值除以总的适应度函数值，便得到该染色体的选择率；第三步：根据每一个染色体的选择率复制该染色体进入下一代种群中。
3.3.2 交叉算子交叉算子在遗传算法中起着关键作用，是产生新个体的主要方法。交叉策略是：以垂直于z轴的平面将两个个体分割，交换两个个体的z>z’部分(z’为分割点)。
3.3.3 变异算子在遗传算法中属于辅的搜索操作，它的主要目的是维持群体解的多样性。变异策略是：随机地确定垂直于z轴的一个平面，为这个平面上的所有基因块重新随机地赋值0或1。
为了避免染色体早熟，改善交叉与变异概率。采用上述的基于符号函数的自适应遗传算法来确定交叉概率Pc和变异概率Pm。
3.4 确定适应度函数遗传算法是在个体适应度评价函数的引导下进行的。在设计个体适应度评价函数时，要充分考虑课程表的诸多约束因素。染色体的个体适应度评价函数定义为：fitness（Chromosome）=y（wi+pi）。（pi是约束因素的期望值，wi是pi的权重）
3.5 确定遗传算法的终止条件遗传运算的终止条件通常有以下几种：①一个个体已经满足最优解的条件，即最优解已经找到；②适应度已经达到饱和，继续进化不会产生适应度更好的个体；③进化次数的限制；④计算耗费的资源限制（例如计算时间、计算占用的内存等）；本排课系统中的遗传运算终止条件为：连续10代最大适应度函数值不改变。
4结束语
实验证明，把改进的自适应遗传算法应用到排课系统中，可以较好地完成整个学院的排课，同时提高排课效率。对于极个别产生冲突的课程，可人工进行调整。
参考文献：
[1]张建安，杨学俊，吴文一.基于关联规则算法的排课系统设计与实现.现代电子技术，2010，33(2):60-64.
关键词： 高中生物教学 遗传概率问题 “误” “悟”
新课程强调以学生发展为本，课堂教学不仅要关注知识和技能的掌握情况，更应对学生如何掌握和获得知识的过程与方法予以关注。特别是对于学生在掌握和获得知识的过程经中常出现的错误要予以关注。因为“错误”往往是发现“真理”的契机。高一学生初学遗传规律时，对遗传概率的计算经常出错，课堂教学中应该让学生勇敢地将错误展现出来，通过对自己错误思维的过程与方法的剖析，加深对知识的理解与掌握，学会从“误”中“悟”。
一、忽视概率的前提导致错误
例：两只杂种黑毛兔杂交产下四只小兔，则这四只小兔的表现型是（D）
A.三黑一白 B.全是黑色
C.两黑两白 D.以上情况都有可能
典型错答：A。
误区分析：这是一道遗传的分离定律常见题目，高一学生初学概率，解题的常规思维是亲本基因型为Aa×Aa，则后代表现型应该符合3：1的性状分离比，即三黑一白。而并未想到3：1分离比的一个重要前提是后代数量足够多，而此题只是一次实验且后代只有4只兔子，实验结果一定是偶然的。所以错误主要是学生对概率的前提理解不到位，未能从统计学意义上理解概率。
“误”中“悟”：概率的本质是描述某个事件发生的可能性的大小，它揭示的是随机事件在相同条件下做大量重复实验时所表现出的一种规律，也就是说概率的前提是样本需足够大对于一次实验来说，其结果是随机的，不确定的。
二、重复计算概率导致错误
例：父亲正常，母亲为红绿色盲基因携带者，他们婚后生了一个白化病孩子，则这对夫妇再生一个白花色盲男孩的概率是（1/16）。
典型错误：这对夫妇的基因型为AaX■Y×AaX■X■后代为白化色盲男孩的概率计算为：1/4×1/4×1/2=1/32。
误区分析：学生在计算此题时将白化色盲男孩当做三个相互独立的事件处理，即：白化、色盲、男孩。这样概率似乎理所当然计算为：白化概率×色盲概率×男孩概率=1/4×1/4×1/2=1/32。而未考虑到伴性遗传的特点是表现型往往与性别相联系，此题中患色盲的一定为男孩。因而导致概率重复计算而不知。
“误”中“悟”：要注意到概率计算中相互独立事件的“真”“伪”，概率计算中真正的相互独立事件是指事件A、B同时发生的情况下，事件A发生与否不影响事件B的发生（反之亦然）而有些相互独立事件并非真正相互独立，它们存在内在联系，特别是伴性遗传类题目要特别小心。
三、不理解概率的概念导致错误
例：如图是某白化病家族的遗传系谱，请推测Ⅲ-10与白化病男子结婚，生白化病孩子的概率是（1/3）。
典型错误：Ⅲ-10基因型为：2/3Aa或1/3AA白化病男子基因型为aa，则他们后代患病的概率为：0或1/3。
关键词：遗传算法 生理信号 情绪识别 特征选择
中图分类号：Q819 文献标识码：A 文章编号：1007-3973（2012）001-089-03
1 引言
情感计算是关于情感方面的计算，其目的是使得与人交互的计算机拥有识别、理解、表达情感的能力，其中一个重要组成部分是情绪识别。目前在情绪识别领域，国内外众多的研究机构和研究人员在生理信号等方面取得了不错地成果，但目前的主要精力都集中在情绪状态建模、与情绪相关的信号选择和情绪状态的分类判别等方面，对与情绪相关的信号进行特征选择的研究极少涉及，但是特征选择过程又是分类识别中不可或缺的重要环节，因此本文将自适应遗传算法应用于生理信号情绪识别的特征选择过程中。
2 遗传算法用于情绪特征选择的思路
遗传算法（GA, Genetic Algorithms）是经美国的Michigan大学的John Holland教授提出的一种模拟达尔文的自然选择学说和自然界的生物进化过程的随机搜索算法。自适应遗传算法通过自适应的方式对遗传算法的关键参数进行调整，能有效地解决早熟问题，而且能提高收敛精度，也显著地加快了收敛速度。其思路是首先从生理信号中提取特征构成原始的特征矩阵，再用遗传算法产生若干个可能的情绪特征子集，用评价函数来对每一个特征子集衡量其对于分类识别率的有效性，并记录当前识别率最高的情绪特征组合以及相应的识别率，直到满足算法的停止条件，最末代的适应度（即识别率）最大的个体就是对分类该种情绪状态效果最好的情绪特征组合。本文中分类器采用支持向量机算法。
3 生理数据特征提取
本文以德国奥森堡大学多媒体与信号处理实验室提供的情绪数据进行特征提取。该数据采用的是被试者在高兴、愤怒、悲伤和愉快这四种情绪状态下的四个生理信号（肌电、皮肤电导、心电图和呼吸信号），采集25天的生理数据，共计100个样本。然后对每种生理数据进行统计特征提取，提取出186个特征作为原始特征集，对上述的186个特征进行特征选择实验分析和分类结果分析。其中提取的统计特征有均值、标准差、中值、一阶差分、最值等等。不同的生理信号还具有各自不同的特征，如ECG信号P波、R波、Q波、S波的幅度峰值、HRV（心率变异性）、给定频段的功率谱密度，其他信号还有诸如RSP的呼吸率等等。
4 自适应遗传算法用于特征选择
4.1 染色体编码
二进制编码方法是遗传算法中常用的一种编码方法，它所使用的编码符号集是由二进制符号0和1所组成的二进制符号集，它构成了一个二进制编码符号串的个体基因型。这种编码方式简化和优化了交叉、变异等遗传操作。二进制编码是一种对于特征选择较好的编码方法。
4.2 评估函数的确定
特征选择是为了少量达到相同的或更好的分类效果，因此适应度的评价一共包括两大部分：(1)分类识别率；(2)使用的特征数量。因此构建适应度函数必须全面考虑两个部分的影响作用，选出的每个特征子集包含一定数量的特征，如果两个特征子集得到的识别率相同，则包含特征少的子集被选中。因此，适应度的选择如式4-1所示。
Fitness=CreRate+zeros （4-1）
式（4-1）中，C为准确率的经验权值，为提高分类正确率的重要性，赋予较大的权重，根据实验决定，reRate为识别率，zeros为染色体中包含“0”的数量，高分类正确率就意味着高适应度，准确率相同的两个个体，特征数少的就会在竞争中获胜。本文中识别率reRate为SVM分类判别后的识别率，即特征选择过程中需要调用分类器对样本进行分类评估得出识别率以此识别率再对遗传算法选择的特征进行评估，使识别率高的特征容易保留下来。
4.3 遗传算子设计
4.3.1 选择算子
本课题尝试采用非线性排名算法和锦标赛法相结的选择算法，当遗传开始的初期，尽量使用非线性排名算法以克服早熟问题和停滞现象，并改善锦标赛算法不利于开发搜索其他可行区域的缺点；在遗传算法的后期，尽量使用锦标赛算法，发挥其动态性能，并提高运算速度，克服非线性排名的运算速度低下的缺点。这里所说的“尽量”是一个概率的概念，并非一定，这个概率概念的“尽量”又通过赌的方式实现，由gen/MAXGEN来作为概率，其中gen为当前代数，MAXGEN为最大代数。
4.3.2 交叉算子
传统的交叉算法存在一个致命的弱点――早熟，即收敛到局部最优解而非全局最优解，因此需要对交叉算子进行自适应改进，通过采用不同的交叉概率变化方式来得到自适应的交叉概率，更加合理的分配每一个个体的交叉概率的大小，提高算法的计算速度，减小收敛的代数，提高收敛的精度。
双重自适应交叉概率是随着进化代数和适应度的变化而变化的。首先将交叉分为三个阶段，其中每个阶段交叉概率的上限和下限都是不一样的，上下限随着进化代数的增加而减小，这种从广泛到细致的搜索有效的避免了最优解被破坏的情况。另外，利用正弦自适应的变换方式得到交叉概率。这里采用分阶段交叉概率从大到小的变化方式，在整个进化阶段交叉完成从广泛到细致的搜索操作，这样既可以保证搜索的全面性，又可以更快的收敛从而得到最优化的解。
正弦自适应的交叉概率计算式压低了处于平均适应度favg附近以及最大适应度fmax附近的个体的交叉概率，所以这里的交叉概率是是按曲线进行变换，而不再是按个体的适应度进行简单的线性变换，另外，通过与分阶段交叉概率相结合的办法，正弦自适应交叉概率计算避免了交叉概率的骤升骤降，使交叉概率稳定的沿着从大到小的方向变化。通过将两种方法结合在一起，既算法进化过程的稳定性得到了提高，也减少了收敛的代数。
设最大进化代数为MAXGEN，交叉概率上限为Pc1，下限为Pc2，三个阶段的划分采用黄金分割点划分法：第一阶段为[0,0.382MAXGEN),此时Pc1和Pc2可以取大一点，初始分别设为0.9和0.7；第二阶段为：[0.382MAXGEN,0.618MAXGEN)，此时按Pc1和Pc2差值0.2，将它们分别设为0.7和0.5；第三阶段为：[0.618MAXGEN,MAXGEN)，Pc1为0.5，Pc2为0.3，这样交叉概率公式如式4-2。
（4-2）
式4-2中，Pc1和Pc2为交叉概率的上限和下限，f'为两个要交叉的基因的适应度的最大值，fmax为种群最大适应度值，favg为种群评价适应度值。
4.3.3 变异规则
对于自适应的变异，本文主要是对自适应的变异概率进行改进，采用以下策略：通过从广泛搜索到细致搜索（即变异率减小），产生新的个体，当变异率减小到一定程度或者种群迭代到一定的代数时，保留新的个体，并将新种群作为初始种群循环进行从广泛到细致的搜索过程，直到算法结束。也就是说将大变异概率作为依据，把更多的个体变异到距离原来比较远的地方。
变异概率的自适应调整的原理同自适应交叉算法的交叉概率原理，如下：
（4-3）
式中：Pm1和Pm2为交叉概率的上限和下限，f'为要变异的基因适应度，fmax为种群最大适应度值，favg为种群评价适应度值。
4.3.4 终止条件
终止条件不但考虑最大迭代次数，还要考虑能否自动判别算法达到收敛。算法是否收敛是以最大识别率c_best和种群平均识别率c_avg为统计对象，对c_best和c_avg在某一范围内波动的代数进行统计，如果超过K代没有较大波动，则终止算法。经过调研，此处的值一般为种群大小的1/3。
如何判定c_best和c_avg没有较大的波动，是c_best和c_avg曲线在K代内趋于水平，最大值和最小值之差小于一定的阀值（Max_Min），误差不会超过一定阀值（Var）。
其中曲线趋于水平的判别变量本课题采用线性拟合的方法，即考虑K代范围内，将c_best和c_avg进行线性拟合，拟合后的结果分别为：
c_best_line=S_best(1)t+S_best(2)
c_avg_line=S_avg(1)t+S_best(2) （4-4）
其中c_best_line和c_avg_line为拟合输出，t=1,2,3…K，为遗传代数，S_best(1)和S_avg(1)是两个线性拟合直线的导数，本课题以S_best(1)和S_avg(1)分别作为c_best和c_avg在K代内是否水平的判别参数，当他们的绝对值小于等于一个阀值S_时认定满足第一条件。本文中阀值S_设为0.50-3时可以满足导数水平的条件。
5 实验结果
根据德国奥森堡大学提供的实验数据，对共计100个样本提取出186个特征作为原始特征集，对上述的186个特征进行特征选择实验和分类结果分析。
自适应遗传算法特征选择的参数设置如下：种群大小为80，采用非线性排名选择和锦标赛法混合选择算法作为特征选择，采用自适应多点交叉，初始交叉概率为0.85，采用自适应变异，初始变异概率为0.02,最大迭代次数为200，支持向量机的评价策略采用随机法（random-split）进行分类评估时结果如图1所示。
实验运行10次的结果如表1所示。
如表1所示，本文研究的自适应遗传算法，用于德国奥森堡大学的数据库，在平均识别率为90.68%的情况下算法终止代数大概在49代左右，算法选出的特征个数大概在52个左右，识别率的最大最小值之差仅为6.91%，有限次测量数据的标准偏差的估计值为4.1051，效果十分不错。
本课题还分别采用SGA、ANOVA、SFS、SBS对同一数据库进行特征选择研究，都采用SVM作为选择策略进行特征选择，跟本课题改进的自适应遗传算法进行对比，其结果如表2所示。
表2中，SFS和SBS特征个数是手动设置的，本课题将其特征选择个数设为52以和自适应算法进行比较。通过表中数据可以看出，本课题改进的遗传算法无论是在特征选择个数还是在最终识别率上，均优异于其他算法。
6 结论
本文选用了四种与情绪相关的生理信号，ECG、EMG、RSP和SC，用其分类识别Joy、Anger、Sadness和Pleasure这四种情绪状态，并以德国奥格斯堡大学多媒体与信号处理实验室的数据为例，应用人工智能算法中的自适应遗传算法对分类识别过程中的最优化特征子集进行研究。为更科学地进行情感计算提供新的方法，有着重要的学术价值和应用意义。
参考文献：
[1] Sloman A.More things than are dreamt of in biology: Information Processing in Biologically Inspired Robots [J].Cognitive Systems Research,2005(6):145-174.
[2] Stemmer G, Heldmann M, Pauls C A, et al. Constraints for emotion specificity in fear and anger:the context counts [J].Psychophysiology,2001,38:275-291.
[3] 周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1999.
[4] 李敏强,寇纪松,林丹,等.遗传算法的基本理论与应用[M].北京:科学出版社,2004.
一、先审题，再下笔
在许多遗传的计算中，常常由于审题不清而出现一些错误，所以一定要看清题目。
例1 ：一个正常男孩体细胞中的46条染色体，来自其祖父的染色体。
A.12条的可能性最大
B.一定是23条
C.最多不超过13条
D.可能不含有
解析：学生往往会选B项。原因在于审题时没有看清楚题目要求。
考虑常染色体的来源是男孩有22条（都是非同源染色体）来自父亲。而父亲有22 条（都是非同源染色体）来自祖父，那么来自父亲的22条非同源染色体可能全来自祖父（只要是非同源染色体就行了）也可能为0条常染色体。再考虑性染色体，男孩的Y只能来自于父亲，而父亲的Y只能来于祖父，所以男孩一定从祖父得到Y染色体。即D不对。那么来自祖父的染色体的数目在23至1。即最多是23条。最少是1条。可排除B、C。选答案A由于父亲从祖父和祖母各得到22条常染色体，所以在传给男孩的概率相等因此从祖父得到11条常染色体的可能性最大。再加上Y性染色体，是12条。
二、考虑问题要周到
在遗传的计算中，亲本常常有多种可能的基因型，因此，必须确定好亲本的基因型的比例。
例2：囊性纤维变性是一种常染色体遗传病。在欧洲人群中，每2500个人中就有一个患此病。如一对健康的夫妇有一患有此病的孩子，此后，该妇女又与健康的男子再婚。再婚的双亲生一孩子患该病的概率是多少？
通过题干可以看出，控制该病的基因是隐性基因。设控制该性状的基因为A和a，因为2500人中有1个人是患者，所以a基因频率是1/50，所以A的基因频率是49/50，健康人的基因型为AA或Aa，Aa在人群中的比例为2×1/50×49/50，AA在人群中的比例为49/50×49/50，所以Aa在健康人群中的比例为：2×49/49×49+2×49=2/51。由于该妇女的基因型为Aa，所以她与健康人婚配后患病的概率为0+1/4×2/51=1/102。这种类型的题目是易错题，一般人会忽略Aa在健康人群中的比例，而直接将其在整个人群中的基因型比例带进去，而得出错误答案。
三、正确地使用加减乘除法进行解题
拿到一道题目，我们首先要对它的遗传图解进行分析，然后再套用法则，若一个人甲病的患病概率为A，则正常的概率为1-A；乙病的患病概率为B，则正常的概率为1-B。则此人：只患甲病的概率：题意是患甲病，但乙病方面正常，上诉两种情况同时成立，用乘法。即：A×（1-B）。只患乙病的概率：同理：（1-A）×B。同时患甲乙两种病的概率：A×B。不患病的概率：（1-A）×（1-B）。患病的概率：第一种方法：它包括只患甲病，只患乙病，同时患甲乙两病，三种情况都符合题意，所以用加法原则。A×（1-B）+（1-A）×B+ A×B。第二种方法：除去正常的剩下都是患病的，1-（1-A）×（1-B）。
例3 ：患甲病（显性基因为A，隐性基因为a）和乙病（显性基因为B，隐性基因为b）两种遗传病，已知Ⅱ-1不是乙病基因的携带者，请判断：
（1）甲病是 性遗传病，致病基因位于 染色体上
（2）乙病是 性遗传病，致病基因位于 染色体上。
（3）Ⅲ-2的基因型是____。
（4）若Ⅲ-1与Ⅲ-4结婚，生一个只患甲病的概率是____，同时患两种病的是____，正常的概率是____， 患一种病孩子的概率是____。
解析：解题步骤：第一步将甲乙两种病的系谱图分开来画。
（1）甲病：II-5，II-6，III-3的关系，有中生无是显性。看男病II-5，若为伴X，则I-1，III-3都应该有病，但是图中看出III-3是没有病的，所以否定伴X遗传。则甲病为常染色体显性遗传病。
（2）乙病：II-1，II-2，III-2的关系，无中生有是隐性。如果常染色体遗传则II-1一定是乙病的携带者，这明显与题意矛盾。所以乙病为伴X染色体隐性遗传病。
（3）从甲病看，Ⅲ-2的基因型为A，II-1aa一定要把一个a给Ⅲ-2，所以Ⅲ-2的基因型确定为Aa。从乙病看，Ⅲ-2的基因型为XbY。两者组合Ⅲ-2的基因型为AaXbY。
（4）若求若Ⅲ-1与Ⅲ-4结婚，生一个患病孩子的概率是多少，必须先清楚Ⅲ-1与Ⅲ-4的基因型及概率。
甲病：Ⅲ-1：aa×Ⅲ-4：1/3AA，2/3Aa
甲病：1/3×1+2/3×1/2=2/3；
无甲病：2/3×1/2=1/3。
乙病：由条件知II-1：XBY，II-2：XBXb；Ⅲ-1：1/2XBXb ，1/2XBXB×Ⅲ-4：XBY
乙病：1/2XBXb×XBY：1/2×1/4=1/8；
无乙病：1-1/8=7/8。（或者：1/2×1+1/2×3/4=7/8。）
只患甲病：2/3×7/8=7/12
患两种病：2/3×1/8=1/12
正常：1/3×7/8=7/24
患一种病：7/12+1/24=15/24
因此，我们在解题时要细心，不要怕烦，掌握了好的方法，搞清楚了概念大部分题目都会迎刃而解。
参考文献：
[1] 邓成武.从审题开始破解一道遗传学难题，中学生物学.2013.
[2] 徐海燕.生物遗传概率计算的相关技巧探讨，吉林教育：综合.2013.
[3] 张克芳.浅析高中生物遗传学习题的解析技巧，理科考试研究：高中版.2013.
【关键词】自适应遗传算法；计算过程；优化施工
1 自适应遗传算法在工程中的应用
在实际的工程设计中，由于一些技术性指标的计算和设计往往都有涉及到多元化的因素，因此多数设计的变量都是呈现离散状态，也就是其设计参数和指标没有固定的线性规律可言依循，只能去有限定条件的离散值进行设计，离散变量的结构优化属于是网络化问题，其求解也是网络化中较为困难的问题。遗传算法的提出是利用自然界生物法则为基础，利用生物化模拟自然界中的遗传和进化而形成的概率性全局收敛型的计算方法。因为在工程中解决全局性优化不完全依赖于模型特性和可并行性的高效率，所以这个方法成为了解决离散优化问题时较为合理的算法。
近些年，遗传算法在工程结构优化领域中得到了广泛的重视和应用，就是因为其对建筑工程中离散变量的结构优化应用有着现实意义。遗传算法依据的是自然法则，即适者生存、优胜劣汰，这种规律使得不同的生物种群得到了进化和发展。遗传算法的选择、交叉、变异等计算因子的形成正是受到了自然法则的影响，而对生物繁衍、变异、竞争、选择等进化机制的类似和模拟。与传统的优化计算方法相比较，遗传算法对处理对象的基本属性没用限定，具有很好的全局性能，依据适应函数的值进行遗传计算，不需要多余的信息资料，因而在模拟识别、系统控制等具有较好的实践经验。
2 关于优化设计的数学模拟
在存在变量的设计优化中，通常参与的函数包括了目标函数和约束函数，约束函数的作用是对达成目标的韩式进行条件上的约束，即要实现某个目标则必须以某种条件为约束。其中涉及到的数学参数有设计变量X，目标函数用F(X)表示，其变化方向为最大或者最小，而约束函数利用gj(X)表示，其值满足gj(X)≤cj，其中j=1,2,3，…k。
3 如何实现自适应遗传计算
通过前面的表述，遗传算法的机理是借助于遗传和自然优选，并以此得到优化结果，同时在计算中将其所涵盖的空间映射到遗传空间，即将问题转化为遗传问题。这时每个可能的求解编码即转化为一个与染色体相似的数字串，所有的染色体组成的种群及时计算的基础。对于重力坝体型优化来说，遗传算法可以解释为，所及的种群（POP）组表征重力坝形体中可控的变量，这些序列中的变量可以利用前面提到的X来表示，从而形成一个以n个变量为量级的种群组，并将其作为进行优化的母体，按照预先设定的目标，即目标函数来进行评价，种群中每个染色体的适应度，根据对染色体的适应度来进行选择、交叉、变异等遗传学操作，从而将低适应度的元素剔除，保留适应性高的染色体，从而到了新的种群。这样就可以完成一种收敛式的遗传计算，从而得到重力坝的形体优化。
3.1 对参数进行编码组合
为了使得计算更加简单和可操作，因此应对具体变量进行编码。影响因素即为染色体的每个向量都是可以成为优化设计中可控变量的真实值，公式如下：
（i=1,2,3，…，n）
公式中的的各个变量就是实际中的控制参数，变量表示为xi，这个数值从最大到最小变化；而m为设计时控制的精度要求；Nrand则是一个小于m的随机数。这样就将整个变量归纳在一个编码组中，方便计算。
3.2 优化中的适应函数
遗传算法是一个对个体进行优势评价的过程，适应性的求解是非负数的，因为必须适应最低要求，而且体现出来的适应性概率是最大值，因为需要优胜劣汰。对与最小值的问题则需要理由目标函数和适应度函数之间的转换来实现。因此采用适应度函数来衡量，具体如下：
公式中的f(X)即表示为目标函数，c则是目标函数的界定值，为保守估计，同时c满足大于0，同时c+f(X)也大于0。但是遗传算法的计算中通常只能计算没有条件限制的问题，因此需要通过约束函数将其规则性问题转换为无约束的问题，以此适应算法。设计变量的结合约束在编码的时候就应当予以考虑，如采用某种函数来进行处理，即利用满足某种条件函数的参与将整个计算约束起来。
3.3 运算的实现
3.3.1 交叉的计算
交叉计算从遗传角度看，就是寻找父本双亲已有但是没有体现价值的遗传基因。实数编码采用的是交叉计算，即利用随机的样本进行线性组合形成两个子代。计算中架设两个父本进行交叉产生后代，其运算中的变量为随机数。
3.3.2 变异的计算
通过变异可以将新的基因导入到种群中，遗传保证种群的多样性，这在某方面看就是利用计算将可变的影响因子导入到遗传中，使得产生的收敛的结果更加的合理化。具体的方法是：设一个个体X的每个分量为Xi，i=0,1,2,3，…，n并以概率为1/n来变异。设对分量变化的Xk进行变异处理，其定义的区间为最大到最小，则有公式：
公式中的Rand则是0-1之间的随机数值，rand函数则是产生最大值的正整数。
3.4 对参数的适应性调整
在遗传算法中，参与的交叉和变异都是建立在概率的基础上，由于概率的参与使得算法会受到一些不利于计算的影响，从而影响收敛的效果。在这里如果交叉概率大就好使得新个体产生速度快，当交叉概率超过一定范围的时候就会影响传统的遗传模式，而导致计算结果失控，如果变异概率小就会导致没有新个体，如果其无限增加则会导致整个计算变成单纯的随机计算。因此在实际的应用中一个利用适当的计算方法的约束，控制适应性参数的无限变化。
4 重力坝的优化
在利用自适应遗传计算优化重力坝的体型时，首先应根据实际的施工要求设定约束变化的基本条件，如下：上游坝坡的坡率约束条件；下游的坝坡的坡率条件；上游折坡点最高点高度占坝高的比例限制；下游折坡的最高点高度占坝高的比例限定；稳定约束参数；坝踵的应力参数；坝趾的应力参数。利用这些基本条件的限定来对整个遗传变异的情况进行约束，以此达到利用遗传算法优化的目的。
在计算中，大坝的高度和大坝顶部的宽度可以看做是设计中的定量，因此设计中的变量就取决于上游坝坡的坡率和下游坝坡的坡率，上游的折坡点比例和下游的折坡点比例，其运算的目标函数就是大坝的横断面积。这样就可以将大坝的设计转化为遗传算法，将优化设计转化为对变量X的求解，而其中大坝的横断面积则趋向于最小，同时满足前面提及的多个约束条件。这样既可利用遗传算法得到合理的大坝的截面积，这样就可降低大坝的施工成本和施工的工艺难度。
5 结束语
总之，在利用遗传算法进行大坝优化设计的时候，需要掌握的是遗传算法的关键点，即对某些条件的限定一定要准确，同时对所求解的变量应进行合理的选择，对于大坝而言，其设计的优化核心就是在稳定和安全的基础上降低成本和施工难度，因此应将截面积设定为变量，并以此为核心进行约束性的遗传计算，已得到收敛结果。
参考文献：
[1]涂年华,郑楠.基于遗传模拟算法的水库坝体模型参数优选[J].水电自动化与大坝, 2009,(03).
[2]王玉鹏,孔晓东.基于改进遗传算法的水电坝体设计研究[J].大坝工程, 2009,(05) .
[3]杨道辉.利用遗传算法的水库优化设计[J].水电自动化与大坝监测, 2009,(05) .
摘 要： 量子遗传进化算法是量子计算和遗传算法相结合的产物，量子比特是两个量子态的叠加态，在此，详细介绍了量子遗传进化算法。尝试使用量子遗传进化算法来解决高校排课问题，并进行了实验。实验结果表明，该算法获得了比较好的结果。
关键字： 高校排课问题； 遗传算法； 量子遗传进化算法； 课程表
中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2013）20?0007?04
高校排课问题一直是很多人关注的一个问题，排课问题的本质是将课程、教师和学生在合适的时间段内分配到合适的教室中，涉及到的因素较多，是一个多目标的调度问题，在运筹学中被称为时间表问题。
1 排课问题分析
高校排课问题中实际上是时间表安排的问题[1]。在实际排课过程中，主要涉及到：教室、班级、课程、时间和老师等5个因素的问题。在处理这5个因素关系的过程中会发生很多冲突，这就需要有一些约束条件，这些约束条件可以大致分为硬约束和软约束，详见表1。
根据以上的分析排课问题数学模型分为下面5个集合如下：教室集合：[R={r1，r2，…，rm}]；班级集合：[C={c1，c2，…，cn}]；课程集合：[L={l1，l2，…，lp}]；教师集合：[S=表1 排课问题的软硬约束条件
上述5个元素是影响排课问题的主要的因素，每个集合中取一个组成在某个时间某班上的课程由哪位老师来授课，在哪个教室上课，但必须满足一定的条件。
2 量子遗传进化算法
量子遗传进化算法是量子计算与遗传算法相结合的产物[2]。目前，这一领域的研究主要集中在两类模型上：一类是基于量子多宇宙特征的多宇宙量子衍生遗传算法（Quantum Inspired Genetic Algorithm）；另一类是基于量子比特和量子态叠加特性的遗传量子算法（Genetic Quantum Algorithm，GQA）[3]。
2.1 量子位表示法
在量子信息论中， 信息的载体不再是经典的比特，而是个一般的二态量子体系，称为量子比特（qubit）。量子比特与经典位不同就在于它可以同时处在两个量子态的叠加态中[4]，比如：
式中：[α，β]是两个复常数，满足：
式中[0]和[1]分别表示自旋向下和自旋向上态。所以一个量子比特可同时包含态[0]和[1]的信息；[α]表示相应的 qubit 处于0状态的概率幅；[β]表示其处于1状态的概率幅。[α2]表示处于0状态的概率，[β2]表示处于1状态的概率[3]。一个具有m个量子比特位的系统可以描述为：
其中[αj2+βj2=1，j=1，2，…，m]。这种表示方法可以表示任意的线性叠加态， 例如一个具有如下概率幅的量比特系统：
则系统的状态可以表示为：
上面结果表示状态[00，001，010，011，100，101，][110，111]出现的概率分别为[38，132，332，332，332，][132，332，332，]即这个量子比特系统表示了8个状态叠加的信息而且随着趋于1或0， 量子染色体收敛于一个状态， 这时多样性消失， 算法收敛[5]。
2.2 量子旋转门
在遗传算法中，可以通过交叉，变异来得到新的个体，而在量子遗传进化算法中，是通过量子旋转门来进行更新的[6]。
量子旋转门如下：
比如对[αiβi]进行更新，可以用式（6）来进行更新：
式中[Δθi]的取值对算法的执行效率有很大的影响，具体确定过程如表2所示。其中：[fx]和[fb]表示解的 fitness，[x]为当前解，[b]为 [btj]；[Xi]和[bj] 分别表示解[x]和[b]的第i个 bit 位的取值；[sαiβi]为[Δθi]的符号[7]。
例如，如果条件[fx≥fb]成立，且[xi]和[bj]分别为1和0，则[Δθi]的取值为0.025π，然后根据[αi]和[βi]的值可将其符号设置为+1，-1和0来增加 qubit 处于1状态的概率。若[αiβi>0]，即[Δθi]为+0.025π，将[Δθi]代入式（6）中得到新的[αli]和[βli]，使qubit处于1状态的概率增加，具体分析如图1所示。
[Δθi]取值的大小会影响算法的收敛速度，如果取值过大会导致早熟收敛得不到最优解；[Δθi]的符号决定解的收敛方向[8]。
3 量子遗传进化算法和遗传算法来解决高校
排课问题
3.1 具体高校排课问题简介
对于一个具体的排课问题，分别采用量子遗传进化算法和遗传算法来解决，并对它们的结果进行分析[9]。简化的高校排课问题是针对一个班级来排课，有7门课程，其中，有部分课程是一周上一次，还有部分课程是一周上两次，每门课程都有各自的重要性，每个时间段，都有不同的听课效率，为了排出合格课表。下面先通过量子遗传进化算法来排课表，最终得到的课表通过课程的重要性乘以时间段的听课效率的总和来比较课表的优劣，最终的值越大，且不存在冲突，则课表越好[10]。
图1 量子门坐标图
排课时的一些要求，其中一周上两次的课，不能排在同一天或者相邻两天，至少相差一天。项目中主要牵涉到的数据，每门课程的重要性，将它们存放在一个数组中，其中，无课也放在了数组中，则最终的数组应该是一个一维数组，包括8个元素。
int classWeights[] ={0，70，60，55，75，80，90，85}
对应的课程为无课，体育，计算机基础，政治，数据结构，高数，英语，操作系统。其中，classWeight[0]无课的重要性，没有课程 ，那重要性当然为0，后面依次是第几们课程的重要性。下标为几，即为第几们课程的重要性。各个时间段的重要性存放在一个二维数组中，数组中共有25个元素，因为这里讨论的排课问题，一个星期共有五天上课，一天共有五节课，其中上午两节课，下午两节课，晚上一节课，这里的一节课包括两个学时。第一个下标加1后的值表示的是星期几，第二个下标加1后的值表示的是第几节课，如timeWeights[2][3]表示的是星期三第四节课。有：
double[][] timeWeights =
{ { 0.65， 0.90， 0.85， 0.60， 0.50 }，
{ 0.90， 0.85， 0.80， 0.75， 0.70 }，
关键词：遗传计算教学 基本原理 特殊处理
在遗传知识的学习中，关于遗传概率的计算，是学生最棘手的问题，如何让学生突破难点，更好地掌握这一知识，化难为易，是教师教学的重点。在教学中，既要要求学生掌握遗传计算的基本原理（即概率的运算定理），又要注重概率定理的实际应用和相关数据的灵活处理，才能达到夯实基础，培养能力的目的。
1 遗传计算中的基本原理
1．1 关于遗传中的计算，主要是涉及概率的计算，故概率计算的基本定理即为遗传计算中的基本原理。概率是指某一事件发生的机会和可能性的大小，即某一事件发生的次数在总事件中所占的比例。概率是生物统计学中最基本的概念，它的大小在0~1之间。概率计算的基本定理主要是乘法定理和加法定理。
1．2 乘法定理，两个或两个以上的独立事件同时出现的概率等于它们各自概率之积。所谓独立事件是指一个事件的发生与另一个事件的发生没有关系。在教学中，教师可先以抛掷硬币为例分析，再以简单的遗传计算入手，要求学生掌握，做到知其然且知其所以然。例：同时抛出两个硬币，每一个硬币出现图案或文字在上的概率都各是1/2，且抛出的两个硬币互不影响，故构成两个独立事件。那么两个硬币都是图案在上的概率为它们各自概率的乘积，即1/2×1/2=1/4。同理，任意两个面同时在上的概率均为1/2×1/2=1/4。由此引入遗传计算：基因型为Rr的个体自交时，亲本产生R和r雄性配子的概率都分别是1/2，产生R和r雌性配子的概率也分别是1/2，且产生雄配子和产生雌配子互不影响，即构成独立事件。则通过受精作用结合成合子时，出现RR的概率为1/2×1/2=1/4，出现rr的概率也是1/2×1/2=1/4，出现每一个Rr的概率也是1/2×1/2=1/4。
1．3 加法定理，如果两个事件非此即彼，或相互排斥，则出现这一事件或另一事件的概率是它们各自概率之和。例：抛掷一个硬币，下落后，图案在上或是文字在上的概率都各是1/2，且图案在上时文字就不可能在上，文字在上时图案也不可能在上，这就构成了两个互斥事件。则在抛出下落后，图案在上或文字在上都可的概率为它们各自概率之和，即1/2+1/2=1。同样由此引入遗传计算：基因型为Rr的个体自交时，后代可能基因型为RR、Rr、rr，且它们各自的概率分别为1/4、1/2、1/4。在实际中，每一个雌配子或雄配子都只有一次受精的机会，故可推出出现RR、Rr、rr的事件为互斥事件，若现在要推算出现纯合子的概率，即出现RR或rr均可，则可利用加法定律计算，即出现纯合子的概率为1/4+1/4=1/2；若要推算出现显性性状的概率，即出现RR或Rr均可，同理其概率为1/4+1/2=3/4。
2 用乘法定理分析孟德尔关于两对相对性状的杂交实验
2．1 掌握了遗传学中概率计算的两个基本定理，应将其融会贯通，用于分析解释孟德尔的遗传实验，加深学生对知识的理解。我们知道，一对等位基因（Rr）的杂合子自交时，后代基因型之比为RR∶Rr∶rr=1∶2∶1，即3种基因型，2种表现型，且表现型之比为3∶1。那么两对或两对以上等位基因的杂合子自交时（每对等位基因独立遗传）（下同），用乘法定理求其基因型种类及比例或表现型种类及比例，以及每一种基因型或表现型的概率均可迎刃而解了。例：基因型为YyRr的黄色圆粒豌豆自交时，因为豌豆种子的颜色和形状是由两对相对独立的基因控制的，各自独立遗传，构成独立事件，且要同时成在，符合乘法定理的条件，故可用乘法定理解之。在求解时，先把这两对独立遗传的基因分开，一对一对地看，再利用乘法定理计算。即：基因型的种类为3×3=9种，其比例为（1∶2∶1）×（1∶2∶1）=1∶1∶2∶2∶4∶2∶2∶1∶1，基因型依次为YYRR，YYrr，YYRr，YyRR，YyRr，Yyrr，yyRr，yyRR，yyrr。表现型种类为2×2=4种，其比例为（3∶1）×（3∶1）=9∶3∶3∶1，表现型依次为黄色圆粒，黄色皱粒，绿色圆粒，绿色皱粒。
3 用乘法定理求子代概率
3．1 用乘法定理求子代基因型概率和基因型种数
3．1．1 具有两对或两对以上相对性状的个体杂交，子代基因型的概率等于每对相对性状相交所得的基因型概率的乘积。
例：已知双亲基因型为AaBb×AABb,求子代基因型为AaBb的概率。
解：Aa×AA1/2Aa，Bb×Bb1/2Bb，
子代AaBb的概率=1/2×1/2=1/4。
3．1．2 具有两对或两对以上相对性状的个体杂交，子代基因型的种数等于每对相对性状相交所得的基因型种数的乘积。
例：已知双亲的基因型为TtRr×ttRr，求子代有几种基因型。
解：Tt×tt2种(Tt、tt)，Rr×Rr3种(RR、Rr、rr)，
子代基因型种数=2×3=6种。
3．2 用乘法定理求子代表现型的概率、表现型种数和表现型比值
3．2．1 具有两对或两对以上相对性状的个体杂交，子代表现型的概率等于每对相对性状相交所得的表现型概率的乘积。
例：已知双亲基因型为AaBb×AABb,求子代双显性性状（A_B_）的概率。
解：Aa×AA1(AA,Aa)，Bb×Bb3/4(BB,Bb)，
双显性性状（A_B_）的概率=1×3/4=3/4。
3．2．2 具有两对或两对以上相对性状的个体杂交，子代表现型的种数等于每对相对性状相交所得的表现型种数的乘积。
例：已知双亲的基因型为TtRr×ttRr，求子代表现型种数。
解：Tt×tt2种(Tt、tt)，Rr×Rr2种(R_、rr)，
子代表现型种数=2×2=4种。
3．2．3 具有两对或两对以上相对性状的个体杂交，子代表现型的比例等于每对相对性状相交所得的表现型比例的乘积。
例：已知双亲基因型为YyRr×Yyrr，求子代表现型的比值。
解：Yy×Yy(1YY，2Yy)∶yy=3∶1，Rr×rrRr∶rr=1∶1，
子代表现型比值为：（3∶1）×（1∶1）=3∶1∶3∶1。
4 遗传计算中数据的特殊处理
4．1 在遗传计算题中，若能根据数据特点，结合遗传知识，利用乘法定理或加法定理的原理对其数据进行特殊处理，便能达到化难为易，轻松解题的效果。
例：在香豌豆中，当A、B两个显性基因都同时存在时，花色为红色，一株红花香豌豆与基因型为Aabb的植株杂交，子代中约有3/8的个体开红花，若让此植株自花受粉，则后代中非红花植株占（Aa与Bb自由组合）：A.10/16B.6/9C.7/16 D.6/16。要求出后代中非红花植株所占比例，则要先求出亲本中红花香豌豆的基因型，而解此题的关键在于对3/8的特殊处理。由题意可知亲代基因型可表示为A_B_×Aabb,已知子代有3/8的个体开红花，即有子代3/8A_B_，而3/8=3/4×1/2。根据亲代基因型为A_B_和Aabb，可推出3/4为一对等位基因的杂合子自交所得含显性基因个体的概率，即：Aa×Aa3/4A_；1/2为一对等位基因的杂合子与隐性纯合子杂交所得含显性基因个体的概率，即：Bb×bb1/2Bb，由此可知，亲代中红花香豌豆的基因型为AaBb。其自花受粉即自交时，可产生9/16 A_B_（为红花），其于均为非红花植株，即为1-9/16=7/16。正确答案为C。
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文
再例：一杂交组合后代的表现型有四种，其比例为3∶1∶3∶1，则这组杂交组合为：A.Ddtt×ddttB.DDTt×ddTtC.DDTt×Ddtt D.Ddtt×DdTt。此题是已知后代表现型种数和比例求亲代基因型及其组合，若从被选项中逐一推算则太繁琐，巧解此题的关键是对数据的转换处理，即：3∶1∶3∶1=（3∶1）×（1∶1）。由3∶1可看出，亲代是一对等位基因的杂合子自交，由1∶1可看出，亲代为一对等位基因的杂合子和隐性纯合子测交，再将两组亲代基因组合即可得出正确答案D。
4．2 在遗传规律的学习中，对课本中几组常见数据必需熟记于心。有时，试题中一些数据就是课本数据的变形。在实际应用时，若能对一些数据进行巧妙处理，将其还原成原来的形式，就能很清析地看出其中的内函，问题就会迎刃而解了。
例：一种观赏植物，纯合的蓝色品种与纯合的鲜红色品种杂交，F1为蓝色，F1自交，F2为9蓝∶6紫∶1鲜红。若将F2中的紫色植株用鲜红植株授粉，则后代表现型及其比例是：A.2鲜红∶1蓝B.2紫∶1鲜红C.1鲜红∶1紫D.3紫∶1蓝。由题意F1为蓝色可知：蓝色为显性，鲜红色为隐性。解此题的关键在于确定F2中紫色植株的基因型，然而题目并未对其基因组成作直接的说明或提示，但根据题干提供的信息：F1自交，F2为9蓝∶6紫∶1鲜红，若对F2中出现的表现型比例9∶6∶1进行技巧性处理，即变为9∶3∶3∶1，问题就简单了。从9∶3∶3∶1不难看出F1是由两对等位基因控制的双杂合子，即基因型可设为AaBb。当自交时，若后代中同时出现A、B两个显性基因时，该植株为蓝色；当全为隐性基因时，该植株为鲜红色；当只有一个显性基因A或B时，该植株为紫色。故F2的紫色植株中有1/6AAbb，2/6Aabb和1/6aaBB，2/6aaBb。将其授以鲜红色植株（aabb）的花粉，对其进行逐一推算：1/6AAbb×aabb1/6Aabb（紫色），2/6Aabb×aabb1/6Aabb（紫色）和1/6aabb（鲜红）；1/6aaBB×aabb1/6aaBb（紫色），2/6aaBb×aabb1/6aaBb（紫色）和1/6aabb（鲜红）。即可得后代表现型及比例为2紫∶1鲜红，正确答案为B。
总之，对于遗传规律的学习，必需理解基因分离定律和基因自由组合定律的实质，掌握其基本规律。在解决遗传计算的实际问题中，要正确利用概率计算的基本原理，充分结合题意，融会贯通。既注重一般规律和基本原理的运用，又注重对一些数据进行技巧性的特殊处理，才能真正达到提高能力的目的。
一、专业术语不规范
例1 （2014新课标卷I，29）（1）在观察大蒜根尖细胞有丝分裂的实验中，常用盐酸酒精溶液处理根尖，用龙胆紫溶液染色。实验中，盐酸酒精混合液的作用是 ;龙胆紫溶液属于 性染料，能够使细胞中的 着色。
（2）用光学显微镜观察细胞，可以看到细胞核。细胞核的功能可概括为： 。
【错因剖析】一是基础知识掌握不牢，导致答题不准确。如不能正确区分“控制代谢的中心”与“代谢的中心”。二是书写错误。如将“新陈代谢”写成“生成代谢”“生陈代谢”“新陈代泄”等。
【正确答案】（1）使组织中的细胞相互分离 碱 染色体 （2）细胞核是细胞内遗传物质储存、复制和转录的主要场所，是细胞代谢和遗传的控制中心
【抢分策略】正确处理看书与做题的关系。
（1）看书（主要是教材）与做题是相辅相成的。看书能形成知识网络，做题能有效检测前阶段的学习效果及灵活运用知识的能力，查找自己掌握知识点的漏洞和缺陷所在。所以在冲刺阶段也要要适量、有针对性地做题，查漏补缺，回归教材，巩固基础。
（2）做题应精做多思，所选的题目应有针对性，照顾到各类题型。要真正地把生物学习的知识和解题的能力内化为生物学中的一种“涵养”，真正懂得每做一道题都能高效回顾基础的理论和概念，认真地品味它们在整个章节体系中，尤其是在一些常用的重要方法中的地位和意义。
（3）看而不做不知运用，做而不看效率低下。要先把当天计划复习的内容快速浏览一遍，思考一遍，理解后再有针对性地去做题。
二、审题能力欠缺
例2 （2013新课标卷Ⅰ，31）一对相对性状可受多对等位基因控制，如某植物花的紫色（显性）和白色（隐性）。这对相对性状就受多对等位基因控制。科学家已从该种植物的一个紫花品系中选育出了5个基因型不同的白花品系，且这5个白花品系与该紫花品系都只有一对等位基因存在差异。某同学在大量种植该紫花品系时，偶然发现了1株白花植株，将其自交，后代均表现为白花。回答下列问题：
（1）假设上述植物花的紫色（显性）和白色（隐性）这对相对性状受8对等位基因控制，显性基因分别用A、B、C、D、E、F、G、H表示，则紫花品系的基因型为 ;上述5个白花品系之一的基因型可能为 （写出其中一种基因型即可）。
（2）假设该白花植株与紫花品系也只有一对等位基因存在差异，若要通过杂交实验来确定该白花植株是一个新等位基因突变造成的，还是属于上述5个白花品系中的一个，则：该实验的思路 ;预期的实验结果及结论 。
【错因剖析】第（1）问，由于不能正确理解品系的含义和不能准确把握题中相关信息，将基因型写成杂合子;或因书写过快，导致基因型没有写完整（如基因型写成AABBCCDDEEFFGG，漏写了HH等）。
第（2）问第1空，由于题型训练不到位，没有注意总结解答此类题目的一般规律，不能完整表述实验设计思路;或者没有对实验步骤设计的规范性和必要性进行研究，语言不精炼，不能准确切中要点;有的没有正确使用专业术语作答，如将自交、杂交、测交等专有名词混用。
第（2）问第2空，考生因没有正确把握实验目的，下笔千言，废话连篇;或者由于对第（1）问的基因型不能正确把握，导致结果预期和结论描述不准确或描述错误;或者未对自己的方案中的各种基因型进行有效的分析，凭感觉书写结果和结论，如有考生答成“紫花品系与白花杂交后代出现了紫花”。
【正确答案】（1） AABBCCDDEEFFGGHH aaBBCCDDEEFFGGHH （写出其中一种即可） （2） 用该白花植株的后代分别与5个白花品系杂交，观察子代花色 在5个杂交组合中，如果子代全部为紫花，则该白花植株是一个新等位基因突变造成的;在5个杂交组合中，如果4个组合的子代为紫花，1个组合的子代为白花，则该白花植株属于这5个白花品系之一
【抢分策略】缜密审题，规范答题。在高三冲刺复习过程中，考生要养成良好的审题习惯，在读题的过程中尽可能地抓住题目中的关键字眼，准确理解题意。
获取信息：认真读懂题干，读懂题干给出的新信息，理解题干创设新情境中的新知识。
提炼信息：结合提出的信息，提炼出有价值的信息，找出干扰信息，从中找出规律。
运用信息：应用比较、归纳、推理等方法，将发现的规律和已有的旧知识牵线搭桥，迁移到要解决的问题中来，解答问题。
三、实验探究能力欠缺
例3 （2013广东理综卷，29）某新能源研究兴趣小组尝试用木薯块根的淀粉制备燃料酒精。他们用酶将木薯淀粉降解成单糖。查阅资料后，安装的酒精发酵装置、采用的发酵条件如图所示。
（1）向发酵瓶中加入5g酵母菌开始试验，发酵初期，通气阀①需要偶尔短时间打开，并在A通气口处打气，以利于__________;实验过程中，通气阀②需要偶尔短时间打开，目的是______________。
（2）第3天，取出少量发酵液，滴加含有_______的浓硫酸溶液来检测酒精。
（3）检测后发现，尽管酵母菌菌种合适、淀粉酶解物充足、操作正确、发酵温度和pH适宜，但酒精含量（+）比预期低，他们展开了讨论，认为还有其他影响因素，如__________，请设计试验对此因素进行探究并预测实验结果（用表格形式呈现;用“+”表示酒精量，最高含量为“+ + + + +”）。
（4）请对预测的结果进行分析，并得出结论。
【错因剖析】（4）探究能力欠缺，不能科学绘制图表。如表格中自变量不是数字、没有标注变量梯度、自变量的取值范围和单位等要素;自变量设置不准确;预测的实验结果（因变量范围、变化趋势）与题意不符或者不合理;未注明无关变量取值;部分考生把表格设计为双因素、三因素对实验结果的影响的表格。
（5）概念模糊，答题不规范。把“结果分析”错误地理解为“结果描述”而复述表格中的内容与变化趋势，有的没有阐述相关的原因，有的没有阐述结论或所阐述的结论与探究实验的目的不一致。部分考生因不能正确分析预测结果和得出结论及忽略了对无关变量的控制而丢分。在要求考生用表格形式呈现实验设计中因变量与自变量之间的关系，没有按要求运用规定符号“+”“+ + + + +”等表示酒精的含量。
【正确答案】（1）酵母菌生长和繁殖 释放CO2 （2）重铬酸钾 （3）发酵时间（酵母菌的量、通气时间/量/次数 或含O2量或O2浓度）
实验组 ① ② ③ ④ ⑤ ⑥ ⑦
发酵天数 3 4 5 6 7 8 9
预测结果 + + + + + + + + + + + + + + + + + + + + + + + + +
（注：酵母菌加量为5 g，其他条件与图中所给条件相同）
或：
实验组 ① ② ③ ④ ⑤ ⑥
酵母菌的量（g） 5 7 9 11 13 15
预测结果 + + + + + + + + + + + + + + + + + + + +
（注：发酵时间为3天，其他条件与图中所给条件相同）
或：
实验组 ① ② ③ ④ ⑤ ⑥
通气时间（min） 1 2 3 4 5 6
预测结果 + + + + + + + + + + + + + + + + + + + +
（注：发酵时间为3 d、酵母菌的量为5 g，其他条件与图中所给条件相同）
（4）预测结果中，发酵7天的产量已达到最高，大于7天酒精含量不再增加，可能原因是高浓度酒精抑制酵母菌活性或淀粉酶解物已被完全利用，因此在此装置和酵母菌加量为5g时，最好的发酵时间是7天。
【抢分策略】高考命题强调在考生对知识理解的基础上设置探究性、开放性、综合性试题。复习时要重视“考生对探究试题不适应”的问题，培养探究能力;加强诸如“各举一例”“提出研究的问题”“做出相应的假设”“分析可能的原因”等开放性试题的训练;注重模块与模块知识、模块内各知识点和学科主干知识与邻近学科常识性知识的综合训练，培养综合能力。
四、综合分析能力不强
例4 （2013新课标卷Ⅰ，32）南方某地的常绿阔叶林等因过度砍伐而遭到破坏。停止砍伐一段时间后，该地常绿阔叶林逐步得以恢复。下表为恢复过程一次更替的群落类型及其植物组成。回答下列问题：
演替阶段 群落类型 植物种类数/株
草本植物 灌木 乔木
1 草丛 34 0 0
2 针叶林 52 12 1
3 针、阔叶混交林 67 24 17
4 常绿阔叶林 106 31 16
（1）该地常绿阔叶林恢复过程中群落演替的类型为 演替。常绿阔叶林遭到破坏后又得以恢复的原因，除了植物的种子或者繁殖体可得到保留外，还可能是原有的 条件也得到基本保留。
（2）在有上述群落构成的生态系统中，恢复力稳定性最强的是 生态系统，抵抗力稳定性最强的是 生态系统。
（3）与草丛相比，针叶林的动物分层现象较为 （填“简单”或“复杂”），原因是 。
【错因剖析】（1）第2空可将“土壤”答成“自然条件”“环境条件”，但不能因为没有认真审题答成更具体的其他环境条件，如“营养”“气候”“湿度”“温度”“水分”等。
（2）因对“恢复力最强”“最稳定”的理解不透彻，将第2空答成“草丛”，第1空答成“常绿阔叶林”;或因不能正确区分生态系统和种群，将第1空答成“草本植物”“草原”。
（3）第1空错误地认为针叶林乔木灌木较少而答成“简单”。第2空得分率较低，典型错误主要有：认为“草丛只有水平结构，针叶林既有水平结构又有垂直结构”;没有明确“动物种类数量的复杂性从根本上是由植物群落结构的复杂程度决定”;没明确主题词为“植物”，错误答作“针叶林中群落的垂直结构更复杂”或“针叶林生物多样性高”;没明确“种类多”，错误答作“针叶林植物多或食物多”;没有弄清仅“数量多”不能说明其复杂的原因。
【正确答案】（1）次生 土壤条件 （2）草丛 常绿阔叶林 （3）复杂 植物的种类数多并且有较为复杂的分层现象，能为动物提供复杂的栖息场所和食物来源
【抢分策略】生物学表格类试题给考生呈现情境变化的问题材料，让考生把预设在新情境中的相关知识准确地表述出来，是一种适合对较高能力目标层次进行测试评价的题型。表格信息就是相关试题中最重要的信息，分析结果时，首先要弄清表格的由来，然后根据生命过程的原理或实验的目的和原理，正确分析题中的设问。在解答材料表格题时必须通过阅读表格，理解表格中所表达的生物学内涵，转化简化有效信息为可利用的信息，并将其迁移到新情景中去解答问题。
复习时：一要学会看“点”，注意表中的特殊数据，如0、最多、最少和平均等;二看“线”，弄请数字的变化规律，如上升、下降;三看“面”，采用对比或分组对比，找出各组数据之间的异同。
五、原因分析不全面
例5 （2010年全国卷，31）从某植物长势一致的黄化苗上切取等长幼茎段（无叶和侧芽），自茎段顶端向下对称纵切至约3/4处。将切开的茎段浸没在蒸馏水中。一段时间后，观察到半边茎向外弯曲生长，如图所示。若上述黄化苗茎段中的生长素浓度是促进生长的，放入水中后半边茎内、外两侧细胞中的生长素浓度都不会升高。请仅根据生长素的作用特点分析半边茎向外弯曲生长这一现象，推测出现该现象的两种可能原因：
原因1是 ;原因2是 。
【错因剖析】（1）不注意题干所给的诸如“黄化苗茎段中的生长素浓度是促进生长的”信息和题目的要求，而出现“内侧生长素浓度低促进生长，而外侧生长素浓度高抑制生长”的错误描述。
（2）只阐明生长素的作用特点，而没有依据该特点分析半边茎弯曲这一现象，也就是没有根据原因分析结果，这是答题中普遍存在的问题。
【正确答案】内侧细胞中的生长素浓度比外侧高，所以内侧细胞生长较快 内外两侧细胞中的生长素浓度相同，但内外侧细胞对生长素敏感性不同，该浓度的生长素更有利于内侧细胞的生长
【抢分策略】建构原因题的答题模型。解答原因题的关键是要尽量用“三个桥墩”作答，以免出现因答案不完整而扣分。三个桥墩是指：①前桥墩――关键原因;②中桥墩――生理作用（注意完整性）;③后桥墩――连目的地。在答题时应用“因为……所以……”模式，即“因为①②③，所以得到题干的结论”。分析原因时，既不能缺少关键原因前桥墩，也不能缺少中桥墩阐述生理作用，更不能缺少连接目的地的后桥墩。解题时，要根据题干信息全面把握，选择表达。
六、遗传推理判断能力欠缺
例6 （2014年广东理综卷，28节选）下图是某家系甲、乙、丙三种单基因遗传病的系谱图，其基因分别用A、a，B、b和D、d表示。甲病是伴性遗传病，Ⅱ-7不携带乙病的致病基因。在不考虑家系内发生新的基因突变的情况下，请回答下列问题：
（1）甲病的遗传方式是 ，乙病的遗传方式是 ，丙病的遗传方式是 ，Ⅱ-6的基因型是 。
（2）假如Ⅲ-15为乙病致病基因的杂合子、为丙病致病基因携带者的概率是，Ⅲ-15和Ⅲ-16结婚，所生的子女只患一种病的概率是 ，患丙病的女孩的概率是 。
（3）有些遗传病是由于基因的启动子缺失引起的，启动子缺失常导致 缺乏正确的结合位点，转录不能正常起始，而使患者发病。
【错因剖析】（1）书写不规范。第（1）小题出现的错误是Ⅱ-6基因型表达错误：写成XAB Xab 。
（2）计算能力和综合分析能力欠缺。根据题干信息推知5号基因型为 DdXaBXab，16号基因型为DDXaBY或DdXaBY。出现的错误有：误认为5号乙病基因的杂合子和丙病基因携带者的概率均为，得出错误的答案为“，”;在综合计算患两种遗传病的概率是没有按独立事件处理，没有认真审题，误认为所生的子女只患一种病的概率即为患乙病的概率与患丙病的概率之和，得出错误的答案为“，”;误认为16号基因型为DDXaBY或DdXaB Y，得出错误的答案为“，”。
（3）对启动子的功能缺乏理解，错答作“DNA聚合酶”。
关键词：概念教学；遗传学前概念；前概念成因
中图分类号：G427文献标识码：A 文章编号：1992-7711（2014）11-085-1本文中，前概念指的是学生在习得某一科学概念之前，通过自己的观察、实践与体验产生的对该概念的理解和认识。学生在学习科学知识时，他们总是试图将新的信息、观念、经验与最适合的已有知识联系起来。因此，对于科学概念的教学而言，发现学生的前概念，分析学生科学概念建构的障碍之所在，才能采取适当的方法和策略帮助学生由前概念向科学概念的转变。
高中遗传学以分子生物学为基础，研究遗传的物质基础、细胞学基础和遗传规律等内容，涉及基因、染色体、细胞分裂、遗传定律等众多核心概念。由于遗传学概念的抽象性和相互之间联系的复杂性，学生在学习过程中形成了较多的遗传学前概念。本文对高中生具有的遗传学前概念进行调查，并对前概念成因进行了分析，为遗传学概念教学提供参考。
一、高中生具有的遗传学前概念
高中生在“基因”概念的学习中往往认为“基因是染色体片段”、“DNA中有染色体，染色体上有基因”；而在学习“细胞分裂”时，学生认为“同源染色体只出现在减数第一次分裂时期”、“同源染色体必须为‘X’形，且形态、大小相同并两两配对”等；在有关“性状”概念的学习中，学生认为“相对性状是同一生物的不同性状”、“相对性状只能有两种不同的表现类型”、“隐性基因控制的隐性性状是不能表现出来的”等；学生在应用“基因自由组合定律”时认为“基因型YyRr的个体形成Yy、Rr两种配子”。
二、高中生遗传学前概念的成因
1．日常生活经验因素
生物学与生活的密切联系决定了生物学前概念的一个重要来源是日常生活经验。学生在日常生活中通过直接观察和感知，形成大量的感性知识。以这些感性知识为基础，学生对一些日常生活现象作出判断，而这些感性知识将形成日常生活概念。日常生活概念对现象的解释要求以满意为主，而科学概念追求的是对现象的完美解释和预测，二者对事物本质掌握度的要求不同导致学生在将日常生活概念向科学概念转化中遇到困难，这些困难将导致学生形成前概念。［1］
2．社会媒体信息因素
现代生物技术与人们日常生活的关系越来越密切，普通大众对一些生物科学的前沿技术的关注度越来越高。为了能让更多的人理解那些深奥的生物学术语和专用名词，媒体往往会对这些术语和名词进行浅显易懂的诠释。在这个过程中，科学概念的严谨性和精确性会被人为降低，导致学生从社会媒体中获得的科学资讯和生物学概念教学中的信息存在不一致而引起前概念的产生。［2］
3．相关学科知识因素
生物学很多的知识与数学、化学、物理等学科有着密切的联系。由于不同学科对同一概念的阐述有差异，或者是相关学科的背景知识还没有学习，学生在建构某些生物学科学概念时存在很大的困难。
例如：应用两大遗传学定律计算概率的问题，数学上有关概率的内容还没有学习，学生对于概率的一些原理如“乘法原则”、“加法原则”常难以理解，导致对概率计算的问题始终是迷迷糊糊。另外，数学上有关概率的内容几乎不涉及“条件概率”的问题，而遗传学概率计算很多都涉及这方面的内容，如“生病男孩”和“男孩生病”在数学上没有任何的不同，但在遗传学概率计算时是显著不同的。
4．学科概念教学因素
研究表明，教师拥有大量的科学领域中的前概念。在教学中，教师有时在科学用语、术语上的表达不够严谨以及教师口语等问题都会对学生产生影响。而正式或非正式教材上的定义、图表或者提供的实例不够全面也会使学生产生歧意，从而导致前概念的产生。
例如：在进行“相对性状”的概念学习时，老师对“同一种性状的不同表现类型”进行举例往往都是举两种不同的表现类型，如“豌豆高茎和矮茎”、“人眼睑形状的单和双”等，给学生造成同一性状的不同表现类型只能是两种，从而在判断“人血型分A型、B型、AB型、O型”不属于相对性状。
5．个人认知缺陷因素
学生在学习科学概念的过程中，由于自身的认知缺陷导致前概念的产生。这可以表现在以下两个方面：一方面学生自身的学科知识不足，往往对概念的了解不够全面、准确；另一方面学生自身的思维方式缺陷，如进行不恰当的类比，依靠直觉和想象进行判断等。
［参考文献］
关键词：LAMP；缴费系统；学分制
中图分类号：TP315 文献标志码：A 文章编号：1673-8454（2013）21-0086-04
一、 前言
近年来随着教育部对于学分制改革推进的要求和高校规模继续不断扩大的现状，我国高校的教育教学管理体制正缓慢地由学年制向学分制的转变。因此，对能够适应学分制教学管理、学生按照各自经济情况和学习目标自主选择学习方向和进度，支付多样化，选排课算法优异的，符合财务管理规定的高效安全的学分制选排课缴费系统进行设计和研究是十分必要的。
在平台选择方面，系统的安全性和健壮性的要求极为重要，LAMP（Linux+Apache+MySQL+PHP）架构的数据吞吐性能，稳定性安全性较Windows系统更高，对高校这种规模的应用来讲，系统投入的成本也在承受范围之内，所以系统选择采用基于PHP的LAMP体系来研究和构建。
在排课方面，排课问题属于运筹学中的时间表（TTP）问题，高校排课问题很早就成为了众多软件开发者做关注的问题之一，研究人员对排课算法进行了大量的研究和改进，国内的研究主要选用了目前性能公认较为优良的遗传算法，所以本系统选用遗传算法来解决排课的课题。
在网络自主缴费方面，系统主要根据合作银行网银系统的数据接口定义，编制了和银行直接通信的前置系统，能够达到即时结算，准实时数据更新的水平。
二、系统主要问题的实施策略和设计
1.竞争性选课
目前高校在少量的选修课上试点应用了网络选课的方式，但即使在这种极少选课量的情况下，学生争夺教学资源却变成了拼抢硬件资源，为了保证公平性，本系统采用在学生选课初始化时，赋予每个学生同样的分值或者称为“虚拟货币”，出价可以反映学生选择此课程的意愿程度，竞价过程不公开，相当于投标书，然后根据课程开设的规模进行排名，同时可以开放进行多轮选课，解决竞价失败的问题。
2.排课算法
排课问题其实是一种调度问题（Scheduling Problem），是一个非线性的，需要满足各种软硬约束条件的，模糊多目标优化的，N-P完全的时空组合问题。其复杂性来源于要达到排课的目标其需要满足的软硬约束条件非常之多，为了编排出合理人性化的课程表，还必须考虑到课程重要程度、课程优先级、教师时间安排等，多校区教学还要避免出现密集跨校区问题。所以自动排课方案已经成为当今诸多研究者感兴趣的课题。主要排课算法包括遗传算法，禁忌搜索，蚁群算法，进化算法或者上述几种的混合。其中遗传算法正在越来越广泛地得到应用。这是由于这种方法是能够在元素级条件下找到最优解决方案的强大算法，所以以这种算法为基础的改进能够在可控的时间范围完成目标工作。
遗传算法的基本步骤：（1）对问题的可行进行编码，使之形成一条染色体；（2）对最大代数、种群规模、选择概率、交叉概率、变异概率等参数进行初始化；（3）根据设定的参数和编码方案生成初始种群P；（4）使用交差概率对种群进行交叉操作，产生新的染色体并构成子种群P；（5）使用变异概率对子种群进行变异操作，形成P；（6）使用选择概率对种群集合P∪P进行选择操作，生成P；（7）使用适应度函数对P进行评价，若种群P是最优解，则算法结束，若不是则选择适应度较强的染色体形成种群P转第4步。遗传算法流程如图1所示。
在学分制管理体系下，公共必修课的教学安排仍然按照学年制的方式有计划地进行，方式仍然为按照行政班级，年级等进行排课，学生不选课。在其他课程包括专业必修课，专业选修课，公共选修课方面，将“班级”和“年级”在学分制体系下合并体现为“所学专业”，则算法的约束条件主要有：
（1）遗传算法在公共必修课的排课业务中的约束条件。本文采用的是对公共必修课按照班级和周课表的形式进行预排课。公共必修课排课的具体约束条件包括硬性条件和软性条件，其中：
1）硬性条件
a.同一个现实世界中的实体对象（学生，老师，教室）不能同时处于两件以上的事务中；
b.一个教室安排的人数不能超过教室能容纳的最大人数；
c.教师半天内不能跨校区授课；
d.教室（场地）设备配备。
2）软性条件
a.课程类型对时间的要求，繁重的课程应放在精神状态比较好的上午；
b.体育课、实习课应安排在下午；
c.课程在时间片上应合理均匀地分布；
d.为了避免教学资源浪费，尽量避免教室内空出大片座位；
e.教师在一天内最好不要跨校区教学；
f.个别教师具体要求。
这些条件也就是适应性函数构成的要素。
（2）遗传算法在公共必修课的排课业务中的算法设计
1）编码
遗传算法中第一个要考虑的问题是如何对染色体进行编码，一条染色体中应包含课程、教师、教室、班级、时间片、校区等相关的信息，采用二维表的形式，以时间片作为基准资源使用，假设每周可供开课的时间片数5×5=25，为每两小节为一个时间片，设时间片集合为：T={11，12，13，14….53，54，55}，11表示周一的第一二节课，以此类推，教室集合为：R={R1，R2，R3……Rn}，时间片和教室的笛卡尔积，也就是可供使用的时空资源为 G=T×R={（11，R1），（ 12，R1），….（55，Rn）}，那么资源一共55×n个，排课所求解的目标就是为每一个教学任务找到合适的资源。
2）生成初始种群
首先要在初始种群生成前进行一些设置操作，比如体育课等要安排在下午等，之后可以开始进行初始种群，首先确定公共必修课教学任务的条数M，并将教学任务进行编号，然后用$L=rand（0，M-1，1）；shuffle（$L）生成一个随机的0～M-1的不重复的随机数字序列F1，依次将数组F的元素代表的教学任务的信息提取出来生成初始种群。
因为教学任务序列F1经由系统随机产生，仅仅循环M次，导致教学任务所使用的时空资源差异不够，对于后面的再生、交叉、编译操作不利，所以再取随机数列F2，F3，可产生足够数量染色体的初始种群。
3）适应度函数设计
系统重点考虑课程类型对时间片的合理安排和避免教师跨校区教学，则单个基因适应度设计见公式（1）
f（a，b，c，d，e）=0.3a+0.1b+0.3c+0.1d+0.2d（1）
变量a代表困难课程安排的优劣度评价，权重为0.3，变量b代表体育、实习类课程安排的优劣度评价，权重为0.1变量c代表教学任务在一周内分布的优劣度评价，权重为0.3，同样的一个教学任务，如果相隔太近甚至在同一天安排，则容量太大，如果相隔太长，则容易遗忘。变量d代表教室座位的利用率优劣度评价，权重为0.1，变量e代表教师在同一天内在/不在一个校区内教学，权重为0.3。这样，每条染色体的适应度的值为每个基因的适应度值之和。每个染色体有M个基因，设每个基因的适应度为f（k）（0≤k≤M-1），则每条染色体的适应度见公式（2）
0≤k≤M-1，0≤≤3M-1 （2）
4）选择操作
选择操作的主要方法有：赌，局部选择等。赌选择操作完全依赖于系统生成的随机数，容易丢失极为优良的染色体，系统采用直接对每个染色体的适应度值进行排名，选择最大的20%直接复制到下一代，则可得到全局最优解。
5）交叉操作
交叉操作的主要方法有：单点交叉、均匀交叉等，但由于多校区的因素存在，使得产生硬性冲突的几率极高，所以系统将每对染色体中的部分进行交叉，这样产生冲突的几率大为降低。具体的方法是，设教学任务为TM，TM有三个维度，分别为（Teacher x，Class y，Course z），而时空资源表有两个维度，分别为教室和时间。根据生成的初始种群，采取二维资源片编码十进制方式混合编码，假设一个基因是TM01000111，表示TM教学任务在01校区0001教室周一上午一二节课上课，依次生成开课的数据，形成一个染色体，交叉操作如图2所示。
选取一对染色体，随机选择交叉点，将其中的教学任务相同的基因中时空资源部分进行交换。在交叉的过程中既交叉点作为参考点，既可以选择交叉点的前后的基因都进行交叉，也可以单独对交叉点前或者后的基因进行交叉，在对交叉点前后的基因进行交叉时，交叉分步进行，交叉时进行判断，如果有冲突，交叉取消，另随机取交叉点。
6）变异操作
变异操作采用相应的时空资源变异操作，根据变异概率选出一个染色体，随机选择变异点，在变异点前方或者后方选择基因中的时空资源片，变换资源，并检测变异冲突，发现有冲突变异取消，基本过程如图3所示
7）冲突处理的步骤
在交叉变异的过程中，采用教学任务的时空资源进行交叉，大大减少了冲突发生的情况，但是毕竟冲突是无法避免的，所以应该在进行各种遗传操作之前进行冲突检测，检测到冲突则取消操作，基本方法是：
a.教师冲突的处理：假设总共有T位教师，对教师进行编码，编码范围是0～T-1，并依次读出每个教师可以执教的教学任务，再检测时间片表，如果存在重复的行，则表明冲突，取消遗传操作，没有则表明正常，可以遗传。
b.教室冲突的处理：假设某校区共有R个教室，编码范围是0～R-1，遗传检测同教师冲突
c.班级冲突的处理：假设共有C个班级，编码范围是0～C-1，遗传检测同教师冲突
d.校区冲突的处理：这里系统的交叉操作不会产生学生跨校区上课的情况，因为在生成初始种群时就已经排除了学生跨校区上课的情况，所以同班级要完成的教学任务都在同一个校区内进行，对班级来说，只有时空资源片可能会发生改变，所以系统只需要对教师遍历，如果搜索出多个校区编号的情况，则说明有冲突，则需要恢复到交叉前的状态，进行下一对染色体的交叉操作。
系统采用这样的遗传算法，能够保留遗传的每一代最好的个体，随着遗传代数的增高，不断丢弃最差的个体，在初始进化的数百代中，适应度呈波动变化，随着遗传代数的增大，适应度值平稳增高，逐渐趋近最优解。
（3）遗传算法在其他课程排课业务中的算法设计
其他课程系统采用先选课，后排课的模式进行，同公共必修课排课算法不同的是班级的概念消失了，取而代之的是选课结束以后产生临时的修习同一门课程的学生集，在数据库中必须建立临时教学集合表，代替班级表行使职责。在初始化种群的时候，读取待排课专业的“专业课程树”，一个专业一个专业的按照硬约束初始化种群，当然，占用的时空资源，包括教室占用表，时间片占用表是在专业之间来说公用的。初始化种群时选择专业的先后次序也采用随机抽取的方式，以求专业之间的公平性。
3.网银支付
学生在本系统选课完毕，确认缴费后，使用URL参数传递的方式将信息传至合作行网银系统：缴费成功后，网银系统向本系统发送的信息，本系统接受URL，并通过读取URL参数的方式获取参数信息，并进行相应的数据库操作。
4.安全
Linux 为增加系统安全性提供了防火墙保护。系统使用系统内置的软件iptables定制适合自己的“数据包处理策略”。iptables的防火墙策略主要有三种，包过滤（Packet Filter），（Proxy），状态分析（Stateful Inspection）。本系统将这三种技术混合使用建立了较为稳固的Linux防火墙系统。
对于恶意攻击，系统选用了Linux平台下广泛使用的PSAD程序，可以和系统防火墙合作，可根据行为判断并防范几乎所有的针对Linux网络的恶意企图，能够深入到应用层对内容进行分析，并对用户进行警告。本系统采用此方法检测入侵和滥用效果良好。
三、系统测试
1.竞价方式选课测试
在现有的选课系统中，采用竞价选课方式的极少，系统对竞价方式选课进行了长时间大量数据的测试，发现还有如下问题需要改善。
（1）需要事先对教学安排有一定的规划和估算，在进行一定的选课导向教育的同时要科学设定授课规模，否则极容易导致选课失败，在邀请学生进行测试的过程中，选课链断裂出现的几率有时候高达13%。
（2）虚拟货币的设定一定要科学，数额最好要大一点，否则容易导致排名的末尾出现多个相同出价的学生，系统无法决策哪个竞价有效，需要人工干预。
2.排课测试
公共必修课排课适应度代数二维图如图4所示。
非公共必修课排课适应度代数二维图如图5所示。
可见公共必修课排课为了应对多校区的因素对传统遗传算法排课进行了改良，性能良好，非公共必修课因为采用先选课后排课的方式，按照数据初始化时设定的课程优先级，预先抢占一些时空资源片，再进行排课操作，性能较公共必修课排课略差。
四、总结
系统将选课、排课、自助缴费这三个学生在校期间的主要活动结合起来协同运作系统，对排课、选课、自助缴费这三大系统进行了较为深入地整合，采用的对公共必修课预排课，其余课程开放学生选课的方式，应用改进遗传算法，较好地解决了完全学分制教学管理体制下的选排课问题，最后的排课结果也比较符合系统设计的目标。
但是，由于完全学分制管理体系下的选排课工作极其复杂，系统在先排后选算法方面仍然有很大的改进余地，应该在提高算法效率，稳定排课结果适应度值方面进一步开展研究。?
参考文献：
[1]黄干平，刘娟.解“时间表问题”的启发式算法[J].武汉大学学报（自然科学版），1996，42（1）：71-74.
[2]Nakayama.M， Hoshito.J. Development of A Support System for University Course Selection Using Semantic Web Technology[R]. 5th International Conference on Web Information Systems and Technologies，2009：389-392.
[3]Chinnasri.W， Sureerattanan.N. Comparison of performance between different selection strategies on genetic algorithm with course timetabling problem[R]. Advanced Management Science（ICAMS）， 2010 IEEE International Conference on.2010（2）：105.
[4]李敏强，寇纪淞，林丹等.遗传算法的基本理论与应用[M].北京：科学出版社，2002：316-317.
关键字： 高校排课问题； 遗传算法； 量子遗传进化算法； 课程表
中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2013）20?0007?04
高校排课问题一直是很多人关注的一个问题，排课问题的本质是将课程、教师和学生在合适的时间段内分配到合适的教室中，涉及到的因素较多，是一个多目标的调度问题，在运筹学中被称为时间表问题。
1 排课问题分析
高校排课问题中实际上是时间表安排的问题[1]。在实际排课过程中，主要涉及到：教室、班级、课程、时间和老师等5个因素的问题。在处理这5个因素关系的过程中会发生很多冲突，这就需要有一些约束条件，这些约束条件可以大致分为硬约束和软约束，详见表1。
根据以上的分析排课问题数学模型分为下面5个集合如下：教室集合：[R={r1，r2，…，rm}]；班级集合：[C={c1，c2，…，cn}]；课程集合：[L={l1，l2，…，lp}]；教师集合：[S=表1 排课问题的软硬约束条件
上述5个元素是影响排课问题的主要的因素，每个集合中取一个组成在某个时间某班上的课程由哪位老师来授课，在哪个教室上课，但必须满足一定的条件。
2 量子遗传进化算法
量子遗传进化算法是量子计算与遗传算法相结合的产物[2]。目前，这一领域的研究主要集中在两类模型上：一类是基于量子多宇宙特征的多宇宙量子衍生遗传算法（Quantum Inspired Genetic Algorithm）；另一类是基于量子比特和量子态叠加特性的遗传量子算法（Genetic Quantum Algorithm，GQA）[3]。
2.1 量子位表示法
在量子信息论中， 信息的载体不再是经典的比特，而是个一般的二态量子体系，称为量子比特（qubit）。量子比特与经典位不同就在于它可以同时处在两个量子态的叠加态中[4]，比如：
式中：[α，β]是两个复常数，满足：
式中[0]和[1]分别表示自旋向下和自旋向上态。所以一个量子比特可同时包含态[0]和[1]的信息；[α]表示相应的 qubit 处于0状态的概率幅；[β]表示其处于1状态的概率幅。[α2]表示处于0状态的概率，[β2]表示处于1状态的概率[3]。一个具有m个量子比特位的系统可以描述为：
其中[αj2+βj2=1，j=1，2，…，m]。这种表示方法可以表示任意的线性叠加态， 例如一个具有如下概率幅的量比特系统：
则系统的状态可以表示为：
上面结果表示状态[00，001，010，011，100，101，][110，111]出现的概率分别为[38，132，332，332，332，][132，332，332，]即这个量子比特系统表示了8个状态叠加的信息而且随着趋于1或0， 量子染色体收敛于一个状态， 这时多样性消失， 算法收敛[5]。
2.2 量子旋转门
在遗传算法中，可以通过交叉，变异来得到新的个体，而在量子遗传进化算法中，是通过量子旋转门来进行更新的[6]。
量子旋转门如下：
比如对[αiβi]进行更新，可以用式（6）来进行更新：
式中[Δθi]的取值对算法的执行效率有很大的影响，具体确定过程如表2所示。其中：[fx]和[fb]表示解的 fitness，[x]为当前解，[b]为 [btj]；[Xi]和[bj] 分别表示解[x]和[b]的第i个 bit 位的取值；[sαiβi]为[Δθi]的符号[7]。
例如，如果条件[fx≥fb]成立，且[xi]和[bj]分别为1和0，则[Δθi]的取值为0.025π，然后根据[αi]和[βi]的值可将其符号设置为+1，-1和0来增加 qubit 处于1状态的概率。若[αiβi>0]，即[Δθi]为+0.025π，将[Δθi]代入式（6）中得到新的[αli]和[βli]，使qubit处于1状态的概率增加，具体分析如图1所示。
[Δθi]取值的大小会影响算法的收敛速度，如果取值过大会导致早熟收敛得不到最优解；[Δθi]的符号决定解的收敛方向[8]。
3 量子遗传进化算法和遗传算法来解决高校
排课问题
3.1 具体高校排课问题简介
对于一个具体的排课问题，分别采用量子遗传进化算法和遗传算法来解决，并对它们的结果进行分析[9]。简化的高校排课问题是针对一个班级来排课，有7门课程，其中，有部分课程是一周上一次，还有部分课程是一周上两次，每门课程都有各自的重要性，每个时间段，都有不同的听课效率，为了排出合格课表。下面先通过量子遗传进化算法来排课表，最终得到的课表通过课程的重要性乘以时间段的听课效率的总和来比较课表的优劣，最终的值越大，且不存在冲突，则课表越好[10]。
图1 量子门坐标图
排课时的一些要求，其中一周上两次的课，不能排在同一天或者相邻两天，至少相差一天。项目中主要牵涉到的数据，每门课程的重要性，将它们存放在一个数组中，其中，无课也放在了数组中，则最终的数组应该是一个一维数组，包括8个元素。
int classWeights[] ={0，70，60，55，75，80，90，85}
对应的课程为无课，体育，计算机基础，政治，数据结构，高数，英语，操作系统。其中，classWeight[0]无课的重要性，没有课程 ，那重要性当然为0，后面依次是第几们课程的重要性。下标为几，即为第几们课程的重要性。各个时间段的重要性存放在一个二维数组中，数组中共有25个元素，因为这里讨论的排课问题，一个星期共有五天上课，一天共有五节课，其中上午两节课，下午两节课，晚上一节课，这里的一节课包括两个学时。第一个下标加1后的值表示的是星期几，第二个下标加1后的值表示的是第几节课，如timeWeights[2][3]表示的是星期三第四节课。有：
double[][] timeWeights =
{ { 0.65， 0.90， 0.85， 0.60， 0.50 }，
{ 0.90， 0.85， 0.80， 0.75， 0.70 }，
{ 0.95， 0.90， 0.85， 0.80， 0.65 }，
{ 0.90， 0.80， 0.75， 0.70， 0.60 }，
{ 0.85， 0.90， 0.70， 0.60， 0.50 } }
Fitness函数如下：
[fx=i=0i=4j=0j=4timeWeightsij?classWeightsk，0≤k≤7]
函数[f（x）]是评价排出课表好坏的函数，[f（x）]值越大，则排出的课表越好。
3.2 两种算法的测试结果
在项目中还有一些辅助的类就在此不做详细介绍，WriteFile.java中方法的作用是将运行的结果输入到Excel文件中。test.java是一个主函数的类，最终采用进化1 000代，种群规模为10，每种算法运行25次，最终分别对它们的1次运行和25次求的平均画图，比较两种算法，可看出量子遗传进化算法在求具体的高校排课问题的优越性。在控制台中也会输出每次运行中的最优解的课表。其中第1次到第25次运行的是量子遗传进化算法，第26次到第50次运行的是遗传算法。运行结果的截图如图2，图3所示。
图2 QEA与CGA一次运行最好解的fitness值
图3 QEA与CGA运行25次的最好解的平均fitness值
从图2和图3中可以很明显的看出量子遗传进化算法求出的解要比遗传算法求出的解要好，下面给出两种算法排出的具体课表，这里取出某次运行中的最优解的课表。
表3是量子遗传进化算法排出的课表，表4是遗传算法排出的课表。它们的fitness值可以从图2中看出，量子遗传进化算法排出的课表的fitness值明显大于遗传算法排出的课表的fitness值。
表3 量子遗传进化算法第10次运行排出的课表
表4 遗传算法第10次运行排出的课表
4 结 语
通过对高校排课问题的分析，对高校排课问题中主要的影响因素进行比较深入的了解，并根据量子启发式进发算法优点，采用量子遗传进化算法来解决高校排课问题。从最终的结果对比可以看出，量子遗传进化算法得出的解比遗传算法得出的解要好很多，收敛速度上，量子遗传进化算法和遗传算法的收敛速度差不多。所以，采用量子遗传进化算法来解决高校排课问题比较高效，能得到很好的解。
参考文献
[1] HAN K H， KIM J H. Quantum?inspired evolutionary algorithm fora class of combinatorial optimization [J]. IEEE Transactions on Evolutionary Computation， 2002， 6（6）： 580?593.
[2] 杨俊安，庄镇泉.量子遗传算法研究现状[J].计算机科学，2003，30（11）：13?15.
[3] NARAYANAN A， MOORE M. Quantum?inspired genetic algorithm [C]// Proceedings of IEEE Congress on Evolutionary Computation. Nogama： IEEE， 1996： 61?66.
[4] HART K H，PARK K H.Parallel quantum?inspired genetic algorithm for combinatorial optimization problems [C]// Proceedings of the IEEE Conference on Evolutionary Computation.Piscataway： IEEE Press， 2001： 1422?1429.
[5] TONY H.Quantum computing： all introduction [J].Computing & Control Engineering Journal，1996， 10（3）： 105?112.
[6] LIU Wen?jie， CHEN Han?wu， YAN Qiao?qiao，et al. A novel quantum?inspired evolutionary algorithm based on variable angle?distance rotation [C]// 2010 IEEE Congress on Evolutionary Computation. Barcelona： IEEE， 2010： 1?7.
[7] RECHENBERG I. Evolutionsstrategie： optimierung technischer systemenach prinzipien der biologishen evolution stuttgart [M]. Germany： From?mann?Holzbog， 1973.
[8] 雷英杰，张善文，李续武，等.Matlab遗传算法工具箱及应用[M].西安：西安电子科技大学出版社，2005.
1频谱分配模型
［4］频谱分配是指根据需要接入系统的节点数目及其服务要求将频谱分配给一个或多个指定节点。图1表示的就是对频谱分配问题的一个简单描述［3］。在效益最大化的频谱分配模型中，由认知用户构成的网络拓扑结构可抽象成图G(V，E，L)。V是顶点集合，一个顶点代表一个认知用户;E是边的集合，若两个认知用户i，j的干扰范围不出现重叠，则ei，j=0，否则ei，j=1;L用来表示次用户的信道可用性。如图2所示。图中1－5代表认知用户，有三个信道A、B、C对于认知用户来说是机会式可用的。I－IV表示主用户，它们目前正占用信道A、B、C。假设所有信道拥有相同的带宽，主用户和次用户都具有相同的功率，所有的主用户在各个信道上覆盖的区域大小相同，即具有相同的覆盖半径，同理认知用户在个信道上具有相同的干扰半径。频谱共享协议规定，主用户占用的信道不能被其邻近的认知用户使用。因此，在主用户I－IV干扰范围内的认知用户不能与主用户使用同一频段。在图中，虚线组成的圆代表各主用户的干扰范围。图论着色模型中的频谱分配问题可用信道矩阵、效益矩阵、干扰约束矩阵和分配矩阵描述。它们的定义如下:1)信道的可用矩阵L：其中ln，m=1表示认知用户n可以使用信道m;ln，m=0表示认知用户n不能使用信道m。2)干扰矩阵C:C={cn，k，mcn，k，m∈{0，1}}N×N×M(2)它是一个三维矩阵，当认知用户n和k同时使用信道m，将会造成干扰，此时cn，k，m=1;若同时使用m时不产生干扰，则cn，k，m=0。干扰矩阵C与可用矩阵L也有着关联，即cn，k，m≤ln，m×lk，m;当n=k时，cn，n，m=1－ln，m，此时，干扰矩阵仅由信道的可用矩阵决定。3)效益矩阵B:B={bnmbnm＞0}N×M(3)B表示认知用户n使用信道m时所获得的效益权重。bn，m=α表示认知用户n使用信道m时获得效用权重为α;bn，m=0表示认知用户n不能够使用信道m。4)无干扰的频谱分配矩阵A:A=an，man，m∈{0，1}，an，m≤ln，{}mN×M(4)其中，an，m=1表示信道m被分配给了用户n;否则an，m=0。矩阵A必须满足无干扰限制条件:an，m+ak，m≤1，ifcn，k，m=1，0＜n，k＜N，0＜m＜M。在频谱分配过程中，单个认知用户n获得的效益定义为:rn=∑Mm=1an，m·bn，m。所有认知用户获得的效益可组成矩阵R=rn=∑Mm=1an，m·bn，{}mN×1。把所有无干扰的频谱分配集定义为Λ(L，C)N×M。频谱分配的系统效益定义如下:U(R)=∑Nn=1rn=∑Nn=1∑Mm=1an，m．bn，m(5)同时为了更好的验证算法的新能，本文还引入了评价频谱分配的时间开销的方法。假设每次分配的循环时间均为t，这样算法总的分配时间开销等于算法循环次数乘以t。算法的循环次数为矩阵A的矩阵范数am1。T为算法分配的总的时间开销。
2基于黄金分割率的混合自适应遗传算法
自适应交叉变异策略是由SrinivasM、PatnaikLM等提出来的［10］，在自适应遗传算法中，交叉概率和变异概率不是一个固定的值，而是按群体的适应度进行自适应调整。因为个体适应度值越接近最大适应度值，交叉概率与变异概率就越小;当等于最大适应度值时，交叉概率和变异概率为零。这种调整方法在群体处于进化后期时是比较合适的，但在进化初期是不利的，因为在进化初期群体中的较优个体几乎处于一种不发生变化的状态，而此时的优良个体不一定是优化的全局最优解，这增加了进化走向局部最优解的可能性。因此，本文引入了混合的自适应思想［11］。混合的自适应遗传算法改进了上述的基本自适应遗传算法的不足，它是根据进化代数来判断是否进行自适应交叉和变异的，在进化初期采用固定的交叉和变异概率，在种群的进化后期采用自适应交叉和变异概率。但考虑到当前代群体中的较优个体应具有较高的交叉和变异概率，因此，在最优个体不被破坏仍然保留的情况下，要确定以最佳的自适应点进行交叉和变异。本文又引入了黄金分割率［12］来进行最佳自适应点的选择。GA是一种模拟生物进化过程的算法，因此极有可能隐藏着黄金分割率。在改进的自适应算法公式中引入黄金分割率，依照“去坏留好”的原则、对称原则、等比收缩原则来逐步缩小搜索范围。每次搜索空间缩小0.382倍或0.618倍，直至缩为一点。这是一个收敛速度很快的一维搜索方法。改进的交叉和变异概率公式如下:自适应交叉概率Pc如(10)式所示:其中:f为要变异个体的适应度值，f'为要交叉的两个个体中较大的适应度值，favg为平均适应度值，fmax为最大适应度值，Pcmax=0.9，Pmmax=0.1。
3基于黄金分割率的混合自适应遗传算法的频谱分配模型
本文算法中的可用频谱矩阵L、效益矩阵B、干扰矩阵C都是按照上述频谱分配模型定义的。把目标函数(系统效益、时间开销)的表达式作为遗传算法的适应度函数。编码方式采用实数编码。实数编码就是将问题的解用一个实数来表示。实数编码直接在解的表现型上进行遗传操作，也就是说，在执行中，遗传空间就是问题解空间，染色体将直接反映优化问题的规律和特性。本文的遗传算法中的核心算子:选择、交叉、变异操作分别如下方法进行［11］:1)选择算子赌选择方法是一种基于适应度值的回放式随机采样的方法。它的基本思想是:每个个体被选中的概率都与它的适应度值大小成正比。设种群规模为n，种群中的一个个体i的适应度值为fi为，则该个体被选择的概率pi如式(12)所示:2)交叉算子双点交叉的具体操作是:在个体串中随机的设定两个交叉点，然后将两个交叉点之间的个体结构进行互换。3)变异算子变异操作决定了遗传算法的局部搜索能力，能够维持群体的多样性和防止出现早熟现象。本文采用基本位变异算子，即个体中的基因实现0和1之间的翻转。在本文的频谱分配方案中，每一条染色体的二进制串表示一种可能的频谱分配，由于无干扰频谱分配A与可用矩阵L中等于0的元素位置相对应，而且每条染色体的长度由可用矩阵L中等于1的元素个数来决定。因此矩阵A的更新只需将每代新的染色体的每个基因依次取代矩阵L中为1的元素即可。此外，每次更新结束后，还需作适当的处理使新的矩阵A满足C的条件，最终获得的无干扰分配矩阵A就是一种可行的频谱分配方案。具体方法为:对C中所有满足cn，k，m=1且的n≠kn和k，判断An，m和Ak，m是否均为1，若是，将其中之一置为0。综上所述，将基于黄金分割率的混合自适应遗传算法应用到认知无线电频谱分配，一般步骤为:1)初始化可用频谱矩阵、效益矩阵和干扰矩阵，该优化问题的维数为l=∑Nn=1∑Mm=1ln，m，种群大小为P。记录可用矩阵L中为1的元素，即L1={(n，m)|ln，m=1}，矩阵中的元素按n、m递增的方式进行排列。维数l的值等于L1中元素的个数;2)在进化的第0代，即g=0时，根据二进制编码初始化种群;3)优化种群Q(g)得到二进制串P(g);4)P(g)中每个染色体的第j位映射到an，m中，1≤j≤l，(n，m)是L1中第j个元素。对于全部的频谱m，找出所有满足cn，k，m=1且n≠k的认知用户集合，验证分配矩阵A中的第n行m列及k行m列的元素是否全部为1，若是，随机将其中的一个元素置0，另一个保持不变;5)频谱分配中的效益函数作为适应度函数，计算出适应度函数，之后将结果保存到B(g)中;6)用赌选择法，进行双点变异交叉操作，并进行种群Q(g)的更新;其中交叉变异操作的过程为:首先计算进化代数，判断是否满足进行自适应交叉变异的条件，若满足，则运用(10)(11)式计算交叉变异概率并进行自适应交叉变异操作，否则进行固定参数的交叉及变异操作;7)断是否有达到进化的终止代数，若是将B(g)中保存的最优解映射成矩阵A的形式即已经到达了最佳分配则算法结束;否则继续循环执行;8)g+1;9)测量种群Q(g－1)，产生确定状态P(g)，转至步骤4)。
4仿真结果与分析
认知无线电频谱分配性能最常见的评价方式是系统效益和公平性，因此，为了验证改进遗传算法的性能，把本文算法与自适应遗传算法在系统效益和算法的时间开销上进行了比较，设定认知用户数为10，主用户数为20，频带数为20，运用Matlab进行了仿真。为了简化问题，在仿真试验中，假设系统是个准静态无噪声的无线系统，且不考虑功率控制因素;也是就是系统在一次完整的频谱分配过程中，每个认知用户的可用信道和干扰关系保持不变。同时，所有主用户在各个信道上的干扰半径相同，所有认知用户的干扰半径也相同。算法仿真中的L、B、C矩阵如表1所示。图3表示的是基本遗传算法，自适应遗传算法和基于黄金分割率的自适应遗传算法系统的平均效益随着迭代次数的变化曲线图。有上图可以看出，随着迭代次数的增加，系统效益逐渐增加，基本遗传算法和自适应遗传算法在迭代500次左右的时候达到全局最优解，而本文算法在迭代300次就达到了最优解，很明显比其它算法的收收敛速度更快，而且获得的系统效益也更好一点。图4表示的是传统的遗传算法和自适应遗传算法，基于黄金分割率的混合自适应遗传算法的系统效益随着认知用户改变的变化曲线图。随着认知用户的增加，系统效益逐渐减少。但是，本文算法的系统效益最好，其次是自适应算法，图5表示的是网络效益随试验次数的变化曲线。由图5可以看出，本文算法得到的网络效益只有很少部分上效果不明显，大部分都是明显优于其它两种算法。图6表示的是本文算法和自适应遗传算法的时间开销随迭代次数的变化曲线图，由图可以看出算法的时间开销随着迭代次数的增加逐渐上升，自适应算法和遗传算法的分配时间消耗相差不大，本文提出的算法的分配时间开销明显比基本遗传算法的要小。因此，此算法提高了频谱分配的效率。
5结束语
本文提出了融合黄金分割率的混合自适应遗传算法的频谱分配方案。第一，在计算交叉和变异概率时引入黄金分割率的思想，解决陷入局部最优解的问题;第二，运用混合自适应的思想，动态的调整使用固定的交叉变异还是自适应的交叉变异，有效解决了运算时间长的问题。仿真证明了该算法比传统自适应遗传算法具有更好的性能:提高了算法的搜索效率，收敛速度更快，系统的效益更大且不易陷入局部最优解。
作者：杨铁军 林培培 单位：河南工业大学信息科学与工程学院
