遗传算法论文范文10篇

遗传算法论文范文篇1

论文摘要：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结束语

遗传算法论文范文篇2

遗传算法的思想由来已久。早在20世纪50年代，一些生物学家就着手于计算机模拟生物的遗传系统。1967年，美国芝加哥大学的Holland,J.H.教授在研究适应系统时，进一步涉及进化演算的思考，并于1968年提出模式理论。1975年，Holland教授的专著《自然界和人工系统的适应性》问世，全面地介绍了遗传算法，为遗传算法奠定了基础[228]。此后，遗传算法无论在理论研究方面，还是实际应用方面都有了长足发展。

伴随遗传算法的发展，其独特的优越性逐渐被体现出来，且各种理论、方法都得到了进一步发展和完善。但是，遗传算法的实际应用仍然存在着缺陷，具体表现在：

遗传算法在寻优过程中易出现“早熟”、设计变量增多时效率较低以及结构分析时间长，在线功能差。为此，在实际运用中尚需改进，寻找更优秀的算子和编码方法等。目前，改进的方法也各有优劣，有对遗传算法遗传算子进行改进的，也有将遗传算法与其他方法结合起来的。编码方法有二进制编码、多值编码、实值编码、区间值编码、Delta编码等多种编码方法。在执行策略方面有如下几种方法值得注意：遗传算法与模拟退火算法的结合、遗传算法与局部优化方法的结合、并行遗传算法、共存演化遗传算法、混乱遗传算法。

遗传算法的噪声适应性问题。遗传算法主要是针对无噪声的确定性环境设计的，在应用过程中，知识的不确定性、训练样本的错误、人为因素等都可导致问题求解环境包含一个或多个噪声。事实上，噪声是不可避免的，在实际工程测量中，测量得到的静态应变常常会伴有一定的噪声。遗传算法的进化过程是通过适应度大小来进行选择、变异、交*等遗传算子操作，从而对个体进行优胜劣汰。然而在噪声环境下，目标函数或适应度带有噪声，不能反映个体真正的适应度。显然，用有噪声的适应度去进化，其结果可能会被误导。在这种情况下，遗传算法的性能如何，怎样改进，还有待深入研究。

遗传算法论文范文篇3

1．1基因编码设计

编码就是将遗传算法中处理不了的空间参数转换成遗传空间的由基因组成的染色体或个体的过程．其中基因在一定意义上包含了它所代表的问题的解．基因的编码方式有很多，这也取决于要解决的问题本身．常见的编码方式有：二进制编码，基因用0或1表示，通常用于解决01背包问题，如基因A：00100011010（代表一个个体的染色体）；互换编码，主要用于解决排序问题，如调度问题和旅行商问题，用一串基因编码来表示遍历城市顺序，如234517986，表示在9个城市中先经过城市2，再经过城市3，依此类推；树形编码，用于遗传规划的演化编程或表示，其编码的方法就是树形结构中的一些函数，本文采用的是树形编码．

1．2交叉算子设计

交叉运算的含义是参照某种方式和交叉概率，将两组相互配对的个体互换部分基因，生成新个体的过程．交叉运算在遗传算法中起关键作用，是产生新个体的主要方法．交叉操作流程如图1所示．交叉操作首先判定要交叉的基因是否相同，如果相同进行子基因组的交叉，然后再判定交叉是否完成，没完成就继续，完成就退出；如果交叉的基因不相同，就要选择是否依据概率进行基因交换，选择交换就交换其所有的次级基因结构，然后再判定交叉是否完成，选择不交换就直接判定交叉是否完成．

1．3变异算子设计

变异操作从第i个子结构开始．依据变异概率进行第i个基因的变异，如果变异完成，就初始化其所有次级基因结构，如果变异没有完成，就进行子基因组的变异操作．重复操作上面的步骤，直至变异操作结束．

2遗传算法在机械产品设计中的应用

机械产品设计是在研究人机协同方案设计的工作机制上，建立产品的人机分析、人机约束模型和协同方案设计求解模型，确立人机协同系统的同步与异步交互、任务协同、数据共享、数据可视化、易用性等工作机制．

2．1基于遗传算法的数控车床设计

2．1．1数控车床总体设计任务分解

首先确定数控车床总体设计任务，然后根据多层次结构知识进化算法设计要求，将数控车床的总体设计任务分解。

2．1．2数控车床设计的基因编码表示

依据数控车床设计任务分解的结果，可以得出数控车床设计的基因编码图．数控车床设计任务按多层次结构划分为床身、滑台、刀架、尾台、冷却、控制器、电机．每个结构都包含多个选择方案．不同选择方案的有些结构含有子结构，并且这些子结构还可以进一步分解出多种选择方案．通过数控车床设计的基因编码，可看到数控车床设计任务每一层次的关系，包括各层次之间的约束关系．

2．2基于遗传算法的机械产品设计系统应用

遗传算法论文范文篇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

遗传算法论文范文篇5

关键词：遗传算法全局寻优自动化组卷

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.

[3]袁富宇等，多目标相关分类的算法，浙江大学学报，33(3),1999

遗传算法论文范文篇6

关键词全局最优；混合算法；遗传算法；Powell方法

1引言

不可微非线性函数优化问题具有广泛的工程和应用背景，如结构设计中使得结构内最大应力最小而归结为极大极小优化（minmax）问题、数据鲁棒性拟合中采取最小绝对值准则建立失拟函数等。其求解方法的研究越来越受到人们的重视，常用的算法有模式搜索法、单纯形法、Powell方法等，但是这些方法都是局部优化方法，优化结果与初值有关。

近年来，由Holland研究自然现象与人工系统的自适应行为时，借鉴“优胜劣汰”的生物进化与遗传思想而首先提出的遗传算法，是一种较为有效的求不可微非线性函数全局最优解的方法。以遗传算法为代表的进化算法发展很快，在各种问题的求解与应用中展现了其特点和魅力，但是其理论基础还不完善，在理论和应用上暴露出诸多不足和缺陷，如存在收敛速度慢且存在早熟收敛问题[1,2]。为克服这一问题，早在1989年Goldberg就提出混合方法的框架[2]，把GA与传统的、基于知识的启发式搜索技术相结合，来改善基本遗传算法的局部搜索能力，使遗传算法离开早熟收敛状态而继续接近全局最优解。近来，文献[3]和[4]在总结分析已有发展成果的基础上，均指出充分利用遗传算法的大范围搜索性能，与快速收敛的局部优化方法结合构成新的全局优化方法，是目前有待集中研究的问题之一，这种混合策略可以从根本上提高遗传算法计算性能。文献[5]采用牛顿－莱佛森法和遗传算法进行杂交求解旅行商问题，文献[6]把最速下降法与遗传算法相结合来求解连续可微函数优化问题，均取得良好的计算效果，但是不适于不可微函数优化问题。

