时间：2022-07-01 00:20:08
引言：易发表网凭借丰富的文秘实践，为您精心挑选了九篇遗传算法论文范例。如需获取更多原创内容，可随时联系我们的客服老师。
论文摘要：TSP是组合优化问题的典型代表,该文在分析了遗传算法的特点后,提出了一种新的遗传算法(GB—MGA),该算法将基因库和多重搜索策略结合起来,利用基因库指导单亲遗传演化的进化方向,在多重搜索策略的基础上利用改进的交叉算子又增强了遗传算法的全局搜索能力。通过对国际TSP库中多个实例的测试,结果表明:算法(GB—MGA)加快了遗传算法的收敛速度,也加强了算法的寻优能力。
论文关键词：旅行商问题遗传算法基因库多重搜索策略
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算法在单亲遗传演化中就使用了基因库中的优质基因,使得单个个体的进化速度大大提高,从而为进一步的演化提供了条件,群体演化过程的选择机制和收敛准则的恰当选取使得算法在注重了求解质量的同时兼顾了算法的效率。
4结束语
关键词遗传算法；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
关键词：遗传算法，混沌，图像分割
0引言
遗传算法是一种全局优化搜索算法，它使用了群体搜索技术，用种群代表一组问题解，通过对当前种群施加选择、交叉和变异等一系列遗传操作，从而产生新的一代种群，并逐渐使种群进化到包含最优解或近似最优解的状态。近几年来借助于混沌改进遗传算法的性能是遗传算法领域研究的热点之一，遗传算法和混沌优化的组合,可以使遗传算法的全局寻优能力，搜索精度，搜索速度等几方面得到较明显的改进。
1混沌的特征和虫口方程
混沌是存在于非线形系统中的一种较为普遍的现象，具有遍历性、随机性等特点，混沌运动能在一定的范围内按照其自身的规律不重复地遍历所有状态。因此，如果利用混沌变量进行优化搜索，无疑会比随机搜索更具有优越性。科技论文。
描述生态学上的虫口模型Logistic映射自May于1976年开始研究以来，受到了非线形科学家的高度关注，Logistic映射是混沌理论发展史上不可多得的典范性的混沌模型，如下式所示：
2混沌遗传算法
基于混沌遗传算法的二维最大熵算法基本步骤如下：
1.设置混沌遗传算法的种群规模以及最大进化代数；
2.生成初始群体。随机产生S 和T ,其中, S ,T ∈(0 ,1) 。然后利用式
计算每个个体的适应值。式（2-1）中的s 和t 分别由以下公式确定：s =(int)( S*255) ，t = (int)(T*255) 。对初始种群执行混沌扰动，如果在C1 步之内找到更优个体，则替换原来的个体，否则保留原个体。科技论文。混沌扰动方式按式(1-1)进行。
3.如果当前进化代数大于G，转步骤5，否则执行变异操作。变异方式按如下公式进行：
其中，fRandom()产生（0,1）之间的随机数，如果变异后的个体具有更优的适应值,则把该个体加入当前种群；
4.执行混沌操作。如果在C2 步之内找到更优解,则替代原来的个体, 否则保留原个体。混沌扰动按公式(1-1)进行。结束后转步骤6。
5. 在较小范围内执行混沌扰动。扰动方式：
其中m1,m2为混沌变量，且m1,m2∈（0,1）。如果变异后的个体具有更优的适应值, 则替换原来的个体,否则保留原个体。
6.按规定的种群规模直接选择最优个体进入下一代。
7.如果满足终止条件, 返回最优解, 否则从步骤3重复上述过程。
8.利用最优解分割图像。
3实验结果与分析
为了检验本算法的效果，用文中提出的基于混沌遗传算法（以下简称为B算法） 和基于传统遗传算法的二维最大熵算法（以下简称为A算法）对Couple.bmp 图像进行了实验比较。科技论文。当文中算法和基于传统遗传算法的二维最大熵算法中各取最大进化代数为10 时,分割效果如图3、4所示。
图1 Couple 原图图2 Couple图像直方图
图3 A算法结果图图4 B算法结果图
4结论
混沌遗传算法是混沌思想与遗传算法思想的结合，比传统遗传算法具有更好的群体多样性、更强的全局寻优能力。文中将混沌遗传算法与二维最大熵图像分割算法结合，应用于图像分割，对比于基于传统遗传算法的二维最大熵算法，文中算法具有更强的稳定性,更快的执行速度，分割效果好。
参考文献
[1]吴薇，邓秋霞，何曰光．基于免疫遗传算法的图像阈值分割．纺织高校基础科学学报，2004，17(2)：160-163
[2]薛景浩，章毓晋，林行刚．二维遗传算法用于图像动态分割．自动化学报，2000，26(5)：685-689
[3]王小平，曹立明．遗传算法－理论、应用与软件实现．西安交通大学出版社．2002
【关键词】自动导航小车；路径规划；免疫遗传算法；疫苗
1、引言
目前，为使移动机器人规划出良好的去去路径，所用的方法很多，如栅格法[1]、势场法[2]、可视图法[3]等。但各种方法有其使用局限。人工智能的发展为AGV的路径规划提供了新思路，产生了诸如神经网络学习法、遗传算法等方法。这些算法在一定程度上解决了AGV的路径规划问题，但也有其缺陷。如神经网络学习法对于复杂环境难以数学建模，范化能力差；模糊法灵活性差。遗传算法在迭代过程中，个体在进化过程中不可避免地会产生退化。受生物免疫系统的启发，论文将免疫引入到遗传算法中，在保留遗传算法优点的情况下，利用待求问题的一些特征信息，采用免疫方法所具有的识别、记忆等功能来抑制遗传算法在进化中所出现的退化现象。本文所设计的基于免疫遗传算法的AGV路径规划方法利用AGV在移动过程中的特殊信息对所选路径进行优化，可较快地使AGV根据环境信息搜索一种满意的路径，提高了AGV路径规划的智能性。
2、环境信息建模
对AGV进行路径规划前，应解决对其环境信息的描述即环境建模问题。为此，作以下假设[3]：
（1）AGV在二维平面中运动，不考虑其高度方向的信息；（2）规划环境的边界及其内所有障碍物（妨碍AGV运动的所有物体）用凸多边形表示。（3）考虑到AGV的大小等，对环境边界进行缩小和对障碍物进行扩大时，其缩放量为AGV外形最大尺寸的一半。即AGV为“点机器人”。
至此，AGV的工作空间可描述为：工作平面和障碍物群{Oi|i=1，2…N}。具体到其个障碍物Oi，可描述为Oi={顶点1坐标（xi1， yi1），….. 顶点n坐标（xni， yni）}。为方便数据处理，对多边形顶点沿顺时针方向编号。起点为S，终点为E。工作平面可表示为矩形{（Xmin，Ymin），（Xmax，Ymax）}。
设在AGV的工作环境中有n个已知的障碍物Oi（i=1，2，...，n），对应的顶点数为Si，顶点坐标为（x（i，j），y（i，j））（j=1，2，…Si）。为描述AGV工作环境中的障碍物，采用Dm×m矩阵对环境信息进行描述，其中，m为障碍物顶点总数。定义d（i，j）为：
3、免疫遗传算法设计
3.1路径编码方式
采用免疫遗传算法求解最优问题的关键是对所求问题的解进行编码。编码的长度与搜索空间的大小及求解精度有直接关系，也影响算法的效率。对AGV进行路径规划时，传统的二进制或实数编码方式都不适用。本文设计了一种自适应变长度实数数组编码方式，即第p代Xp的第k条染色体Xkp的第j位基因Xkp（j）表示为Xkp（j）=|io，xk，yk|T，其中io为障碍物序号，（xk，yk|）为第io号障碍物的某顶点坐标。由于路径的起点为AGV的起始点，终点为其目标点，在路径规划时可省去以缩短染色体的长度。定义，AGV的可能运动路径由数条直线段组成，相邻两直线段的交点称为AGV的路径拐点。为使AGV不穿越障碍物运动，基于对工作规划空间建模时所作的假设，AGV可沿多边形障碍物的边界线移动，也可以障碍物的顶点为拐点在自由空间中移动。染色体即AGV的某行路径Xkp为Xkp={Xkp（1）， Xkp（2），…， Xkp（nkp）}，其中nkp为第p代中第k条染色体的长度，每代中各条染色体长度不同。
3.2适应度函数
在对AGV进行路径规划时，其优化目标为在所有可能的运动路径Xp={Xkp|k=1， 2，…，N}中找出一条最优或次优路径。设某个体Xkp的路径长度Dk为：
其中dj为Xk中各直线段轨迹长。因为AGV由一直线轨迹向另一直线轨迹过渡时运动速度的变化会影响其运行时间，因此，在对所选路径进行评价时，除考虑其总长度外，可要求路径中的拐点数尽可能的少或AGV的姿态角变化量尽要能的小。本论文的路径规划目标是路径短且拐点较少。定义适应度函数为：
式中，和为调整系数。这里取=0.8，=0.2。N为种群大小，Dj为种群中第j个体的路径长度，nj为第j个体路径拐点数。
3.3算法的实现
在进行路径规划时，首先判断AGV从起点向终点沿直线轨迹运动时是否穿越障碍物。若无障碍物，两点间的连线为AGV的最佳运动路径，无须进行路径规划。否则进行路径规划。
免疫遗传算法中，疫苗是根据待求问题的先验知识构造的最佳个体基因的估计，抗体是根据疫苗将某个体基因进行修正后所得到的新个体。论文所设计的基于免疫遗传算法的路径规划过程如下：
（1）根据问题从记忆抗体库中提取问题的抗体P得到初始种群 ，不足N个时在AGV起始点和目标点之间随机产生N-P条路径。个体的产生方法是：以包围AGV的起点、终点和所有在线障碍物的最小矩形为规划区域，在规划区域内的障碍物顶点个数为M，在线障碍物为m，则染色体的最大长度为M-m。以规划区域内的障碍物顶点为被选对象，沿一定的条件随机选取基因位上的基因组成一条染色体，同用样的方法产生其它染色体以组成群体。
（2）根据先验知识抽取疫苗H={h1， h2， …， hm}；
（3）计算第p代种群Ak所有个体的适应度，并进行终止进化判断。
（4）对当前群体Xp进行遗传算子操作得到子代群体Bp。进行交叉操作时，采用单点交叉。交叉操作时，两个个体若有相同的基因（而非等位基因）进行交叉操作。当相同基因位不止一个，随机选择其一进行交叉；当无相同基因位则不进行交叉。进行变异操作时，从个体中随机删除一基因位或随机选取一基因位插入一新基因位，或在个体中随机选取一基因位用另一随机产生的基因位交换。
（5）对子代Bp进行免疫操作，得到新代Xp+1；接种疫苗和免疫选择是免疫算法的主要操作，接种疫苗是为了提高个体的适应度，免疫选择是为了防止个体的退化。接种疫苗即从Bp中按比例K随机抽取Nk=KN个个体Bip（i=1，2，…，Nk），并按先验知识修改Bip（这时就变为抗体），使其以较大的概率具有更高的适应度。接种疫苗时，若Bip已经是最佳个体，则其以概率1转移为Bip。对路径规划，接种疫苗就是对所选个体进行判断：首先，相邻两点间能否使AGV无障碍的沿直线运动；其次，任意两点间能否使AGV无障碍的沿直线运动？条件满足，则删除中间点。免疫选择分两步完成：免疫检测和退火选择。免疫检测即对抗体进行检测，若出现适应度下降，此时由父代个体代替其参加竞选，退火选择即以概率P（Bip）在当前子代中进行选择：
其中，为适应度函数；Tk是单调递减趋于0的退火温度控制序列，Tk=ln（T0/k+1），T0=100，p是进化代数[3]。
（6）选择个体进入新的群体。更新抗体库，并转到第（3）步。
4、仿真实验
仿真是在Matlab6.1上进行的。AGV的工作环境大小为8×6m2，其内有6个形状各异、排列任意的障碍物（如图2所示），现欲使AGV从S点无碰撞地运动到E点且使其运动路径最短，建立如图4所示的可视图。其可视矩阵如左图：
论文采用所设计的路径规划方法和现有的遗传和免疫算法对AGV进行路径规划以寻找最佳路径。取遗传操作中的交叉概率Pc=0.8，变异概率Pm=0.2，免疫操作中的接种疫苗概率Pv=0.6，初始种群大小为N=20，抗体库M=5，遗传代数不超过K=200。图3为路径规划的最佳路径。进化过程中适应度变化和路径长度变化如图4所示。
由仿真结果知，采用免疫遗传算法进行路径规划时，退化现象基本不会发生，再能很快得到问题的最优解。其原因是，利用免疫遗传算法对AGV进行路径规划，一方面利用了遗传算法的优点，由于是对编码进行操作，对问题的依赖性小，且操作是并行进行，优化速度快；同时针对遗传算在进行交叉和变异操作时是以以概率方式随机地、缺泛指导性地进行导致问题进化时产生退化的现象，采用适当的指导，弥补了遗传算法的缺点。利用遗传免疫算法进行优化，在保证算法收敛的前提下，有效地提高计算速度。利用此法对AGV的路径进行规划，比其它的方法更有效。
5、结论
论文主要针对环境建模和路径搜索两大问题进行了研究。基于可视图环境建模方法优点，完成了对环境信息的建模。并结合遗传和免疫算法的优点设计了具有精英保留策略的基于免疫遗传算法的AGV路径规划方法。通过比较采用遗传算法、免疫算法和本论文所设计的免疫遗传算法对AGV进行路径规划结果和效率的比较，分析了所提出的基于免疫遗传算法的AGV路径规划方法的优点。仿真结果表明：
A.本论文采用改进的可视图法对环境信息进行建模，在改变障碍物位置、形状、大小和AGV的起点及终点的情况下，均可快速构建AGV的环境信息模型。
B.采用本论文所设计的基于免疫遗传算法的AGV路径规划方法对AGV进行路径规划，在速度方面优于传统的免疫算法和遗传算法，且系统退化现象基本得到消除。
参考文献
[1]吴锋，杨宜民.一种基于栅格模型的机器人路径规划算法[J].现代计算机（专业版），2012，4（3），7-9，13.
[2]沈凤梅，吴隆.基于改进人工势场法的移动机器人自主导航和避障研究[J].制造业自动化，2013，35 （12），28-30，39.
[3]李善寿，方潜生，肖本贤.全局路径规划中基于改进可视图法的环境建模[J].华东交通大学学报，2008，25（6），73-77.
作者简介
关键词：自动排课；遗传算法；求解与优化
中图分类号：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.
摘 要：文章将遗传算法应用于仓储管理调度系统的储位分配过程，分析了基本遗传算法应用于储位分配的优缺点。通过采用精英保留策略，保证了基本遗传算法设计的多样性，实现了算法搜索的快速收敛和最优性能保持，克服了基本遗传算法的“返祖”现象。
关键词：改进遗传算法；精英保留策略；储位分配
中图分类号：F252.13 文献标识码：A
Abstract： This thesis applies genetic algorithm into the storage allocation process of warehouse management dispatching system， and analyzes the advantages and disadvantages of applying genetic algorithm into storage allocation. By adopting elitism-reserved strategy， it has ensured the diversity of the basic genetic algorithm design， realized the fast convergence and optimal performance of algorithmic search， and has overcome the“atavism”phenomenon of basic genetic algorithm.
Key words： improved genetic algorithm； elitism-reserved strategy； storage allocation
1 研究背景
随着经济的全球化，给很多跨国公司带来前所未有的发展机遇，也给物流行业带来新的发展契机。在国内，电商企业如雨后春笋般的发展势头一个比一个好，也带动物流业快速发展，与电商发展亦步亦趋，相辅相成。仓储是物流的关键环节之一，只有拥有先进的仓储管理系统，具备完善的仓储调度策略，才能在当前激烈的市场竞争中不断发展壮大。
众多学者认为，当前世界经济处于经济危机后深度调整中，我国经济发展也在转型中跨入新常态。就物流业当前面临的形势来看，物流业的地位正处于快速发展机遇期，也意味着这一时期将是我国物流业发展的完善期和物流发展的拓展期。通过研究该领域的动态，不难发现我国物流业有以下几种发展趋势：
（1）物流平台开始崭露头角，合同物流或将逐渐退出
为了追求利益的最大化，物流业势必面向平台化整合，以替代合同物流。伴随着电子商务的蓬勃发展，新的互联网经济将传统的TOB业务变革成TOC业务，这种散碎的物流服务是促进物流平台建设的有利基础。
（2）在大数据的作用下，物流数据将成为新的价值点
从马云对菜鸟的定位来看，“菜鸟”通过利用和整合获得的数据和信息，找到新的物流成本压缩点。合理分配存储区域，去除物流发展资源利用不充分的大屏障。
从小的方面来看，做好仓储内部调度，合理安排货物储位也是适应物流业发展的需要。因此本文利用遗传算法，研究货物上下架的优化策略，通过改进遗传算法的搜索策略，快速实现货物上下架调度。
2 遗传算法的基本理论
遗传解释了生物能够延续并不断进化的内在机理及其规律，而遗传算法正是诞生于生物科学和计算机科学的交叉点。将遗传进化的某些特质，融合在计算机编程和算法的设计之中，应用于工业控制、管理优化等诸多方面。
2.1 遗传算法的基本原理
遗传算法（Genetic Algorithm，GA）是由美国密歇根（Michigan）大学心理学教授、电子工程和计算机科学教授Holland提出的一种随机自适应全局搜索算法。这种算法模拟的自然界生物遗传进化过程，对优化问题的最优解（近似解）进行不断的迭代搜索。算法在维护一个潜在解的集合（群体），对群体进行优化，在优化过程中，算法引入了选择、交叉、变异等遗传算子。而遗传算法在搜索全局最优解过程中，是一个不断迭代的过程（每次迭代相当于自然界生物遗传的一次进化），直到算法满足终止条件为止。
2.1.1 相关概念
（1）染色体
一个染色体是问题的一个有效解。相对于生物群体中的一个个体。遗传算法的每个染色体，又由多个基因组成。如果将求解问题简化称一个y=fx的函数，那么染色体就可以看作变量x的取值。
（2）基因
可以认为是问题的一个有效解的某一维的值。它的改变会改变一个染色体的适应值，但一般不会引起整个种群发生太大变化。如果x的值由一段编码组成，那么一个编码序列可以看作是一个基因。
（3）适应值
适应值是用来表征一个染色体在群体中的优劣程度。一般来说，一个染色体的值越大，该染色体离最优解就越“近”。适应值就可以看作是这个函数y=fx的应变量y。
（4）评价函数
评价函数是用来计算一个染色体的适应值的大小，判断染色体优劣的一个手段。对应一个函数y=fx的对应法则f。
（5）选择算子
在对群体中若干个染色体进行筛选时，需要依据一定的规则，选出一些适应值较好的染色体进入下一代。那么如何选择，才能让更多、（适应值）更好的染色体从当前过度到下一代，同时保证染色体分布不失均匀，这就取决于选择算子。
（6）交叉算子
在对两个染色体作用时，交换两个染色体的部分基因，希望交换后，能从新的得到的染色体中能产生适应值更好的一个或两个染色体。为此而设计染色体概率性的交换基因片段的一个过程，使得算法能具备良好的全局搜索最优解的能力。
（7）变异算子
对比交叉算子，那么使染色体的某个基因发生变化，可以让算法具备较好的具备搜索最优解的能力。
通常，传统方法在求解某类优化问题采用的都是分析问题的某些特质，简化问题的约束，针对该问题的特质来求解。而Holland教授提出的遗传算法的基本思想，却不是去分析待求解问题的特质，而是采用一种泛化的求解原则。
2.2 遗传算法的基本流程
设计实现遗传算法，通常有以下几个比较重要的步骤：
（1）对群体进行初始化：包括选择适当规模的群体，每个染色体的编码方式，设计准确的适应度评价函数。
（2）群体适应值评价：用评价函数计算染色体适应值，并按照适应值的优劣，对染色体进行排序。
（3）选择种群进入下一代：利用设计好的选择算子，选出适应值较优秀的染色体进入下一代。
（4）交叉操作产生新的染色体：利用交叉算子，产生一些新的染色体。一个染色体通过评价函数的计算，会对应一个适应值。而交叉操作一般设计成不定向的，故交叉操作等可能产生适应值更差的染色体。
（5）变异操作产生新的染色体：利用变异算子，产生一些新的染色体，但是相比较交叉操作，变异后的新染色体，其适应值可能变化不是特别大。
3 遗传算法的应用于仓储优化
现代物流的竞争力在于：如何向客户提供更优质的服务，即服务效率高、物流过程安全。仓储物流是物流的关键环节之一。本文重点研究仓储物流的优化，将智能算法引入仓储物流过程中，实现对现有货位的合理规划。
现假设需将10个货物堆放至一个规格为10×20的空货架中，堆垛机事先通过3D标签获得了各类货物的进出库频次和各个货物的质量。通常来说，我们在货物入库时会考虑一些因素：如质量较大的货物放置在货架的底层，有利于货架重心保持稳定。进出库频次较高的货物放置在靠近出入巷道的位置，同时尽量放置在货架的底层。
货物的质量和出入库频次如表1所示。
3.1 算法实现
（1）种群初始化
初始化产生一个拥有40个个体的种群pop，每个个体的特点就是10个货物随机散落在该10×20的货架中。
5 结 论
对比采用精英保留策略和未采用该策略的10次运行结果，重复10次，计算最佳适应值个体的平均值分别为705.8和765.4，平均减小7.78%。从图5也能直观看出，采用精英保留策略得到的最佳适应值个体的优化值基本优于策略使用前的结果值。因此，通过采用精英保留策略来改进遗传算法，不仅能使得算法在运行过程中绝对收敛（单调趋优），也能改进算法的搜索性能。
参考文献：
[1] 侯景超. 基于改进遗传算法的仓储系统动态货位优化研究[D]. 沈阳：沈阳工业大学（硕士学位论文），2014.
[2] 张飞超. 基于微遗传算法的仓储布局优化方法研究[D]. 锦州：辽宁工业大学（硕士学位论文），2015.
[3] 侯秋琚. 基于遗传算法的中小型仓储配送车辆路径优化策略[J]. 物流技术，2014（11）：210-211，243.
关键词：遗传算法；肝脏CT图像；图像分割；阈值
中图分类号：TP391文献标识码：A文章编号：1009-3044(2011)04-0864-02
Research on Liver CT Image Segmentation Based on Genetic Algorithm
KONG Xiao-rong1, SHI Yan-xin2, LIU Peng1
(1.Department of Computer Technology，Inner Mongolia Medical College, Huhhot 010059; 2.Department of Mathematics and Physics, Xi'an Technology University, Xi'an 710032, China)
Abstract: Genetic Algorithm (GA) is a global optimization and random search algorithm based on natural selection and genetic mechanism. It is suited to dealing with the tradition searching algorithms which cannot solve difficult and complicated problem. And it have great potentialities. First, this paper discusses fundamental principle and primary features of Genetic Algorithm. And it emphases on image segmentation based on GA. Then applying genetic algorithm to select theproper threshold, and it uses maximum entropy method to process liver CT images by segmentation methods. It obtains the results by segmentation experimentation and analyses the results.
Key words: genetic algorithm; liver CT images; image segmentation; threshold value
遗传算法(Genetic Algorithm, GA)的基本思想来源于Darwin的生物进化论和Mendel的群体遗传学，该算法最早是由美国Michigan大学的John Holland教授于20世纪70年代创建，之后，遗传算法的研究引起了国际组织及学者的关注。遗传算法通过模拟生物的遗传进化过程形成一种全局优化概率搜索算法，提供了一种求解复杂系统优化问题的通用框架，可以不依赖于问题的具体领域[1]。近年来，遗传算法已被广泛应用于函数优化、组合优化、生产调度、自动控制、人工智能、人工生命、机器学习、图像处理和模式识别等多个领域，具有巨大的发展潜力。本文主要介绍遗传算法在医学图像处理方面的应用。
1 遗传算法的基本原理
遗传算法是模拟生物进化和遗传机制发展起来的一种全局优化、随机、自适应搜索算法。它模拟了自然界遗传过程中的繁殖、和变异现象，依据适者生存、优胜劣汰的进化原则，利用遗传算子（即选择、交叉和变异）逐代产生优选个体（候选解），最终搜索到适合的个体。
遗传算法的运算对象是由N个个体所组成的集合，称为群体。遗传算法的运算过程是一个群体反复迭代的过程，这个群体不断地经过遗传和进化操作，每次按照优胜劣汰的进化原则将适应度较高的个体以更高的概率遗传到下一代，这样最终在群体中将会得到一个优良的个体，它将达到或接近于问题的最优解[2]。
遗传算法的求解步骤如下：
1）编码：定义搜索空间解的表示到遗传空间解的表示的映射，两个空间的解需一一对应且编码尽量简明。遗传算法把问题的解也称为个体或染色体，个体通常由字符串表示，字符串的每一位称为遗传因子，多个个体形成一个种群。
2）初始化种群 随机产生N个个体组成一个种群，此种群代表一些可能解的集合。GA 的任务是从这些群体出发，模拟进化过程进行优胜劣汰，最后得出优秀的种群和个体，满足优化的要求。
3）设计适应度函数：将种群中的每个个体解码成适合于计算机适应度函数的形式，并计算其适应度。
4）选择：按一定概率从当前群体中选出优良个体，作为双亲用于繁殖后代，一些优良的个体遗传到下一代群体中，适应度越高，则选择概率越大。进行选择的原则是适应性强的优良个体将有更多繁殖后代的机会，从而使优良特性得以遗传。选择是遗传算法的关键，它体现了适者生存原则。
5）交叉：交叉操作是遗传算法中最主要的遗传操作。对于选中的用于繁殖的每一对个体，随机选择两个用于繁殖下一代的个体的相同位置，在选中的位置实行交换。交叉体现了信息交换的思想。
6）变异：从群体中选择一个个体，对于选中的个体按一定的概率随机选择改变串结构数据中某个串的值，即对某个串中的基因按突变概率进行翻转。变异模拟了生物进化过程中的偶然基因突变现象，遗传算法中变异发生的概率很低。对产生的新一代群体进行重新评价、选择、杂交和变异。
7）终止准则：如此循环往复，使群体中最优个体的适应度和平均适应度不断提高，直至最优个体的适应度满足某一性能指标或规定的遗传代数，迭代过程收敛，算法结束。
2 遗传算法在图像分割处理中的应用
在图像处理中，图像分割是图像三维重建的基础，常用的分割方法包括阈值法、边缘检测法和区域跟踪法，其中阈值法是最常用的方法[3]。图像阈值分割算法是利用图像中目标物体与背景灰度上的差异，根据图像灰度值的分布特性把图像分为不同灰度级的目标区域和背景区域，目前已有模糊集法、共生矩阵法、四元树法、最大类间方差法、最佳直方图熵法、最小误差阈值法等多种阈值分割方法。
遗传算法在图像分割中的作用是：帮助现存的图像分割算法在参数空间内搜索参数，或者在候选的分隔空间内搜索最优的分隔方案[3]。在参数空间内搜索参数主要是指利用遗传算法的全局搜索特性优化现有的阈值分割算法，用于帮助确定最佳分割阈值。
3 基于遗传算法的肝脏CT图像分割
本文基于遗传算法选取阈值，采用最大熵原则对肝脏CT图像进行分割。目的是将图像的灰度直方图分成两个或多个独立的类，使得各类熵的总量最大，根据信息论，这样选择的阈值能获得的信息量最大[4]。在图像的灰度直方图中设定一个灰度阈值，可以把图像分成背景和物体两类区域，这是一般的单阈值选择的情况，而设定N个阈值，可以把图像分成N+1类区域[4]。
最大熵分割方法步骤为：
用p0,p1,…,pn表示灰度级的概率分布，如果把阈值设置在灰度级s，将获得两个概率分布，一个包含1到s间的灰度级，另一个包含s+1到n间的灰度级，这两个分布如下：
其中，与每一个分布相关的熵为：
令: (4)
当该函数取最大值时即为图像的最佳分割，用此函数作为遗传算法中的适应度函数。通过遗传算法的设计步骤，取得最佳阈值，既而对人体肝脏中有病灶组织的CT图像进行分割，得到下面分割处理实验结果。
(a) 原图 (b) 分割结果(c)原图 (d) 分割结果
图1 对有病灶肝脏图像进行分割
通过实验结果可以看到，基于遗传算法采用最大熵原则，对人体肝脏CT图像进行分割，能够使选取的阈值获得的信息量比较大，从而原始图像和分割图像之间的信息量差异最小。因此分割后的图像效果明显，具有一定的优势[5]。
但由于医学图像的复杂性和人体的差异性，对人体同一器官不同状况的图像，无法找出一种最为适合的分割方法处理，必须根据具体情况具体分析，针对图像的特点来选取相应的分割算法，才能较好地解决问题。
参考文献：
[1] 田莹,苑玮琦.遗传算法在图像处理中的应用[J].中国图象图形学报,2007,12(3):389-396.
[2] Hsieh puted Tomography Principle, Design, Artifacts and Recent Advances（中文翻译版）[M].北京:科学出版社,2006.
[3] 徐丹霞,郭圣文,吴效明,等. 肝脏CT图像分割技术研究进展[J].医疗卫生装备,2009,30(3):34-36.
关键词：在线测试；组卷策略；遗传算法
中图分类号：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).
关键词：六自由度机械臂 遗传算法 避碰问题 机械臂设计
1.模型分析
首先对模型进行假设，假设已知机器人初始的位姿和目标点，反解机器人在由初始位姿到达目标点的过程中的各个动作？机器人在初始位姿时的各个连杆的相对空间关系是确定的，那么就可以求出连杆坐标系 和连杆坐标系 之间的奇次变换矩阵，本文在这些奇次变换矩阵，设计了另外得求解方法，即利用非线性规划模型求出指尖最接近目标点时的旋转角度，从而可以求出目标点的旋转角度与初始姿态的旋转角度之差 。
假设在初始位置与目标位置之间的区域中有若干个已知大小、形状、方向和位置的障碍物，为了不损坏机器，要求机械臂在运动中始终不能与障碍物相碰（机械臂连杆的粗细自己设定）？由于各个障碍物的大小、形状、方向和位置是已知的，那么就可以确定障碍物的空间范围，只要保证机器人各个连杆滑过的空间范围不与障碍物的空间范围不相交，那么机械臂就不会与障碍物相碰。
2. 模型建立、求解与结果分析
2.1模型建立与求解方法
针对本模型中的六自由度机械臂，可以首先对六个关节点建立了D-H 四点参数坐标系。
图6-1 机械臂初始状态及各个关节点的D-H 四点参数坐标系
然后利用6自由度机械臂的连杆D-H参数，写出各连杆齐次变换矩阵，将各连杆变换矩阵相乘，可得6自由度机器人的总的变换矩阵，由机械臂运动学正解方程可以得出 ，其中 为机械臂指尖坐标
则有：
…………（1-1）
可以看出机械臂指尖坐标 的3个维度上的坐标均是 的方程，若已知机械臂指尖坐标
，根据机械臂运动学逆解方程，就可以反解出旋转角度 。
为了达到精准的目的只能尽可能的接近，为求出最接近的终点处的旋转角度，本文以实际到达点与目标点指尖的距离最小为目标函数，以各个旋转角度的范围作为约束条件，建立模型如下：
…………（1-2）
在Matlab软件下，利用遗传算法就可以求得最接近目标点的终点的旋转角度 ，由于模型（6-2）中目标函数相对较复杂，包含有六个变量的，故本文设计了“转角遗传算法”来求解这个模型。
2.2具体编码过程
1）编码解码
采用等长的十进制进行编码：对可选的关节旋转角的集合进行编码作为一个基因，六个基因组成一个个体。
2）适应度函数
用适应度函数来评价遗传算法时，适应度越大，解的质量越好，本题中以机械臂最终到达点与目标点距离最短的方式最优？
3）遗传算子
a）选择算子
采用比例选择方式：
第一步：先计算出群体中所有个体的适应度的总和；
第二步：其次计算出每个个体的相对适应度的大小，它即为各个个体被遗传到下一代群体中的概率。
b）交叉算子
采用单点交叉算子：
第一步：对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。
第二步：对每一对相互配对的个体，依设定的交叉概率pc在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。
5）运行参数
运用转角遗传算法求出机械臂旋转角度 ，进而可以求出机械臂从初始点到目标点旋转角度的变化量
，机械臂指尖从一个点移动到另一个点可以由不同的动作组合完成，那么本文就可以建立一个数学模型？为了达到快捷目的，本文在建立模型过程中以机械臂动作个数最少为目标函数，约束条件是机械臂经过动作序列控制后，各个关节旋转角度之和为旋转角度的变化量 ，模型如下：
…………（1-3）
以动作幅度 最大为准则求解模型（6-3），得出结果。
3. 结论
（1）在使用四点参数法（D-H法）建立了齐次坐标系的基础上，确定了连杆参数，得到了六自由度机械臂的正运动学方程，并导出其运动学逆解；并设计了具有良好的适应性、较高准确率和障碍处理功能的“转角遗传算法”和“指令系列遗传算法”。
（2）采用“转角遗传算法”解决了机器臂取用工具问题；采用“转角遗传算法”和样条插值解决了沿轨迹焊接问题；采用“指令系列遗传算法”解决了容器内部焊接可能遇到障碍物问题。
参考文献：
[1]机器人控制研究 丁学恭 浙江大学出版社 2006 P19
