遗传算法论文范文

引言：寻求写作上的突破？我们特意为您精选了12篇遗传算法论文范文，希望这些范文能够成为您写作时的参考，帮助您的文章更加丰富和深入。

篇1

 

1 引言

“物竞天择，适者生存”是达尔文生物进化论的基本原理，揭示了物种总是向着更适应自然界的方向进化的规律。可见，生物进化过程本质上是一种优化过程，在计算科学上具有直接的借鉴意义。在计算机技术迅猛发展的时代，生物进化过程不仅可以在计算机上模拟实现，而且还可以模拟进化过程，创立新的优化计算方法，并应用到复杂工程领域之中，这就是遗传算法等一类进化计算方法的思想源泉。

2 遗传算法概述

遗传算法是将生物学中的遗传进化原理和随[1]优化理论相结合的产物，是一种随机性的全局优算法。遗传算法不但具有较强的全局搜索功能和求解问题的能力，还具有简单通用、鲁棒性强、适于并行处理等特点数学建模论文，是一种较好的全局优化搜索算法。在遗传算法的应用中，由于编码方式和遗传算子的不同，构成了各种不同的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。基于这个共同点，Holland的遗传算法常被称为简单遗传算法（简记SGA），简单遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，这种改进的或变形的遗传算法，都是以其为基础[1]。

2.1遗传算法几个基本概念

个体(IndividualString)：个体是遗传算法中用来模拟生物染色体的一定数目的二进制串，该二进制串用来表示优化问题的满意解。

种群(population)：包含一组个体的群体，是问题解的集合。

基因模式(Sehemata)：基因模式是指二进制位串表示的个体中，某一个或某些位置上具有相似性的个体组成的集合，也称模式。

适应度(Fitness)：适应度是以数值方式来描述个体优劣程度的指标，由评价函数F计算得到。F作为求解问题的目标函数，求解的目标就是该函数的最大值或最小值。

遗传算子(genetic operator)：产生新个体的操作，常用的遗传算子有选择、交叉和变异。

选择(Reproduetion)：选择算子是指在上一代群体中按照某些指标挑选出的，参与繁殖下一代群体的一定数量的个体的一种机制龙源期刊。个体在下一代种群中出现的可能性由个体的适应度决定，适应度越高的个体，产生后代的概率就越高。

交叉(erossover)：交叉是指对选择后的父代个体进行基因模式的重组而产生后代个体的繁殖机制。在个体繁殖过程中，交叉能引起基因模式的重组，从而有可能产生含优良性能的基因模式的个体。交叉可以发生在染色体的一段基因串或者多段基因串。交叉概率（Pc）决定两个个体进行交叉操作的可能性数学建模论文，交叉概率太小时难以向前搜索，太大则容易破坏高适应度的个体结构，一般Pc取0.25~0.75

变异(Mutation)：变异是指模拟生物在自然的遗传环境中由于某种偶然因素引起的基因模式突变的个体繁殖方式。在变异算子中，常以一定的变异概率（Pm）在群体中选取个体，随机选择个体的二进制串中的某些位进行由概率控制的变换（0与1互换）从而产生新的个体[2]。如果变异概率太小，就难以产生新的基因结构，太大又会使遗传算法成了单纯的随机搜索，一般取Pm=0.1~0.2。在遗传算法中，变异算子增加了群体中基因模式的多样性，从而增加了群体进化过程中自然选择的作用，避免早熟现象的出现。

2.2基本遗传算法的算法描述

用P(t)代表第t代种群，下面给出基本遗传算法的程序伪代码描述：

基本操作：

InitPop（）

操作结果：产生初始种群，初始化种群中的个体，包括生成个体的染色体值、计算适应度、计算对象值。

Selection（）

初始条件：种群已存在。

操作结果：对当前种群进行交叉操作。

Crossover（）

初始条件：种群已存在。

操作结果：对当前种群进行交叉操作。

Mutation（）

初始条件：种群已存在。

对当前种群进行变异操作。

PerformEvolution（）

初始条件：种群已存在且当前种群不是第一代种群。

操作结果：如果当前种群的最优个体优于上一代的最优本，则将其赋值给bestindi，否则不进行任何操作。

Output（）

初始条件：当前种群是最后一代种群。

操作结果：输出bestindi的表现型以及对象值。

3 遗传算法的缺点及改进

遗传算法有两个明显的缺点：一个原因是出现早熟往往是由于种群中出现了某些超级个体，随着模拟生物演化过程的进行，这些个体的基因物质很快占据种群的统治地位，导致种群中由于缺乏新鲜的基因物质而不能找到全局最优值；另一个主要原因是由于遗传算法中选择及杂交变异等算子的作用，使得一些优秀的基因片段过早丢失，从而限制了搜索范围，使得搜索只能在局部范围内找到最优值，而不能得到满意的全局最优值[3]。为提高遗传算法的搜索效率并保证得到问题的最优解，从以下几个方面对简单遗传算法进行改进。

3.1编码方案

因实数编码方案比二进制编码策略具有精度高、搜索范围大、表达自然直观等优点数学建模论文，并能够克服二进制编码自身特点所带来的不易求解高精度问题、不便于反应所求问题的特定知识等缺陷，所以确定实数编码方案替代SGA中采用二进制编码方案[4]。

3.2 适应度函数

采用基于顺序的适应度函数，基于顺序的适应度函数最大的优点是个体被选择的概率与目标函数的具体值无关，仅与顺序有关[5]。构造方法是先将种群中所有个体按目标函数值的好坏进行排序，设参数β∈(0,1)，基于顺序的适应度函数为：

（1）

3.3 选择交叉和变异

在遗传算法中，交叉概率和变异概率的选取是影响算法行为和性能的关键所在，直接影响算法的收敛性。在SGA中，交叉概率和变异概率能够随适应度自动调整，在保持群体多样性的同时保证了遗传算法的收敛性。在自适应基本遗传算法中，pc和pm按如下公式进行自动调整：

（2）

（3）

式中：fmax为群体中最大的适应度值；fave为每代群体的平均适应度值；f′为待交叉的两个个体中较大的适应度值；f为待变异个体的适应度值；此处，只要设定k1、k2、k3、k4为（0，1）之间的调整系数，Pc及Pm即可进行自适应调整。本文对标准的遗传算法进行了改进，改进后的遗传算法对交叉概率采用与个体无关，变异概率与个体有关。交叉算子主要作用是产生新个体，实现了算法的全局搜索能力。从种群整体进化过程来看，交叉概率应该是一个稳定而逐渐变小，到最后趋于某一稳定值的过程；而从产生新个体的角度来看，所有个体在交叉操作上应该具有同等地位，即相同的概率，从而使GA在搜索空间具有各个方向的均匀性。对公式（2)和（3）进行分析表明，适应度与交叉率和变异率呈简单的线性映射关系。当适应度低于平均适应度时，说明该个体是性能不好的个体数学建模论文，对它就采用较大的交叉率和变异率；如果适应度高于平均适应度，说明该个体性能优良，对它就根据其适应度值取相应的交叉率和变异率龙源期刊。

当个体适应度值越接近最大适应度值时，交叉概率和变异概率就越小；当等于最大适应度值时，交叉概率和变异概率为零。这种调整方法对于群体处于进化的后期比较合适，这是因为在进化后期，群体中每个个体基本上表现出较优的性能，这时不宜对个体进行较大的变化以免破坏了个体的优良性能结构；但是这种基本遗传算法对于演化的初期却不利，使得进化过程略显缓慢[6]。因为在演化初期，群体中较优的个体几乎是处于一种不发生变化的状态，而此时的优良个体却不一定是全局最优的，这很容易导致演化趋向局部最优解。这容易使进化走向局部最优解的可能性增加。同时，由于对每个个体都要分别计算Pc和Pm，会影响程序的执行效率，不利于实现。

对自适应遗传算法进行改进，使群体中具有最大适应度值的个体的交叉概率和变异概率不为零，改进后的交叉概率和变异概率的计算公式如式（4）和（5）所示。这样，经过改进后就相应地提高了群体中性能优良个体的交叉概率和变异概率，使它们不会处于一种停滞不前的状态，从而使得算法能够从局部最优解中跳出来获得全局最优解[7]。

(4)

(5)

其中：fmax为群体中最大的适应度值；fave为每代群体的平均适应度值；f′为待交叉的两个个体中较大的适应度值；f为待变异个体的适应度值；pc1为最大交叉概率；pm1为最大变异概率。

3.4 种群的进化与进化终止条件

将初始种群和产生的子代种群放在一起，形成新的种群，然后计算新的种群各个体的适应度，将适应度排在前面的m个个体保留，将适应度排在后面m个个体淘汰数学建模论文，这样种群便得到了进化[8]。每进化一次计算一下各个个体的目标函数值，当相邻两次进化平均目标函数之差小于等于某一给定精度ε时，即满足如下条件：

(6)

式中，为第t+1次进化后种群的平均目标函数值，为第t次进化后种群的平均目标函数值，此时，可终止进化。

3.5 重要参数的选择

GA的参数主要有群里规模n，交叉、变异概率等。由于这些参数对GA性能影响很大，因此参数设置的研究受到重视。对于交叉、变异概率的选择，传统选择方法是静态人工设置。现在有人提出动态参数设置方法，以减少人工选择参数的困难和盲目性。

4 结束语

遗传算法作为当前研究的热点，已经取得了很大的进展。由于遗传算法的并行性和全局搜索等特点，已在实际中广泛应用。本文针对传统遗传算法的早熟收敛、得到的结果可能为非全局最优收敛解以及在进化后期搜索效率较低等缺点进行了改进，改进后的遗传算法在全局收敛性和收敛速度方面都有了很大的改善，得到了较好的优化结果。

参考文献

[1]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,1999:66-68.

[2]王小平,曹立明.遗传算法理论[M].西安交通大学出版社,2002:1-50,76-79.

[3]李敏强,寇纪淞,林丹,李书全.遗传算法的基本理论与应用[M].科学出版社, 2002:1-16.

[4]涂承媛,涂承宇.一种新的收敛于全局最优解的遗传算法[J].信息与控制,2001,30(2):116-138

[5]陈玮,周激,流程进,陈莉.一种改进的两代竞争遗传算法[J].四川大学学报:自然科学版,2003.040(002):273-277.

[6]王慧妮,彭其渊,张晓梅.基于种群相异度的改进遗传算法及应用[J].计算机应用,2006,26(3):668-669.