本文提出把Powell方法融入浮点编码遗传算法，把Powell方法作为与选择、交叉、变异平行的一个算子，构成适于求解不可微函数优化问题的混合遗传算法，该方法可以较好解决遗传算法的早熟收敛问题。数值算例对混合方法的有效性进行了验证。

2混合遗传算法

编码是遗传算法应用中的首要问题，与二进制编码比较，由于浮点编码遗传算法有精度高，便于大空间搜索的优点，浮点编码越来越受到重视[7]。考虑非线性不可微函数优化问题(1)，式中为变量个数，、分别是第个变量的下界和上界。把Powell方法嵌入到浮点编码遗传算法中，得到求解问题(1)如下混合遗传算法：

min(1)

step1给遗传算法参数赋值。这些参数包括种群规模m，变量个数n，交叉概率pc、变异概率pm，进行Powell搜索的概率pPowell和遗传计算所允许的最大代数T。

Step2随机产生初始群体，并计算其适应值。首先第i个个体适应值取为fi’=fmax-fi，fi是第i个个体对应的目标函数值，fmax为当前种群成员的最大目标函数值，i=1,2,…,m。然后按Goldberg线性比例变换模型[2]式(2)进行拉伸。

fi’=a×fi’+b（fi³0）(2)

step3执行比例选择算子进行选择操作。

step4按概率执行算术交叉算子进行交叉操作。即对于选择的两个母体和，算术交叉产生的两个子代为和，是[0，1]上的随机数，1,。

step5按照概率执行非均匀变异算子[8]。若个体的元素被选择变异，，则变异结果为，其中，

(3)

(4)

返回区间[,]里的一个值，使靠近0的概率随代数的增加而增加。这一性质使算子在初始阶段均匀地搜索空间，而在后面阶段非常局部化。是[,]之间的随机数，为最大代数，为决定非均匀度的系统参数。

step6对每个个体按照概率pPowell进行Powell搜索。若个体被选择进行Powell搜索操作，则以作为初始点执行Powell方法得，若则把所得计算结果作为子代，否则，若取=；若取=，1。

step7计算个体适应值，并执行最优个体保存策略。

step8判断是否终止计算条件，不满足则转向step3，满足则输出计算结果。

作为求解无约束最优化问题的一种直接方法，Powell法的整个计算过程由若干轮迭代组成，在每一轮迭代中，先依次沿着已知的n个方向搜索，得一个最好点，然后沿本轮迭代的初始点与该最好点连线方向进行搜索，求得这一阶段的最好点。再用最后的搜索方向取代前n个方向之一，开始下一阶段的迭代。为了保持算法中n个搜索方向是线性无关的，保证算法的收敛性，对替换方向的规则进行改进，在混合法的计算步骤step6中采用文[9]中的改进Powell方法，其求解过程如下：

(1)变量赋初值，n个线性无关的n个方向,,…,，和允许误差ε>0，令k=1。

(2)令，从出发，依次沿方向,,…,作一维搜索，得到点,,…,求指标m，使得-=max{-}，令。若ε，则Powell方法计算结束，否则，执行(3)。

(3)求使得=min，令==，若，则Powell方法计算结束，得点；否则，执行(4)。

(4)若，令，否则令()，然后置，转(2)。

3算例

T[-500,500]

图1函数f(x)特性示意图

函数f(x)有相当多的极小点,全局极小点是=-420.97，=1,2,…,，最优值为-837.97；次最优点为={(,,…,)：=-420.97,,=302.52}，=1,2,…,，次优值-719.53。变量个数n=2时函数f(x)特性如图1示。程序编制和运行环境采用FortranPowerStation4.0，随机数由内部随机函数产生，在奔腾133微机上运行。

采用改进的Powell方法计算100次，初值在区间[-500,500]内随机产生，只有6次（即以概率0.06）搜索到全局最优，计算成功的概率极低。

Holland建立的标准（或简单）遗传算法，其特点是二进制编码、赌轮选择方法、随机配对、一点交叉、群体内允许有相同的个体存在。取种群规模m=30，交叉概率pc=0.95、变异概率pm=0.05，最大进化代数T=1000，每个变量用串长为L=16的二进制子串表示。二进制编码比浮点编码遗传算法计算精度低，对于标准遗传算法以目标函数小于-800为搜索成功，标准遗传算法运行100次。当取最大进化代数为T=200时，40次（以概率0.40）搜索到全局最优，平均计算时间为0.51秒；当取T=500时，51次（以概率0.51）搜索到全局最优，平均计算时间为1.13秒。

采用本文混合法计算，取m=30，pc=0.85、pm=0.2，T=100，进行Powell搜索的概率pPowell取不同值，混合法运行100次，计算结果见如表1。对于这个具有多极值的算例，多次计算表明pPowell=0.3时，混合法能以完全概率搜索到全局最优的准确值，但是此时混合法计算时间约为标准遗传算法取T=500时计算时间的4/5。对应的浮点编码遗传算法，取m=30，pc=0.85、pm=0.2，T=100，运行100次，82次（以概率0.82）搜索到全局最优（如表1中PPowell=0所示），计算时间约为标准遗传算法取T=500时计算时间的1/8，但是搜索到全局最优的概率却远远高于标准遗传算法。

表1pPowell取不同值时混合法的计算结果

PPowell

0.0

0.02

0.05

0.1

0.2

0.3

求得最优解的次数

82

85

89

94

98

100

求得最优解的概率

0.82

0.85

0.89

0.94

0.98

1.00

平均计算时间/秒

0.14

0.20

0.31

0.47

0.68

0.87

4结束语

针对不可微函数的全局优化问题，本文提出一种把Powell方法与浮点编码遗传算法相结合的混合遗传算法，该算法兼顾了遗传算法全局优化方面的优势和Powell方法局部搜索能力较强的特点，提高求得全局解的概率。计算结果表明混合法优于遗传算法和Powell法，可以可靠地搜索到具有多个局部极值的函数优化问题的全局解。由于计算中只用到函数值信息，本文混合法不仅适用于不可微函数优化问题，也适合可微函数全局优化问题。

参考文献

[1]周明，孙树林．遗传算法原理及应用[M]．北京：国防工业出版社，1999．

