前言：中文期刊网精心挑选了遗传算法论文范文供你参考和学习，希望我们的参考范文能激发你的文章创作灵感，欢迎阅读。
遗传算法论文范文1
关键词遗传算法；TSP；交叉算子
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
[2]IMOliverDJSmithandJRCHolland，Astudyofpermutationcrossoveroperatorsonthetravelingsalesman[C]//ProblemofthesecondInternationalConferenceonGeneticAlgorithmsandTheirApplication，Erlbaum1897：224-230
遗传算法论文范文2
关键词：自动排课；遗传算法；求解与优化
中图分类号：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）可行课程表的产生。
这样，我们就有了一个课程表的数据库表。因此，可以打印其中某一班级的课程表或全校的课程表了。
结论
本文采用遗传算法来对课表编排问题进行求解，是求解这种难解的组合优化问题方法中较明智的选择，目的是在遗传算法基础上提出一个课表方案的随机生成和优化方案，能够较大程度地实现课表编排和多个目标的最优化。本文算法对我们这类院系较多、教师工作量大、学科变化较大、不确定性较多的学校能有所借鉴。
参考文献
[1]安勐.遗传算法在排课问题求解中的应用[J].铜仁学院学报，2009，11（2）：135-139.
遗传算法论文范文3
关键词：在线测试；组卷策略；遗传算法
中图分类号：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.
[4] 夏爱月.基于遗传算法的自动组卷系统研究与实现[J].电脑编程技巧与维护,2008(10).
遗传算法论文范文4
关键词：排课；遗传算法；哈希图；时间粒度；适应度函数
中图分类号：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.
[6] 杨宇.高校排课系统理论研究与开发遗传算法在课表问题中的应用[M].北京:北京理工大学出版社,2003:35-67.
遗传算法论文范文5
关键字：遗传算法；机器学习；人工生命；人工神经网络；神经网络拓扑结构
中图分类号：TP183文献标识码：A文章编号：1009-3044(2008)27-2040-03
The Application of Genetic Algorithm to the Artificial Intelligence
WANG Hui
(Xinjiang Petroleum Institute, Urumqi 830000, China)
Abstract: In this paper the author introduces the basic conception of genetic algorithm(GA for short),the feature of GA and the calculation steps. We can also get a general idea of the development in the machine learning, Parallel Processing, artificial Life, and the integration of evolutionary rules and strategies. At last, the application of GA to artificial neural networks is discussed, especially the application of GA to the study of neural networks weight and the neural network topology.
Key words: genetic algorithm; machine learning; artificial life;artificial neural networks; neural network topology
1 遗传算法简介
遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，与传统数学模型截然不同，它为那些难以找到传统数学模型的难题找出了一个解决方法。遗传算法借鉴了生物科学中达尔文的物竞天择、适者生存的进化准则，1975年，Michigan大学Holland教授根据这一规律首次提出了遗传算法（genetic algorithm，简称GA），其基本思想是力求充分模仿这一自然寻优过程的随机性、鲁棒性和全局性。这是一种新型的全局优化搜索算法，因为其直接对结构对象进行操作，不存在求导和函数连续性的限定等数学问题，鲁棒性强、随机性、全局性以及适于并行处理，已广泛应用于神经网络、计算机科学、优化调度、运输问题、组合优化、机器学习、信号处理、自适应控制和人工生命等领域，并且遗传算法在实际应用中也取得了巨大成功。
2 基本遗传算法
遗传算法的工作过程本质上就是模拟生物的进化过程。首先，要规定一种编码方法，使得你的问题的任何一个潜在可行解都能表示成为一个“数字”染色体。然后，创建一个由随机的染色体组成的初始群体（每个染色体代表了一个不同的候选解），并在一段时期中，以培育适应性最强的个体的办法，让它们进化，在此期间，染色体的某些位置上要加入少量的变异。
遗传算法是一种基于空间搜索的算法，它的求解可以看成是最优化过程。遗传算法的最大优点就是，你不需要知道怎么去解决一个问题，你需要知道的仅仅是用什么样的方式对可行解进行编码，使得它能被遗传算法机制所利用。遗传算法并不能保证所得到的解是最优解，但可以将误差控制在容许的范围内。遗传算法具有以下特点：
1） 遗传算法是对参数集合的编码而非针对参数本身进行优化；
2） 遗传算法是从问题解的编码组开始而非从单个解开始搜索；
3） 遗传算法利用目标函数的适应度这一信息而非利用导数或其他辅助信息来指导搜索；
4） 遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。
那么下面对基本遗传算法给出一个求解步骤：
1） 定义一个目标函数；
2） 将可行解群体在一定的约束条件下初始化，每一个可行解用一个向量x来编码，称为一条染色体，向量的分量代表基因，它对应可行解的某一决策变量；
3） 计算群体中每条染色体xi(i＝1，2，…，n)所对应的目标函数值，并以此计算适应值Fi，按Fi的大小来评价该可行解的好坏；
4） 以优胜劣汰的机制，将适应值差的染色体淘汰掉，对幸存的染色体根据其适应值的好坏，按概率随机选择，进行繁殖，形成新的群体；
5） 通过杂交和变异的操作，产生子代。杂交是随机选择两条染色体（双亲），将某一点或多点的基因互换而产生两个新个体，变异是基因中的某一点或多点发生突变；
6） 对子代群体重复步骤(3)～(5)的操作，进行新一轮遗传进化过程，直到迭代收敛（适应值趋稳定）即找到了最优解或准最优解。
3 遗传算法的发展动向
GA在应用方面的取得了较丰硕的成果，其主要应用领域在于函数优化，机器人学，设计，组合优化，信号处理，人工生命等，此外遗传算法还有几个引人注目的新动向。
3.1 基于GA的机器学习
这一新的研究方向把GA从历史离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法，这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望，GA作为一种搜索算法从一开始就与机器学习有密切联系。分类器系统是第一个基于GA的机器学习系统。基于GA的概念学习是近几年机器学习领域的一个较为引人注目的研究方向。还有一些嵌入领域知识的基于GA的机器学习的研究。
3.2 并行处理的GA
并行处理的GA的研究不仅是GA本身的发展，而且对于新一代智能计算机体现结构的研究都是十分重要的，GA在操作上具有高度的并行性，许多研究人员都正在搜索在并行机上高效执行GA的策略。近几年也发表了不少这方面的论文，研究表明，只要通过保持多个群体和恰当地控制群体间的相互作用来模拟并执行过程，即使不使用并行计算机，我们也能提高算法的执行效率。在并行GA的研究方面，一些并行GA可以分为两类：一是粗粒度并行GA，它主要开发群体间的并行性，如Coboon分析了在并行计算机上解图划分问题的多群体GA的性能；另一类是细粒度并行GA，它主要开始一个群体中的并行性，如Kosak将群体中的每个个体映射到一个连接机的处理单元上，并指出了这种方法对网络图设计问题的有效性。
3.3 GA与人工生命的渗透
人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。人工生命与GA有密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础，虽然人工生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人工生命的研究提供了一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。
3.4 GA与进化规则及进化策略的结合
GA，进化规则及进化策略是进化计算的三个主要分支，这三种典型的进化算法都以自然界中生物的进化过程为自适应全局优化搜索过程的借鉴对象，所以三者之间有较大的相似性，但三种算法又是从不完全相同的角度出发来模拟生物的进化过程，分别是依据不同的生物进化背景，不同的生物进化机制而开发出来的，所以又有差异。但在进化计算领域内更重要的工作是生物的进化机制，构造性能更加优良且适应性更加广泛的进化算法。
4 基于遗传算法优化神经网络的应用研究
神经网络和遗传算法目标相近而方法各异。因此，将这两种方法相互结合，必能达到取长补短的作用。近年来,在这方面已经取得了不少研究成果，形成了以遗传算法与神经网络相结合的进化神经网络(ENN)。遗传算法在神经网络中的应用主要是用遗传算法学习神经网络的权重和学习神经网络的拓扑结构两个部分。
4.1 遗传算法学习神经网络的权重
而最主要的是学习神经网络的权重，也就是用遗传算法来取代一些传统的学习算法 。目前广泛研究的前馈网络中采用的是Rumel hart等人推广的误差反向传播（BP）算法，BP算法具有简单和可塑的优点，但是BP算法是基于梯度的方法，这种方法的收敛速度慢，且常受局部极小点的困扰，采用遗传算法则可把神经网络的结构优化和权值学习合并起来一起求解，克服了BP算法的缺陷，是神经网络权值学习的有效方法。
遗传算法学习神经网络权值的算法步骤如下：
1） 随机产生一组分布，采用某种编码方案对该组中的每个权值（或阈值）进行编码，进而构造出一个个码链（每个码链代表网络的一种权值分布），在网络结构和学习算法已定的前提下，该码链就对应一个权值和阈值取特定值的一个神经网络；
2） 对所产生的神经网络计算它的误差函数，从而确定其适应度函数值，误差与适应度成反比关系；
3） 选择若干适应度函数值最大的个体，直接遗传给下一代（精英保护策略）；
4） 利用交叉和变异等遗传操作算子对当前一代群体进行处理，产生下一代（新一代）群体；
5） 重复步骤2～4，使初始确定的一组权值分布得到不断的进化，直到训练目标得到满足或者迭代次数达到预设目标为止。
4.2 遗传算法学习神经网络的拓扑结构
神经网络结构包括网络的拓扑结构（连接方式）和接点转移函数两方面。利用遗传算法设计神经网络可根据某些性能评价准则如学习速度，泛化能力或结构复杂程度等搜索结构空间中满足问题要求的最佳结构。利用遗传算法设计神经网络的关键问题之一仍然是如何选取编码方案。
遗传算法学习神经网络结构的算法步骤如下:
1） 随机产生若干个不同结构的神经网络，对每个结构编码，每个码链对应一个网络结构，N个码链构成种群。
2） 利用多种不同的初始连接权值分别对每个网络进行训练。
3） 计算在每个对应码链下神经网络的误差函数，利用误差函数或其他策略（如网络的泛化能力或结构复杂度）确定每个个体的适应度函数。
4） 选择若干适应度函数值最大的个体构成父本。
5） 利用交叉，变异等遗传操作算子对当前一代群体进行处理，产生新一代群体。
6） 重复上述2）-5）步骤，直到群体中的某个个体（对应一个网络结构）能满足要求为止。
5 结束语
遗传算法作为一种新型的全局优化搜索算法，由于其直接对结构对象进行操作，不存在求导和函数连续性的限定，又具有鲁棒性强、随机性、全局性以及适于并行处理的优点，在人工神经网络的应用上展现了它的独特魅力与优势，但同时，它在理论和应用技术上也存在着许多不足和缺陷，比如相对鲜明的生物基础，其数学基础显得极为薄弱，尤其是缺乏深刻且具有普遍意义的理论分析。随着理论研究的深入，可以肯定，作为一种高效并行的全局搜索方法，遗传算法以其特有的算法特点使其在许多实际问题中的应用会越来越广；同时，广泛的数学方法和强大的计算机模拟工具的出现，必将使遗传算法的研究取得长足的进展。
参考文献：
[1] 蔡自兴. 人工智能及其应用[M]. 3版.北京：清华大学出版社，2003.
[2] 王风琴. 基于遗传算法的神经网络优化[J].燕山大学学报，2001，25（3）：234-239.
[3] 陈国良. 遗传算法及其应用[M].北京：人民邮电出版社，1999.
[4] 陈颖琪. 进化计算与神经网络的结合[J].红外与激光工程，1999，（4）：8-11，35.
[5] Kretnovich v.Qmtana C and Puentes O.Genetnc Algorithms-What Fitness Scaling is Optimal. Ctberm and System 1993.24.
[6] S W Mathfoud.Genetic drift in sharing methods. 0-7803-I899-4/94.1994 IEEE
[7] V Petrochs.S Kazarns. Varying quality function Gengentic algorithms and the cutting problem. 0-7803-I899-4/94.1994 IEEE
[8] 杨旭东，张彤. 遗传算法应用于系统在线识别研究[J].哈尔滨工业大学学报， 2000，32（1）：102-104.
[9] Pham D T，Jin G. Genetic algorithms using gradient-like ren reduction operator. Electronics Letters. 1995 .31.
[10] Nover D，Baskaran S，Scbuster P. Understanding genetic algorithms dynamics using harvesting strategies. Physics D 79, 1994.
[11] Kao T, Hwang S Y. A genetic algorithm with sruptive selection[J]. IEEE Transcations on System, Man. And Cybernetris-Part B: Cybernetics 1996,26.
遗传算法论文范文6
关键词：遗传算法，自动组卷，算子
1．引言
随着因特网技术以及教育网络技术的不断发展，越来越多的学校和机构开始采用网络考试的考核形式，而在网络考试中采用组卷形式的优劣与否将直接影响到试卷的质量与考试的成效。传统的网络考试中，学生只是随机的从已有的几套试卷中抽取一套，这样会导致试卷的维护成本变高，同时试卷的重复率相对较大。当前较为先进的组卷方式，是随机从已有的试题库中按照考试的各项要求，如题型、考核点分布、难度、分值等因素选择相应的题目自动组卷，组卷灵活，试卷的维护相对容易，这种方式已经被广泛地应用到各种网络考试系统当中。自动组卷技术实现的关键是组卷算法的选择与实现，它将直接影响到组卷的质量。本文主要介绍的是使用遗传算法进行自动组卷的思路与具体的实现。
2．常用的自动组卷算法
当前使用较多的自动组卷算法主要有三种。第一种是基于随机抽题的算法，它根据问题空间的一些指标，从试题库中随机地抽取一道试题放入待生成的试卷中，此过程不断重复，直到组卷完毕或无法从题库中抽取满足条件的试题为止。该组卷方法的重复率高，组卷成功率非常低，即使组卷成功，花费时间也较长。第二种是基于回溯试探法的算法，它是将随机抽题算法产生的第一状态类型记录下来，当搜索失败时释放上次记录的状态类型，然后再根据一定的规律变换出一种新的状态类型进行试探。该算法的不足之处在于当试卷总题量较大时，状态类型的变换便成为一个巨大的数字。因此这种方法只适用于状态类型和试卷总题量都较少的题库系统。第三种是基于遗传算法的组卷算法，它可以从群体中选择更满足条件的个体，具有很强的智能性。同时它能根据不同的环境产生不同的后代，具有动态性，自适应性，从而能满足试题库容量、覆盖面不断变化的要求。
3．遗传算法数据模型的建立
自动组卷时会根据组卷的原则对试卷的质量提出很多方面的要求，即试题的控制指标，如每种题型包含的题目数量、每种题型所占分数、每道试题的难度系数等。因此，在组卷之前应该为自动组卷建立模型。其模型如下图所示：