[7]金晶,苏勇.一种改进的自适应遗传算法[J].计算机工程与应用,2005,41(18):64-69.

篇2

1引言

遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。总的说来，遗传算法是按不依赖于问题本身的方式去求解问题。它的目标是搜索这个多维、高度非线性空间以找到具有最优适应值(即最小费用的)的点[1]。

基本遗传算法是一个迭代过程，它模仿生物在自然环境中的遗传和进化机理，反复将选择算子、交叉算子和变异算子作用于种群，最终可得到问题的最优解和近似最优解。

2遗传算法程序设计改进比较

2.1基本遗传算法对TSP问题解的影响

本文研究的遗传算法及改进算法的实现是以C++语言为基础，在Windows2000的版本上运行，其实现程序是在MicrosoftVisualStadio6.0上编写及运行调试的。

1)遗传算法的执行代码

m_Tsp.Initpop()；//种群的初始化

for(inti=0；i<m_Tsp.ReturnPop()；i++)

m_Tsp.calculatefitness(i)；//计算各个个体的适应值

m_Tsp.statistics()；//统计最优个体

while(entropy>decen||variance>decvar)//m_Tsp.m_gen<100)

{

//将新种群更迭为旧种群，并进行遗传操作

m_Tsp.alternate()；//将新种群付给旧种群

m_Tsp.generation()；//对旧种群进行遗传操作，产生新种群

m_Tsp.m_gen++；

m_Tsp.statistics()；//对新产生的种群进行统计

}

2)简单的遗传算法与分支定界法对TSP问题求解结果的对比

遗传算法在解决NPC问题的领域内具有寻找最优解的能力。但随着城市个数的增加，已没有精确解，无法确定遗传算法求解的精度有多高。一般情况下，当迭代代数增大时，解的精度可能高，但是时间开销也会增大。因此可以通过改进遗传算法来提高搜索能力，提高解的精度。

2.2初始化时的启发信息对TSP问题解的影响

1)初始化启发信息

在上述实验算法的基础上，对每一个初始化的个体的每五个相邻城市用分支界定法寻找最优子路径，然后执行遗传算法。

2)遗传算法与含有启发信息的遗传算法求解结果的对比

当城市数增至20个时，用分支定界法已经不可能在可以接受的时间内得到精确的解了，只能通过近似算法获得其可接受的解。试验设计中算法的截止条件：固定迭代1000代。表2中的平均最优解为经过多次试验(10次以上)得到的最优解的平均值，最优解的出现时间为最优解出现的平均时间，交叉操作次数为最优解出现时交叉次数的平均值。

表220个城市的TSP问题求解结果数据

算法交叉操作

次数最优解

出现时间平均

最优解

简单遗传算法80244.479.4s1641.8

含初始化启发信息的GA79000.237.4s1398.9

从表2中可以看出，当初始种群时引入启发信息将提高遗传算法的寻优能力。同时缩短了遗传算法的寻优时间和问题的求解精度。

2.3交叉算子对TSP问题解的影响

1)循环贪心交叉算子的核心代码

for(i=1；i<m_Chrom；i++)

{

flag=0；

city=m_newpop[first].chrom[i-1]；//确定当前城市

j=0；

while(flag==0&&j<4)

{

sign=adjcity[city][j]；//adjcity数组的数据为当前城市按顺序排列的邻接城市

flag=judge(first，i，sign)；//判断此邻接城市是否已经存在待形成的个体中

j++；

}

if(flag==0)//如果所有邻接城市皆在待扩展的个体中

{

while(flag==0)

{

sign=(int)rand()/(RAND_MAX/(m_Chrom-1))；//随机选择一城市

flag=judge(first，i，sign)；

}

}

if(flag==1)

m_newpop[first].chrom[i]=sign；

}

2)问题描述与结果比较

下面笔者用经典的测试遗传算法效率的OliverTSP问题来测试循环贪心交叉算子的解的精度和解效率。OliverTSP问题的30个城市位置坐标如表3所示[2]。

从表4、图1中可以看到，贪心交叉算子大大提高了遗传算法的寻优能力，同时也降低了交叉操作次数。在多次试验中，贪心交叉算子找到的最优解与目前记载的最佳数据的误差率为2.7%。而部分匹配交叉算子找到的最优解与目前记载的最佳数据的误差率高达7%。从而可以得到交叉算子对于遗传算法

2.4并行遗传算法消息传递实现的核心代码

1)主程序代码

//接收各个从程序的最优个体

for(i=0；i<slave；i++)

{

MPI_Recv(Rchrom[i]，chrom，MPI_UNSIGNED，MPI_ANY_SOURCE，gen，MPI_COMM_WORLD，&status)；

}

//计算接收各个从程序的最优个体的回路距离

for(i=0；i<slave；i++)

{

fitness[i]=0.0；

for(intj=0；j<chrom-1；j++)

fitness[i]=fitness[i]+distance[Rchrom[i][j]][Rchrom[i][j+1]]；

fitness[i]=fitness[i]+distance[Rchrom[i][0]][Rchrom[i][chrom-1]]；

}

//找到最优的个体并把它记录到文件里

for(i=0；i<slave；i++)

{

if(1/fitness[i]>min)

{

sign=i；

min=1/fitness[i]；

}

}

fwrite(&gen，sizeof(int)，1，out)；

for(i=0；i<chrom；i++)

fwrite(&Rchrom[sign][i]，sizeof(unsigned)，1，out)；

fwrite(&fitness[sign]，sizeof(double)，1，out)；

//每九代向从程序发送一个最优个体

if(gen%9==0)

MPI_Bcast(Rchrom[sign]，chrom，MPI_UNSIGNED，0，MPI_COMM_WORLD)；

2)从程序代码

//将上一代的最优个体传回主程序

MPI_Send(Rchrom1，chrom，MPI_UNSIGNED，0，gen，MPI_COMM_WORLD)；

//每九代接收一个最优个体并将其加入种群中替换掉最差个体

if(gen%9==0)

{

PI_Bcast(Rchrom2，chrom，MPI_UNSIGNED，0，MPI_COMM_WORLD)；

Tsp.IndiAlternate(Rchrom2)；

}

//进行下一代的计算

Tsp.Aternate()；

Tsp.Generation()；

Tsp.Statistics()；

3)并行遗传算法的性能

笔者在MPI并行环境下，用C＋＋语言实现了一个解决TSP问题的粗粒度模型的并行遗传算法。该程序采用的是主从式的MPI程序设计，通过从硬盘的文件中读取数据来设置染色体长度、种群的规模、交叉概率和变异概率等参数。试验环境为曙光TC1700机，测试的对象是OliverTSP问题的30个城市的TSP问题。

正如在测试串行遗传算法所提到的数据结果，并行遗传算法也没有达到目前所记录的最好解，但是它提高了算法的收敛性，并行遗传算法的收敛趋势如图2所示[4]。

图2遗传算法的收敛过程

3结束语

本文通过对基本遗传算法的不断改进，证明了添加启发信息、改进遗传算子和利用遗传算法固有的并行性都可以提高遗传算法的收敛性，其中对遗传算法交叉算子的改进可以大大提高遗传算法的寻优能力。

参考文献

[1]刘勇、康立山，陈毓屏著．非数值并行算法－遗传算法．北京：科学出版社1995.1

篇3

 

0引言

遗传算法是一种较新的全局优化搜索算法，它使用了群体搜索技术，用种群代表一组问题解，通过对当前种群施加选择、交叉和变异等一系列遗传操作，从而产生新的一代种群，并逐渐使种群进化到包含最优解或近似最优解的状态。但由于算法复杂度的限制, 遗传算法虽然能以概率收敛到全局最优解，其局部搜索速度和精度并不能得到很好的保证。近几年来遗传算法作为优良的全局寻优方法日趋成熟,尤其是和其他寻优方法的结合,进一步提高了遗传算法的性能，其中借助于混沌改进遗传算法的性能,是近年来遗传算法领域研究的热点之一，遗传算法和混沌优化的组合,可以使遗传算法的全局寻优能力,搜索精度,搜索速度等几方面得到较明显的改进。

1混沌的特征和虫口方程

混沌是存在于非线形系统中的一种较为普遍的现象。混沌并不是一片混乱，而是有着精致内在结构的一类现象。混沌运动具有遍历性、随机性等特点，混沌运动能在一定的范围内按照其自身的规律不重复地遍历所有状态。因此，如果利用混沌变量进行优化搜索，无疑会比随机搜索更具有优越性。

描述生态学上的虫口模型Logistic映射自May于1976年开始研究以来，受到了非线形科学家的高度关注，Logistic映射是混沌理论发展史上不可多得的典范性的混沌模型，如下式所示：

2混沌遗传算法

GA较传统数学优化方法更易找到全局最优解，但对于一些问题也存在过早收敛、收敛速度较慢、难以找到较精确解的情况。因此，本文通过Logistic映射及相关混沌理论提出了一种运算性能较好的混沌遗传函数优化算法。混沌遗传算法(CGA)的主要步骤如下：

1.初始化:预先确定运行参数，包括：种群规模M，交叉概率pc，变异概率pm，最大迭代次数n。随机产生一个分布均匀的初始群体(包含n个初始解)，计算各个个体的适应度值；

2.采用比例选择算子对当前种群进行选择操作，实现强留劣汰；

3.对当前种群进行交叉运算。将种群内个体两两随机组合，对每个配对的组合，首先由系统随机生成一个(0,1)之间的数，由交叉概率决定是否交叉。论文参考。论文参考。若交叉，则采用映射生成的序列经简单映射后利用高斯函数来决定交叉位置，否则，看下一对组合。所有的交叉位置由一个混沌序列即可决定；

5.若终止条件满足，则算法中止，否则转向步骤(2)。

本文尝试在将改进后的遗传算法与混沌优化算法相结合，提出一种基于混沌理论的混合遗传算法，算法的流程如下页流程图所示：

图1 改进后的混沌遗传算法（ICGA）流程图

3仿真分析

本文选用一维和多维多峰值函数为例，见表1，用遗传算法（GA）、混沌遗传算法（CGA）和本文算法（ICGA）进行比较研究。

表1 测试函数

实验结果比较如下（以下图纵坐标表示最大适应值，横坐标表示演化代数）

图2 f2实验结果比较示意图图3 f3实验结果比较示意图

