遗传算法论文精选(九篇)

前言：一篇好文章的诞生，需要你不断地搜集资料、整理思路，本站小编为你收集了丰富的遗传算法论文主题范文，仅供参考，欢迎阅读并收藏。

第1篇：遗传算法论文范文

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基于遗传算法的机械产品设计系统应用

第2篇：遗传算法论文范文

关键词：入侵检测，否定选择，克隆选择

 

1.引言

克隆选择是基于人工免疫机制的入侵检测系统中一个重要组成部分。Forrest小组提出的静态克隆选择算法能够在一个静态数据集上建立一个有效的误用检测器，但它最大的缺点是不能适应网络流的变化，即不具有自适应性[1]。在Forrest的静态克隆选择算法中，首先产生随机检测器集合D，D中的检测器都是经过随机产生器产生，再经否定选择后送到集合D中，D中的检测器初始适应度值为0。否定选择的目的，是为了排除和“自体”匹配的无效检测器，使随机产生的检测器，先和“自体”数据库中的所有记录进行比较，若匹配，则丢弃；否则，送入检测器集合D。由于“自体”数据库非常大，因此进行否定选择的时间很长。

J. Kim此此算法略作改进[2]，使否定选择函数返回一个特定的值，作为检测器的初始适应度值，检测器的优劣由适应度值的大小来衡量。可以把适应度值限制在0和1之间，在进行否定选择时，计算产生的每个随机检测器和“自体”数据库中的每个“自体”模式匹配的相异度值，否定选择函数返回这些相异度的平均值，并把这个返回值作为这个检测器的初始适应度值。即

其中：fitness(i)为随机产生的第i个随机检测器；N为自体数据库中“自体”模式的个数；dissimilarity(antibody(i),self (j))为产生的第i个随机检测器和“自体”数据库中第j个“自体”模式匹配的相异度值。论文格式，否定选择。

静态克隆选择算法在一定程度上改进了否定选择算法。但是，传统的克隆选择算法是在静态的抗原数据集基础上进行模式识别的，这种方法对先前已经收集到的数据具有较好的效果[3]。不过，现实环境中(比如网络中的入侵检测)，不停的有新的入侵模式, 也就是说AIS每天面对的可能是各种不同的抗原。更重要的是, 现实中某时刻被认为Self(正常行为模式)，到了下一时刻可能就成了Nonself(异形模式)。因此，我们要求AIS除了具备先前已经描述的具有识别新的未知模式的能力外，当识别器的识别能力不再正确的时候，它应该随时被替换[4]。

2.否定选择算子

检测系统选择两个双亲检测器，采用交叉、变异的方法去产生后代检测器，并用后代检测器中更优的子检测器去代替父检测器中检测效果较差的检测器。由于两个父检测器随机选取，交叉、变异的过程中可能产生无效的检测器，所以有必要用否定选择算法对新生成的子检测器做一个判定，当后代检测器与任一自体抗原匹配时，这个后代检测器就被淘汰。当一个无效后代检测器产生时，检测系统就用同一对双亲检测器基因算子产生一个新的后代检测器。当产生有效后代检测器失败次数超过T时，检测系统就选择一对新的双亲检测器产生新的后代检测器。论文格式，否定选择。

3.遗传选择算子

遗传算法是克隆选择算法的核心。遗传算法的基本原理是直接由自然行为类推而来。每个个体根据问题的好坏被赋予一个适应度。适应度越高的个体有更高的机会与其他个体交叉繁殖进行再生，新产的个体被称为后代，它们共享一些来自于它们双亲的特征。那些适应度较低的个体因为不太可能被选出来，最后都会灭亡。克隆选择算法用遗传算法作为遗传算子，随机选择成熟的检测器，这样能产生更新更优的子检测器。用遗传算法产生的新的子检测器中，有更优的，但也有更不合格的，所以需要用否定选择算法对他们作一个选择。遗传算法是建立在自然选择和群体遗传学机理基础上的随机、迭代、进化，具有广泛适用性的搜索方法。所有自然种类都是适应环境而得以生存，这一自然适应性是遗传算法的主旋律。论文格式，否定选择。遗传算法搜索结合了达尔文适者生存和随机信息交换，前者消除了解中不适应因素，后者利用原有解中己有知识，从而有力地加快了抽索讨程。

下面举例说明基本方法。对于一个给定的优化问题，设目标函数

F=(x,y,z), (x,y,z),FR

要求(x0,y0,z0)使得

F=f(x0,y0,z0)=max(f(x,y,z))

其中 (x,y,z)为自变量，是(x,y,z)的定义域，(x,y,z) 可以是数值，也可以是符号；F为实数，是解的优劣程度或适应度的一种度量；f 为解空间(x,y,z) 到实数域FR的一种映射，那么遗传算法的求解步骤如下:

（1）编码

用一定比特数的0,1二进制码对自变量x,y,z进行编码形成基因码链，每一码链代表一个个体，表示优化问题的一个解。如x有16种可能取值x0,x1，…x15，则可以用4bit的二进制码0000-1111来表示。将x,y,z的基因码组合在一起则形成码链。

（2）产生群体

t=0，随机产生n个个体组成一个群体P(t)，该群体代表优化问题的一些可能解的集合。当然，一般来说，它们的素质都很差，遗传算法的任务是要从这些群体出发，模拟进化过程，择优汰劣，最后得出非常优秀的群体和个体，满足优化的要求。

（3）评价

按编码规则，将群体P(t)中的每一个体的基因码所对应的自变量取值(xi,yi,zi)代入(4-l)式，算出其函数值Fi ,i=1,2,…,N。Fi越大，表示该个体有较高的适应度，更适应于f所定义的生存环境，适应度F为群体进化时的选择提供了依据。