[2]GoldbergDE.Geneticalgorithmsinsearch,optimizationandmachinelearning[M].Reading,Ma:AddisonWesley,1989．

[3]孟庆春，贾培发．关于Genetic算法的研究及应用现状[J]．清华大学出版社，1995，35(5)：44－48．

[4]戴晓晖，李敏强，寇纪松．遗传算法理论研究综述[J]．控制与决策，2000，15(3)：263－268．

[5]LinW，Delgado-FriasJG．HybridNewton-Raphsongeneticalgorithmfortravelingsalesmanproblem[J].Cyberneticsandsystems,1995，26(5)：387-412．

[6]赵明旺．连续可微函数全局优化的混合遗传算法[J]．控制与决策，1997，12(5)：589－592．

[7]GoldbergDE．Real-CodeGeneticAlgorithm,VirtualAlphabetsandBlocking[J].ComplexSystems，1991，5：139-167．

[8]MichalewiczZ．Amodifiedgeneticalgorithmforoptimalcontrolproblems[J]．Computersmath.Application，1992，23（12）：83-94．

[9]陈宝林．最优化理论与算法[M]．北京：清华大学出版社，1989．

[10]俞红梅．全过程系统能量综合方法的研究[D]．大连理工大学博士学位论文，1998．

Hybridapproachforglobaloptimaofindifferentiablenonlinearfunction

遗传算法论文范文篇7

关键词全局最优；混合算法；遗传算法；Powell方法

1引言

不可微非线性函数优化问题具有广泛的工程和应用背景，如结构设计中使得结构内最大应力最小而归结为极大极小优化（minmax）问题、数据鲁棒性拟合中采取最小绝对值准则建立失拟函数等。其求解方法的研究越来越受到人们的重视，常用的算法有模式搜索法、单纯形法、Powell方法等，但是这些方法都是局部优化方法，优化结果与初值有关。

近年来，由Holland研究自然现象与人工系统的自适应行为时，借鉴“优胜劣汰”的生物进化与遗传思想而首先提出的遗传算法，是一种较为有效的求不可微非线性函数全局最优解的方法。以遗传算法为代表的进化算法发展很快，在各种问题的求解与应用中展现了其特点和魅力，但是其理论基础还不完善，在理论和应用上暴露出诸多不足和缺陷，如存在收敛速度慢且存在早熟收敛问题[1,2]。为克服这一问题，早在1989年Goldberg就提出混合方法的框架[2]，把GA与传统的、基于知识的启发式搜索技术相结合，来改善基本遗传算法的局部搜索能力，使遗传算法离开早熟收敛状态而继续接近全局最优解。近来，文献[3]和[4]在总结分析已有发展成果的基础上，均指出充分利用遗传算法的大范围搜索性能，与快速收敛的局部优化方法结合构成新的全局优化方法，是目前有待集中研究的问题之一，这种混合策略可以从根本上提高遗传算法计算性能。文献[5]采用牛顿－莱佛森法和遗传算法进行杂交求解旅行商问题，文献[6]把最速下降法与遗传算法相结合来求解连续可微函数优化问题，均取得良好的计算效果，但是不适于不可微函数优化问题。

本文提出把Powell方法融入浮点编码遗传算法，把Powell方法作为与选择、交叉、变异平行的一个算子，构成适于求解不可微函数优化问题的混合遗传算法，该方法可以较好解决遗传算法的早熟收敛问题。数值算例对混合方法的有效性进行了验证。

2混合遗传算法

编码是遗传算法应用中的首要问题，与二进制编码比较，由于浮点编码遗传算法有精度高，便于大空间搜索的优点，浮点编码越来越受到重视[7]。考虑非线性不可微函数优化问题(1)，式中为变量个数，、分别是第个变量的下界和上界。把Powell方法嵌入到浮点编码遗传算法中，得到求解问题(1)如下混合遗传算法：

min(1)

step1给遗传算法参数赋值。这些参数包括种群规模m，变量个数n，交叉概率pc、变异概率pm，进行Powell搜索的概率pPowell和遗传计算所允许的最大代数T。

Step2随机产生初始群体，并计算其适应值。首先第i个个体适应值取为fi’=fmax-fi，fi是第i个个体对应的目标函数值，fmax为当前种群成员的最大目标函数值，i=1,2,…,m。然后按Goldberg线性比例变换模型[2]式(2)进行拉伸。

fi’=a×fi’+b（fi³0）(2)

step3执行比例选择算子进行选择操作。

step4按概率执行算术交叉算子进行交叉操作。即对于选择的两个母体和，算术交叉产生的两个子代为和，是[0，1]上的随机数，1,。

step5按照概率执行非均匀变异算子[8]。若个体的元素被选择变异，，则变异结果为，其中，

(3)

(4)

返回区间[,]里的一个值，使靠近0的概率随代数的增加而增加。这一性质使算子在初始阶段均匀地搜索空间，而在后面阶段非常局部化。是[,]之间的随机数，为最大代数，为决定非均匀度的系统参数。

step6对每个个体按照概率pPowell进行Powell搜索。若个体被选择进行Powell搜索操作，则以作为初始点执行Powell方法得，若则把所得计算结果作为子代，否则，若取=；若取=，1。

step7计算个体适应值，并执行最优个体保存策略。

step8判断是否终止计算条件，不满足则转向step3，满足则输出计算结果。

作为求解无约束最优化问题的一种直接方法，Powell法的整个计算过程由若干轮迭代组成，在每一轮迭代中，先依次沿着已知的n个方向搜索，得一个最好点，然后沿本轮迭代的初始点与该最好点连线方向进行搜索，求得这一阶段的最好点。再用最后的搜索方向取代前n个方向之一，开始下一阶段的迭代。为了保持算法中n个搜索方向是线性无关的，保证算法的收敛性，对替换方向的规则进行改进，在混合法的计算步骤step6中采用文[9]中的改进Powell方法，其求解过程如下：

(1)变量赋初值，n个线性无关的n个方向,,…,，和允许误差ε>0，令k=1。

(2)令，从出发，依次沿方向,,…,作一维搜索，得到点,,…,求指标m，使得-=max{-}，令。若ε，则Powell方法计算结束，否则，执行(3)。

(3)求使得=min，令==，若，则Powell方法计算结束，得点；否则，执行(4)。

(4)若，令，否则令()，然后置，转(2)。

3算例

T[-500,500]