从图2、图3的比较结果看，本文中算法初始种群较好，进化开始就能找到高的最大值，加快搜索的速度，整个算法的寻优结果比遗传算法好。论文参考。考虑到算法中使用了随机操作，仅仅由一次实验得到的结果是不能够充分说明问题的，因此，再进行统计比较。本文中进行了20次统计实验。比较结果如表2

篇4

中图分类号：TP183文献标识码：A文章编号：1009-3044(2008)14-20917-02

1 引言

近年来，遗传算法以其高效实用的特点迎来了兴盛发展的时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是在应用研究方面，众多的研究者在组合优化、模式分类、预测控制等领域都取得了丰硕的成果。对于大自然生物演化的行为准则，达尔文给出了“物竞天择，适者生存”的有力概括，这一学说也成为人们向大自然学习的一个依据。

2 国内外研究现状

遗传算法研究的兴起是在80年代末和90年代初期，但它的历史起源可追溯至60年代初期。早期的研究大多以对自然系统的计算机模拟为主。如raser的模拟研究，他提出了和现在的遗传算法十分相似的概念和思想。Holland和DeJong的创造性研究成果改变了早期遗传算法研究的无目标性和理论指导的缺乏。其中，Holland于1975年出版的著作《自然系统和人工系统的适配》系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论。它使用群体搜索技术，通过对目标群体实施选择、交叉、变异等一系列遗传操作，从而产生新一代的群体，并使群体进化包含或接近最优的状态。

自1985年以来，国际上已多次召开了遗传算法的学术会议和研讨会，国际遗传算法学会组织召开的ICGA（International Conference on Genetic Algorithms）会议和FOGA(Workshop on Foundation of Genetic Algorithms)会议，为研究和应用遗传算法提供了国际交流的机会。

3 遗传算法的产生及发展

遗传算法(Genetic Algorithms,GA)是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，20世纪60年纪末期到70年代初期，主要由美国著名学者密西根大学教授John.Holland其同事、学生们研究形成了一个较完整的理论和方法，从试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。它采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索方向。遗传算法的操作对象是一群二进制串（称为染色体、个体），即种群。这里每一个染色体都对应问题的一个解。从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个体，使用杂交和变异来产生下一代种群。如此模仿生命的进化一代代演化下去，直到满足期望的终止条件为止。由于它采用种群（即一组表示）的方式组织搜索，这使得它可以同时搜索空间内的多个区域。而且用种群组织搜索的方式使得遗传算法特别适合大规模并行。在赋予遗传算法自组织、自适应、自学习等特征的同时，优胜劣汰的自然选择和简单的遗传操作使遗传算法具有不受其搜索空间限制性条件（如可微、连续、单峰等）的约束及不需要其它辅助信息（如导数）的特点。这些崭新的特点使得演化算法不仅能获得较高的效率而且具有简单、易于操作和通用的特征，而这些特征正是遗传算法越来越受到人们青睐的主要原因之一。

4 遗传算法的基本原理

遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

遗传算法的实施过程包括编码、产生初始群体、计算适应度、复制、交换、突变、反复迭代、终止等操作。我们用Gen代表遗传（迭代）的代次，遗传算法从Gen=0开始。根据所研究问题的表达方式确定字符串长度L，接着随机产生M个初始群体。刚开始时，终止条件不会被满足，于是依次计算群体中各个个体的适应度。根据计算结果，依次进行复制、交换、突变等遗传操作。

遗传算法的思想简要给出如下：（1）初始化群体；（2）计算群体上每个个体的适应度值；（3）按由个体适应度值所决定的某个规则选择将进入下一代的个体；（4）按概率Pc进行交叉操作；（5）按概率Pc进行突变操作；（6）没有满足某种停止条件，则转第（2）步，否则进入（7）；（7）输出种群中适应度值最优的染色体作为问题的满意解或最优解。

5 遗传算法的缺点及改进

尽管遗传算法有许多优点，但目前存在的问题依然很多，如：（1）适应度值标定方式多种多样，没有一个简洁、通用的方法，不利于对遗传算法的使用；（2）遗传算法的早熟现象（即很快收敛到局部最优解而不是全局最优解）是迄今为止最难处理的关键问题；（3）快要接近最优解时在最优解附近左右摆动，收敛较慢。

因此，遗传算法通常需要解决以下问题，如确定编码方案，适应度函数标定，选择遗传操作方式及相关参数，停止准则确定等。相应的，为改进简单遗传算法的实际计算性能，很多学者的改进工作分别从参数编码、初始群体设定、适应度函数标定、遗传操作算子、控制参数的选择以及遗传算法的结构等方面提出的。

6 总结

遗传算法是将生物学原理应用于计算机科学的仿生学理论成果。由于它具有极强的解决问题的能力，引起了众多学者的兴趣与参与，已成为学术界跨学科的热门专题之一。遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多优化领域。据不完全统计，进化算法已经在16 个大领域、250 多个小领域中获得了应用。遗传算法在机器学习、过程控制、经济预测、工程优化等领域取得的成功，己引起了数学、物理学、化学、生物学、计算机科学、社会科学、经济科学及工程应用等领域专家的极大兴趣和广泛关注。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。

参考文献：

[1] Holland J H(1975).Adaptation in natural and artificial systems. University of Michigan Press.

[2] 田延硕.遗传算法的研究与应用[D].电子科技大学硕士论文.

[3] 李敏强,寇纪淞,林丹,等.遗传算法的基本理论与应用[M].科学出版社,2003.

篇5

中图分类号：TP301 文献标识码：A

排课问题在学校教学管理中十分重要，它是一个有约束的、多目标的组合优化问题，并且已经被证明为是一个NP完全问题。由于涉及信息较多且求解比较复杂资源的最优化配置不容易实现，因此使用计算机对排课信息进行管理，能够极大地提高学校教务管理的效率，也是各种体制学校管理科学化、现代化的重要条件。现在大多数的排课系统是以编程语言为实现语言，采用各种算法为实现手段，比如遗传算法、回溯算法、模拟退火算法等。作为对排课问题的探索，本文采用遗传算法的思想，提出一个课表方案的随机生成和优化算法，以期能够较大程度地反映实际排课情况和尽量达到多个目标最优。

1 排课问题分析

1.1 排课问题的因素

从手工排课的过程看出，排课问题需要考虑的条件很多，如周课时设置、课程信息、班级信息、教师信息、教室信息等等。从排课过程可能引起潜在冲突的角度，可以将排课问题涉及的因素考虑如下：

时间：在排课问题中涉及关于时间的概念有学年、学期、周、天、节。

课程：每个课程都有自己的编号、名称。每个课程都有指定的教师、教室等。某些课程由于上课班级较多难以协调或照顾教师要求等诸如此类原因，应该预先给定时间或教室。

教室：每个教室都有编号、门牌号和名称。每个教室在同一时间内只能接纳一门课程的授课，并且教室容量应该大于等于上课的人数。

班级：每个班级都有编号和名称。每个班级同一时间只能上一门课程。

教师：每个教师都有编号和姓名。每个教师同一时间只能上一门课程。

1.2 排课过程的约束条件

排课是将教师与学生在时间和空间上根据不同的约束条件进行排列组合，以使教学正常进行。避免排课因素发生冲突是排课问题中要解决的核心问题。只有在满足全部约束条件和避免冲突的基础上，才能保证整个教学计划合理正常进行。而对教师、教室、学生及时间等资源进行最优化组合配置，才能保证充分发挥各资源的优势和提高教学质量。

排课过程中常见的约束条件如表1所示：

1.3 排课问题的目标实现

排课问题是一个多目标的组合规划问题，要想制定出一个“合理、实用、有特色”的课表，必须保证所有的约束条件都不发生冲突。一套高质量的课表，在时间、教室资源、课程安排等很多方面都应该做到科学的安排，并且应该具有人性化的考虑。课表编排问题的难点在于：保证课表在时间及人员的分配上符合一切共性和个性要求，在此基础上，所有的课程都能够安排合适的时间和教室，使安排方案在各个目标上尽量达到全局最优。

遗传算法是1975年美国MIChiga大学的John.H.Holland教授及其学生们根据生物进化的模型提出的一种优化算法。作为一种随机的优化与搜索方法，遗传算法有两个主要特性：1智能性。即遗传算法在确定了编码方案、适应值函数及遗传算子以后，算法将利用演化过程中获得的信息自行组织搜索。适应值大的个体具有较高生存概率，它是具有“潜在学习能力”的自适应搜索技术。2并行性。由于遗传算法采用种群的方式组织搜索，从而可以同时搜索解空间内的多个区域，并相互交流信息，这种搜索方式使得遗传算法能以较少的计算获得较大的收益。正是由于遗传算法的这两个特性，使得遗传算法迅速被运用于求解组合优化的排课问题，且操作简单，可以更少地依赖于实际问题的情况，实现课表的优化。

2 遗传算法在课表编排中的应用

2.1 遗传算法的基本原理

遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。一般的遗传算法都包含三个基本操作：复制、交叉、变异。

2.1.1 复制，是从一个旧种群中选择生命力强的个体字符串产生新种群的过程。复制操作过程中，目标函数是该字符串被复制或被淘汰的决定因素。遗传算法的每一代都是从复制开始的。

2.1.2 交叉，在由等待配对的字符串构成的匹配池中，将新复制产生字符串个体随机两两配对，然后随机地选择交叉点，对匹配的字符串进行交叉繁殖，产生一对新的字符串。

遗传算法的有效性主要来自复制和交叉操作，尤其是交叉在遗传算法中起着核心的作用。

2.1.3 变异，遗传算法中，变异就是某个字符串某一位的值偶然的随机的改变，即在某些特定位置上简单地把1变成0，或反之。变异操作可以起到恢复字符串字符位多样性的作用，并能适当地提高遗传算法的搜索效率。

2.2 遗传算法在课表编排中的设计

使用遗传算法编排课表，我们把课程和老师当作同一变量考虑，这样编排课表只需将教师编码排入周课表，在以后打印课表时，将教师编码改为课程名即可。于是我们设计以下步骤：对每一门任课教师进行编码；使用二维数组来构成初始群体；冲突的检验和消除；定义课表的适应度函数(x)(x∈{1,2,…,N}),其中x表示个体在群体中的位置。当函数值为0时，即找到了本次优化过程的最优值；复制操作：按照适配值计算选择率和期望的复制数；交叉操作：将种群中的个体配对产生的交叉点再分别交换；变异操作：将随机产生的同列的两个位置互换；再次进行冲突检测和消除，直至无冲突存在。