（4）选择(复制)

按一定概率从群体P(t)中选取M对个体，作为双亲用于繁殖后代，产生新的个体加入下一代群体P(t+1) 中。一般P,与F,成正比，就是说，适合于生存环境的优良个体将有更多的繁殖后代的机会，从而使优良特性得以遗传。选择是遗传算法的关键，它体现了自然界中适者生存的思想。

（5）交叉

对于选中的用于繁殖的每一对个体，随机地选择同一整数n，将双亲的基因码链在此位置相互交换，如个体x,y在位置3经交叉产生新个体x’,y’，它们组合了父辈个体x,y的特征，即

x=x1x2x3x4x5[00011]

y=y1y2y3y4y5[11100]

x’=x1x2x3x4x5[00000]

y’=y1y2y3y4y5[11100]

交叉体现了自然界中信息交换的思想。论文格式，否定选择。

（6）变异

以一定概率凡从群体P(t+1)中随机选取若干个体，对于选中的个体，随机选取某一位进行取反运算，即由10或由01。同自然界一样，每一位发生变异的概率是很小的。变异模拟了生物进化过程中的偶然基因突变现象。遗传算法的搜索能力主要是由选择和交叉赋予的，变异算子则保证了算法能搜索到问题解空间的每一点，从而使算法具有全局最优，它进一步增强了遗传算法的能力。

对产生的新一代群体进行重新评价选择、交叉、变异，如此循环往复，使群体中最优个体的适应度和平均适应度不断提高，直至最优个体的适应度达到某一限值或最优个体的适应度和群体的平均适应度值不再提高，则迭代过程收敛，算法结束。

4.多层动态克隆选择算法

为了有效解决上面的问题，对静态克隆选择算法进行改进。引入几个重要的参数和与先前有所不同的新的免疫细胞，称为记忆识别器。即成熟识别器集中除了一般的经过克隆选择生成的成熟识别器之外，还包括记忆识别器。一个参数是生命期限，指的是成熟识别器参与模式识别的期限，当一个成熟识别器不能在规定的期限内识别出Nonself，说明该识别器并不是理想的识别器，应该被去掉；另一个参数是记忆计数器，每当成熟识别器识别出一个异形模式，则该计数器自动增加，当超过预先设定好的阀值时，说明该成熟识别器具有较高的识别效率，因此将其作为记忆识别器加入到成熟识别器集合中。这样，识别器集合具有了多层次性。同时，为了适应Self和Nonself的动态变化，用新增的抗原对成熟识别器进行再选择，去掉那些不再有用的识别器，以降低伪肯定率(误判)。

算法描述：首先初始化识别器种群，计算种群中每个检测器的适应值，在适应值高的检测器中随便选择两个检测器进行克隆繁殖产生子检测器，让子检测器通过一个否定选择过程去掉那些能够识别自体的检测器，这样就得到了成熟的检测器集合。下面是另一个再选择过程，因为我们动态的增加了自体或非自体，所以有必要对成熟的检测器进行一次再选择过程，通过再选择过程的检测器经过监测而达到激活阀值的就激活，而没达到激活阀值的就等待或者死亡。论文格式，否定选择。

算法分析：算法能动态的适应不断变化的网络环境，能够根据环境的要求动态的优化检测器。而在检测器通过初次选择成为成熟检测器后又通过一个再选择过程，这个过程能很好的配合动态新增自体或非自体，因为每次动态新增加了自体或者非自体后原来的一些检测器可能会改变它的属性，如原来合格的成熟检测器可能因为新增自体而变为无效检测器，这个在选择过程就能够把它过滤掉，从而能在保持误报率不变的基础上提高检测率。论文格式，否定选择。

结束语

由于遗传算法的特点，静态克隆选择算法产生的检测器有可能是无效检测器，所以本文提出了一种多层动态克隆选择算法，对每次动态克隆的新检测器再次检测，判断其有效性，从而过滤掉无效低检测器但是本算法也增加了算法的复杂度，这也是日后需要改进的地方。

参考文献

[1]S.Forrest,Hofmeyr,Somayaji.ComputerImmunology.CommunicationsoftheACM,1997,40(10):88~96

[2]J.Kim,P.Bentley.TowardsanArtificialImmuneSystemforNetworkIntrusionDetection:AnInvestigationofDynamicClonalSelection.TheCongressonEvolutionaryComputation，Honolulu,2002:1015~1020.

[3]M.Balazinska,E.Merlo,M.Dagenais,etl.Advancedclone-analysistosupportobject-orientedsystemrefactoring.Proceedings.SeventhWorkingConferenceonReverseEngineering,Brisbane,2000:98~107.

[4]ZejunWu,YiwenLiang.Integratedplatformofartificialimmunesystemforanomalydetection.WSEASTransactionsonInformationScienceandApplications,2005,2(2):144~149

第3篇：遗传算法论文范文

关键词：遗传算法；整数编码；离散变量；R.C.框架优化设计

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

0 引言

遗传算法(Genetic Algorithm，GA)是近几年发展起来的一种崭新的全局优化算法。与传统优化算法相比，其具有隐行性、全局性和较好的鲁棒性的同时，又易于理解，操作简单的优点。采用二进制编码的标准遗传算法(SGA)在结构优化领域已经取得了一定的成果，但当变量数量和约束数量增加时，标准遗传算法由不一定能搜索到最优个体。本文尝试采用整数编码进行遗传算法编写，减少不同代码之间的转换工作，同时解决了离散化变量的优化问题，与实际工程更为相符。

1 R.C.框架优化模型

1.1目标函数和设计变量

以框架结构主体（主梁和柱）总造价为钢筋混凝土框架结构的目标函数：

(1.1)

NEB、NEC――分别为梁总数和柱总数；