函数f(x)有相当多的极小点,全局极小点是=-420.97，=1,2,…,，最优值为-837.97；次最优点为={(,,…,)：=-420.97,,=302.52}，=1,2,…,，次优值-719.53。变量个数n=2时函数f(x)特性如图1示。程序编制和运行环境采用FortranPowerStation4.0，随机数由内部随机函数产生，在奔腾133微机上运行。

采用改进的Powell方法计算100次，初值在区间[-500,500]内随机产生，只有6次（即以概率0.06）搜索到全局最优，计算成功的概率极低。

Holland建立的标准（或简单）遗传算法，其特点是二进制编码、赌轮选择方法、随机配对、一点交叉、群体内允许有相同的个体存在。取种群规模m=30，交叉概率pc=0.95、变异概率pm=0.05，最大进化代数T=1000，每个变量用串长为L=16的二进制子串表示。二进制编码比浮点编码遗传算法计算精度低，对于标准遗传算法以目标函数小于-800为搜索成功，标准遗传算法运行100次。当取最大进化代数为T=200时，40次（以概率0.40）搜索到全局最优，平均计算时间为0.51秒；当取T=500时，51次（以概率0.51）搜索到全局最优，平均计算时间为1.13秒。

采用本文混合法计算，取m=30，pc=0.85、pm=0.2，T=100，进行Powell搜索的概率pPowell取不同值，混合法运行100次，计算结果见如表1。对于这个具有多极值的算例，多次计算表明pPowell=0.3时，混合法能以完全概率搜索到全局最优的准确值，但是此时混合法计算时间约为标准遗传算法取T=500时计算时间的4/5。对应的浮点编码遗传算法，取m=30，pc=0.85、pm=0.2，T=100，运行100次，82次（以概率0.82）搜索到全局最优（如表1中PPowell=0所示），计算时间约为标准遗传算法取T=500时计算时间的1/8，但是搜索到全局最优的概率却远远高于标准遗传算法。

表1pPowell取不同值时混合法的计算结果

PPowell

0.0

0.02

0.05

0.1

0.2

0.3

求得最优解的次数

82

85

89

94

98

100

求得最优解的概率

0.82

0.85

0.89

0.94

0.98

1.00

平均计算时间/秒

0.14

0.20

0.31

0.47

0.68

0.87

4结束语

针对不可微函数的全局优化问题，本文提出一种把Powell方法与浮点编码遗传算法相结合的混合遗传算法，该算法兼顾了遗传算法全局优化方面的优势和Powell方法局部搜索能力较强的特点，提高求得全局解的概率。计算结果表明混合法优于遗传算法和Powell法，可以可靠地搜索到具有多个局部极值的函数优化问题的全局解。由于计算中只用到函数值信息，本文混合法不仅适用于不可微函数优化问题，也适合可微函数全局优化问题。

参考文献

[1]周明，孙树林．遗传算法原理及应用[M]．北京：国防工业出版社，1999．

[2]GoldbergDE.Geneticalgorithmsinsearch,optimizationandmachinelearning[M].Reading,Ma:AddisonWesley,1989．

[3]孟庆春，贾培发．关于Genetic算法的研究及应用现状[J]．清华大学出版社，1995，35(5)：44－48．

[4]戴晓晖，李敏强，寇纪松．遗传算法理论研究综述[J]．控制与决策，2000，15(3)：263－268．

[5]LinW，Delgado-FriasJG．HybridNewton-Raphsongeneticalgorithmfortravelingsalesmanproblem[J].Cyberneticsandsystems,1995，26(5)：387-412．

[6]赵明旺．连续可微函数全局优化的混合遗传算法[J]．控制与决策，1997，12(5)：589－592．

[7]GoldbergDE．Real-CodeGeneticAlgorithm,VirtualAlphabetsandBlocking[J].ComplexSystems，1991，5：139-167．

[8]MichalewiczZ．Amodifiedgeneticalgorithmforoptimalcontrolproblems[J]．Computersmath.Application，1992，23（12）：83-94．

遗传算法论文范文篇8

关键字：频率分配遗传算法GECP组合优化

1.通信网频率分配问题的背景

无线通信设备之间通过相互发射电磁波达成信息沟通。相互通信的设备之间使用特定的频率（信道）构成无线通信链路。由于电磁波的自然特性，无线通信设备发射的电磁波可能对位于附近、满足一定功率和频率条件的其它设备形成干扰。频率分配（FAP）的目的就是给工作在一定地域内的无线通信设备指定使用的工作频率(或信道)，使所有设备都以尽量小的概率被干扰，从而使整个网络的可用性得到优化。FAP可以描述为：对N个给定的待分配工作频率的链路，设G={S1,S2,…Sn}为所有状态构成的解空间，C(si)为状态si对应的目标函数值，寻找最优解s*，使任意si∈G，C(s*)=minC（si）。因此FAP是一种组合优化问题。

具体设备频率分配方法虽然会随着设备的工作方式（单工、双工）、工作频段、天线类型、信号的调制解调方式的不同而有所区别，但是大部分频率分配算法都可以转换为等价的图的边着色问题。从图论算法理论上讲，图的广义边着色问题是NPC问题[7]，也就是说无法在多项式时间内求得问题的最优解。例如对于存在n条边的无向图，使用c种颜色对其着色，在没有其它约束条件下，其解空间是cn。即使在不考虑颜色重复使用（c>n）的情况下，其解空间也达到n!。这两者都是超越数，在c和n的值较大的情况下想利用穷举搜索的方法求得问题的最优解在时间上是不可行的。

在工程实践中许多NPC问题使用一些使用的近似算法得到问题的可行解。这些方法包括[]：只对问题的特殊实例求解；动态规划（DP）或者分支界限算法（BC）；概率算法；求近似解；启发式算法（HeufisticAlgorithms）等。这些方法的和核心是分割问题的解空间，按照特定规则搜索典型解作为次最优解。

对于FAP问题国内外许多学者进行了深入的研究，提出许多解决问题的方法。文献[4]在对FAP进行理论分析的基础上给出了几种常用算法的框架，这些算法包括：最小-最后次序查找算法，贪心T着色算法、模拟退火算法（SA）、列表寻优算法（TS）、遗传算法（GA）、神经网络（NN）多面体算法等，并指出各种算法有各自的适用范围；文献[2]提出了利用启发式的蚂蚁算法，并对解决CELAR、GRAPH、PHILADELPHIA上的几类问题同TS和SA算法进行了比较；文献[1]比较了SA、TS、GA、VDS（variable–depthsearch）、BC等算法的性能。文献[7]利用GECP理论对存在禁用频率的异频双工设备的频率分配给出工程上的实用算法；文献[9]则采用了BC方法频率分配的全排列算法进行了优化。本文将探讨如何遗传算法解决FAP问题。