2.3 算法的实现

遗传算法结束后，可以得到综合效率函数值最好的个体。根据这个结果，即可生成相应的课程表。系统的流程分为以下几个主要的过程：（1）初始种群的产生：形成本学期教学信息二维表，对教师编码；产生染色体。（2）对各类冲突进行检测，如存在冲突则消除它。（3）计算适应度函数值、期望值及其复制数。（4）进行遗传操作。（5）可行课程表的产生。

这样，我们就有了一个课程表的数据库表。因此，可以打印其中某一班级的课程表或全校的课程表了。

结论

本文采用遗传算法来对课表编排问题进行求解，是求解这种难解的组合优化问题方法中较明智的选择，目的是在遗传算法基础上提出一个课表方案的随机生成和优化方案，能够较大程度地实现课表编排和多个目标的最优化。本文算法对我们这类院系较多、教师工作量大、学科变化较大、不确定性较多的学校能有所借鉴。

参考文献

篇6

1 前言

对于一个粗糙集决策属性表，人们总是期望能找出所有约简或最小约简，然而一个信息表的属性约简并不是唯一的，得到信息表的包含最少条件属性的约简已被证明是NP 完全问题。由于免疫遗传算法在NP问题领域取得了比较好的效果，论文提出了一种基于免疫遗传算法的粗糙集属性约简算法，实验结果证明该算法是有效的，可快速收敛到全局最优解。

2 属性约简的免疫遗传算法设计

2.1 染色体编码

采用传统的二进制编码，即若决策表中有N个待约简的条件属性，算法产生一个长度为N的0-1二进制串，每一位代表一种对条件属性的取舍，1表示采用该位上的条件属性，0则表示不采用。

2.2 初始种群的产生

初始种群设置的好坏直接影响到最后的求解效果。任何一个信息表或决策表的相对核都包含在所有相对约简当中，即具有唯一性。因此考虑在产生初始种群的时候使每个染色体都含有相对属性核。

2.3 适应度函数的构造

适应度函数用来评价染色体的优劣，在对每一个染色体进行适应度评价前，先要对每个染色体进行一定的调整。调整是基于属性重要度相关的某种启发式信息，给出染色体的调整步骤：

（1）计算决策表S中条件属性集C关于决策属性集D的重要度γc（D）；

（2）设C'为当前染色体采用的条件属性集，计算条件属性集C'关于决策属性集D的重要度γc'（D）；

（3）比较γc（D）和γc'（D）的大小，若γc'（D）

（4）对任意属性ai（∈C-C'）（1=1，2，…，|C-C'|），计算每一个μD（ai），令j={j|μD（aj）=max（μD （ai））}，然后将染色体上第j位上的0置为1，并且C'=C'∪{aj}，转到步骤②；

（5）调整过程结束。当染色体经过如上调整以后，就可以应用适应度函数对该染色体进行评价，适应度函数的计算公式为：

F=|C|-|C'| （5.16）

则染色体中采用的条件属性个数越少，该染色体的适应度函数值就越高，个体就越优良。

2.4 抗体产生的促进和抑制

要使适应度高的抗体进行促进，浓度高的抗体进行抑制。

抗体相似性通过抗体编码的Manhattan距离来度量。抗体X={a1，a2，…an}与抗体Y={b1，b2，…bn}之间的相似度为：

d值越大，表示两者的相似程度越低，如果d=0，则表示两个抗体完全相同。故抗体X的浓度定义为：

其中，函数D（X）表示抗体X相似度小于λ的抗体数目，λ为一给定的阈值

2.5 基于收缩精度的逐级进化策略

可以用收缩精度作为算法的停止准则，即当收缩精度小于某个比较小的正数K时算法停止进化。假设优化目标为求目标函数F的最大值，在不同的进化时期适应度函数J采用不同的形式如下：

式中α、β、k1 和k1为正数，根据优化目标的需要取不同的值。其中α 和β是为了在算法的中后期拉大群体内个体之间的差距，α

3 实例分析

在某次战斗任务中，我方使用各种常规武器对敌方6处战场目标实施打击。参与毁伤效果评估计算的我方武器“投入”和“产出”数据离散化得出一个毁伤评估决策信息表。应用改进的遗传算法进行属性约简。图1所示为免疫遗传算法求解最优约简属性向量的迭代过程。改进后的基于收缩精度的遗传算法在进化15代以后即停止搜索，得出了近似最优解。

由图1可以看出在算法的进化过程中，迭代曲线每隔几代都会变化一次。并且在算法的中后期，曲线依然出现明显变化。一方面说明算法自始自终都实现了对解空间的有效搜索，另一方面与传统算法相比，没有出现过早收敛的现象。说明改进后免疫遗传算法的科学性和有效性。

参考文献

[1]曾子林，张宏军，张睿，邢英.变精度粗糙集的逻辑解释及其约简[J].计算机应用研究，2013（05）.

[2]肖大伟，王国胤，胡峰.一种基于粗糙集理论的快速并行属性约简算法[J].计算机科学，2009（03）.

篇7

Abstract: On the basis of analyzes the high embankment settlement characteristics, settlement prediction methods are discussed, studied the curve fitting, the legal gray system method, artificial neural network, genetic algorithm, the inverse analysis method, based on genetic algorithms and neural networks prediction methods, as well as Pierre - genetic neural network method and other high embankment settlement prediction method and its application, to provide a theoretical reference for the accurate prediction of high embankment settlement.Key words: high embankment; settlement prediction; principle; application

中图分类号：F272.1文献标识码： A 文章编号：

1引言

随着我国公路建设的快速发展，高速公路逐步向山区延伸，出现了越来越多的高路堤。与一般路基相比，高路堤沉降量大，沉降稳定时间长。然而，高路堤的沉降是一个很复杂的过程，环境条件、地基土的应力历史、路堤填料的工程性质、路堤填筑高度和施工工艺等因素都不同程度地影响和制约着高路堤沉降。目前，国内外针对软基沉降的预测开展了大量的研究，取得了较丰富的的研究成果[1]，但对于高路堤沉降预测尚缺乏系统、全面的研究。因此，对现有高路堤沉降预测方法进行系统的总结分析，并提出改进措施，以期找到一种较适宜的高路堤沉降预测方法具有较为重要的工程。

2现有沉降预测方法分类

路基沉降预测方法可以分为三类：以经典土力学为基础的传统预测方法、以本构理论为基础的数值计算法和根据实测沉降资料预测法。

2.1 传统预测方法

传统的沉降预测方法是建立在太沙基等人创立的经典土力学基础之上。传统预测方法包括：一维沉降计算法、司开普顿和比伦法、三维计算法和应力路径法[2]。

2.2 数值分析方法

数值分析方法包括有限元法和有限差分法。

(1)有限元法[3]：有限元法将地基和路堤作为一个整体来进行分析，将其划分网络，形成离散体结构，在荷载作用下求得任一时刻路堤和地基各点的位移和应力。

(2)有限差分法[4]：有限差分法是用差分公式将地基沉降问题的控制方程转化为差分方程，然后结合初始条件和边界条件，求解线性代数方程组，得到所求问题的数值解。

2.3 根据实测资料的沉降预测方法

根据实测资料进行沉降预测的方法主要有双曲线法、指数曲线法、泊松曲线法、Asaoka法、三点法、星野法、皮尔曲线法、龚帕斯曲线法、灰色预测法、神经网络预测法、模糊综合评判法、反分析法等[5]。

2.3.1 曲线拟合法

曲线拟合法假定地基沉降历程符合某一种已知函数曲线，利用实测沉降数据拟合曲线的参数，然后利用确定后的曲线公式预测地基在任一时间的沉降值。包括双曲线法、指数曲线法、时间对数拟合法、泊松曲线法、Asaoka法、三点法、星野法等。其中最常见的有双曲线法、指数曲线法、时间对数拟合法、泊松曲线法、Asaoka法。

（1）双曲线法[6]假定沉降平均速度随时间按双曲线变化，其基本方程式为：

（2）指数曲线法[7]假定沉降平均速度随时间按指数曲线变化，其基本方程式为：

（3）时间对数拟合法[8]假定沉降平均速度随时间按对数曲线变化，其基本方程式为：

利用这些曲线方程可以计算任一时刻t（）的沉降量。同时，对分别求一阶导和二阶导可以求得沉降速率及沉降速率变化率。当时，利用极限方程可以推算出最终的地基沉降量。其中为荷载稳定之后的某一时刻。

（4）泊松曲线就是逻辑斯蒂成长曲线[9]，也称皮尔曲线，其表达式为：

其中a、b、c均为待定参数，t为时间，为t时刻的沉降值。

（5）Asaoka[10]法是一种从一定时间过程所得的沉降观测资料来预计最终沉降量和沉降速率的方法，其基本表达式为：

为时间时的沉降量，，，且为常数。根据实测沉降资料，作图确定待定参数、和最终沉降量。

2.3.2 灰色预测法[11,13]

GM(1,1)模型是灰色系统理论中最基本也是最常用的模型，它是通过对已知的单位时段内的沉降量的研究来获得沉降的变形规律，从而预测它在未来时间内的变化量。其基本思想是对无规则的数据序列做一定变换使其变得有规则。

GM(1,1)常用的微分方程式为：

对原始数列做累加生成：（=1,2,3…n）

得到GM(1,1)灰色微分方程的时间响应序列解为：

=1,2,…，n

还原值 =1,2,…，n

根据上列各式，便可对观测数列的后序值进行预测。

2.3.3 神经网络预测法

神经网络中目前比较成熟且应用最为广泛的是误差逆传播网络，简称BP网络。它一般由输入层、隐含层及输出层组成，同层节点间没有任何联系，不同层节点均采用前向连接方式。BP神经网络模型实现特定的输入与输出的映射分为学习过程和运用过程两部分。其学习过程可归纳为“信号正向传播、误差逆向传播、记忆训练、学习收敛”。具体学习算法可归纳如下[14]：

(1) 网络初始化：随机给全部权值及神经元的阈值赋以初始值，给定输入模式和输出模式；

(2) 用输入模式计算中间层各单元的输入，然后利用计算中间层各单元的输出；

(3) 利用计算输出层各单元的输入，然后利用计算各单元的响应；

(4) 计算各单元的一般化误差并修正连接权，通过修正各权值使误差最小；

(5) 选择下一个学习模式对从第3步开始，直至全部模式对训练完毕；