――第i号主梁的造价，包括梁的混凝土成本、纵筋成本、箍筋成本、模板成本；

――第j号柱的造价，包括柱的混凝土成本、纵筋成本、箍筋成本、模板成本；

梁柱以截面编号分组，一组构件共享一个截面属性，每个截面属性有b、h两个变量。另外每层柱的砼号相同，每层柱共享一个砼等级变量。对于一个5层框架结构，若有梁柱截面分组各20个，则共有85非设设计变量。

1.2 约束条件

1）梁最大配筋率约束

要求支座两端和跨中的受压区高度满足相对界限受压区的高度要求，即

(1.2)

(1.3)

(1.4)

ξl 、ξr、ξm――为左支座、右支座、跨中的相对受压区高度；

ξb ――界限受压区高度。

2）梁最小截面约束

对于非抗震组合设计时钢筋混凝土梁受剪截面应满足如下约束：

(1.5)

V――梁剪力设计值；

βc――混凝土强度影响系数。

对于抗震组合设计时钢筋混凝土梁受剪截面应满足如下约束：

当l0/h > 2.5时，有：

(1.6)

当l0/h ≤ 2.5时，有：

(1.7)

3）梁挠度约束

(1.8)

f ―― 准永久荷载组合下梁的挠度；

[f ] ――梁挠度限制。

4）梁截面高宽比约束

(1.9)

bbh――梁的截面高宽比，一般取4。

5）柱最大配筋率约束

(1.10)

Asb、Ash ――分别为b方向、h方向单偏压计算配筋面积。

ρmax ―― 柱全截面最大配筋率，取5%。

6）柱最小截面约束

以h方向的抗剪截面要求为例，非抗震组合设计时钢筋混凝土梁受剪截面应满足如下约束：

(1.11)

抗震组合设计时钢筋混凝土梁受剪截面应满足如下约束：

当剪跨比λ大于2.5时，有：

(1.12)

当剪跨比λ不大于2.5时，有：

(1.13)

7）柱轴压比约束

(1.14)

αp ――轴压比限值。框架结构抗震等级为一级、二级、三级、四级时分别取0.65、0.75、0.85、0.90。

8）柱截面高宽比约束

以h方向截面高宽为例

(1.15)

cbh――柱的截面高宽比，一般取3。

9）楼层混凝土等级约束：

第i层的混凝土等级不大于第i-1层的混凝土等级，其约束表达式为：

(1.16)

2整数编码遗传算法设计

2.1初始种群生成和适应度函数

已知框架结构中的变量均为符合一定模数制的离散值。

设已有目标函数f (x)，有x=(x1，x2，x3……,xn)，x ∈ XD，(i=1,2,3……,n)，其中XD为离散空间。

对第i个变量，有vi ≤ xi ≤ui ，其中vi、ui为第i个变量的上下界，ci为xi在定义域内的间隔距离，vi ∈ N*、ui ∈ N*、ci ∈ N*，N*为正整数集合。

指定遗传算法中迭代种群规模为M时，则随机生成的个体变量如下：

(2.1)

(i=1,2,3……,n) (j=1,2,3……,M)

其中为在[0,1]内的随机数，INT为向下取整的计算。对目标函数为最小化的问题可构造如式2.2的适应度函数：

(2.2)

cmax可以是是当前所有代或最近K代中f(x)的最大值。

2.2自适应交叉算子

为了保障在种群进化过程中优良的个体不被破坏流失，同时保障有新的个体加入，本文不采用固定的交叉概率，而是根据需要交叉配对的两个个体的适应值计算自适应的交叉概率。假设和两个需要进行交叉计算的个体，其确定自适应交叉概率的公式为式2.3：

(2.3)

――为当前种群的平均适应值

――为这前种群中的最佳适应值

k1、k2――确定交叉变量Pc的相关常数，由计算人员确定，一般k2比k1略大

当和中适应值的较大者大于等于平均适应值时，调整减小交叉概率Pc。当和中适应值的较大者小于平均适应值时，交叉概率Pc等于较大的k2。

当交叉的随机判定数RND小于Pc时，个体和需要进行染色体交叉计算生成新的子代染色体，否则两者直接遗传到子代中，见式2.4，式中为程序自带产生的随机数。为了保证交叉产生的子代满足模数制，还需用式2.5进行修正。

(2.4)

以为例进行基于模数制的修正，有：

(2.5)

2.3自适应变异算子

本文同样不采用固定的变异概率，而是根据需要变异个体的适应值计算自适应的变异概率。假设个体需要进行变异计算，其确定自适应变异概率的公式为式2.6：

(2.6)

k3、k4――确定交叉变量Pm的相关常数，由计算人员确定，一般k4比k3略大

当个体的适应值的大于等于平均适应值时，根据式2.6-(1)调整减小交叉概率Pm。当的适应值的小于平均适应值时，根据2.6-(2)交叉概率Pm等于k4。

当交叉的随机判定数RND小于P m时，根据式2.7对基因进行非均匀变异：

(2.7)

、――系统程序自带产生的随机数。

2.4锦标赛选择算子

本文根据选用锦标赛选择作为主要选择方法。锦标赛选择，又称随机联赛选择，是每次随机从进化代种群中取出一定数量（Tour）个体，然后选择其中最佳个体进入下一代种群。重复操作，直到新的种群规模达到原来的种群规模。

3算例分析

3.1工程概况