2.遗传算法在频率分配问题中的适用性

2．1遗传算法的原理

遗传算法(GeneticAlgorithmsGA)是根据生物学上的染色体基因因子构成机制而产生的。1975年Holland教授首次提出了GA的思想，从而吸引了大批的研究者，迅速推广到优化、搜索、机器学习等方面。遗传算法是一种全局优化算法，其仅以目标函数值为搜索依据，通过群体优化搜索和随机执行基本遗传运算，实现遗传群体的不断进化，适合解决组合优化问题和复杂非线性问题[6]。

利用遗传算法解最优化问题，首先应对可行域中的点进行编码（一般采用二进制编码），然后在可行域中随机挑选一些编码组成作为进化起点的第一代编码组，并计算每个解的目标函数值，也就是编码的适应度。接着就像自然界中一样，利用选择机制从编码组中随机挑选编码作为繁殖过程前的编码样本。选择机制应保证适应度较高的解能够保留较多的样本；而适应度较低的解则保留较少的样本，甚至被淘汰。在接下去的繁殖过程中，遗传算法提供了交叉和变异两种算子对挑选后的样本进行交换。交叉算子交换随机挑选的两个编码的某些位，变异算子则直接对一个编码中的随机挑选的某一位进行反转。这样通过选择和繁殖就产生了下一代编码组。重复上述选择和繁殖过程，直到结束条件得到满足为止。进化过程最后一代中的最优解就是用遗传算法解最优化问题所得到的最终结果。

实践表明，遗传算法解最优化问题的计算效率比较高、适用范围相当广。为了解释这一现象，Holland给出了模式定理。所谓模式，就是某些码位取相同值的编码的集合。模式定理说明在进化过程的各代码中，属于适应度高、阶数低且长度短的图式的编码数量将随代数以指数形式增长[6]。最近的研究则表明，上述遗传算法经适当改进后对任意优化问题以概率1收敛于全局最优解[5]。

2．2遗传算法的基本结构

在遗传算法中，将问题的求解的过程，看成一个在候选解空间寻找满足问题要求的解或近似解的搜索过程。遗传算法的重点在适应规划和适应度量方面。遗传算法的适应规划用于指导算法怎么样在空间进行搜索，一般采用遗传算子(或称遗传操作)诸如交配(Crossover)和变异(Mutation)等，以及模拟自然过程的选择机制，采用计算适应值的方法来评估一个候选解的优劣。

遗传算法求解问题的基本步骤可以描述如下：

1.首先生成一组初始的候选解群体(假设为N个候选解个体)，称为第0代；

2.计算群体中各个候选解的适应值；

3.如果有候选解满足算法终止条件，算法终止，否则继续4；

4.根据交配概率，将候选解群体中的个体随机两两配对，进行交配操作以生成新的候选解；

5.根据变异概率，对4中生成的候选解群中的每个个体进行变异操作；

6.使用选择机制形成新一代候选解；转2。

GA算法具有下述特点：GA是对问题参数的编码组进行，而不是直接对参数本身；GA的搜索是从问题解的编码组开始搜索，而不是从单个解开始；GA使用目标函数值（适应度）这一信息进行搜索，而不需导数等其他信息；GA算法使用的选择、交叉、变异这三个算子都是随机操作，而不是确定规则。

遗传算法通过编码和遗传操作，达到了处理的并行性，可以同时处理群体中的多个个体，即同时对搜索空间内的多个解进行评估，具有较好的全局搜索性能，减少了限于局部最优解的风险。

3.遗传算法用于频率分配

3．1算法的基本流程

采用遗传算法的FAP基本流程如下图：3．2遗传算子的选择

3．2．1选择算子

选择算子在父代群体中选出父体和母体。生物界中，父母亲素质比较高的其后代素质高的概率也大。模拟这种现象，在FAP中选择算子采用轮赌算法实现。

轮赌算法流程如下：

sum=0;i=0;

wheelpos=rand()*sumfitness;

for(sum<wheelpos&&i<pop-size)

｛

i++;

if(i≥pop-size)

｛

sum=0;i=0

wheelpos=rand()*sumfitness;

｝

j=rand()*pop-size;

sum+=fitness［j］;

｝

returnj;

3．2．2交叉算子

交叉算子让父体和母体互相交换某部分基因而产生下一代个体的雏形，起全局搜索的作用。交叉算子通常有单点交叉、双点交叉、多点交叉等等。在频率自动分配的算法中，为了不破坏基因段内部频点间的关系，采用单点交叉和双点交叉比较合适。此外，在生物界中并不是两个个体相遇了就一定会结合，模拟此现象，引入交叉因子pc。

其基本流程如下：

//flip函数中，产生一个0到1的随机数，若小于pc，则返回1，否则返回0

if(flip(pc))

crossover1(mother,father);

elseif(flip(pc))

crossover2(mother,father);

else

copy(mother);

copy(father);

3．2．3变异算子

变异算子对后代个体的某些基因进行变异，起局部搜索的作用.生物界中，父母的染色体交叉后产生后代个体的染色体雏形，这个雏形在成长过程中会发生基因的变异，正是这种变异使得下一代的群体中会出现各种特征的个体.另外，生物界中并非每个基因都会变异，模拟此现象，引入变异因子pm，使用方法与交叉因子类似。

其基本流程如下：

while(allfrequentpoint)

{

if(flip(pm))mutate(frequentpoint)；}

4.工程上需要注意的问题

4．1初始候选种群

由于遗传算法和其它启发式算法一样，不对全部解空间进行穷举搜索，因此初始的候选解群体的选择会对得到最终解的速度和质量有影响。初始的候选解群体在解空间内分布得越均匀，它们拥有的遗传基因就越有代表性。实践中采用文献[7]的GECP得到以各个顶点为主顶点的可行解作为初始候选种群。

4．2编码方案

编码就是用一种数字排列方案来表示问题的解的方法，利用编码将问题的解空间映射到GA算法的编码空间。编码方案的选择依赖于问题的性质，并影响到算法内操作的设计，是影响算法性能的重要因素。常见的编码方案有二进制编码、十进制编码、实数编码等。频率分配问题适合采用十进制编码方案，每个码表示一条通信链路，码值表示分配的信道编号。

4．3适配值函数

适配值函数对个体（频率分配方案）进行评价，也是优化过程发展的依据。可以采用如下方式来计算适应度：

fitness=1000/Σ(pri×seperate(Freq))。

其中：