(6) 达到误差精度和循环次数后输出结果，否则返回第3步。

2.3.4 遗传算法[15]

遗传算法模拟了自然选择和遗传过程中发生的繁殖、杂交和变异现象。在利用遗传算法求解问题时，每个可能的解都被编码成一个“染色体”，即个体，若干个体构成了群体，即所有可能解。选择、交叉、变异这3个操作算子构成遗传算法的遗传操作。使用遗传算法时，首先要随机地产生一些初始解，同时给出一个目标函数和适应度值，然后根据预定的目标函数对初始解进行评价，根据适应度值按“优胜劣汰”的原理选择复制下一代。在这个过程当中，因为选择来复制的是好的个体，因此，选择出来的个体经过杂交和变异算子进行再组合生成的新的一代就继承了上一代的优良性状，这样一来，就可以使得遗传过程朝着更优解的方向进行。

2.3.5反分析法

反分析法是利用施工过程中实测的地基沉降资料反演确定地基土的物理力学模型参数，再将反演得到的参数代回到正分析模型中计算地基沉降量。进行反分析的方法有很多种，其中直接反分析是比较有效、稳定且应用较多的一种方法，其具体步骤如下[16]：

(1) 建模。这个模型是一个描述实际岩土工程结构问题或理论数学的模型，其中含有一组待定的材料性质参数，用列阵P表示。

(2) 待定参数的选取。用理论模型在外部条件下产生的响应作为待定参数的函数。

(3) 建立目标函数并确定参数的约束条件。目标函数的通用表达式为：

其中，J为目标函数，为观测值向量， X为有限元计算值。

(4) 选择优化策略，使。式中，是最终反分析结果。

2.3.6 基于遗传算法和神经网络的预测方法[17]

基于遗传算法和神经网络的预测方法是遗传算法和神经网络法两种方法的结合。它是指在人工神经网络的学习过程中，应用遗传算法对神经元连接权值进行编码，并随机生成初始群体，进行交叉、变异，同时计算能量函数，调整交叉、变异概率，迭代，直至神经网络训练完成。这种新算法能够改变神经网络法收敛时间长、搜索能力较差的弱点。

2.3.7 皮尔-遗传神经网络法

皮尔-遗传神经网络法是在总结分析皮尔曲线法、遗传算法、神经网络法三种方法的基础上提出来的，它结合了此三种方法的优点。研究表明[18]，皮尔曲线可以较准确地描述高路堤沉降趋势，但是趋势项的偏移量是一个复杂的非线性序列，使用皮尔曲线计算时误差较大，因而采用神经网络模型进行外推。然而人工神经网络学习过程又有收敛时间过长、易陷入局部最小以及搜索能力较差等缺点，故采用遗传神经网络法来进行研究。这种方法与上述的基于遗传算法和神经网络的预测方法的唯一不同就是先采用皮尔曲线建模，然后对趋势偏移量用神经网络法建模，其后的算法同遗传-神经网络法。

3结语

通过对沉降预测方法的分析，可以看出各种沉降预测方法既有其优越性也有其缺陷，没有一种方法是万能的。因此，如何充分利用各方法的优点，改正其缺点是探求一种精确预测方法时必须考虑的问题。

(1) 在曲线拟合法中，目前还没有一种方法能够精确的拟合实测沉降曲线。比如，运用双曲线法预测最终沉降量有时偏大，指数法有时偏小，同时双曲线和指数曲线更适合于施工前期预测，对于后期预测误差比较大，而皮尔曲线则更适合长期预测。因此，分析各种曲线的优缺点及其适用条件以找到一种能够精确拟合实测沉降的曲线方法显得很有必要。

(2) 运用神经网络法进行预测时存在收敛时间过长，易陷入局部最小，以及搜索能力较差等缺点。针对这个问题，有人提出了遗传-神经网络法，将遗传算法与神经网络法结合，用遗传算法来改变神经网络法收敛时间长、搜索能力差的弱点。同时也有人提出了皮尔-遗传神经网络法，用皮尔曲线提取趋势线，用神经网络法对偏移量进行外推，用遗传算法进行计算。这为我们指出了一个研究的方向，那就是如何使各种方法优势互补，以找到一种能准确预测沉降量的方法。

(3) 目前已有的沉降预测方法虽然较多，但是相对来说还是比较笼统，对于不同的地质情况使用什么样的预测方法还没有系统的研究。比如，对于填土、填石、土石混填以及不同性质的土料分别填筑路基时选用何种预测方法有待于进一步研究。

主要参考文献

周焕云,黄晓明.高速公路软土地基沉降预测方法综述[J]. 交通运输工程学报,2002,2(4):7-10.

罗鑫.高路堤沉降预估方法的研究[D].长沙:长沙理工大学硕士论文,2003:1-8.

李婕.高速公路填方路基沉降预测方法研究[D].桂林:桂林工学院硕士论文,2008:14-25.

黎鹏.山区高填路堤沉降研究及有限元分析[D].武汉:湖北工业大学硕士论文,2007．

徐晓宇.高填方路基沉降变形特性及其预测方法研究[D].长沙:长沙理工大学硕士论文,2005:16-17.

潘林有,谢新宇.用曲线拟合的方法预测软土地基沉降[J]. 岩土力学,2004,25(7):1053-1058.

金 莉.几种预测模型在高路堤沉降预测中的对比分析[J].西部探矿工程,2006,(4):234-235.

杨盛福,张之强,李家本,等.高速公路路基设计与施工[M].上海:人民交通出版社,1997.

周密.非等时距皮尔曲线在高路堤沉降预估中的应用[J].中外公路,2006,26(3):42-44.

段文涛.高填路基沉降监测与预测研究[D]. 武汉:湖北工业大学硕士论文,2008.

付宏渊.GM(1,1)灰色模型在高路堤沉降预估中的应用[J].中外公路,2006,26(2):11-13.

魏阳平, 刘涌江.高路堤沉降的灰色系统理论预测方法[J].公路交通技术,2004,(4):5-7.

吴大志,李夕兵,蒋卫东,等. 灰色理论在高路堤沉降预测中的应用[J]. 中南工业大学学报,2002,33(3):230-233.

於永和,李素艳.基于L-M法BP神经网络的高填路堤地基沉降预测[J].交通标准化,2006,(10):167-170.

邹德强,王桂尧.遗传算法在高路堤沉降预测中的应用[J].长沙交通学院学报,2004,20(1):19-24.

邹德强.高填方路基沉降反演及预测方法的研究[D].长沙:长沙理工大学硕士论文,2004.

徐晓宇,王桂尧,匡希龙,戴剑冰.基于遗传算法和神经网络的高路堤沉降预测研究[J].中南公路工程,2006,31(3):30-33.

篇8

中图分类号：TP18文献标识码：A文章编号：1009-3044(2011)29-7217-02

Genetic Algorithm Based on the Network Test System Development and Application

GUO Shu-hua

(Guangsha College of Applied Construction Technology, Dongyang 322100, China)

Abstract: Along with the vigorous development of education and network technology, more and more courses are chosen online practice and test, so how to design and develop the online test system is paid more and more attention to. There are many commonly used test paper methods, but this paper mainly studies the test paper method based on genetic algorithm method. The purpose of this article is to realize the functions of testing paper, testing, scoring, test managing, test paper grade managing and other functions, and develop a complete set of network examination system.

Key words: online testing system; maneuvers of composing examination papers; genetic algorithm

如今，计算机技术和互联网技术的发展日新月异，它们越来越多地渗透到社会各个领域，对当代社会产生着重大影响。随着计算机等现代科学技术被越来越广泛地应用以及应用水平的不断提高，必将大大改变我们的工作方式、学习方式和生活方式。教育如何迎接现代科学技术，如何应用科学技术，以提高教学质量，培养高素质人才，已引起人们的普遍关注。近年来，我国的开放教育和网络教育正蓬勃发展，越来越多的课程选择在线进行练习或测试，因此如何设计和开发在线测试系统也受到越来越多的人的关注。

在线测试系统作为网络教育系统的一个重要组成部分，作为它的一个子系统，是体现网络教学质量的重要手段，也是实现网络教育的关键环节。而在线考试系统中最重要的一个组成部分就是系统的组卷算法了。随着信息技术和数据库技术的高速发展，利用计算机存储大量的试题信息并结合数据库技术实现试题的自动组卷功能已成为一项非常实际可行并且应用性极其广泛的课题。国外和国内的许多科研单位、学校机构等都在对组卷系统进行研究[1]。

本课题主要的研究遗传算法的思想，并开发一套基于遗传算法组卷的在线考试系统。系统通过遗传算法对题库进行编码初始化，并通过选择、交叉、变异的迭代过程进行组卷，同时实现学生测试，教师评分、成绩查询、试卷管理等功能。

1 算法分析

对于组卷系统来讲，生成符合系统要求的一套试卷是组卷系统中一项最根本的功能要求，而运用什么样的算法来实现抽题组卷对这个组卷系统的性能和质量来讲是关键。自动组卷不但能最有效地把客户的需求与计算机技术结合在一起，生成符合要求的试卷，且比较客观、规范，使用起来也最为方便[1]。 目前，自动组卷系统根据其所使用的组卷策略大致可以分为四类[2]：

1) 随机抽取法；2) 回溯试探法；3) 遗传算法；4) 定性映射算法。

随机抽取法根据状态空间的控制指标，由计算机随机抽取试题组成试卷。该方法实现最为简单，不需要很高的技术支持，但具有很大的随意性和不确定性，使生成的试卷缺少整体性和科学性，组卷的效率也比较低。回溯试探法记录随机产生的每一状态类型，如果搜索失败则将上次记录的状态类型进行释放,然后采用特定的规律运用新的一种状态类型进行回溯试探，直到试卷生成成功或退回到起点为止。回溯试探法不适合大型的题库系统，通常适用于题型和题量都比较小的考试系统。该算法程序实现相对比较复杂，出题的随机性比较差，试卷生成时间也比较长。定性映射算法提出了一种合理分配不同难度试题的方法[2]。这种算法首先要建立一个组卷的数学模型，同时采用多目标优化为选题依据。这种组卷算法在生成试卷的效率和成功率上有比较大的提高，是实现自动组卷的一种新途径。但是要求建立数学模型，对数学的基础要求比较高，同时程序结构比较复杂，算法实现比较困难。

