论文关键词：旅行商问题遗传算法基因库多重搜索策略
TSP(travelingsalesmanproblem)可以简述为:有n个城市1,2,…,n,一旅行商从某一城市出发,环游所有城市后回到原出发地,且各城市只能经过一次,要求找出一条最短路线。TSP的搜索空间是有限的,如果时间不受限制的话,在理论上这种问题终会找到最优解,但对于稍大规模的TSP,时间上的代价往往是无法接受的。这是一个典型的组合最优化问题,已被证明是NP难问题,即很可能不存在确定的算法能在多项式时间内求到问题的解[1]。由于TSP在工程领域有着广泛的应用,如货物运输、加工调度、网络通讯、电气布线、管道铺设等,因而吸引了众多领域的学者对它进行研究。TSP的求解方法种类繁多,主要有贪婪法、穷举法、免疫算法[2]、蚂蚁算法[3]、模拟退火算法、遗传算法等。
遗传算法是一种借鉴生物界自然选择和遗传机制的随机化搜索算法,其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不依赖于梯度信息[4]。遗传算法主要包括选择、交叉和变异3个操作算子,它是一种全局化搜索算法,尤其适用于传统搜索算法难于解决的复杂和非线性问题。遗传算法虽然不能保证在有限的时间内获得最优解,但随机地选择充分多个解验证后,错误的概率会降到可以接受的程度。
用遗传算法求解TSP能得到令人满意的结果,但是其收敛速度较慢,而且种群在交叉算子作用下,会陷入局部解。采用局部启发式搜索算法等,虽然能在很短的时间内计算出小规模城市的高质量解,一旦城市规模稍大就容易陷入局部最优解。因此,为了能够加快遗传算法的收敛速度,又能得到更好的近似最优解,该文采纳了文[5]中杨辉提出的基因库的想法,并结合文[6]中Cheng-FaTsai提出的多重搜索策略思想,使用单亲演化与群体演化相结合的方式来求解TSP问题。该文根据文[7]中最小生成树MST(minimumcostspanningtree)的应用,由MST建立TSP的基因库,保存有希望成为最优解的边,利用基因库提高初始群体的质量进行单亲演化,然后利用改进后的交叉算子和的多重搜索策略进行群体演化。
1单亲演化过程
现有的大多数演化算法在整个演化过程中所涉及的基因,大多来源于个体本身,个体质量的高低决定了算法的全局性能,如果群体中初始个体的适应度都较差,肯定要影响算法的收敛速度,对于规模稍大的TSP尤其明显[8]。该文为了克服上述弱点,首先利用普里姆算法求出TSP中最小生成树,并将各个MST中的每一条边都保存在一个n*(n-1)方阵里面,就构成了一个基因库,在生成初始群体的时候尽量使用基因库中的基因片段,来提高整个初始群体的适应度,从而提高算法的效率。
1.1TSP编码表示
设n个城市编号为1,2,…,n,为一条可行路径,Pk=Vk1Vk2…Vkn为一条可行路径,它是1,2,…,n的一个随机排列,其含意是第k条路径起点城市是Vk1,最后一个城市是Vkn,则第k条环路的总长度可以表示为:
其中,d(Vki,Vkj)表示城市Vki与城市Vkj之间的距离。在算法中环路Pk的总长d(Pk)用来评价个体的好坏[9]。适应度函数取路径长度d(Pk)的倒数,f(Pk)=1/d(Pk)。
1.2构建TSP基因库
对n个编号为1,2,…,n的城市,根据它们的坐标计算各城市之间的欧氏距离d(i,j),i,j=1,2,…,n,得到一个n*n的方阵D={d(i,j)}。然后利用普里姆算法求得该TSP的一棵MST,并将这棵MST中的每一条边e(i,j)对应地存储在一个n*(n-1)的方阵M={e(i,j)},即该文的基因库。由于一个TSP可能有多棵MST,操作可以重复多次,这样生成的基因库中的基因就更多,增强了初始群体的全局性。具体算法如下:
VoidMiniSpanTree—PRIM(MGraphG,VertexTypeu){
Struct{
VertexTypeadjvex;
VRTypelowcost;
}closedge[MAX—VERTEX—NUM];
k=LocateVex(G,u);
for(j=0;j<G.vexnum;++j)
if(j!=k)closedge[j]={u,G.arcs[k][j].adj};
closedge[k].lowcost=0;
for(i=0;i<G.vexnum;++i){
k=minimum(closedge);
printf(closedge[k].adjvex,G.vexs[k]);
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;++j)
if(G.arcs[k][j].adj<closedge[j].lowcost)
closedge[j]={G.vexs[k],G.arcs[k][j].adj};
}
}
1.3单亲演化算法
单亲演化算法是利用遗传算法的优胜劣汰的遗传特性,在单个染色体内以基因重组的方式,使子代在满足TSP问题的限定条件下进行繁衍,然后保留适应度高的染色体种群,达到优化的目的。单亲演化算法的基因重组操作包括基因换位、基因段错位和基因段倒转三种操作来实现。基因换位操作是将亲代的染色体基因进行对换后,形成子代,其换位又分为单基因换位和基因段换位两种方式。基因段错位操作是随机确定基因段,也随机选定错位位置,整段错移。基因段倒转操作则是随机地确定倒转基因段的起止位置,倒转操作是对该段内基因按中垂线作镜面反射,若段内基因数为奇数时,则中位基因不变。单亲演化时可以是单个操作用于单个父代,也可以是几种操作同时采用。为了编程方便,文中采用基因段倒转操作。
2群体演化过程
在单亲演化算法求得的初始群体基础上,再利用多重搜索策略并行地进行群体演化,这样在保证算法的快速收敛的同时也注重了搜索空间的全局性。
2.1交叉算子
该文算子采用一种与顺序交叉OX(ordercrossover)法类似的交叉方法[11],即随机在串中选择一个区域,例如以下两个父串及区域选定为:
P1=(12|3456|789)P2=(98|7654|321)
将P2的区域加到P1的前面或后面,P1的区域加到P2的前面或后面,得
M1=(7654|123456789)
M2=(3456|987654321)
在M1中自区域后依次删除与区域相同的城市码,得到最终的两个子串:
S1=(765412389)S2=(345698721)
同时为了能更好地增强算子的全局搜索能力,对该算子作了如下的改进。子代个体的新边来自:随机生成和群体中其他个体,其选择比例由随机数p和阈值P来决定。如果随机数p小于阈值P,则子代个体的新边来自随机生成,否则就来自群体中的其他个体。
这种改进后的交叉算子在父串相同的情况下仍能产生一定程度的变异效果,这对维持群体的多样化特性有一定的作用。实验结果也证实了这种改进算子对于种群的全局搜索能力有一定的提高,避免搜索陷入局部解。
2.2局部启发式算子
为了增强遗传算法的局部搜索性能,在算法中引入2-Opt局部搜索算子[12]。该算子通过比较两条边并交换路径以提升算法的局部搜索性能,示例见图2。
比较子路径ab+cd和ac+bd,如果ab+cd>ac+bd则交换,否则就不交换。考虑到程序的运行效率,不可能对每对边都做检查,所以选取染色体中的一定数量的边进行比较。2-Opt搜索算子实际上进行的相当于变异操作,同时又不仅仅是简单的变异,而是提高算法的局部搜索性能的变异操作。
2.3选择机制和收敛准则
为了限制种群的规模[13],该文采用了联赛选择法的淘汰规则。联赛选择法就是以各染色体的适应度作为评定标准,从群体中任意选择一定数目的个体,称为联赛规模,其中适应度最高的个体保存到下一代。这个过程反复执行,直到保存到下一代的个体数达到预先设定的数目为止。这样做可能导致种群过早收敛,因此在收敛准则上要采取苛刻的要求来保证搜索的全局性。
遗传算法求TSP问题如果不设定终止条件,其演化过程将会无限制地进行下去。终止条件也称收敛准则,因为多数最优化问题事先并不了解最优的目标函数值,故无法判断寻优的精度。该文采用如下两条收敛准则:在连续K1代不再出现更优的染色体;优化解的染色体占种群的个数达K2的比例以上。当两准则均满足时,则终止运算,输出优化结果和对应的目标函数值。由数值实验表明,添加第2条准则之后,全局最优解的出现频率将大为提高。
2.4基于多重搜索策略的群体演化算法
由于基因库的引入,可能降低初始种群的多样性,为避免算法陷入局部最优解,因此在群体演化中采取多重搜索策略。由Cheng-FaTsai提出的多重搜索策略[6],就是把染色体集中的染色体分成保守型和探索型两种不同类型的集合,然后针对不同类型的染色体集合根据不同的交叉、变异概率分别进行交叉变异操作,对保守型染色体集合就采用比较低的交叉变异概率,而对探索型染色体集合就采用比较高的交叉变异概率。这种策略对保守型染色体集合的操作最大限度地保留了父代的优秀基因片段,另一方面对探索型染色体集合的操作又尽可能地提高了算法的全局搜索能力。为了提高算法的收敛速度,初始染色体集合该文采用了前面单亲演化的结果中的染色体集合,交叉算子则利用的是前面介绍的改进后的算子,改进后的多重搜索策略见下。
3实验结果与分析
该文的GB—MGA算法由C#编程实现,所有的结果都是在P42.0G微机上完成,并进行通用的TSP库实验,选用了具有一定代表性的TSP实例,并把该算法和其他算法做了一个对比。为了减少计算量,程序中的数据经过四舍五入整数化处理,与实数解有一定的偏差,下面给出图Kroa100的示例。
为了证明该文提出的GB—MGA算法的有效性,将该文算法与典型的遗传算法GA、单亲遗传算法PGA以及文[5]中杨辉提出的Ge—GA(genepoolgeneticalgorithm)算法和文[12]中提出的MMGA(modifiedmultiple-searchinggeneticalgorithm)算法都进行了一个对比。
实验结果证明,该文算法的求解质量要优于GA、PGA、MMGA算法,而求解速度方面则优于Ge—GA算法,特别是对于大规模城市的TSP问题求解效果尤其明显,具有快速收敛的特性。Ge—GA算法对于中等城市规模的TSP实例求解,其运算时间就大幅度增加,如果把该算法用于求解大规模和超大规模TSP问题,那么时间上的代价就让人无法忍受。而该文的GB—MGA算法在单亲遗传演化中就使用了基因库中的优质基因,使得单个个体的进化速度大大提高,从而为进一步的演化提供了条件,群体演化过程的选择机制和收敛准则的恰当选取使得算法在注重了求解质量的同时兼顾了算法的效率。
1引言
计算机辅助考试系统的自动组卷的效率与质量完全取决于抽题算法的设计。如何设计一个算法从题库中既快又好的抽出一组最佳解或是抽出一组非常接近最佳解的实体，涉及到一个全局寻优和收敛速度快慢的的问题，很多学者对其进行了研究。遗传算法以其自适应寻优及良好的智能搜索技术，受到了广泛的运用。PottsJC等人基于变异和人工选择的遗传算法对最优群体规模进行了论述；HamiltonMA等结合遗传算法把其运用到神经网络中，并取得了良好的效果[4]；也有众多的学者对保留最佳状态的遗传算法的收敛速度做了讨论。通过理论推导和事实运用，发现遗传算法在寻优和收敛性方面都是非常有效的。
本文结合遗传算法的原理和思想，对考试自动出题组卷的问题进行了研究，找到了一种获得与考试试题控制指标符合的试题模型的解决方法。
2问题描述
自动组卷是考试系统自动化或半自动化操作的核心目标之一,而如何保证生成的试卷能最大程度的满足用户的不同需要,并具有随机性、科学性、合理性,这是实现中的一个难点。尤其在交互式环境下用户对于组卷速度要求较高，而一个理论上较完美的算法可能会以牺牲时间作为代价，往往不能达到预期的效果。因此，选择一个高效、科学、合理的算法是自动组卷的关键。
以往的具有自动组卷功能的考试系统大多采用随机选取法和回溯试探法。随机选取法根据状态空间的控制指标，由计算机随机的抽取一道试题放入试题库，此过程不断重复，直到组卷完毕，或已无法从题库中抽取满足控制指标的试题为止。该方法结构简单，对于单道题的抽取运行速度较快，但是对于整个组卷过程来说组卷成功率低，即使组卷成功，花费时间也令人难以忍受。尤其是当题库中各状态类型平均出题量较低时，组卷往往以失败而告终。
回溯试探法这是将随机选取法产生的每一状态类型纪录下来，当搜索失败时释放上次纪录的状态类型，然后再依据一定的规律（正是这种规律破坏了选取试题的随机性）变换一种新的状态类型进行试探，通过不断的回溯试探直到试卷生成完毕或退回出发点为止，这种有条件的深度优先算法，对于状态类型和出题量都较少的题库系统而言，组卷成功率较好，但是在实际到一个应用时发现这种算法对内存的占用量很大，程序结构相对比较复杂，而且选取试题缺乏随机性，组卷时间长，后两点是用户无法接受的，因此它也不是一种很好的用来自动组卷的算法。
分析上述两种算法的优缺点，不难发现，在限制条件状态空间的控制下，随机选取法有时能够抽取出一组令用户满意的试题。只不过由于它随机选取试题的范围太大，无法确定目前条件下哪些区域能够抽取合适的试题，反而可能在那些已经证明是无法抽取合适试题的区域内反复选题，进行大量的无效操作进入死循环，最终导致组卷失败。回溯试探法组卷成功率高，但它是以牺牲大量的时间为代价的，对于现今越来越流行的考生网上随机即时调题的考试过程来说，它已不符合要求。因此,必须结合以上两种方法寻找一种新的改进算法，这种算法要具有全局寻优和收敛速度快的特点。遗传算法（GeneticAlgorithms）以其具有自适应全局寻优和智能搜索技术，并且收敛性好的特性能很好的满足自动考试组卷的要求。
3遗传算法描述
遗传算法是一种并行的、能够有效优化的算法，以Morgan的基因理论及Eldridge与Gould间断平衡理论为依据，同时融合了Mayr的边缘物种形成理论和Bertalanffv一般系统理论的一些思想，模拟达尔文的自然界遗传学：继承（基因遗传）、进化（基因突变）优胜劣汰（优的基因大量被遗传复制，劣的基因较少被遗传复制）。其实质就是一种把自然界有机体的优胜劣汰的自然选择、适者生存的进化机制与同一群体中个体与个体间的随机信息交换机制相结合的搜索算法。运用遗传算法求解问题首先需将所要求解的问题表示成二进制编码，然后根据环境进行基本的操作：selection，crossover，mutation……这样进行不断的所谓“生存选择”，最后收敛到一个最适应环境条件的个体上，得到问题的最优解。[6,7]
4遗传算法应用
一般来说，用户在自动组卷时会对试卷的质量提出多方面的要求，如总题量、平均难度、题型比例、章节比例、重点章节比例、知识点的交叉与综合等，自动组卷就应最大程度的满足用户的要求。因此，在组卷之前，我们首先为自动组卷过程建立控制指标相应状态空间D，
D=[]
D的每一行由某一试题的控制指标组成，如题号、题型、章节、难度等，并且这些属性指标都进行编码表示成二进制形式，而每一列是题库中的某一指标的全部取值。在具体出题时，考方可能不会用到所有的指标，所以D包含的个体d_target可以表示为d_request和d_void，d_request表示考方要求的控制指标，d_void表示考方不要求的控制指标。即
d_target：：=<d_request>：<d_void>
<d_request>：：={0，1}m
<d_void>：：={0，1}n
试题库[STK]中的每一道试题在建库时都输入了相应的属性指标。试题模型的产生形式是：
if<data>then
<model>
<data>：：={0，1，#}m
#表示0和1之间的任意一位。
考试自动出题的遗传算法如下：
(1)根据考方的出题要求，规划状态空间库D中的数据，保留d_request部分，而不要d_void部分，对其剩余部分进行编码D[1]，D[2]，……D[i]。
(2)初始化试题库[STK]。随机从题库中抽出一组试题，并进行编号STK[1],STK[2]……STK[j],确定合适的交换概率Pc和变异概率Pm；并定义其适应值flexibility[k](k=1,2……j)
flexibility[k]<-0(k=1,2……j)
(3)从试题库[STK]中取出STK[m](0≤m≤j)与状态空间库[D]中的指标D[n](0≤n≤i)进行匹配。如果STK[m]与D[n]完全匹配，则
flexibility[k]<-flexibility[k]+1
如果不匹配，则有
flexibility[k]<-flexibility[k]+0
(4)进行淘汰选择，保留具有高适应度的试题。即把flexibility[k]为0的STK[m]去掉，这样就生成了一个新的试题模型STK[h]。
(5)重复过程2生成新的试题模型STK[p]。按一定的交换概率Pc从[STK]中随机选取模型STK[h]和STK[p]，交换彼此位串中对应的值，产生新的试题模型STK[h]、STK[p]，如
交换前STK[h]=1101011
STK[p]=0011110
交换前STK[h]=1111011
STK[p]=1111110
(6)按一定的变异概率从题库[STK]中随机选出一试题模型STK[h]进行基因突变，产生一个新的试题模型。
(7)在完成以上选择、交叉、变异步骤后，产生一个考试试题模型，按照事先确定的误差精度对其进行收敛性的判别，当其适应度高时，试题组卷成功，转向步骤8，如果其适应度低，则转向步骤3继续执行。
(8)输出相应的考试试题，组卷结束。
以上用遗传算法抽题时，交换概率Pc和变异概率Pm的确定很重要。Pc
太小使选题工作进展缓慢，太大则会破坏适应值高的试题模型。通常规定其为0.4。同样，Pm太小就不能产生新的试题模型，太大又会产生过多的试题模型。它宜规定为0.1。
在自动选题时，选题的方式可采用父辈挑选和生存选择两种。父辈挑选就是采用不返回随机抽样，它使每个题目都有被选中的可能；生存选择采用允许父辈和子代进行竞争，并让其中的优良者进入下一轮竞争环境的二分之一择优选择。两种选择方式共同作用于选题保证了选题的顺利完成。在选题的过程中，哪一道题目被选中是一个非均匀随机事件，其概率依赖于上一次选题的过程。
5结束语
本文利用遗传算法的全局寻优和收敛速度快的特点，结合随机选取法和回溯试探法的优点，设计了一种用于自动组卷的好的算法，使自动组卷的成功率和速度都得到了明显的提高。要使自动出题的误差精度和收敛速度进一步得到改进，还需要做出更深的研究。
参考文献
[1]J．H．Holland，Adaptationinnaturalandartificialsystems[M]，Annarbor:UniversityofMichigenpress,1975.
[2]HamiltonMA.JavaandtheShifttoNet-centricComputing.IEEEComputer,29(8),1996.
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
中图分类号:TP18文献标识码:A文章编号:1009-3044(2009)33-9615-02
Discuss the Method of Classification with Genetic Algorithm
WANG Xin-Xin
(Software College, MinJiang University, FuZhou 350011, China)
Abstract: In the classifier system, applied genetic algorithm(GA) to optimized the classifier system which is use a single classify method or multiple classify methods. For the first classifier system, GA make the better precision; and for the other one, GA can make the classifier system to be more precise and apprehensive.
Key words: genetic algorithm(GA); classifier system; classify optimization; ensemble learning
分类问题是集成学习的基本研究问题,即对一个分类器输入一个实例的特征集,然后对这些特征进行判断,对这个样本进行归类并输出。在医疗诊断、语音识别、数据挖掘、人像识别等领域都有广泛的应用。
J.H.Holland于1975年出版了《Adaptation in Natural and Artificial Systems》[1],标志着遗传算法的正式产生。遗传算法是一种概率搜索算法,利用编码技术作用于被称为是染色体的二进制数串,其基本思想是模拟这些串组成的群体的进化过程。遗传算法通过有组织的然而是随机的信息交换来重新组合那些适应性好的串,在每一代中,利用上一代串结构中适应性好的位和串来生成一个新的串的群体。这是一类随机算法,但不是简单地随机走动,而是利用已有的信息来搜寻那些有希望改善质量的串,这个过程类似于自然进化。[2]
1 遗传算法的特点
与其他传统的优化算法相比,遗传算法在搜索的过程中采用群体搜索方式,有利于达到全局最优。依据个体相对优劣的适应度指标进行搜索,即使所定义的适应函数存在不连续、不规则或有噪声等情况,也可进行处理。通过在遗产算法中使用杂交算子,可将算法的注意力更多地集中到搜索空间中期望值高的那部分;同时,为了避免局部最优,在遗传算法中引入变异,这样既可在当前附近找到更好的解得同时保持群体多样性,有利于群体的继续优化。[2]
但是,由于进化的过程具有随机性,遗传算法搜索的结果具有一定的不稳定性,因此,与传统的优化算法相比,遗传算法的优化效率相对较低。[3]
2 基于遗传算法的分类优化方法
文献[4]中提出了一种基于遗传算法的分类优化方法。该方法针对两种分类器进行优化。一种分类器采用一种分类方法,使用遗传算法对分类结果进行优化。另一种是在分类器中使用几种不同的分类方法,使用遗传算法作为综合方法对分类结果进行综合优化。在一套训练集上使用一种方法,由此产生一个唯一的模型,不同的方法在同一套训练集上产生的模型也不一定相同。有些方法在某一类任务上的性能很好,但是在另外一类任务上的性能则较差,它们的预测结果有可能是错的,因此使用遗传算法可以将多种分类方法结合起来提高精度。
2.1 数据和算法集的定义
数据集合L={xn,yn},n=1,…,N},其中,xi是输入属性,yi是输出属性,N是例子数目。设有M个学习算法,分别用A1,A2,…,AM表示。A(R,S),其中A是算法,R是算法空间,S是算法搜索的空间。算法对数据集合进行学习,得到不同的学习结果,利用遗传算法对这些结果进行结合,得到一个综合结果。
2.2 基于遗传算法的组合方法框架
在L0层中,每个算法对输入的训练集数据进行训练,各自生成一套对分类问题的表示,利用规则产生器对将L0层中关于分类问题的表达转换为规则,然后作为L1层的输入。在L1层中使用遗传算法对规则集进行综合,生成最终分类器。这种方法综合各分类器的优点,其结果精度高于各单个分类器,用规则集表示其结果。
2.3 如何使用遗传算法对规则进行优化
1) 编码表示
GlodBerg在上个世纪80年代对遗传算法进行归纳,在文献[5]中总结了遗传算法的基本框架。根据该算法,一个个体代表问题的一组解,每一个个体含有表达全部解的一组规则集。规则由条件和结论组成:“if (x1,y1) and (x2,y2),…,and (xn,yn) then Cj”每一个规则用一个染色体表示。
2) 适应函数
适应函数由匹配值和不匹配值两个参数组成,当分类器能对规则进行正确识别并与结果匹配,则增加匹配值;若不能,则增加不匹配值;如果条件无法识别,则这两个参数都不变。
3) 选择策略
利用遗传算法来产生新的规则,采用限制策略,对于同类规则,可进行进化,而对于结论相同的规则,则只在其条件部分进行进化。对于结论相同的规则只在条件部分进行进化的目的是为了防止出现不收敛的情况。
4) 遗传算子
选择算子:选择算子从群体中选择优秀的个体,淘汰劣质的个体,将适应度高的候选解遗传到下一代。在选择的过程中以适应度为依据进行选择,独立于编码方式。
杂交算子:杂交是按照一定的概率将两个父代个体的部分结构加以交换重组,然后产生新的个体。在本文中,个体间同类规则的相同基因位进行交叉。
图2对遗传算法的交叉算子进行描述。
变异算子:变异算子使个体中某些基因发生突变,遗传算法中的变异运算通过位的取反操作实现。在本文中,通过对属性边界值进行突变实现。图3描述了变异算子。
5) 终止规则
遗传算法循环执行计算适应值,选择复制和应用杂交和变异算子几个步骤,直到找到满足条件的解。
3 优化结果讨论
3.1 对使用一种分类方法的分类器进行优化
文献[4]表明,遗传算法优化后的精度优于使用单个算法的精度。对于属性值十分接近的分类目标,使用单一属性生成的规则进行区分是很难实现的,而只有采用属性值的组合才能实现这类分类目标的区分。
3.2 对使用多种分类方法的分类器进行优化
在文献[4]中,使用遗传算法对基于C5.0和神经网络的规则集进行优化。优化后,得到两套规则集,基于C5.0的规则集边界值发生改变,新的规则在精度上比原来更高。而基于神经网络的规则集在形式上没有发生改变。对两种规则集进行比较,发现基于C5.0的规则集和基于神经网络的规则集均具有较高的精度,但是从理解性的方面考虑,基于C5.0的规则集既有较好的可理解度。
4 小结
该文讨论了一种基于遗传算法的分类器优化方法,在分类技术中结合遗传算法可以得到更好的分类效果,得到的分类结果更精确、易于理解。用分类技术处理原始数据集从而得到初步的规则集,而遗传算法通过优化规则条件的部分边界值提高了分类的精度。这种方法具有较好的鲁棒性和可延展性,当给定的边界值与其正确的位置相距很远,也可通过遗传算法对全局进行搜索得到解空间的最优解;如果在分类器中采用新的分类方法,可将分类的结果转化为规则集作为遗传算法输入,这些新的规则集与已有的规则集一起进行演化,从而得到更好的结果。
参考文献:
[1] Holland J H. Adaptation in Natural and Artificial Systems[M]. MIT Press,1992.
[2] 刘勇,康立山,陈毓屏.非数值并行算法遗传算法[M].2册.北京:科学出版社,1995.
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
0 引言
PID控制作为最早实用化的控制算法已有70多年历史，现在仍然是控制系统中应用最为普遍的一种控制规律。它所涉及的算法和控制结构简单，实际经验以及理论分析都表明，这种控制规律对许多工业过程进行控制时， 一般都能得到较为满意的控制效果。随着控制理论的发展，尤其是人工智能研究的日趋成熟，许多先进的算法理论逐渐被应用到传统的PID控制中，并取得了更为优越的控制效果。本文就以传统PID控制和遗传算法理论为基础，简述了基于遗传算法整定的PID控制基本理论和方法。
1 PID控制
通过将偏差的比例（Proportional）、积分（Integral）、微分（Derivative）进行线性组合构成控制量，对被控对象进行控制，这种控制方法叫做PID控制。在自动控制发展的历程中，常规PID控制得到了广泛的应用，整个控制系统由常规PID控制器和被控对象组成，根据系统给定值r（t）与实际输出值y（t）存在的控制偏差e（t）=r（t）-y（t）组成控制规律。PID控制器将偏差e（t）的比例-积分-微分通过线性组合构成控制量，对被控对象进行控制。其基本控制规律为
式中，Kp为比例增益，Ti为积分时间常数，Td为微分时间常数，u（t）为控制量，e（t）为偏差。
2 遗传算法基本操作
遗传算法，简称GA（Genetic Algorithms），是由美国Michigan大学的Holland教授于上世纪六十年代率先提出的一种高效并行全局最优搜索方法。遗传算法是模拟达尔文生物进化论的自然选择和孟德尔遗传学机理的生物进化过程的计算模型，它将“优胜劣汰，适者生存”的生物进化理论引入优化参数形成的编码串联群体中，按所选择的适配值函数通过遗传中的复制、交叉和变异对种群个体进行筛选，并保留适配值高的种群个体，组成新的群体。新的群体既继承了上一代的种群信息，又包含有优于上一代的个体信息，这样周而复始，种群中个体的适应度不断提高，直到满足一定的特定条件而停止运算，从而得到最优解。
遗传算法的关键技术包含以下几个方面：
（1）遗传编码：遗传算法的编码方式主要有二进制编码、十进制编码、实数编码等。二进制编码是比较常见的编码方式，它将解空间编码成二进制串，然后对其进行遗传算法运算，二进制编码既符合计算机处理信息的原理，也方便了对染色体进行复制、交叉和变异等操作，但它通常都需要进行参数进制转换，需要对高维参数进行编码时很难平衡编码长度和变量精度之间的关系，算法的执行效率也是一大问题。实数编码将问题的解用一个实数来表示，解决了编码对算法精度和存储空间的影响，精度高，便于大空间搜索，适于高维复杂优化问题。
（2）适应度评估：遗传算法依照与个体适应度成正比的几率决定当前种群中各个个体遗传到下一代群体中的机会，个体适应度大的个体更容易被遗传到下一代，而用来衡量个体适应度大小的函数则被称为个体适应度函数。为正确分析遗传概率，通常要求所有个体的适应度必须为非负值，因此需要确定由目标函数到个体适应度值之间的转换规则。
（3）遗传算子：遗传算法的遗传算子主要包括选择算子、交叉算子和变异算子。选择算子是指从当前种群中根据“优胜劣汰、适者生存”的自然原理，选择适应度值高的个体以产生池的过程。选择的主要目的是避免有效基因的损失，提高全局收敛性和计算效率，通常使用的方法有适应度比例法、期望值法、排位次法等；交叉算子是指将两个父代个体的相关染色体的特定基因，加以重组排列出新个体的过程。交叉算子是遗传算法的核心，并决定遗传算法的收敛性和、，可提高算法执行过程中的优化效率，常用的交叉运算方式有单点交叉、多点交叉和均匀交叉运算等；变异算子是指以一定的概率模拟自然界生物进化中染色体上某等位基因发生的突变现象，从而改变遗传基因的过程。若只有选择和交叉，而缺乏变异，则有可能使进化过程在早期就陷入局部解而进入终止过程，造成算法的早熟收敛，变异操作一定程度上克服了这种情况，有利于在尽可能大的空间中获得质量较高的优化解。
（4）算法参数：遗传算法运行时有几个参数需要在种群初始化或者种群进化过程中进行合理的选择和控制，主要包括个体编码长度l、群体规模M（一般取20～100）、终止进化代数G（一般取100～500）、交叉概率Pc（一般取0.4～0.99）和变异概率Pm（一般取0.0001～0.1）。
3 基于遗传算法的PID控制
在传统的控制理论当中，PID控制的好坏主要取决于三个控制参数调节的好坏，而遗传算法的出现则提供了一种优化参数调节的可行方法。利用遗传算法对PID控制参数进行寻优并寻找合适的控制参数，使得设定的性能指标达到最优化，这就是基于遗传算法的PID控制的基本思想。
选取被控对象为二阶传递函数，采样时间为1ms，
采用10位二进制编码方式，样本群体规模为M=30，终止进化代数G=100，交叉概率为Pc=0.60，变异概率为Pm=0.001，进行Matlab仿真实验，其阶跃响应如图1所示。
4 结果讨论
由Matlab仿真实验结果可见，基于二进制编码遗传算法的PID控制阶跃响应过渡平稳，能快速达到控制要求，控制效果较为优良。根据遗传算法的特性，在实际应用中通过改变编码方式、交叉变异概率、样本数量及终止进化代数等参数都能显著影响到控制效果，这也为进一步提升遗传算法的优化方案指明了发展方向。
参考文献
[1] 刘金琨. 先进PID控制及Matlab 仿真[M]. 北京： 电子工业出版社，2011.
[2] 侯志强. 基于遗传算法的PID控制参数优化在炉温监控系统中的应用[D]. 长沙：中南大学，2012.
[3] 朱成娟. 遗传算法的改进及其若干应用[D]. 秦皇岛：燕山大学，2006.
中图分类号：TU323.4文献标识码： A 文章编号：
引言：
近年来，大型智能桁架结构在航空航天领域得到越来越多的应用。其模型具有不确定性，模型结构和参数在很大范围内变化，基于精确模型的传统控制理论和现代控制理论都有局限性[1]。模糊控制不依赖于被控系统的精确数学模型，而是通过对系统动态特征的定性认识、直接推理、在线确定或变换控制策略，以达到对复杂的、非线性的、不确定性的被控系统的控制，这种方法容易实现，也更加易于保证其实时性。2005年，赵国伟等[2]将PID和LQG成功的应用于大型空间复杂智能桁架结构的振动主动控制上，2009年，张京军等[3]将模糊控制应用于智能悬臂梁的控制当中。本文基于对智能桁架结构模型的认识与分析，设计出相应的模糊控制器，并采用遗传算法对其控制规则进行优化，然后通过一实例仿真验证该方法的有效性。
1智能桁架结构有限元模型
设智能桁架结构中共有个压电主动杆，考虑压电主动杆的机电耦合特性，基于有限元法，建立智能桁架结构的运动方程: （1）
式中，、、分别为质量矩阵、阻尼矩阵和刚度矩阵、、分别为加速度矢量、速度矢量和位移矢量；是由主动杆的方向余弦组成的向量矩阵；为外部节点力矢量；是维主动杆产生的控制力向量。
为简化结构的仿真模型，对智能桁架结构的动力学模型做模态截断处理,则其独立模态空间的动力学方程及观测方程为：
（2）
（3）
式中，、、，，为第阶振动的固有频率，为第阶的模态阻尼比，为外界干扰力，为维模态控制力，其中为模态向量矩阵，为对角阵，为第个作动器单位压电作用下产生的控制力，为对角阵，为第个主动杆等效刚度，为模态坐标，为作动电压。
2.模糊控控制器的设计
目前振动控制中常用的模糊控制器多为双输入-单输出的结构形式。本文采用的也是这种结构模式，其输入输出变量分别为智能桁架的结构位移、速度和对其施加的控制反力。这三个变量都要从物理论域量化到整数论域上，然后再在整数论域上给出若干语言变量值，从而实现整个论域元素的模糊化过程。本文将位移和速度作为误差和误差变化率。设量化值、有统一论域，的论域为。为表达控制规则需先确定输入变量、输出变量的词集，为了简化设计过程，设计量化后的误差、误差变化、控制量的词集均为：负大（NB）、负中（NM）、负小（NS）、零（ZO）、正小（PS）、正中（PM）、正大（PB）。在模糊化时，输入变量选择三角形和梯形的隶属函数，输出变量选择三角形隶属函数。模糊控制规则直接影响到控制系统的性能，本文根据桁架的位移、速度和控制力之间的关系，总结出用语言值表示的二维控制规则表，见表1.
表1 二维模糊控制器控制规则表
模糊推理采用Mandain法，清晰化采用重心法。
3.遗传算法优化控制规则
利用遗传算法进行优化求解时，首先要对控制规则进行编码，然后选择合适的适应度函数，通过复制、交叉、变异等遗传操作，获取最佳种群，。该种群中最优个体为优化问题的解，即为最优模糊规则。
3.1 遗传编码
遗传算法中常见的编码方法有二进制编码和十进制编码。本文将采用十进制编码方法对模糊控制规则进行编码，用数字集{1,2,3,4,5,6,7}来依次表示模糊语言集{ NB，NM，NS，0，PS，PM，PB }，即对设计的控制规则进行数值化，按从左到右，从上至下的顺序把控制规则展开成一维形式，这样便形成了遗传算法所需要的个体。前面设计的控制器含有49条控制规则，即是含有49个待寻优参数，这样每个染色体就包含有49个遗传基因，每个染色体长度也就是49位。对其进行数字化处理后可以表示为染色体表2
表2 染色体表
3.2 适应度函数选择
要想利用遗传算法对控制规则进行优化，首先要解决种群个体的评估问题。本文研究的是智能桁架结构的模糊控制，其控制目标是在激励荷载作用下使得桁架结构的振幅达到最小、衰减随度达到最快。本文以模糊规则表的49个模糊语言集作为设计变量，以智能桁架结构的自由端最大挠度作为评价控制器性能指标的目标函数。其表达式为：
（4）
因为遗传算法要求个体适应度越大越优，故需将目标函数转化为最大值问题后作为目标函数，转换函数为：
（5）
3.3遗传操作
3.3.1 选择
选择算子是遗传算法中对群体中个体进行优胜劣汰的操作，本文采用适应度比例选择 ，设群体大小为，个体的适应度值为，则个体被选择的概率表示为：
（6）
3.3.2 交叉
交叉运算是两个配对染色体按照某种方式相互交换其部分遗传基因，从而产生两个新的个体。为了保证交叉运算后产生的新一代染色体个体的规则总数量不变，本文采用对位交叉算法。
3.3.3 变异
变异是指将个体染色体编码串中的某些基因位串上的基因值用该位串的其他等位基因来替换，从而产生新的个体。本文在进行变异操作时，是对个体染色体的49个基因，随机选择一位或多位基因值进行变异，随机变异所选用的基因用1-7之间的随机数值来代替
3.4遗传算法实现
首先，确定遗传算法的相关参数：本文的设计变量49个，取种群个数为15个，最大迭代次数取20次。然后，用遗传算法对控制规则进行优化，
4 实例仿真
本文所选桁架是由普通杆和由粘贴有压电片的主动杆构成，其结构尺寸为，共有83根杆件，普通杆是由铝合金材料构成，弹性模量为，密度，泊松比，杆件直径为。主动杆压电片采用压电陶瓷材料，传感器/作动器同位布置，布置在固定端端部，设该桁架结构的模态阻尼比为，顶端节点所受作用力，作用时间为0.01s。
将设计的模糊控制器和在遗传算法优化控制规则后设计的控制器分别作用于智能桁架结构，通过算法程序的运行可以得到
桁架架结构的仿真图：
仿真图中，红色线代表遗传算法优化模糊控制规则后的模糊控制器的控制效果，黄色线表示没有使用遗传算法的普通模糊控制器的控制效果。从仿真图中我们可以看出，遗传算法优化后的模糊控制器比普通模糊控制器有更好的控制效果，每阶的位移曲线最大位移都有明显的较小，智能桁架结构振动的衰减速度也有所加快。
5结论
本文对遗传算法做改进，然后作用在模糊控制器的控制规则优化上的方法是可行有效的，同时也说明了控制规则对于控制器的控制效果起着至关重要的作用。
参考文献
复杂建筑结构设计问题一般都是先将其分解为易于求解的子问题，且多学科的交叉存在于子问题中。不同学科的专家小组会参加复杂建筑结构的设计，他们之间还互不知晓，这就形成了优化过程中的四个特征：复合多目标，学科交叉，巨大数量的设计约束，大的设计变量空间。相对于复杂建筑耦合系统优化来说，协同优化方法是比较新的方法。作为一种新的优化方法，许多不足之处仍然存在。优化效率及效果是这一方法的关键课题。
1、建筑协同设计
1.1建筑协同设计的特点
建筑设计是一门集经济性、艺术性和实用性于一体的综合性的学科。建筑功能、造型、空间及工程预算等诸多问题在建筑设计中都要考虑，涉及多工种。多学科的协调和交叉。目前越来越激烈的市场竞争氛围，使得复杂建筑结构协同设计理论在学术界和设计单位受到越来越多的关注。建筑协同设计是一种新兴的网络环境下的建筑设计方式，设计人员及管理人员都能在不同地点同步的参与设计工作，提高了设计的效率和质量。建筑设计需要多学科合作及反复协作与修改，以满足客户需要的最优设计方案。一般工程设计的各种特性建筑设计中都有，但是复杂建筑结构要求高，总体设计难度非常大，从而建筑协同设计有以下几个明显的特点：综合与协调，反复迭代，创造性和科学性。
1.2建筑协同设计的冲突
在建筑协同设计过程中，各领域参数的确定是协同小组共同完成的，其中就有在一个领域内协同小组在一些数据指标上的分歧以及协同小组在不同领域对相关参数的范围的确定，从而发生协同设计的冲突。因此，可以分类管理存在建筑设计中的冲突，这样就可以从各个角度分析和处理建筑协同设计中存在的冲突。建筑设计冲突主要是设计目标冲突和设计结果冲突两种，根据建筑设计的特点，设计冲突在建筑协同设计中又分为以下几个方面：总体冲突，装配冲突，各领域之间冲突，经济性冲突。
2、协同遗传算法在建筑结构优化设计中的应用
2.1遗传算法简介
尽管传统结构优化方法中的解析法和直接法已经在实际工程中广泛应用，但对于如极点问题、非连续设计变量问题、目标函数的强非线性问题等特殊问题处理难度仍然很大。特别是功能函数的偏导数在许多传统算法中需要被计算，而这就要求工程函数的连续性特别良好，这就给计算带来了极大的麻烦。遗传算法作为一种新的算法，与以往方法截然不同，显示了强大的生命力，是复杂建筑结构优化设计的一个新思路。最初遗传算法是用来指导模拟人工自然系统和解释自然界的适应性的，后来这种方法对于复杂建筑结构优化设计的有效性在许多报告和论文中都论证了。但此法也存在许多问题，例如不利于工程应用、收敛速度慢等。目前研究的重点就是在总结以往方法的基础上提出加快收敛的改进方法。
对于单个计算点的优化追踪过程，遗传算法放弃了这个传统的优化方法，而是多个计算点同时控，一个生物群体被看成了操作的对象。遗传算法是改变线列集团的质量，通过遗传操作算子，有三种最基本的操作：交叉，再生产和突然变异。
2.2遗传算法的优化过程
遗传算法为求解复杂建筑结构优化问题提供了一种通用框架，它不仅仅只依赖于问题的种类和领域。对一个实际应用问题进行优化计算，遗传算法构造求解该问题一般可按下述步骤来进行。
第一步：确定各种约束条件及决策变量，即确定问题的解空间和个体的表现型X。
第二步：建立优化模型，确定是求目标函数的最小值或是求目标函数的最大值，即确定目标函数的类型及其量化方法或数学形式。
第三步：确定表示染色体编码的可行解方法，即确定出遗传算法的搜索空间及确定出个体的基因型X。
第四步：确定编码方法，即个体基因型X到个体表现型X的转换方法或对应关系的确定。
第五步：确定量化评价个体适应度的方法，即目标函数f（x）到个体适应度fit（x）的转换规则的确定。
第六步：设计遗传算子，即确定变异运算、选择运算、交叉运算等遗产算子的操作具体方法。
第七步：确定有关遗传算法的运行参数，即遗传算法的pc、pm等参数的确定。
研究遗传算法的优化过程一直被实际工程问题直接的推动，高效实用的遗传算法优化的研究和探讨具有广泛而深远的意义。
2.3遗传算法提高精度、加快收敛的策略
通常按照上述计算步骤进行遗传算法复杂建筑结构优化的收敛速度比较慢，跳跃的现象经常在计算过程中出现。为了更好的解决上述问题，下面介绍了三种修正方法。
第一种是引入突变算子，减小局部出现最优解的可能性。做法是按一个较小的概率取反池中经过交换算子操作过的个体的二进制串的每一个。如果更优个体产生，则使之保留，反之淘汰。一般突变概率很小，不宜超过0.005，根据实际情况来定。
第二种是可以保护最优的几个个体，使它们直接进入下一代而不受任何影响，直至更优的个体的出现；或者强制令最优的几个个体进行，其它个体进行正常过程的。这样局部退化现象就会有效的减少，收敛进程加快。
第三种是每个个体自己的代表值依据自己所处的环境来改变。具体做法是下一代所有个体代表值的平均值是目前最有个体的代表值，修正了每一个个体的代表值。
结语
遗传算法作为一种全新的复杂建筑结构优化设计的方法，如目标函数的强非线性问题、设计变量的非连续性问题、对多峰函数求解最优化的问题等传统优化方法存在的多种弊端都被它克服了，同时，遗传算法的结构优化方法及过程都比较简单，而且计算机的编程计算特别适用于传算法。并且三种遗传算法改进策略的联合使用明显使优化计算收敛速度加快，减少计算时间的同时，结果的准确性也很高。可以说对于处理复杂建筑结构优化问题，遗传算法及准确又可靠，非常值得深入研究。
参考文献：
中图分类号：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）可行课程表的产生。
这样，我们就有了一个课程表的数据库表。因此，可以打印其中某一班级的课程表或全校的课程表了。
结论
本文采用遗传算法来对课表编排问题进行求解，是求解这种难解的组合优化问题方法中较明智的选择，目的是在遗传算法基础上提出一个课表方案的随机生成和优化方案，能够较大程度地实现课表编排和多个目标的最优化。本文算法对我们这类院系较多、教师工作量大、学科变化较大、不确定性较多的学校能有所借鉴。
参考文献
中图分类号：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.
中图分类号：TP391.6文献标识码：A文章编号：1009-3044(2011)31-
The Research of The Selection of Knowledge Reasoning Method Based on Genetic Algorithm
TAN Hui-lin1,2, LIU Xian-feng1
(1. Shaoyang Medical College, Shaoyang 422000, China; 2. Mathematic and Computer Science College of Hunan Normal University, Changsha 410081, Chin)
Abstract: This paper gets a knowledge reasoning method based on genetic algorithm, it will build an optimal learning path for learners. This method is carried on matlab R2009a, using the best preservation of individual operator, ranking selection operator and greedy algorithm to control the procedures of the cross and the mutate which improve the efficiency of the algorithm, and it can simultaneously consider the difficulty level of the course and the course of concept continuity while generating a customized learning path.
Key words: genetic algorithm; greedy algorithm; knowledge reasoning
随着网络技术和数据挖掘技术的发展，智能教学系统的个性化学习路径的寻径成为重要课题。专家认为，学习者的学习成绩会受到教学材料的组织方式、教学材料的呈现方式以及教学内容的类型三者交互作用的影响[1]。该文是以学习认知和布卢姆的掌握学习理论为支撑，用遗传算法针对学习者所需要加强学习的课程构建了一条自适应的最优学习路径。
1 掌握学习理论
掌握学习理论是美国著名教育学家布卢姆在卡罗尔的“学校学习模式”的基础上提出的，关于教学系列化和管理结构化研究的一种个别化教学理论[2]，“矫正-反馈”系统是掌握学习理论的一大特色[3]。布卢姆认为在教学前和过程中应及时对学习者进行评价，这样才能给学习者呈现最有益的学习序列，做到因材施教。
2 课程难度
该文选取难度值较低的课程作为起始课程，这一做法符合了学习认知理论的循序渐进原则。首先由课程专家依据李克特氏5点量表对课程的难度系数进行初始化，然后根据学习者反馈信息调整课程难度参数[4]。因此，课程的难度系数逐渐趋于合理和稳定，能有效降低部分学习者的异常反馈信息，具体计算公式如下所示：
其中bj(tuned)是专家预设和学习者投票线性组合后的第j个课程自适应调整的难度参数； bj(initial)是由专家所给定的第j个课程的难度初始值；bj(voting)是由学习者在测验后投票出的第j个课程的平均难度；w是调节权重，可以随课程类型变化而变化。
3 课程相似度
从认知能力发展的角度来说，相近的课程更方便学习者完成知识的同化与顺应。为了呈现符合学习者认知能力背景和需求的最佳学习路径，课程的相似度就成为了重要的课题。
为了便于计算课程的相关性，我们使用向量空间模型(VSM) [5]对课程进行建模。令A=(A1,A2,…,An)表示由m个知识点术语构成的n个课程文档集合，其中Aj=(A1j,A2j,…,Amj)T是课程文档向量，Aij表示知识点术语i在课程文档j中的信息权重。
假设课程i和课程j的知识点术语集合的个数为n。课程i和j 的相似度rij可以用余弦度量法来计算：
4 基于遗传算法的知识推理模型
基于遗传算法的知识推理模型如图1所示，其主要步骤如下：
1) 由有经验的教师作为专家依据教学目标对每个课程设计相应的测试题目；
2) 学习者进行测试得到相应的评估数据，即：学习者需要的课程以及课程难度系数；
3) 分析模块将各课程的专家预设难度系数与学习者投票得出的难度系数进行线性调整，得出各课程的难度系数；
4) 系统将学习者需要进行校正活动所对应的课程难度系数和课程之间的相似度系数送到基于遗传算法知识推理模块，为学习者推荐最优个性化课程序列。
5 基于遗传算法的推理模块
5.1 基于传统遗传算法的知识推理
1) 染色体编码方法
假设课程库共有n个课程，给每个课程分配从1到n的序号[6]。每个课程分配的序号与其后续课程的序号相结合形成的染色体代表了个性化课程学习路径。
2) 初始化种群
该文将生成一个以难度值最低的课程作为起始基因，由随机函数随机产生其它课程序列的初始种群。
3) 选择算子
采用赌选择算子来完成选择操作。
4) 交叉算子
采用两点交叉算子的变形，区域交叉算子[7]，作为交叉操作的方式。
5) 变异算子
采用倒置变异[8]算子，也就是逆转变异算子作为变异操作的方式。
6) 适应度函数
该文把个性化学习路径上的所有相继课程染色体之间的相似度系数之和作为适应度函数。染色体的适应度函数值越高，所得染色体越优越。推荐的适应度函数定义如下：
其中，r(i-1)i代表了连继的两个课程的相似度，n代表了所需考虑的总课程量。
7) 仿真实验与分析
计算机的实验平台是：处理器Intel(R)Core(TM)Duo T5750 2.0GHz 2.0GHz，内存3.0GB，操作系统Windows 7，在Matlab R2009a对知识推理实现仿真：假设一个学习者在诊断性测验或形成性测验中不正确检测项目数为10，其错误项目相对应的课程之间的相似度及课程本身的自适应调整难度参数如表1所示：
Pc为0.90；Pm设定为0.01；初始种群为100；迭代次数为150。
表1 错误项目对应的课程之间的相似度及课程本身的自适应调整难度参数
实验发现：基于传统遗传算法的知识推理算法最快迭代48次就能收敛到全局最优解，最慢迭代96次才能收敛到全局最优解。
图2是适应度函数图，其中圆圈所在的曲线代表了适应度函数最高值随着遗传迭代次数变化的曲线，方块所在的曲线代表了适应度函数平均值随着遗传迭代次数变化的曲线。
图2 传统遗传算法的知识推理算法的适应度函数图
接下来，我们用表2来展示采用基于传统遗传算法的知识推理算法所寻找的最优个性化学习路径，并对路径中前后连续课程之间的相似度和课程本身的难度系数进行说明。
表2 基于传统遗传算法的知识推理算法所寻找的个性化学习路径表
5.3 基于改进的遗传算法的知识推理
该文所提出的改进遗传算法与传统遗传算法的区别之处在于选择算子、交叉算子、变异算子和各遗传参数的不同，初始化、编码和适应度函数两者是一致的。
1) 选择算子
中国计量学院的学者提出了两次最优个体保存法[9]，实验证明该方法能加快坐标测量系统的标定过程且算法精确。该文对两次最优个体保存法进行改进，提出了三次最优个体保存法和排序选择相结合的选择算子，即：在初始化、交叉后和变异后三次使用最优个体保存法，最后使用排序选择算子将对种群实施优胜劣汰的操作。
实验发现：新选择算子的遗传算法最快迭代10次就能收敛到全局最优解，最慢迭代30次也能收敛到全局最优解，其适应度函数图如图3所示。
图3 新选择算子的知识推理算法的适应度函数图
2) 交叉算子
厦门大学的学者提出将贪心算法引入到遗传算法的交叉算子[10]中，有效解决了TSP问题中的群体多样性和收敛速度的矛盾。该文将区域交叉算子换成基于贪心算法思想的交叉算子，即：在父代课程染色体p1、p2中分别找到交叉点的右或左课程基因cr1、cl1和cr2、cl2，选择与交叉点相似度系数大的课程基因作为下一课程基因以及新的交叉点。
实验发现：新交叉算子的遗传算法最快迭代45次就能收敛到全局最优解，最慢迭代100次才能收敛到全局最优解，其适应度函数图如图4所示。
图5 新交叉算子的知识推理算法的适应度函数图
3) 变异算子
该文试着采用贪心算法和Inver-Overt算子相结合的变异算子操作方法，即每次选择的两交叉点的相似度是最大的。
实验发现：改进了变异算子的遗传算法最快迭代25次就能收敛到全局最优解，最慢迭代100次才能收敛到全局最优解，解空间分散的比较均匀，其适应度函数图如图5所示。
图6 新变异算子的知识推理算法的适应度函数图
4) 仿真实验与分析
下面我们应用Matlab对整个改进遗传算法的知识推理进行仿真实验，换言之，在与传统遗传算法知识推理中设定的一致情境中为学习者找寻一条符合其知识能力背景和需求的个性化学习路径。
Pc为0.90；Pm设定为0.01；初始种群为100；迭代次数为100。
实验发现：使用基于改进遗传算法的知识推理算法可以5次得到全局最优解6.4070，其它的解均可看成是近似最优解，其适应度函数图如图7所示。
图7 改进遗传算法的知识推理算法的适应度函数图
综上所述，结合文中两种知识推理算法所进行的仿真实验，我们可以得到如下结论：使用改进的遗传算法的知识推理算法所得到的结果要明显好于使用传统的遗传算法的知识推理算法所得到的结果。前者的收敛速度更快，且产生的解空间均可看成近似最优解，解空间的染色体适应度函数值远高于后者。
6 结束语
该文提出了基于遗传算法的知识推理模型，该模型能为学习者推荐符合其知识能力背景和需求的，以难度参数值最低的课程起始的、课程序列的相似度系数之和达到最大值的个性化学习路径，为构建个性化学习服务的智能教学系统提供了支持。
参考文献：
[1] 赖丁R.认知风格与学习策略[M].庞维国,译.上海:华东师大出版社,2003:128.
[2] 吴杰.外国现代主要教育流派[M].吉林:吉林教育出版社,1989:345-346.
[3] 张春玲.对布卢姆掌握学习理论的再认识[J].洛阳师范学院学报,2001(1):80-82.
[4] Chen C M,Lee H M,Chen YH.Personalized e-learning system using Item Response Theory[J].Computers & Education,2005(44):237-255.
[5] 陶跃华.基于向量的相似度计算方案[J].云南师范大学学报,2001(9):17-19.
[6] Huang M J,Huang H S,Chen M Y.Constructing a personalized e-learning system based on genetic algorithm and case-based reasoning approach[J].Expert Systems with Applications,2007(10):551-564.
[7] 蒋望东,林士敏.基于选择性集成的整数编码遗传算法及TSP问题求解[J].计算机与现代化,2007(5):38-43.
[8] 高经纬.求解TSP问题的遗传算法实现[J].计算机时代,2004(2):19-21.
[9] 王学影.关节臂式坐标测量系统关键技术研究[J].中国计量学院学报,2010(3):12-15