pri是节点的加权值；

函数seperate(Freq)是节点中各条链路发频率同其它链路的收频率间隔的和；

参考文献：

[1]RobertA.Murphey,PanosM.Pardalosetc,FrequencyAssignmentProblems,Handbookofcombinatorialoptimization,KluwerAcademicPublishers,1999

[2]VittorioM.,AntonellaC.,AnANTSHeuristicfortheFrequencyAssignmentProblem,www.csr.unibo.it

[3]JoeBater,PeterJeavons,DavidCohen,ArethereoptimalreusedistanceconstraintsforFAPswithrandomTxplacement?,CSD-TR-98-01,CSRoyalHollowayUni.OfLondon,1998

[4]K.IAardal,C.A.J.Hurkens,J.K.etc.AlgorithmsforFreequencyAssignmentProblems,CWIQuarterly,Vol9(1&2),1996

[5]王凌：《智能优化算法及其应用》清华大学出版社2001

[6]陈国良等：《遗传算法及其应用》人民邮电出版社1996

[7]孙俊柏：禁用频点、频段下野战通信网的频率分配中国科学技术大学硕士学位论文1998

遗传算法论文范文篇9

论文关键词:投影寻踪法；生态城市评价；石家庄市

“生态城市”是20世纪80年代产生的一个全新概念，指将“生态系统”思想引入到城市建设和管理的过程中。它最早是由前苏联生态学家0．Yanitsky1971年在联合国教科文组织发起“人与生物圈计划(MAB)”时提出的。之后，很多学者都对其进行了研究，并给出了定义。如1984年城市生态学家0．Yanistky提出，生态城市是指自然、技术、人文充分融合，物质、能量、信息高效利用，人的创造力和生产力得到最大限度的发挥，居民的身心健康和环境质量得到维护，一种生态、高效、和谐的人类聚居新环境。美国生态学家R．Richard认为，生态城市即生态健康的城市，是低污、紧凑、节能、充满活力并与自然和谐共存的聚居地。虽然生态城市的概念尚处于不停的争论、探索、修改、完善之中，但在原则问题上，人们已经达成一些基本共识：“生态城市”的核心思想是它的区域整体观和可持续发展的生态观，且一般要求具有以下几种特性：和谐性、高效性、持续性、整体性、区域性、结构合理以及关系协调。

1生态城市测评方法概述

生态城市评价是生态城市建设的基础工作，一套科学客观的生态城市评价体系应具备以下功能：①帮助在操作层次理解什么是生态城市；②使城市建设转向生态城市建设；③衡量生态城市建设的趋势和速度，综合衡量生态城市各子系统的协调程度。

具体到测评方法而言，不同的测评方法从不同的角度描述指标体系的属性，由于各种方法的机理不同，方法的层次属性相异，在应用不同的测评方法时，测评的结果也存在差异。因此，要反映一个城市的全貌，体现上述生态城市的内涵要求，必须从多角度、全方位进行研究，这样得出的结论才能体现城市系统的本质和原貌。在数学分析方面，系统科学专家运用定量分析技术开发了几十种测评方法。目前，常用的主要有层次分析法(AnalyticHierarchyProcess，AHP)，因子分析法(FactorAnalysis，FA)以及网络层次分析法(ANP)等。但是，这些方法都有其局限性。层次分析法对应生态城市评价是不适用的，因为指标之间是不完备、不互斥的；因子分析法是较常用且简单的方法，能够反映生态城市建设的大概状况，但会丢失部分信息；网络分析法能够比因子分析法更全面地反映生态城市的概况，但其前提是各因子之间的关系比较清晰，这一过程需要作大量的研究工作。该文借鉴在水质评价中得到广泛应用，并被实践证明比较科学、合理的评价方法——投影寻踪评价法，将其应用到生态城市评价体系中。

2基于实数遗传算法的投影寻踪评价法

投影寻踪评价方法是针对目前常规的系统综合评价方法的形式化、数学化等局限性，以及对某些高维、非线性、非正态评价问题的适应能力不强等不足之处，提出的一种由样本数据驱动的探索性数据分析方法。该方法的思路是把高维数据通过某种组合投影到低维子空间上，对于投影到的构形，采用投影指标函数(目标函数)来描述投影值暴露原系统综合评价某种分类排序结构的可能性大小，寻找出使投影指标函数达到最优(即能反应高维数据结构或特征)的投影值。然后根据该投影值来分析高维数据的分类结构特征(即寻求投影寻踪聚类评价模型)。其中，投影指标函数的构造及其优化问题是运用投影寻踪方法成功的关键。

遗传算法是解决函数优化问题的数据挖掘方法。遗传算法源于对生物系统所进行的计算机模拟研究，是Michigan大学的Holland教授及其学生根据生物模拟技术创造出来的自适应概率优化技术。遗传算法通过计算机编码实现模拟生物进化过程中的复制、交叉、变异、显性、倒位等遗传过程，实现系统设计、函数优化等复杂过程。它与传统的算法不同，传统的优化算法是基于1个单一的度量函数(评估函数)的梯度或较高次统计，以产生1个确定性的试验解序列。遗传算法不依赖于梯度信息，而是通过模拟自然进化过程来搜索最优解，它利用某种编码技术，作用于称为染色体的数字串，模拟由这些串组成的群体的进化过程。遗传算法是通过有组织、随机的信息交换来重新组合那些适应性好的串，生产新的串的群体。

基于实数的加速遗传算法(RAGA)的投影寻踪聚类评价(ProjectionpursuitclassiifcationevaluationmodelbasedonRAGA，PPCE)模型的分析过程包括以下4个步骤。

步骤1：评价指标值的归一化处理。

步骤2：构造投影指标函数。投影寻踪方法就是把P维数据综合成l维投影值。然后根据1维投影值进行分类。在求投影值时，要求投影值的散布特征为：局部投影点尽可能密集，最好凝聚成若干个点团；而在整体上，投影点团之间要尽可能散开。基于此，构造投影指标函数。

步骤3：优化投影指标函数。当各指标值的样本集给定时，投影指标函数只随着投影方向的变化而变化。不同的投影方向反应不同的数据结构特征，最佳投影方向就是最大可能暴露高维数据某类特征结构的投影方向，可通过求解投影指标函数最大化问题来估计最佳投影方向。这是一个复杂非线性优化问题，用常规优化方法处理较困难。模拟生物优胜劣汰规则与群体内部染色体信息交换机制的加速遗传算法是一种通用的全局优化方法，用它来求解上述优化问题较简便和有效。