遗传算法（Genetic Algorithm，GA）是Michigan大学的John Holland在20世纪60年代末期到70年代初期借鉴生物界的进化规律而提出来的随机化搜索方法，主要模拟生物进化论的自然选择和遗传学机理搜索出最优解的方法，遗传算法主要的特点有并行性、通用性、自适应性、全局优化性和收敛速度快等[3]。依据遗传算法的这些特点，将其应用到考试系统的进行自动组卷，组卷效率和质量有大幅度的提高。

2 遗传算法研究

2.1 遗传算法概述

遗传算法是是近几年发展起来的一种崭新的借鉴生物界自然选择和自然遗传机制的全局优化算法，它借用了生物遗传学的观点，是基于群体进化的一种方法，通过自然选择、遗传、变异等作用机制，来提高各个个体的适应度。其思想是从一组随机产生的初代种群中开始搜索，按照适者生存以及优胜劣汰的原理，根据问题域中个体的适应度挑选个体，并运用遗传算子进行组合交叉、变异，产生出符合要求的种群或者达到预先设定的迭代次数为止。

遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域[3]，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学，如函数优化，组合优化。此外，也在生产调度问题、自动控制、图像处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。遗传算法作为一种有效的强大的随机搜索方法，有着重要的理论和实际价值。遗传算法组卷流程图如图1所示。

2.2 约束条件

本系统中，编码方式采用标准的二进制编码，二进制位串的长度为题库的题目数，染色体上的每一个基因代表对应的试题是否被挑选：1为该试题被挑选，0为该试题没有被挑选，那么每一个染色体代表一组选题结果。同时在编码的过程中将基因按题型有序排序。在初始化编码时，通过随机函数产生相应数目的界于1和题目数之间的不同随机数，再将序号和随机数相符的基因设置为1，以实现初始编码。

算法的适应度函数主要通过章节比例约束、难度比例约束、区分度比例约束、时间约束四个约束来实现。

1）章节比例约束的计算公式为：f1= （i为章数，z为应选题目数，Z为总题数）。

2）难度比例的约束公式为：f2= （i为题型数，j为题目数，n为题目难度，N为试卷总难度）。

3）区分度比例约束公式为：f3= （i为题型数，j为题目数，q为题目区分度，Q为试卷总区分度）。

4）时间约束公式为：f4= （i为题型数，j为题目数，s为题目参考时间，S为试卷总时间）。

最后得出目标函数为：f=w1f1+w2f2+w3f3+w4f4（1≤wi≤10）。

2.3 算法实现

遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。本系统的选择算子运用的是基于排序的选择方法，将群体中的个体按照计算出的适应度排序，并按序分配各自的选择概率[4]。

算法中交叉算子采用单点交叉算子[4]。所谓交叉运算，是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。单点交叉的实现方法是在基因串中随机设定一个交叉点并互换该点的前后两个个体的部分结构，生成两个新串。随机交叉占用时间比较多，当题库较大时，组卷时间可能偏长。

算法的变异算子采用的是基本位变异算子。所谓变异运算，是指依据变异概率 Pm 将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索[5]。基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。本算法中设定Pm为0.1。

3 系统实现

3.1 模块划分

根据课题研究分析后，对网络考试系统的模块划分如图2。

3.2 功能概述

学生访问考试平台，需要通过登录界面，学生进入考试平台后默认的是浏览历史考试记录，查询历史考试的答题及成绩信息。

教师以教师身份登录考试平台，系统自动切换到考试评分模块，教师可以根据需要设置题型题库，对题库进行添加、修改、删除等管理操作,也可以通过考试系统中的“试题组卷”功能进行批量组卷。组卷前需要对试卷名称、考试时间、试卷份数、题目数、分数、难易度及区分度等试卷参数进行设置，设置完成后点“开始组卷”按钮系统会自动生成考试试卷并保存在数据库中。测试后续，教师能对试卷做后期管理，主要有成绩查询、试卷存档、浏览已存档试卷三个功能模块。

4 总结

在线考试系统的实质是利用先进的现代计算机技术，用计算机组卷来代替人工活动，解决在传统的人工考试环境下不能解决的问题，达到提高工作质量和工作效率的目的[5]。

在线考试系统具有降低考试成本，解决繁重的考务工作的优点。利用计算机建立题库并对其进行管理，是实现教考规范化、标准化的一个重要措施。一方面计算机参与管理题库、组卷节省了教师的宝贵时间，另一方面使考试更加标准化，更加客观真实全面地反映教学成果，从而促进教学质量的提高[5]。

参考文献：

[1] 吕盈.基于B_S架构的远程考试系统的设计与实现[D].大连:大连理工大学硕士论文,2006.

[2] 刘丰.在线考试系统的设计与研究[D].北京:北京师范大学,2000.

[3] 邱少明.基于ASP的网上考试系统的设计与实现[D].大连:大连理工大学硕士论文,2006.

篇9

中图分类号：G650 文献标识码：A 文章编号：1003-2851（2012）-09-0180-01