算例框架结构，5层；层高3米；设防烈度7度(0.10g)；地震分组一组；Tg=0.9s；抗震等级为三级；基本风压为0.55kN/m2；地面粗糙程度B类。ETABS模型中每层分为4组梁截面和4组柱截面，平面布置规则以第5层平面图为例，每层构件分组见图1。各组梁截面属性的初始截面为300mm×700mm，柱截面属性的初始截面为500mm×500mm。最大层间位移角限值为1/550。梁混凝土等级统一采用C30，造价为465元/m3。柱混凝土等级共有1~5个代码，分别对应C30~C50的混凝土等级，各等级单价依此为583元/m3，604元/m3，626元/m3，648元/m3 ，676元/m3。梁模板的单价为82元/kg，梁钢筋单价为4793元/t，柱模板单价为99元/kg，柱钢筋单价为4918元/t。主要优化参数设置见表1。

图1ETABS模型三维视图图2第5层平面布置图

3.2整体优化流程

本文整体优化分为两部执行，第一部分冻结内力做结构尺寸的优化，第二部分在第一部分得到的新最优个体的基础上，更新模型内力，再次执行第一部分的操作，反复这个过程直到造价满足收敛条件，终止优化程序，

输出最终的优化结果。在第一部分优化又分两个级别。第一级为不考虑结构刚度对内力的影响，在梁柱构件约束和层间约束下执行遗传算法；第二级为在遗传算法优化得到的最佳个体后，回代入ETABS模型验算位移约束，如果不满足位移约束则执行行相应的调整策略不断更新ETABS模型直到满足位移约束。整体优化的步骤为：

①识别模型

②冻结内力，读取内力分析结果

③生成初始种群

④遗传算法操作：交叉、变异、选择

⑤评估新种群

⑥是否达到遗传算法收敛精度，是则进入下一步，否则返回执行④~⑤

⑦验算位移约束，不通过调整模型直到通过为止

⑧框架总造价是否整体收敛，是则输出内力，否则解冻内力，更新模型，返回执行②~⑦

3.3优化结果

部分优化参数取值见表1，优化过程中造价的下降曲线见图3。本案例共进行了5次整体优化计算，最终优化造价比原始设计造价下降30%，优化效果显著。由于本文引入了遗传算法的自适应参数调整，目标函数的下降速度快，整体优化的效率高。优化后的最大层间位移角出现在第二层为1/552（见表2），说明结构的刚度在满足规范要求的前提下，变得更合理。

表1优化参数取值

图3造价优化下降曲线

表2 优化后的层间位移角

5 结论

本文直接采用整数编码，能够良好得描述工程结构问题中离散变量在遗传算法中的种群生成、交叉、变异、选择。采用分部优化法，反应结构尺寸和结构内力的非线性关系。通过算例验证，本文的方法优化效果良好，优化效率高，给其他采用遗传算法优化设计的结构模型提供了有益的参考。

参考文献

[1] 张琦. 采用遗传算法对钢筋混凝土框架结构进行优化设计[D]. 山东大学硕士学位论文, 2006, 5.

[2]肖国涛. 基于遗传算法的钢管混凝土框架结构优化研究[D]. 华中科技大学硕士学位论文, 2005, 3.

[3] 陆海燕. 基于遗传算法和准则法的高层建筑结构优化设计研究[D]. 大连理工大学博士学位论文, 2009, 6.

[4] [19] 张思才, 张方晓. 自适应遗传算法在桁架结构优化设计中的应用[J].湘潭大学自然科学学报, 2002, 24(4): 37 - 411.

第4篇：遗传算法论文范文

关键词：遗传算法；智能组卷；应用模式

中图分类号：TP311.52

考试作为教育测量学和教育统计学和的基本原理，不仅是对学生学习能力和知识水平的检验方式，也是对教师教育教学水平评价和体现的重要手段之一。如何更加客观公正地反映学生的学习状况，全面地掌握和评价教师的教学工作能力，进一步提升教师的教学水平，实现教学与考试相分离，使得院校整体工作效率得以提高，因而，开发出科学高效的组卷系统尤为重要。

1 遗传算法的基本原理

遗传算法（Genetic Algorithm）GA是以达尔文进化论和孟德尔遗传学作为基础，结合数学理论的一种自适应随机全局优化算法。该算法模拟生物的自然选择和遗传规律，对目标群体施以选择、交叉、变异等一系列遗传操作，使群体内个体的适应性提高，从而产生出新一代群体，个体不断进化并逐渐接近最优解的状态，形成一种“生存+检验”的搜索寻优算法。遗传算法以编码群体为进化基础，将问题的参数空间以编码空间加以替代，评价标准表示为适应度函数，通过对群体中个串进行的遗传操作实现选择和遗传，形成迭代过程。在此过程中，对编码位串中重要的基因进行随机重组，使位串集合的新一代总是优于上一代，群体中的个体不断地进化而接近最优解，达到求解问题的目的。运用遗传算法提供的通用模型，可以解决涉及到任何方面、何种类型的问题，因此遗传算法的应用正在向多学科领域渗透。遗传算法与人工神经网络、模糊控制理论等正在成为二十一世纪计算机智能研究的热点。

2 改进的遗传算法

遗传算法的选择与设计取决于最初的编码设计，而实现问题的解编码成为染色体是编码设计的关键问题。二进制编码、实数编码、字母排列编码等编码方式是目前较为常见的编码方式。

遗传算法适应度函数的确定是采用该算法进行智能组卷的关键。适应度函数值为遗传进化过程设置标准，以此标准有效地区分个体的优劣。如果适应度函数确定的好，在区分个体优劣时，能够防止好的个体过快扩散、坏的个体过快淘汰，从而对群体多样性的保持起到积极作用，遏制“早熟”现象的出现。

3 与智能组卷系统相关理论

3.1 智能组卷原则及特点

智能组卷系统研究的重点是如何在短时间内生成高质量的试卷，并且保证生成的试卷能最大程度地满足使用者的不同需求。由计算机考试系统的试题库中抽取试题组成的试卷，必须能够作为考察学生学习效果、体现教师教学水平的重要工具和手段，因而势必对试卷的组成要求更加提高。