步骤4：排序分类。根据步骤3求得投影值，并进行排序分类。

3投影寻踪评价法在石家庄生态城市测评中的应用

3．1数据的收集和处理指标体系含5个子系统，63个指标分量。数据来源主要有《石家庄统计年鉴》(2001—2007)，《石家庄年鉴》(2001～2006)，《中国环境年鉴》(2001～2005)，《河北环境统计公报>(2oo2—2007)，《石家庄市国民经济和社会发展统计公报》(2005～2OO7)，石家庄市卫生信息网，石家庄市商务局，河北省环境保护局公众网，中国生态网，石家庄发展和改革委员会网站，地方志网站等。对于个别变量在某些年份缺失的问题，可以通过回归分析法、均值法或者成果参照法来估计指标值。如果超过3年不可获得，则将其去掉。对某些不容易定量的指标的量化问题，本着实用的角度，这里采用评价等级的方法确定。

3．2数据处理原始数据在进行分析之前，要先进行无量纲化处理。该文将原始数据处理为0～1的无量纲数据。

3．3对各子系统的评估利用MATIAB软件实现基于实数遗传算法的计算。下面是对石家庄生态城市各子系统的计算分析结果。

(1)资源支持子系统。2OO2～2003年资源支持发展平稳，2OO4～2OO7年，该资源系统得到了较大发展。科技水平、科技资源、文化状况和城市基础设施建设是主要影响指标。

(2)经济发展能力子系统。除2001年经济发展能力倒退之外，2OO02005年经济发展能力一直以较快的速度发展，2005——2O07年发展能力平稳。经济竞争力、经济运行效率、经济水平和经济推动力是主要影响指标。

(3)社会支持系统。除2001年社会支持系统得分有所下降外，其他年份均有所增长，2002年有1个陡增。社会保障、住房、信息获取能力和社会公平是主要影响指标。公务员之家

(4)环境支持子系统。2000～2O02年环境状况一直处于下降趋势，2003～2037年环境不断改善。气候变化、地表水、噪声和大气环境是主要影响指标。

(5)体制与管理子系统。2000～2001年得分下降，到2002年得分有1个陡增，随后发展水平比较平稳。科技投入、财政能力、环境管理和战略实施是主要影响指标。

3．4对石家庄市的综合评价为了更全面地分析石家庄生态城市的建设状况，笔者对63个指标变量进行了综合投影寻踪法分析。石家庄市综合评价得分(即投影值)为：

Zmax=(1．8802，1．8564，2．3935，2．8093，3．3172，4．1416，4．5966，5．6911)

石家庄生态城市评价体系测评得分排序为：2001年<2000年<2002年<2003年<2OO4年<2005年<20O6年<2O07年。即从2132年开始石家庄生态城市建设水平一直处于不断提高中。根据最佳投影方向n，可进一步评价各指标对评价结果的影响程度。结果显示，科技水平、科技投入、经济竞争力和信息获取能力对生态城市建设的影响最大，其次是城市基础设施、资源利用率、经济推动力、综合管理能力、环境管理能力和水质，再次是文化状况、教育水平和大气状况等，其他指标影响较小。

遗传算法论文范文篇10

关键词：并行计算；均匀设计；Powell算法；全局最优化

0引言

最优化理论方法是应用数学的一门分支，研究决策问题的最佳选择，构造寻找最佳解的计算方法，探讨这些计算方法的理论性质及计算表现。目前，求解线性规划、非线性规划、随机规划、非光滑规划、多目标规划、组合优化等各种最优化问题的新方法不断涌现。除了自然科学的各个领域之外，在建筑设计、金融设计、医药设计、生产管理、交通运输等诸多方面均涉及最优化的应用。随着高速计算机的普及和优化方法的不断进步，规模越来越大的优化问题得到解决。

面对最优化问题，目前的困难主要表现在两个方面：①目标函数常常多峰，随着优化问题规模的增大，局部最优解的数目将会迅速增加，往往得到的是局部最优解，而不能得到全局最优解。如何有效地跳出局部最优点而又不大幅度地增加计算代价，是目前的一个难题。②许多在串行计算环境下的最优化算法并不适合于并行环境，并行化难度大。

首先利用均匀设计具有使实验点高维空间均匀分散的特点，与Powell算法结合，并适当改进，经过经典的全局最优化函数测试发现它能够跳出局部最优陷阱，从而准确地找到全局最优点。最后，对算法的时间空间复杂度进行了测试，数据统计显示本文算法时间复杂度与计算问题需要考虑的因素个数的二次方和布点数成线性关系，空间复杂度与因素个数和布点数成线性关系。对算法进行了并行化，经测试得知并行效率很高。该算法具有很好的求解大型优化问题的潜力。

1背景介绍

1．1全局最优化模型

对于解决实际优化问题，特别是对于科学与工程计算问题，全局优化方法非常重要。全局最优化问题可以描述成如下的数学模型：

1．2均匀设计

均匀设计是20世纪80年代，由我国科学家方开泰和王元开创的一种全新的试验设计方法。其思路是让试验点在试验范围内充分均匀分散，这种从均匀性出发的设计被称为均匀设计。

均匀设计主要通过对均匀设计表的设计来体现。均匀设计表是一种规格化的表格，是均匀试验设计的基本工具。均匀设计表有一个代号Un(qs)。其中U表示均匀设计，s表示因素个数，q为试验水平数，n表示所作试验次数。均匀设计的最大特点是试验次数等于最大水平数，而正交设计试验次数是实验水平数的平方，这也是均匀设计的优势。

1．3Powell算法

Powell算法是一种方向集方法，假设计算的问题是m因数，它取m个m维的共轭向量，并沿每一向量的方向进行最优值搜索，那么任何一个m元函数均可用一维搜索方法求其最优值。它专门针对当目标函数特别复杂，因而没有办法掌握目标函数特性的一类优化问题，在实际工程与科学计算中十分有用。它的主要计算步骤如下：

2并行算法的实现及性能分析

2．1将均匀设计思想与Powell算法结合

均匀设计可以根据均匀设计原则在可行域内均匀分布优化初始点，而Powell算法具有很好的求得局部最优值能力。本文将上述两者结合起来设计寻求模型的全局最优解方法。该方法的基本思路如下：

（1)采用均匀设计方法，在优化模型的设计变量空间内均匀分布一系列点，这些点在变量空间内均匀分散。

（2)将可行域内的上述系列布点作为Powell优化计算的初始点，通过Powell算法分别从各初始点开始对模型(1)进行优化计算，得到优化模型的一系列局部最优点和局部最优值。