遗传算法[（genetic algorithm，GA）是一种自适应大规模并行搜索优化算法，较以往传统的搜索算法具有使用方便、鲁棒性强、便于并行处理等特点，因而广泛应用于解决搜索和优化的问题。但由于遗传算法不能很好地维持解种群中个体的多样性，易趋于“早熟”收敛而陷入局部最优解。因此，遗传算法不能保证一定能找到问题的全局最优解，目前公交公司各车队的排班主要依靠工作人员的经验手工进行，虽然它具有一定的实用性，但它存在着明显的不足，很难保证排班的结果在运营效率等方面是最优或者接近最优的。为满足实际应用需求，采用智能化算法来求解车辆调度优化问题，在有限的算法步骤内，找出所有满足约束条件的排班方案中的最优方案或接近最优的方案。

一、遗传算法

1.遗传算法简介

遗传算法（Genetic Algorithms，GA）是一种基于自然选择和基因遗传学原理的自适应全局优化概率搜索方法。它的创立有两个研究目的：一是抽象和严谨地解释自然界的适应过程；二是为了将自然生物系统的重要机理运用到工程系统中。GA从许多点开始并行操作，在解空间进行高效启发式搜索，因而可以有效地防止搜索过程收敛于局部最优解；遗传算法在计算机上模拟生物的进化过程和基因的操作，通过目标函数来计算适配值，并不需要对象的特定知识，它具有全局寻优的能力，能解决高度复杂的问题，被广泛应用于自动控制、图形处理、电力调度等方面。

2.建立调度的数学模型

调度系统所采用的数学模型对运行环境做了简化：车的速度恒定，保持匀速行驶，无特殊事件发生；以分钟作为最小的时间单位，这对安排时刻表是合理的；假设客流模型能反映该段线路上的日常客流量（我们假设到站乘客服从均匀分布，在不同时段有不同的分布密度）。

首班车发车时刻为早上6点整，末班车发车时刻为22点整，所有运营车都在整分钟时刻发车，一天之内的总班次为m，总时间为16小时，即960分钟。用xm表示第m辆运营车发车时刻距首发时刻的时间，以分钟为单位。决策变量为X=[x1，x2，…xn]；染色体X是一个完整的发车时刻表，其中的每个基因为一个车辆的发车时刻。

免疫算法效仿生物免疫系统，把外来侵犯的抗原和免疫产生的抗体分别与实际求解问题的目标函数以及问题的解相对应，生成的抗体能有效地排除抗原，也就相当于求得了问题的最优解；对与抗原亲和力高的抗体进行记忆能促进快速求解。

二、IGA应用于公交动态调度

现仍采用上面建立的数学模型，初始规模N仍为200且不随进化代数而发生变化，便于IGA和GA比较。现利用IGA来进行优化的步骤为：

1.在解空间内随机生成初始群体，并计算其适应度，确定最优个体x0best，并给出的取值？滓0，A取为1，？滓0i取为3，？滓？孜取为0。

2.根据式（4.7）进行进化操作，在解空间内生成子代群体，规模为N。

3.计算子代群体的适应度，确定最优个体xt+1best，若f（xt+1best）>f（xtbest），则选定最优个体为xt+1best，否则最优个体为xtbest。

4.重复执行步骤2和3，直至达到终止条件，这里T取为100，选择最后一代的最优个体作为寻优的结果。

本文在遗传算法的基础上采用了一种较新的混合遗传算法——免疫遗传算法对公交静态调度进行了研究，并对二者的应用结果进行了仿真和比较，结果表明IGA有效的克服了简单GA的不足之处，并提高了寻优过程当中目标函数的收敛速度，并得到了合理的发车时刻表，可以提高公交企业的服务水平，对改善城市交通问题和节约市民出行时间有相当的实际意义。

参考文献

篇10

中图分类号：V2 文献标识码：A

Abstract：In order to overcome the modeling errors existing in the controller design of flight control system and the influence of interference during the flight， this paper completed the controller of a certain type battle fuel machine control system by adopting LQG/LTR robust control method. And in order to improve the control precision of the fighter and to solve the limitations of selection of the weight matrix Q and R， genetic algorithm was added to find the optimal online . Simulation results show that， compared with PID controller based on genetic algorithm， LQG/LTR control system based on genetic algorithm has good robustness， rapid response， and high control accuracy， which can meet the flight control requirements of the fighter.

Key words：LQG/LTR；robust control；genetic algorithm；PID；Matlab/Simulink

1引言

航空发动机是一个结构极其复杂、工作环境极为恶劣、强非线性的被控对象。在实际工作过程中， 航空发动机特性会随着负荷或飞行条件的变化而发生变化。近年来，航空发动机控制性能改善方面发展了许多新方法，文献[1]针对航空发动机分布式控制系统，提出了基于鲁理论容错控制，针对系统的参数扰动，不确定时延等不确定性问题进行控制调节，取得了良好的控制效果；文献[3]针对发动机的非线性和不确定性，采用径向基神经网络逼近系统的方法，验证了其有效性；文献[4]采用基于遗传算法的PID控制具有良好的寻优特性，在不同飞行条件下获得了较好的控制效果；文献[5]通过遗传算法对LQR权矩阵Q和R进行优化，进而提升控制效果。可见，遗传算法在航空发动机控制过程中，因其具有良好的寻优性，同时克服了单纯形法对参数初值的敏感性的优势，应用比较广泛，且取得了良好的寻优效果。

LQG/LTR（Linear Quadratic Gaussian with Loop Transfer Recovery）方法作为鲁棒控制系统中，研究比较多的方法，这种设计方法具有计算简单，控制器结构简单、鲁棒性能好等优点，在工程应用中价值很高。本文采用LQG/LTR控制方法，利用遗传算法在线寻优，设计了某型战斗机的燃油控制系统的控制器，分别用该方法和基于遗传算法的PID控制方法等对不同马赫数和高度下的飞行情况进行仿真，同时为了验证该算法对系统参数摄动不确定性，也进行了相关仿真。

2基于遗传算法的LQG/LTR控制器的设计

基于遗传算法的LQG/LTR控制方法，包括LQG/LTR控制器设计，同时与遗传算法结合，适应度函数选取跟误差积分以及u2（t）相关，同时增加了惩罚手段，减少阶跃响应超调量。通过遗传算法迭代，对权矩阵Q和R进行优化进而得到最优的状态反馈矩阵，代入simulink仿真模块，进而得到仿真结果。

2.1LQG/LTR控制器的设计

LQG/LTR是近年来鲁棒控制发展的重要理论之一，可应用于单输入-单输出（SISO），也可应用于多输入-多输出（MIMO）系统，它以分离原理为核心。通过设计一个Kalman滤波器和一个最优反馈控制器来完成。

选择合适的参数W，V使图1中的I′处卡尔曼滤波器的回比函数HI′的奇异值曲线形状满足系统的鲁棒性要求；再设计一个LQR调节器，通过调节Q，R直至I处的HI的主增益曲线足够地趋近于卡尔曼滤波器回比函数HI′的主增益曲线。因此，应用LQG/LTR设计方法时，只需要设计好I'处的卡尔曼滤波器的回比函数，然后通过LTR就可以使系统性能得到保证。但是一般情况下，LQR调节器中的Q，R权矩阵的选择是通过专家经验，一步步试验得到，工程计算量大，实际上很难达到最优，论文在这个问题上加入了遗传算法进行在线寻优。

2.3遗传算法多目标寻优

LQG/LTR设计方法中，决定闭环系统性能的回比矩阵奇异值图的形状只能通过对LQR加权矩阵Q和R的不同选择来调整，如何去选择，并没有解析方法，只能定性的去选择矩阵参数，实际上很难达到最优，故调整范围有一定的局限性，直接影响了控制性能和鲁棒稳定性。为克服该局限性，本文提出一种LQG/LTR改进方案。

论文应用遗传算法，将LQG/LTR方法中的LQR调节器权矩阵Q和R作为优化对象，以控制系统的e（t），u（t），ts（阶跃响应上升时间）作为性能指标，组成适应度函数，通过全局搜索能力，对加权矩阵进行优化设计，以提高LQR的设计效率和性能。图2为基于遗传算法的LQG/LTR控制的流程图。

从上述仿真曲线可知：

1）由图4.1可看出，随着种群代数的不断增加，最优个体的适应度函数值不断的减小，也就是说，遗传算法搜索到的适应度函数值也越来越小，更符合我们的控制要求。

2）由图4.2可明显看出，基于遗传算的LQG/LTR控制下的系统阶跃响应时间很快，波形稳定，没有稳态误差，上升时间有明显的优势。同时，四种飞行条件下的曲线对比，阶跃响应并没有随着马赫数和高度的增加而呈现明显的趋势变化，但在马赫数为0，高度为0 km的情况下，控制效果更好，响应时间更快。

3）由图4.3至图4.6可看出，曲线①控制效果一般，响应时间较其他两种控制方法较长，只有在图3情况下，响应时间最快，但是却有明显的超调现象；曲线②控制效果较好，响应时间较长，但是一直没有超调不明显；曲线③控制效果最好，响应时间最短，超调也不明显，没有稳态误差。

4）图4.8和图4.9可看出，即使是在参数不确定的情况下，基于遗传算法的LQG/LTR控制仍然能够保持很好的控制效果，具有很好的鲁棒性和抗干扰能力。

5）根据不同马赫数和高度下四个系统的控制效果参数对比，以及对其参数不确定性和外部干扰仿真，基于遗传算法的LQG/LTR控制均具有比较良好的控制效果，具有很好的鲁棒性和抗干扰能力。

5结论

本文通过LQG/LTR方法，设计了模型战斗机的燃油系统的控制器，解决了LQG/LTR在设计LQR调节器时，权矩阵Q和R的选取困难的问题，提出了基于遗传算法的LQG/LTR控制算法，并与经典控制理论基于遗传算法的PID控制算法相比较，进行了不同飞行条件下的控制试验，同时针对航空发动机建模的参数不确定性以及外部干扰试验，经试验结果证明，基于遗传算法的LQG/LTR控制不仅鲁棒性好，控制精度高，而且阶跃响应灵敏，反应快速，同时具有很好的抗干扰能力，更能满足战斗机快速反应的要求，具有很好的现实意义和应用前景。

参考文献

[1]王磊，谢寿生，彭靖波，等. 航空发动机分布式控制系统不确定性鲁棒H∞容错控制[J].推进技术，2013， 34（6）：836-842.

[2]傅强，樊丁. 模糊自适应整定PID在航空发动机中的应用研究[J]. 计算机仿真，2006， 23（3）：54-57.

[3]傅强，智能PID控制器在航空发动机控制中的应用研究[D].2005

[4]彭靖波，谢寿生，胡金海. 基于遗传算法的某型涡扇发动机数字PID控制器设计[J]. 燃气涡轮试验与研究，2008 ，21（1）：47-50.

[5]郭一峰，徐赵东，涂青，等. 基于遗传算法的LQR算法中权矩阵的优化分析[J].振动与冲击，2010，29（11）.

[6]MACIE JOWSKI J M. Multivariable feedback design [M].British：AddisomWesley Publishers Ltd，1989.

[7]樊思齐.航空发动机控制[M].西北工业大学出版社，2008：422-476.

[8]薛定宇. 控制系统计算机辅助设计――MATLAB语言及应用[M].北京：清华大学出版社，2011.

[9]黄辉先，李燕，庄选，等.基于LMI的滑模控制在航空发动机中的应用[J].计算机工程与科学，2014，36（6）：1198-1203.

[10]苗卓广，谢寿生，吴勇，等. 基于改进粒子群算法的航空发动机状态变量建模[J]. 推进技术，2012，33（1）：73-77.

[11]李述清，詹济民，李明，等. 鲁棒PID设计在涡扇发动机中的应用[J]. 计算机仿真，2011，28（3）：106-109.

[12]孙健国. 面向 21 世纪航空动力控制展望[J]. 航空动力学报， 2001， 16（2）： 97-102.

[13]郭虹. 航空发动机控制系统的发展趋势[J]. 沈阳航空工业学院学报， 1997， 14（1）：70-74.

篇11

中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)28-0175-03

The Making Class Schedule System of High School Based on Genetic Algorithms

XIA Xiao-yun1, GAO Wu-jun2

(1.Faculty of Information Engineering,Jiangxi University of Science and Technology, Ganzhou 341000, China;2.Faculty of Science, Jiangxi University of Science and Technology, Ganzhou 341000, China)

Abstract: As the ongoing development in the higher education institutions, the class arrangement model in the management system is also becoming more and more complicated. Course Scheduling is a typical portfolio optimization and uncertainty of scheduling problems, but also a complete problem. Based on the actual situation in high school. In addition, on the basis of GA basic theory, studies how to utilize GA to solve the conflict problem that aroused in schedule arranging system and improve schedule arrangement. We quoted a hash table and time granules, and amend the traditional genetic algorithm chromosome coding models, enhance the flexibility of the model. The practice has proved that GA can simplify the program complexity and shorten the time in generating new perfect schedule. And the curriculum schedule induced by the time code meet the satisfaction of students and teaching staff exactly.

Key words: making class schedule; genetic algorithms; hash map; time granules; fitness function

1 引言

随着高校规模的扩大，学生人数也逐渐增加，高效教务部门排课问题也变得越来越复杂。高校排课问题是在给定教师资源、教室资源、学生人数和开课计划的前提下，如何合理安排课表的问题。排课问题是一个NP难问题[1]。对于较为单一的排课问题来说，可以采取启发式搜索算法找到最优解，而对于复杂的排课问题，该算法很难找到合理和满意的解。遗传算法[2]作为一种有效的全局搜索方法，具有良好的并行性，通过对可行解进行选择、交叉、变异等遗传算子的作用使种群不断进化，从而得到全局最优解或近似最优解。基于遗传算法的鲁棒性，适用范围广，有组织性、自适应和学习性、并行性等许多有点，其应用范围也较为广泛。本论文引入哈希表和时间粒度对编码模式进行修正，并充分利用遗传算法特点，给出了排课问题的有效求解方法，对高校教务管理排课研究具有重要的意义。

2 排课问题中的约束条件及优化目标

在实际排课过程中，以某一等长的时间段为课表的时间安排单位，称之为时间单元[3]。一个可行的课表安排应满足以下约束条件：课表以一个星期为一周期，一个星期的课表就是一个学期的课表；课表应满足班级、教师、教室上课不冲突；教室的座位应该满足上课班级学生的需要；其他一些特殊要求。

高校排课问题实际上是时间表安排的问题[4]。在实际排课过程中，需要考虑到教师、学生、班级、教室、教室的大小、实验设备等方面的问题。这些条件可以根据重要性将其分为硬件约束和软件约束。为了更好的解决问题，我们假设硬件约束为：

某些课程需要安排在特定的教室。

同一时间，同一个教师，同一个学生，同一个教室不允许同时上一门以上课程。

教室必须有足够的座位容纳学生。

对于需要试验设备的课程，教室需要有相应的配套设备。比如计算机课需要电脑。

硬件约束条件是在排课过程中必须满足而无法变更的约束条件。

软件约束为：

安排教师喜欢的特定时间上课。

安排教师喜欢的特定教室上课。

在相应的时间或教师给学生或老师安排特定的课程。

软件约束条件是在排课过程中可以满足但又可以不完全满足的约束条件。

排课问题[5-7]的关键就是为了解决课程安排对时间和空间资源的有效利用并避免相互冲突。排课的优化目标就是使得各类冲突为零，并且尽可能满足教师、学生的要求，达到较好的教学效果 。

3 用遗传算法解决排课问题

3.1 排课问题中的对象描述

1）教师

■

2）学生组（大班）

■

3）教室

■

4）课程

■

5）教学班

■

3.2 染色体编码及适应度函数