3.2 智能组卷系统指标体系

指标体系作为组卷问题的重要组成部分在试题库系统中扮演着重要的角色，某些固有特性参数就包含在试题本身，描述这些固有特性参数需要设定相应的指标，多个指标组织构建成指标体系，试题指标体系的建立对组卷模块功能加以支持。

4 智能组卷系统实现

4.1 系统设计

模块化编程具有使程序结构的设置更加科学合理，可读性进一步增强，并且维护更加简单易行等优点。模块化编程对输出数据的保护表现在，模块之间数据传输通过中间量，属性数据存储在各自的模块中不宜被破坏或丢失，使系统的安全性大幅提高。模块化编程具备较强的通用性，对于同一类型的控制可以直接或简单修改就应用其中。

4.2 系统基本功能

本系统的开发是采用PHP与MYSQL相结合的方式，服务器采用Apache。组卷管理、试题管理、用户管理等是试题库系统必须具备的基本功能。组卷管理包括自动组卷、手动组卷和测验组卷三部分，是系统的核心。试题管理执行试题的录入、修改、删除等功能。用户管理执行用户增加、删除、权限管理等功能。根据实际需要，系统还可以设置试题科目、题型、专业信息等等其他功能。系统功能模块如表1如下：

表1 系统主要功能模块示意图

试题库管理系统

组卷管理 试题管理 综合管理

自动组卷 手动组卷 测验组卷 录入试题 修改试题 删除试题 科目管理 题型管理 专业管理 其他管理

下面以组卷管理模块为例子进行组卷系统生成。

4.3 组卷管理模块

（1）自动组卷。自动组卷生成如图1所示：

图1 系统自动组卷界面

（2）手动组卷。手动组卷虽然在步骤上同自动组卷比较要繁琐得多，但是用户能够根据实际需求组织试卷，因而更具自主性。用户在进入手动组卷模式后，按照先选题型后选知识点的顺序，将符合要求的所有试题选出，再逐一选择试题。对所有题型采用上述操作即可完成手动组卷。

（3）测试组卷。测验组卷与自动组卷在操作上相类似。由于只突出更便于教师测试的功能，因而无需设置试题分数以及对分数进行校验。这种方式可以大幅度提高成卷速度，因而对于完成某些特定情况下的工作具有一定意义。比如要测试选择题出现如图2所示：

图2 系统选择试题界面

总之，通过对组卷问题相关理论的对比、分析、研究，总结出常见组卷策略各自的优缺点。将项目测量理论IRT作为基础，综合考虑教师组卷时的实际需要以及组卷策略必须遵守的基本原则，在对考卷信度与效度、题目难度与区分度等基本属性分析研究的情况下，建立了组卷问题的数学模型。

参考文献：

[1]杨栋.组卷的遗传算法设计[J].现代计算机，2010，8（265）：8-9.

[2]林顺刚.遗传算法概述[J].科技信息（学术研究），2011，22（057）：90.

[3]魏平，熊伟清，赵杰煌.遗传算法的早熟现象研究[J].计算机应用研究，2012（09）：12-14.

第5篇：遗传算法论文范文

关键词:遗传算法,分类器,分类优化,集成学习

中图分类号: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.

[3] 孙瑞祥,屈梁生.进化计算的过去、现在与未来[C]//进化计算研究生论坛论文集.西安:西安交通大学,2001.

第6篇：遗传算法论文范文

论文摘要：tsp是组合优化问题的典型代表,该文在分析了遗传算法的特点后,提出了一种新的遗传算法(gb—mga),该算法将基因库和多重搜索策略结合起来,利用基因库指导单亲遗传演化的进化方向,在多重搜索策略的基础上利用改进的交叉算子又增强了遗传算法的全局搜索能力。通过对国际tsp库中多个实例的测试,结果表明:算法(gb—mga)加快了遗传算法的收敛速度,也加强了算法的寻优能力。

tsp(traveling salesman problem)可以简述为:有n个城市1,2,…,n,一旅行商从某一城市出发,环游所有城市后回到原出发地,且各城市只能经过一次,要求找出一条最短路线。tsp的搜索空间是有限的,如果时间不受限制的话,在理论上这种问题终会找到最优解,但对于稍大规模的tsp,时间上的代价往往是无法接受的。这是一个典型的组合最优化问题,已被证明是np难问题,即很可能不存在确定的算法能在多项式时间内求到问题的解[1]。由于tsp在工程领域有着广泛的应用,如货物运输、加工调度、 网络 通讯、电气布线、管道铺设等,因而吸引了众多领域的学者对它进行研究。tsp的求解方法种类繁多,主要有贪婪法、穷举法、免疫算法[2]、蚂蚁算法[3]、模拟退火算法、遗传算法等。

遗传算法是一种借鉴生物界 自然 选择和遗传机制的随机化搜索算法,其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不依赖于梯度信息[4]。wWw.133229.COM遗传算法主要包括选择、交叉和变异3个操作算子,它是一种全局化搜索算法,尤其适用于传统搜索算法难于解决的复杂和非线性问题。遗传算法虽然不能保证在有限的时间内获得最优解,但随机地选择充分多个解验证后,错误的概率会降到可以接受的程度。