（3)取所有局部最优值中的最优值，认为在一定程度上获得了优化模型(1)的全局最优解。

显然，均匀布点数n越多，所得的结果越逼近全局最优解，但计算量也会随之增加。因此，合理确定布点数也是值得研究的问题。

2．2并行化

按照算法设计中所述基本思路，将初始点平均分配给多个进程，让这些进程并行计算，最后将结果汇集到root进程0。如此实现以后通信量少，并行度高。并行化部分代码如下：

/*确定每个进程需要处理的第一个初始点Begin_Row和最后一个初始点End_Row*/

if(PopSize%size!=0)//PopSize为布点数，size为进程数

{if(myid<PopSize%size)Row_Num=PopSize/size+1;

//Row_Num为分配该进程初始点个数

elseRow_Num=PopSize/size;

if(myid<=PopSize%size)

Begin_Row=myid*(PopSize/size+1);

elseBegin_Row=myid*(PopSize/size)+n%size;

}

else

{

Begin_Row=myid*(PopSize/size);

Row_Num=PopSize/size;

}

End_Row=Begin_Row+Row_Num;

//进入计算部分

/*然后将每个进程计算结果传给root进程0；root取最优值赋给result变量*/

MPI_Reduce(&min,&result,1,MPI_DOUBLE_PRECISION,MPI_MIN,0,mycomm);

2．3性能分析

(1)时间与空间复杂度

(2)并行效率分析

并行实现以后，各个计算过程中进程之间不需要数据传输，所以并行效率比较高。这个结论在3.3节的测试中得到验证。

3算法测试

3．1试验环境

联想深腾6800超级计算机系统;

系统结构：COW；

265个四路节点机；

内存总容量2.6TB，磁盘总容量80TB；

高速连接网络QsNet,点对点通信带宽大于300MB，延迟时间小于7μs。

3．2寻优能力测试

(1)为测试该算法的寻找最优值的能力，选择两个具有代表性的经典全局最优化函数作为测试的目标函数。其特点是局部极值点非常多，因而全局最优值很难准确找到。最后将本文的计算结果与遗传算法的结果进行了对比分析。

从图2中可以看到局部最优值点非常多，所以布的点比较多。在实际工程计算中，一般应该根据问题的复杂程度布尽量多的点。从表2可以看出，在上述4个进程中有2个找到了全局最优值点。最终root进程0选取结果为最优值点：(0)；最优值为：1。

(2)与遗传算法的比较

从表3和4中可以看出，本文设计的算法分别在小数点后面3位和4位比遗传算法精确，这显然不是机器精度的问题，而主要归功于Powell算法具有很强的局部寻优能力。遗传算法是一种带有随机性的寻优方法，有其很强的跳出局部陷阱的能力，但在局部寻优方面却不十分强。Powell算法在寻找全局最优解方面不理想，针对这一点本文用均匀布点的方法将其化解。

由并行加速比和并行效率可以看出该并行算法并行效率比较高。这个测试结果与2.3节中算法性能分析的结论一致。

3．4时间复杂度测试

(1）笔者同样选择函数(6)，问题因素个数也即自变量的维数m从100每次递加100，每次同样布211个点，同样分配4个进程。时间空间统计数据见表6，图形显示如图4、5所示。

从(1)和(2)可以总结出，该算法的时间复杂度为O(维数2×布点数)，空间复杂度为O(维数×布点数)。该测试结果与2.3节中的性能分析(2)一致。

4结束语

本文将均匀设计与Powell算法相结合并进行有效改进，设计基于此的全局最优化并行算法，经过测试该全局最优化算法寻优能力强，时间复杂度与计算问题需要考虑的因素个数的二次方和布点数成线性关系，空间复杂度与因素个数和布点数成线性关系，经过并行性测试该算法并行效率很好。

该方法可适用于各种数值和非数值优化的科学计算问题，如生物信息学和计算化学等领域，也可以用于多种工程计算方面，具有较为广泛的应用。

由于本算法计算时，每个进程只需要部分Uniform矩阵，对于大规模优化问题，大内存的需求可均匀地分布在各个节点的CPU上，故算法具有非常好的利用超级计算机求解大型优化问题的潜力。

利用本算法的思想，也可用于均匀设计类似的正交设计、单纯形法等方法进行空间布点，然后利用可用于局部优化的Powell算法、共轭梯度法、最速下降法等方法进行局部优化，也可能在特殊应用领域达到较好的全局最优化效果。

参考文献：

［1］AIMOT,ANTANASZ.Globaloptimization（lecturenotesincompu－terscience）[M].Berlin:Springer－Verlag,1989：15－42.

[2]WILLIANHP,SANLAT,WILLIANT,etal.NumericalrecipesinC++[M].[S.l.]:PublishingHouseofElectronicsIndustry,2005:295－317.

[3]PARADALOSPM,SHALOWAYD,XUEGL.Optimizationmethodsforcomputingglobalminimaofnon－convexpotentialenergyfunctions[J].JournalofGlobalOptimization,1994,4(1):17－133.

[4]JIANGLL,XUEGL.Optimizationofmoleculesimilarityindexwithapplicationstobiomolecules[J].JournalofGlobalOptimization,1999,14:299－312.

[5]CHENHM,ZHOUJJ,XIEGP.Ageneticevolvedalgorithmtopredictbioactivity[J].ComputSci.,1998,38:243－250.

[6]BYRDRH,ESKOWE,SCHNABELRB.Parallelglobaloptimization:numericalmethods,dynamicschedulingmethods,andapplicationtomolecularconfiguration[D]//FORDB,FINCHAMA.Parallelcomputation.[S.l.]:OxfordUniversityPress,1993:187－207.

[7]CRAMEREJ,DENNISJE,FRANKPD,etal.Problemformulationformultidisciplinaryoptimization[J].SiamJournalofOptimization,1994,4(4):754－776.

[8]AUDETC,DENNISJE.Apattensearchfiltermethodfornonlinearprogrammingwithoutderivatives[D].[S.l.]:DepartmentofComputationalandAppliedMathematics,RiceUniversity,2000.

[9]STEVEB,LOISCM,JORGEJM,etal.Usersmannal.mathematicsandcomputersciencedivision,ANL/MCS－TM－242revision1.5[R].[S.l.]:[s.n.],2003.

[10]方开泰.均匀设计与均匀设计表[M].北京：科学出版社，1992:1－80.

[11]方开泰.均匀设计——数论方法在实验设计的应用[J].应用数学学报，1980,3(4):363－372.