为了更灵活的进行染色体编码，我们假定每周上课时间为周一至周五共五天，而每天从上午9点至晚上9点共十二个小时。规定一小时为一时间片段。我们可以定义一个大小为12*5*教室数量的向量，并使用哈希表存放上课的班级、时间及教室。

遗传算法的进化过程是以每个个体的适应度值为依据来选取下一代种群的。适应度函数设定的好坏直接影响到遗传算法的收敛速度和能否找到最优解。本文中，我们仅考虑硬件约束方面的因素，在本研究中,适应度函数的设计思想是由于课表问题的优化目标有多个，同时约束也有多个，因此采用多目标化和适应度函数相结合的个体适应度评价函数[8]。

每个教学班级有0――5的得分；

如果教学班级使用矛教室，就增加分值；

如果上课教室需要电脑并且安排上课的教室里有电脑，或者上课教室不需要电脑，就增加分值；

如果安排上课的教室没有足够的座位，就增加分值；

如果教师在上课时间没有其它的课程，我们再一次增加分值；

如果学生在上课时间没有其它的课程，我们就增加分值；

如果教学班级在任一时间间隔点破坏了上述规则，不再增加分值。

因此，我们可以定义适应度的计算公式如下：

■

其中， schedule_score代表所有教学班级总得分数， Maximum_score=教学班级数*5，适应度值为0~1之间的单精度浮点型值。

3.3 交叉和变异操作

交叉操作就是对选取的两个父个体哈希表中数据进行组合，然后根据新的哈希表中的内容创建向量。交叉操作对随机产生的部分父个体哈希图进行分裂。分裂的部分由染色体特征中交叉点的数量决定。最终从父个体交替复制到新的染色体中，形成新的向量。

变异操作是很简单的。它是随机的选取课程然后随机的放入所选择的时间段。课程随机移动的数量由变异的染色体特征决定。

4 结论

本文在对遗传算法研究的基础上设计实现了高校智能排课系统。并对传统的编码模式进行了有效的改进。从排课的结果分析得出所编排的课程表满足排课原则，有效解决冲突问题，课时安排比较均匀。并且这种编码模式具有较高的扩展性，算法的性能有待于进一步提高。

参考文献：

[1] GAREY M R, JOHNSON D S, Compute and Intractability: A guide to the theory of NP completeness[M].San Francisco: W.H.Freeman & Co Ltd,1979.

[2] 周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1999.

[3] SAFAAI D,SIGERU O. Incorporating constrain propagation in genetic algorithm for university timetable planning[J].Engineering Application of Artificial Intelligence,1999,12(3):241-253.

[4] 滕姿,邓辉文,杨久俊.基于遗传算法的排课系统的设计与实现[J].计算机应用,2007,27(12):199-204.

[5] 苏仰娜.基于遗传算法的优化排课系统[J].河南大学学报:自然科学版,2005,35(3):47-50.

篇12

DNA计算中的DNA是重要的遗传物质携带着生物体的所有遗传信息，而遗传算法也是采用生物的遗传信息进行操作的算法，其不同是DNA计算是实验室中进行的而遗传算法是在计算机上编程进行的，将二者混合使用可以使遗传算法在生物的遗传调控机理中更深层次的进行模拟，从而使遗传算法的计算性能得到进一步的提升。由于遗传算法的优越性和良好的性能，将其混合到DNA计算中可以突破其计算的局限性[1]【2】。因此学者开始对该混合的DNA遗传算法进行深入的研究，并取得了一定的成果。本文是在前人研究的基础之上，对遗传算法和DNA计算的混合使用中的算子进行了深入的研究。

1.算法中改进的新型算子的提出

1.1 改进算子中的采用技术

受到DNA分子结构的启发，本文将用DNA的四种碱基对问题的潜在解进行编码，由于DNA的编码方式不能直接被计算机处理，本文将使用二进制表示的数0123对碱基进行编码。在这种编码方式中，令0与鸟嘌呤相对应，1与腺嘌呤对应，2与胸腺嘧啶对应，3与胞嘧啶对应，并且0、1、2、3四个整数将采用二进制的形式进行表示。为了在在编码中实现简易的数学和逻辑操作，将二进制数中的第一位作为区分嘌呤和嘧啶的编码位即0代表嘌呤而1代表嘧啶。同时与互补碱基对对应的代码也呈现互补关系，如碱基对C和G互补组合由0（00）与3（11）构成，而1（01）与2（10）构成的A和T碱基对。这样的互补配对关系，有助于新操作算子的设计。

下面是以上面的编码方式为依据的一个n维的最小化问题：

示长度为的四进制数字串，单个个体的编码长度为，每个变量编码精度由求得。

DNA-GA与遗传算法用二进制进行计算编码时的解码方式相似。其均是以n维十进制向量的形式对个体进行解码，其中：

上公式中的为整数串中的第维第列的数字。因为变量取值范围的不同，所以按比例将变量进行转换，这样就可以得到对应问题的解。

按照这种模式进行编码，就可以引入更多的基因操作到遗传算法中，这样就可以设计算法效率更高更有效的算子。

本文所采用的适应度函数和选择算子是原遗传算法中所采用的，这里就不再赘述。

1.2 改进的新型算子

1.2.1 交叉算子

交叉操作是遗传操作中的重要的生物信息遗传操作，故本文对现有的交叉算子进行了改进，在其中加入了DNA计算中的生物操作技术，形成了新的算子。

（1）移位交叉算子

移位交叉的父体为一个，操作过程如图1所示。移位操作是移换个体中的碱基子序列。设父代的基因为ATCGGTACAT，在父代中随机选取一段子序列，这段子序列所包含的碱基数目和所选碱基的位置也是随机选定的。然后将该段子序列移动到一个新的位置，形成一个新的个体。移位交叉算子的执行概率为。如所选子序列是CGGT将其移动到C的后面形成新的个体。

（2）对换交叉算子

对换交叉操作在两个随机配对的个体之间进行，操作过程如图2所示。首先在优质的群体中随机挑选两个个体作为对换交叉操作的父体。然后在两个父体中分别随机选取一段碱基序列，且命名这个碱基序列为转座子。如图2，在两个父体中随机选择两段个数相同的碱基序列，交换这两个父体所选中的碱基序列，形成新的个体。对换交叉操作的执行概率为。

（3）抽换交叉算子

抽换交叉操作是需要从种群中选取两个个体作为父代。而抽换交叉的目的就是改变个体之间的相似性，因此该操作中所选的父代不是随机的，而是选择两个相似的个体。首先在适应度较好的优秀种群中随机选取一个个体作为父代之一，在随机选取两个个体作为候选父代。然后通过对比候选父体与已知父体的相似度，选择与已知父体更相似的个体作为抽换交叉操作的另一个父体。操作过程如图3所示。抽换交叉算子的执行概率为。

以上三种算子，都可以对单个的DNA序列进行操作，而且各有特点。但是同时执行三种算子将大大增加计算复杂度。本文将对换算子作为基本的交叉算子，移位算子和抽换算子则依据概率执行。

1.2.2 新型变异算子

与以往的同变异算子不同，本文所提出的变异算子是以生物体内的DNA转录成RNA并且通过其配对的反密码子决定蛋白质肽链的合成过程，并且计算在反密码子中各个碱基所出现的概率，然后用低概率替换高概率或者高概率替换低概率的最大最小变异算子，最后形成新的DNA分子。生成一个新的个体。其变异概率为。其过程如图4所示。

2.新提算子的运算步骤

步骤1：在运行算法之前，先对算法中所涉及到的参数进行设置，如种群大的大小、终止阙值、最大进化代数和所改进新型算子的运行概率，普通变异概率等。

步骤2：随机产生size个个体，组成初始种群，并将当前的进化代数设置为1.

步骤3：对个体进行编码串解码，求出各个个体的适应度值。

步骤4：按照适应度值的大小将种群中的个体分为高适应度个体和低适应度个体，令交叉后产生的新个体数为Ncnew，并且从第一代交叉算起，不交叉时Ncnew为0。

步骤5：对种群中进行交叉操作，选择个体为父代个体，按其随机产生的概率数与交叉。

概率、，进行比较，所产生的随机数小于哪个交叉算子的概率就执行哪个交叉算子，最后产生新的个体，并且此时产生的新个体数为+1。

步骤6：对经过交叉操作产生的个体以概率进行变异操作。产生新个体。

步骤7：对经过交叉和变异操作产生的个体用精英保留选择机制进行选择保留，选出适应度大的个体，此时进化代数加1.

步骤8：判断是否终止运行，其判断条件是最大进化代数或者是最大进化代数的阙值。满足就结束，输出结果；否则返回步骤3继续进行。

3.实验测试

为了测试出本文所提出的DNA遗传算法的有效性和搜索性能，从以往的文献中选取了两个具有代表性的无约束的函数作为测试函数。本文使用改进的DNA遗传算法求解从文献中选取的测试函数，它们的局部最优点较多，欺骗性很强，一般的算法不易求解到这两个函数的全局最优点。其中，的最优解为3600，在点（0，0）处取得，而的最优解在点（0，0）处取得。

将这两个函数分别用未经过改进的遗传算法、基于进化策略的遗传算法（EGA）[3]和本文所提出的新的混合DNA遗传算法（DNA-GA）进行求解，并将所得到的结果进行比较，三种算法的种群大小均为60，当最大的进化代数时终止运算。

为了对三种算法都进行比较，在三种不同的算法下每个函数都运行了50次，三种算法的对比结果如表1、表2所示。

综上所述，可以发现，本文所设计的遗传算子对提高DNA遗传算法的搜索性能有了很大的作用。对于和两个函数而言，新型的变异算子在算法求解问题的收敛速度等方面提高比新型的交叉算子作用更大，因此将两种新型的算子配合一起来使用，可以进一步提高DNA遗传算法性能。

4.结束语

本文在前人研究的基础前提之上，对已有的算法进行了改进与创新，通过实验函数的验证本文所设计的遗传算子对提高DNA遗传算法的搜索性能有了很大的作用。

但是本文所改进提出的新型算子还是只用于实验研究，需要进一步的使用实践来证明与改进。

参考文献

[1]余文，李人厚.一种有效地双向进化算法[J].小型微型计算机系统，2003，24（3）：527-530.

[2]陈霄.DNA遗传算法及其应用研究[D].浙江科技大学博士论文，2010.

[3]王四春.GP算法中适应度函数的光滑拟合与调整参数方法研究[J].自动化学报，2006（3）：23-30.