用遗传算法求解tsp能得到令人满意的结果,但是其收敛速度较慢,而且种群在交叉算子作用下,会陷入局部解。采用局部启发式搜索算法等,虽然能在很短的时间内 计算 出小规模城市的高质量解,一旦城市规模稍大就容易陷入局部最优解。因此,为了能够加快遗传算法的收敛速度,又能得到更好的近似最优解,该文采纳了文[5]中杨辉提出的基因库的想法,并结合文[6]中cheng-fa tsai提出的多重搜索策略思想,使用单亲演化与群体演化相结合的方式来求解tsp问题。该文根据文[7]中最小生成树mst(minimum cost spanning tree)的应用,由mst建立tsp的基因库,保存有希望成为最优解的边,利用基因库提高初始群体的质量进行单亲演化,然后利用改进后的交叉算子和的多重搜索策略进行群体演化。

1　单亲演化过程

现有的大多数演化算法在整个演化过程中所涉及的基因,大多来源于个体本身,个体质量的高低决定了算法的全局性能,如果群体中初始个体的适应度都较差,肯定要影响算法的收敛速度,对于规模稍大的tsp尤其明显[8]。该文为了克服上述弱点,首先利用普里姆算法求出tsp中最小生成树,并将各个mst中的每一条边都保存在一个n*(n-1)方阵里面,就构成了一个基因库,在生成初始群体的时候尽量使用基因库中的基因片段,来提高整个初始群体的适应度,从而提高算法的效率。

1.1　tsp编码表示

设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,操作可以重复多次,这样生成的基因库中的基因就更多,增强了初始群体的全局性。具体算法如下:

void minispantree—prim(mgraph g,vertextypeu){

struct {

vertextype adjvex;

vrtype lowcost;

}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(order crossover)法类似的交叉方法[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-fa tsai提出的多重搜索策略[6],就是把染色体集中的染色体分成保守型和探索型两种不同类型的集合,然后针对不同类型的染色体集合根据不同的交叉、变异概率分别进行交叉变异操作,对保守型染色体集合就采用比较低的交叉变异概率,而对探索型染色体集合就采用比较高的交叉变异概率。这种策略对保守型染色体集合的操作最大限度地保留了父代的优秀基因片段,另一方面对探索型染色体集合的操作又尽可能地提高了算法的全局搜索能力。为了提高算法的收敛速度,初始染色体集合该文采用了前面单亲演化的结果中的染色体集合,交叉算子则利用的是前面介绍的改进后的算子,改进后的多重搜索策略见下。

3　实验结果与分析

该文的gb—mga算法由c#编程实现,所有的结果都是在p42.0g微机上完成,并进行通用的tsp库实验,选用了具有一定代表性的tsp实例,并把该算法和其他算法做了一个对比。为了减少 计算 量,程序中的数据经过四舍五入整数化处理,与实数解有一定的偏差,下面给出图kroa100的示例。

为了证明该文提出的gb—mga算法的有效性,将该文算法与典型的遗传算法ga、单亲遗传算法pga以及文[5]中杨辉提出的ge—ga(gene pool genetic algorithm)算法和文[12]中提出的mmga(modified multiple-searching genetic algorithm)算法都进行了一个对比。

实验结果证明,该文算法的求解质量要优于ga、pga、mmga算法,而求解速度方面则优于ge—ga算法,特别是对于大规模城市的tsp问题求解效果尤其明显,具有快速收敛的特性。ge—ga算法对于中等城市规模的tsp实例求解,其运算时间就大幅度增加,如果把该算法用于求解大规模和超大规模tsp问题,那么时间上的代价就让人无法忍受。而该文的gb—mga算法在单亲遗传演化中就使用了基因库中的优质基因,使得单个个体的进化速度大大提高,从而为进一步的演化提供了条件,群体演化过程的选择机制和收敛准则的恰当选取使得算法在注重了求解质量的同时兼顾了算法的效率。

结束语　该文在对tsp问题进行分析的基础上,通过对全局最优解和局部最优解中的边关系的分析发现,通过最小生成树的求解保存最有希望成为全局最优解的边,可以提高算法的效率,同时并不降低搜索的性能。在实验中发现,通过生成基因库快速提高种群质量,虽然可以快速收敛,但是tsp问题的求解质量并没有达到一个可以接受的程度,因此在群体演化阶段中又加入了2-opt局部搜索算子和多重搜索策略,对不同类型的染色体以不同几率进行选择交叉操作。

用该算法测试tsp库中的典型实例,结果显示,对初始种群运用单亲遗传算法,并引入基因库方法是可行的,有效地提高了算法的效率和收敛速度,在群体演化过程中引入多重搜索策略的方法,提高了算法的并行性和全局寻优性能,即使在较少的寻优步数也能得到适应度不错的局部优化解。gb-mga算法在提高算法求解质量的同时兼顾了算法的效率, 但是其中还有许多有待解决的问题,比如如何构建高质量的基因库,如何对现有基因库进行优化和扩充,以及算法中一些参数的选取问题等,这些方面,还需要进一步的研究。

参考 文献

1 bck t b,hammel u,schwefel h p.evolutionary computation:comments on the history and current state [j]. leee transactions on evolutionary computation,1997,2(6):3~17

2王磊,潘进,焦李成.免疫算法[j]. 电子 学报,2000,28(7):74~78

3 dorigo m,gambardella l m.ant colony system:a cooperativelearning approach to the traveling salesman problem [j]. ieeetransactions on evolutionary computation,1997,2(8):53~66

4 holland j h. adaptation in natural and artificial systems [m].ann arbor:the university of michigan,1975.10~15

5杨辉,康立山,陈毓屏.一种基于构建基因库求解tsp问题的遗传算法[j].计算机学报,2003,26(12):1753~1758

6 tsai cheng-fa, tsai chun-wei, yang tzer. a modified multiple-searching method to genetic algorithms for solving travelingsalesman problem [j].ieee transactions on systems,man andcybernetics,2002,3(10):6~12

7 baraglia r,hidalgo j i, perego r. a hybrid heuristic for thetraveling salesman problem [j]. ieee transactions on evolutionary computation,2001,5(12):613~622

8 tsai cheng-fa, tsai chun-wei. a new approach for solvinglarge traveling salesman problem using evolutionary ant rules[c].in:proc.of the 2002 international joint conf.on neural networks,hawaiian:honolulu,2002

9 jung s,moon b r.toward minimal restriction of genetic encoding and crossovers for the two-dimensional euclidean tsp [j].ieee transactions on evolutionary computation,2002,6(12):557~565

10李茂军,童调生,罗隆诵.单亲遗传算法及其应用研究[j].湖南大学学报,1998,25(6):56~59

11陈国良,王煦法,庄镇泉,等.遗传算法及其应用[m].徐修存,王晓丹.北京:人民邮电出版社,1996.75~81

第7篇：遗传算法论文范文

关键字：频率分配遗传算法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,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

第8篇：遗传算法论文范文

关键词：钻孔灌注桩;基坑支护;遗传算法;优化设计

Abstract: The genetic algorithm is used for excavation of underground continuous retaining wall optimization design, by editing the automatic calculation program of underground continuous wall supporting structure parameters optimization. Algorithm of all constraints is requirements of related codes are given according to the foundation; through the project example and the results prove the validity of the optimization design method.

Key words: bored pile; foundation pit; genetic algorithm; optimization design

中图分类号：U443.15+4文献标识码：A文章编号：

深基坑支护结构随着城市化建设大量出现，同时支护选型和设计极为保守造成浪费，如何选取合理设计基坑同时保障基坑及周围环境安全前提下使工程造价最低是工程设计最关心的问题，所以深基坑支护结构优化设计具有显著技术经济意义。

深基坑支护优化设计设计参数复杂，目标函数与设计参数之间的关系是复杂的非线性关系[1]，神经网络遗传算法是具备智能性、全局优化性和内在学习性等特点一种优化计算方法，可解决深基坑支护优化设计的非线性关系。

1 遗传算法基本原理

遗传算法采用编码的技术，效仿了生物物种由低级到高级的进化过程，从初始种群开始，采取“优胜劣汰，适者生存” 的自然法则对个体进行选择、、变异，进而产生新一代种群，重复逐代演变进化，直到产生出满足条件要求的个体为止，它是基于种群的智能优化法的一种。

遗传算法具有智能性、全局优化性和隐含并行性三个特点。遗传算法具有智能算法中的自适应、自组织和自学习等特点，由于交叉算子的作用，使得搜索方向集中在空间中期望值最高的部分，同时由于变异算子的作用，确保了群体的多样性，防止了搜索被引导到局部最优。遗传算法具有潜在的并行性，由于搜索过程是同时从多个点出发，使得这种多智能体的协作过程是异步并发进行的，同时搜索解空间内的多个区域，相互交流信息，这种分布式并行模式大大提高整个算法的快速反应能力和运行效率。除此之外，遗传算法还具有通用性、内在学习性、多解性、非定向性等特点，这些特点使遗传算法在实际的工程优化中，得到了很大范围的应用。

遗传算法常用步骤如下：①目标函数确定；②根据约束条件生成解的初始成员种群；③译码染色体使其适合评价并给予适应值；④以根据优胜劣汰，去掉适应值差的染色体，并按概率随机选择幸存的染色体进行复制形成新的群体；⑤根据概率随机选择染色体进行杂交和变异的操作；⑥对子代群体重复步骤③-⑤的操作，不断进行遗传进化，让种群平均适应值和最优个体提高，直到适应值趋于稳定，即完成最优参数。

2 数学模型的建立

某工程基坑支护采用钻孔灌注桩，本文以三层钢支撑形式为例进行数学模型。

2.1优化参数的选取

根据优化参数的选取原则，将钻孔灌注桩支护结构[2]中的桩径D、支撑位置m、嵌固深度hd、桩间距S作为优化参数变量，而将混凝土强度等级、配筋方式、钢筋等级、直径和土层计算参数等变量均作为设计参量预先固定下来，则变量空间为：X=[hd,D,m1,m2,m3,S]T

hd ∈[0.5h , 1.5h] D ∈[0.6 ,1.2]S∈[0.5D , 2.5D]

m1∈[0.1h , h-hs′] m2∈[m1+hs, h-hs′ ]m3∈[m2+hs, h-hs′ ]

其中：hs′为最后一道支撑与基坑底的最小间距；hs为钢支撑竖向的最小间距； S指的是两个桩之间的中心距；h为基坑的开挖深度。将所求解空间X=[hd,D,m1, m2,m3,S]确定每个变量的精度后，利用二进制编码对所求变量的解空间进行转换，形成初始种群。

2.2约束条件处理

用构造罚函数的方法处理约束条件，采用，：

若>0,;若≤0，则；而，定义为违反系数，则上述约束问题转换成为了无约束问题，即：

式中：为原目标函数，称为惩罚后的目标函数，参数为惩罚因子，根据对所求解可行性的要求严格程度而定。

2.3适应度函数的确定

选取单位宽度的桩材料造价作为目标函数，即：

式中：h为基坑开挖的深度 ，hd为桩的嵌固深度，D为桩径，S为桩间距。

选取适应度函数为：

式中：c为系数常量，用以调整适应值的区间，通常取值为100-1000，显然的值越大，该母体越优。

2.4收敛判别

选择下式作为收敛判别准则： （是一个充分小正数），如果满足了收敛判别，则输出结果，否则重复计算。

优化程序的实现是基于MATLAB语言，首先编写遗传算法的运算函数，其中包括了编码、适应度评判、选择、交叉、变异、解码等运算，函数调用了先前编制好的围护结构内力和变形计算的函数，为了便于了变量的输入输出，利用生成界面的GUI函数，编写了参量输入界面、优化运行和结构计算界面。

3 工程概况

浙江杭州市区某车站基坑工程[3]，基坑平均深度为14.6m，按照建筑基坑支护，本车站基坑支护工程安全等级为一级。综合本站周边环境、地质条件和工程造价等，基坑主体围护结构采用钻孔灌注桩，钻孔桩选用循环钻施工。本区间地下水埋深为1.3-2.8m，主要为上层滞水，地下水位不连续，水文地质条件较简单。

3.1 计算参数选取

钻孔灌注桩采用为C30，桩径1300m。围护结构的水平受力体系采用钢管内支撑方案，设三道内支撑，采用Φ600，t=16的钢管支撑，钢管材料采用Q235钢，结构设计时应根据结构类型，按结构整体和单个构件可能出现的最不利情况进行组合，依相应的规范要求进行计算，并考虑施工过程中荷载变化情况分阶段计算 。各土、岩层物理力学指标见表1。

表1 土、岩层物理力学指标

3.2 优化结果与分析

通过程序自动计算，优化结果表明，围护桩的嵌固深度和桩间距的对改变，对设计结果具有较为大的影响，在桩径不变的情况下，嵌固深度的变小和桩间距的增大，都会使得围护结构的上部水平位移和弯矩有所增大，但通过改变支撑的位置和支撑的预加轴力，可以保证围护结构的位移满足规范要求的允许值，优化结果显示：墙体的最大弯矩比原设计增加了14.4%，墙体的最大剪力增加了19.2%，但都在设计允许值之内。而造价比原设计降低了17.4%，因此优化结果是比较理想的。根据优化后的支护结构参数计算所得围护结构变形和受力优化结果对比见表2：

表2 优化结果对比表

4 结语

通过工程实例证明遗传算法能够对基坑支护进行优化设计，具有经济效益，自动化计算程序在工程实践中更具有应用价值。

参考文献

[1]李云安.深基坑工程变形控制优化设计及其有限元数值模拟系统研究:博士学位论文[A].武汉:中国地质大学,2000.

[2]刘建航,侯学渊主编.基坑工程手册[M].北京:中国建筑工业出社,1997.75~321.

第9篇：遗传算法论文范文

【关键词】适应度 反垃圾邮件 数据挖掘

【中图分类号】TP3【文献标识码】A【文章编号】1672-5158（2013）02-0163-02

该遗传算法生成的模型建立在解决垃圾邮件的数据分析的新方法基础上。在模型的决策树上，每个结点数据被设计成拥有一个随机系数，这样的话，数据与系数相乘成为判断该项数据记录是否代表邮件合法的确定性权重。这里的系数基于Ephemeral Random Constants（ERC），是特定于数学建模的遗传算法生成的随机数。该系数的微小变化也会导致进化变异产生。

此系统中，之所以要选取特征子集，是考虑到特征子集的选取是在反垃圾邮件中提高机器学习算法性能的可行办法。特征子集的选取能提高学习算法的准确度，减少计算量，同时可以减少测试数据量，降低分类过程中的消耗等。进行特征子集选取，最重要的目标就是提高邮件检测的准确率，减少分类运算等过程中的数据量。

在系统调用序列数据的挖掘过程中，使用特征向量法，用特征向量的一位标识一个短序列，用挖掘算法就能从特征向量集中找出垃圾邮件的规则来。然而，由于短序列的数量较大，导致特征向量位数过大，特征向量集也相应过大。为了更高效可行地使用数据挖掘算法，采用遗传算法对特征向量集进行优化，寻找特征子集，利于后续的数据挖掘。

在使用遗传算法的过程中，用特征向量的位数决定其个体的大小，随机构造50个二进制位串的个体，其中“0”、“1”代表该位置的短序列是否入选特征子集，如图2所示。在此基础上，进行遗传得到最优个体，该最优个体必然是“0”、“1”交替的位串，将其所有“1”所在位置进行分析，可以得到“1”所在位置代表的短序列集，这就是要寻找的特征子集。后续挖掘算法根据该特征子集中的短序列，对训练数据进行分类等挖掘工作。（如图2）

采用标准交叉算子和变异算子，交叉概率取0.6，变异概率取0.001。遗传过程中，个体的选择比较复杂。因为这里是针对垃圾邮件检测进行的优化，所以在选择个体时，是将该个体代表的入选子集的短序列应用到数据分类算法（RIPPER），该算法训练数据并应用规则得到测试数据，根据检测的性能来确定上述要选择的个体的适应度值。根据个体的适应度值就可以对其进行选择，继续遗传优化工作。

研究表明，个体的适应值可以取决于有垃圾邮件被正确检测到和有正常邮件被误判为攻击，同时考虑个体中置“1”位的数目。本系统设计的适应度函数为：F（Xi）=（a/A-b/B）/（δ*m）；Xi表示某个个体，（a/A-b/B）的含意正如前述，m是Xi中“1”的个数，δ是m对于该适应度函数的相关系数。也就是说，a/A是检出率，b/B是误报率，高检出率低误报率使适应度函数值高，低检出率高误报率使适应度函数值低。个体中置“1”的位数越少，适应度值越大，当然这是出于寻找最小特征子集的考虑，其影响的强弱，用相关系数δ去控制。

本系统采用的遗传算法的基本步骤如下：

1.设定进化代数g=0，生成包含n个个体的初始化群体P（g）；

2.在该群体中对每个个体估值，计算各自适应度f（x）；

3.通过如下步骤，生成新的群体P（g+1）：

A.根据个体适应度f（x），从P（g）中选择两个个体作为父代；（适应度值越大，选中的机会越大）；

参考文献

[1] Richard Blum，开放源码邮件系统安全，人民邮电出版社，2002年11月