遗传算法论文范文

引言：寻求写作上的突破？我们特意为您精选了4篇遗传算法论文范文，希望这些范文能够成为您写作时的参考，帮助您的文章更加丰富和深入。

篇1

 

1 引言

“物竞天择，适者生存”是达尔文生物进化论的基本原理，揭示了物种总是向着更适应自然界的方向进化的规律。可见，生物进化过程本质上是一种优化过程，在计算科学上具有直接的借鉴意义。在计算机技术迅猛发展的时代，生物进化过程不仅可以在计算机上模拟实现，而且还可以模拟进化过程，创立新的优化计算方法，并应用到复杂工程领域之中，这就是遗传算法等一类进化计算方法的思想源泉。

2 遗传算法概述

遗传算法是将生物学中的遗传进化原理和随[1]优化理论相结合的产物，是一种随机性的全局优算法。遗传算法不但具有较强的全局搜索功能和求解问题的能力，还具有简单通用、鲁棒性强、适于并行处理等特点数学建模论文，是一种较好的全局优化搜索算法。在遗传算法的应用中，由于编码方式和遗传算子的不同，构成了各种不同的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。基于这个共同点，Holland的遗传算法常被称为简单遗传算法（简记SGA），简单遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，这种改进的或变形的遗传算法，都是以其为基础[1]。

2.1遗传算法几个基本概念

个体(IndividualString)：个体是遗传算法中用来模拟生物染色体的一定数目的二进制串，该二进制串用来表示优化问题的满意解。

种群(population)：包含一组个体的群体，是问题解的集合。

基因模式(Sehemata)：基因模式是指二进制位串表示的个体中，某一个或某些位置上具有相似性的个体组成的集合，也称模式。

适应度(Fitness)：适应度是以数值方式来描述个体优劣程度的指标，由评价函数F计算得到。F作为求解问题的目标函数，求解的目标就是该函数的最大值或最小值。

遗传算子(genetic operator)：产生新个体的操作，常用的遗传算子有选择、交叉和变异。

选择(Reproduetion)：选择算子是指在上一代群体中按照某些指标挑选出的，参与繁殖下一代群体的一定数量的个体的一种机制龙源期刊。个体在下一代种群中出现的可能性由个体的适应度决定，适应度越高的个体，产生后代的概率就越高。

交叉(erossover)：交叉是指对选择后的父代个体进行基因模式的重组而产生后代个体的繁殖机制。在个体繁殖过程中，交叉能引起基因模式的重组，从而有可能产生含优良性能的基因模式的个体。交叉可以发生在染色体的一段基因串或者多段基因串。交叉概率（Pc）决定两个个体进行交叉操作的可能性数学建模论文，交叉概率太小时难以向前搜索，太大则容易破坏高适应度的个体结构，一般Pc取0.25~0.75

变异(Mutation)：变异是指模拟生物在自然的遗传环境中由于某种偶然因素引起的基因模式突变的个体繁殖方式。在变异算子中，常以一定的变异概率（Pm）在群体中选取个体，随机选择个体的二进制串中的某些位进行由概率控制的变换（0与1互换）从而产生新的个体[2]。如果变异概率太小，就难以产生新的基因结构，太大又会使遗传算法成了单纯的随机搜索，一般取Pm=0.1~0.2。在遗传算法中，变异算子增加了群体中基因模式的多样性，从而增加了群体进化过程中自然选择的作用，避免早熟现象的出现。

2.2基本遗传算法的算法描述

用P(t)代表第t代种群，下面给出基本遗传算法的程序伪代码描述：

基本操作：

InitPop（）

操作结果：产生初始种群，初始化种群中的个体，包括生成个体的染色体值、计算适应度、计算对象值。

Selection（）

初始条件：种群已存在。

操作结果：对当前种群进行交叉操作。

Crossover（）

初始条件：种群已存在。

操作结果：对当前种群进行交叉操作。

Mutation（）

初始条件：种群已存在。

对当前种群进行变异操作。

PerformEvolution（）

初始条件：种群已存在且当前种群不是第一代种群。

操作结果：如果当前种群的最优个体优于上一代的最优本，则将其赋值给bestindi，否则不进行任何操作。

Output（）

初始条件：当前种群是最后一代种群。

操作结果：输出bestindi的表现型以及对象值。

3 遗传算法的缺点及改进

遗传算法有两个明显的缺点：一个原因是出现早熟往往是由于种群中出现了某些超级个体，随着模拟生物演化过程的进行，这些个体的基因物质很快占据种群的统治地位，导致种群中由于缺乏新鲜的基因物质而不能找到全局最优值；另一个主要原因是由于遗传算法中选择及杂交变异等算子的作用，使得一些优秀的基因片段过早丢失，从而限制了搜索范围，使得搜索只能在局部范围内找到最优值，而不能得到满意的全局最优值[3]。为提高遗传算法的搜索效率并保证得到问题的最优解，从以下几个方面对简单遗传算法进行改进。

3.1编码方案

因实数编码方案比二进制编码策略具有精度高、搜索范围大、表达自然直观等优点数学建模论文，并能够克服二进制编码自身特点所带来的不易求解高精度问题、不便于反应所求问题的特定知识等缺陷，所以确定实数编码方案替代SGA中采用二进制编码方案[4]。

3.2 适应度函数

采用基于顺序的适应度函数，基于顺序的适应度函数最大的优点是个体被选择的概率与目标函数的具体值无关，仅与顺序有关[5]。构造方法是先将种群中所有个体按目标函数值的好坏进行排序，设参数β∈(0,1)，基于顺序的适应度函数为：

（1）

3.3 选择交叉和变异

在遗传算法中，交叉概率和变异概率的选取是影响算法行为和性能的关键所在，直接影响算法的收敛性。在SGA中，交叉概率和变异概率能够随适应度自动调整，在保持群体多样性的同时保证了遗传算法的收敛性。在自适应基本遗传算法中，pc和pm按如下公式进行自动调整：

（2）

（3）

式中：fmax为群体中最大的适应度值；fave为每代群体的平均适应度值；f′为待交叉的两个个体中较大的适应度值；f为待变异个体的适应度值；此处，只要设定k1、k2、k3、k4为（0，1）之间的调整系数，Pc及Pm即可进行自适应调整。本文对标准的遗传算法进行了改进，改进后的遗传算法对交叉概率采用与个体无关，变异概率与个体有关。交叉算子主要作用是产生新个体，实现了算法的全局搜索能力。从种群整体进化过程来看，交叉概率应该是一个稳定而逐渐变小，到最后趋于某一稳定值的过程；而从产生新个体的角度来看，所有个体在交叉操作上应该具有同等地位，即相同的概率，从而使GA在搜索空间具有各个方向的均匀性。对公式（2)和（3）进行分析表明，适应度与交叉率和变异率呈简单的线性映射关系。当适应度低于平均适应度时，说明该个体是性能不好的个体数学建模论文，对它就采用较大的交叉率和变异率；如果适应度高于平均适应度，说明该个体性能优良，对它就根据其适应度值取相应的交叉率和变异率龙源期刊。

当个体适应度值越接近最大适应度值时，交叉概率和变异概率就越小；当等于最大适应度值时，交叉概率和变异概率为零。这种调整方法对于群体处于进化的后期比较合适，这是因为在进化后期，群体中每个个体基本上表现出较优的性能，这时不宜对个体进行较大的变化以免破坏了个体的优良性能结构；但是这种基本遗传算法对于演化的初期却不利，使得进化过程略显缓慢[6]。因为在演化初期，群体中较优的个体几乎是处于一种不发生变化的状态，而此时的优良个体却不一定是全局最优的，这很容易导致演化趋向局部最优解。这容易使进化走向局部最优解的可能性增加。同时，由于对每个个体都要分别计算Pc和Pm，会影响程序的执行效率，不利于实现。

对自适应遗传算法进行改进，使群体中具有最大适应度值的个体的交叉概率和变异概率不为零，改进后的交叉概率和变异概率的计算公式如式（4）和（5）所示。这样，经过改进后就相应地提高了群体中性能优良个体的交叉概率和变异概率，使它们不会处于一种停滞不前的状态，从而使得算法能够从局部最优解中跳出来获得全局最优解[7]。

(4)

(5)

其中：fmax为群体中最大的适应度值；fave为每代群体的平均适应度值；f′为待交叉的两个个体中较大的适应度值；f为待变异个体的适应度值；pc1为最大交叉概率；pm1为最大变异概率。

3.4 种群的进化与进化终止条件

将初始种群和产生的子代种群放在一起，形成新的种群，然后计算新的种群各个体的适应度，将适应度排在前面的m个个体保留，将适应度排在后面m个个体淘汰数学建模论文，这样种群便得到了进化[8]。每进化一次计算一下各个个体的目标函数值，当相邻两次进化平均目标函数之差小于等于某一给定精度ε时，即满足如下条件：

(6)

式中，为第t+1次进化后种群的平均目标函数值，为第t次进化后种群的平均目标函数值，此时，可终止进化。

3.5 重要参数的选择

GA的参数主要有群里规模n，交叉、变异概率等。由于这些参数对GA性能影响很大，因此参数设置的研究受到重视。对于交叉、变异概率的选择，传统选择方法是静态人工设置。现在有人提出动态参数设置方法，以减少人工选择参数的困难和盲目性。

4 结束语

遗传算法作为当前研究的热点，已经取得了很大的进展。由于遗传算法的并行性和全局搜索等特点，已在实际中广泛应用。本文针对传统遗传算法的早熟收敛、得到的结果可能为非全局最优收敛解以及在进化后期搜索效率较低等缺点进行了改进，改进后的遗传算法在全局收敛性和收敛速度方面都有了很大的改善，得到了较好的优化结果。

参考文献

[1]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,1999:66-68.

[2]王小平,曹立明.遗传算法理论[M].西安交通大学出版社,2002:1-50,76-79.

[3]李敏强,寇纪淞,林丹,李书全.遗传算法的基本理论与应用[M].科学出版社, 2002:1-16.

[4]涂承媛,涂承宇.一种新的收敛于全局最优解的遗传算法[J].信息与控制,2001,30(2):116-138

[5]陈玮,周激,流程进,陈莉.一种改进的两代竞争遗传算法[J].四川大学学报:自然科学版,2003.040(002):273-277.

[6]王慧妮,彭其渊,张晓梅.基于种群相异度的改进遗传算法及应用[J].计算机应用,2006,26(3):668-669.

[7]金晶,苏勇.一种改进的自适应遗传算法[J].计算机工程与应用,2005,41(18):64-69.

篇2

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

篇3

 

0引言

遗传算法是一种较新的全局优化搜索算法，它使用了群体搜索技术，用种群代表一组问题解，通过对当前种群施加选择、交叉和变异等一系列遗传操作，从而产生新的一代种群，并逐渐使种群进化到包含最优解或近似最优解的状态。但由于算法复杂度的限制, 遗传算法虽然能以概率收敛到全局最优解，其局部搜索速度和精度并不能得到很好的保证。近几年来遗传算法作为优良的全局寻优方法日趋成熟,尤其是和其他寻优方法的结合,进一步提高了遗传算法的性能，其中借助于混沌改进遗传算法的性能,是近年来遗传算法领域研究的热点之一，遗传算法和混沌优化的组合,可以使遗传算法的全局寻优能力,搜索精度,搜索速度等几方面得到较明显的改进。

1混沌的特征和虫口方程

混沌是存在于非线形系统中的一种较为普遍的现象。混沌并不是一片混乱，而是有着精致内在结构的一类现象。混沌运动具有遍历性、随机性等特点，混沌运动能在一定的范围内按照其自身的规律不重复地遍历所有状态。因此，如果利用混沌变量进行优化搜索，无疑会比随机搜索更具有优越性。

描述生态学上的虫口模型Logistic映射自May于1976年开始研究以来，受到了非线形科学家的高度关注，Logistic映射是混沌理论发展史上不可多得的典范性的混沌模型，如下式所示：

2混沌遗传算法

GA较传统数学优化方法更易找到全局最优解，但对于一些问题也存在过早收敛、收敛速度较慢、难以找到较精确解的情况。因此，本文通过Logistic映射及相关混沌理论提出了一种运算性能较好的混沌遗传函数优化算法。混沌遗传算法(CGA)的主要步骤如下：

1.初始化:预先确定运行参数，包括：种群规模M，交叉概率pc，变异概率pm，最大迭代次数n。随机产生一个分布均匀的初始群体(包含n个初始解)，计算各个个体的适应度值；

2.采用比例选择算子对当前种群进行选择操作，实现强留劣汰；

3.对当前种群进行交叉运算。将种群内个体两两随机组合，对每个配对的组合，首先由系统随机生成一个(0,1)之间的数，由交叉概率决定是否交叉。论文参考。论文参考。若交叉，则采用映射生成的序列经简单映射后利用高斯函数来决定交叉位置，否则，看下一对组合。所有的交叉位置由一个混沌序列即可决定；

5.若终止条件满足，则算法中止，否则转向步骤(2)。

本文尝试在将改进后的遗传算法与混沌优化算法相结合，提出一种基于混沌理论的混合遗传算法，算法的流程如下页流程图所示：

图1 改进后的混沌遗传算法（ICGA）流程图

3仿真分析

本文选用一维和多维多峰值函数为例，见表1，用遗传算法（GA）、混沌遗传算法（CGA）和本文算法（ICGA）进行比较研究。

表1 测试函数

实验结果比较如下（以下图纵坐标表示最大适应值，横坐标表示演化代数）

图2 f2实验结果比较示意图图3 f3实验结果比较示意图

从图2、图3的比较结果看，本文中算法初始种群较好，进化开始就能找到高的最大值，加快搜索的速度，整个算法的寻优结果比遗传算法好。论文参考。考虑到算法中使用了随机操作，仅仅由一次实验得到的结果是不能够充分说明问题的，因此，再进行统计比较。本文中进行了20次统计实验。比较结果如表2

篇4

中图分类号：TP183文献标识码：A文章编号：1009-3044(2008)14-20917-02

1 引言

近年来，遗传算法以其高效实用的特点迎来了兴盛发展的时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是在应用研究方面，众多的研究者在组合优化、模式分类、预测控制等领域都取得了丰硕的成果。对于大自然生物演化的行为准则，达尔文给出了“物竞天择，适者生存”的有力概括，这一学说也成为人们向大自然学习的一个依据。

2 国内外研究现状

遗传算法研究的兴起是在80年代末和90年代初期，但它的历史起源可追溯至60年代初期。早期的研究大多以对自然系统的计算机模拟为主。如raser的模拟研究，他提出了和现在的遗传算法十分相似的概念和思想。Holland和DeJong的创造性研究成果改变了早期遗传算法研究的无目标性和理论指导的缺乏。其中，Holland于1975年出版的著作《自然系统和人工系统的适配》系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论。它使用群体搜索技术，通过对目标群体实施选择、交叉、变异等一系列遗传操作，从而产生新一代的群体，并使群体进化包含或接近最优的状态。

自1985年以来，国际上已多次召开了遗传算法的学术会议和研讨会，国际遗传算法学会组织召开的ICGA（International Conference on Genetic Algorithms）会议和FOGA(Workshop on Foundation of Genetic Algorithms)会议，为研究和应用遗传算法提供了国际交流的机会。

3 遗传算法的产生及发展

遗传算法(Genetic Algorithms,GA)是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，20世纪60年纪末期到70年代初期，主要由美国著名学者密西根大学教授John.Holland其同事、学生们研究形成了一个较完整的理论和方法，从试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。它采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索方向。遗传算法的操作对象是一群二进制串（称为染色体、个体），即种群。这里每一个染色体都对应问题的一个解。从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个体，使用杂交和变异来产生下一代种群。如此模仿生命的进化一代代演化下去，直到满足期望的终止条件为止。由于它采用种群（即一组表示）的方式组织搜索，这使得它可以同时搜索空间内的多个区域。而且用种群组织搜索的方式使得遗传算法特别适合大规模并行。在赋予遗传算法自组织、自适应、自学习等特征的同时，优胜劣汰的自然选择和简单的遗传操作使遗传算法具有不受其搜索空间限制性条件（如可微、连续、单峰等）的约束及不需要其它辅助信息（如导数）的特点。这些崭新的特点使得演化算法不仅能获得较高的效率而且具有简单、易于操作和通用的特征，而这些特征正是遗传算法越来越受到人们青睐的主要原因之一。

4 遗传算法的基本原理

遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

遗传算法的实施过程包括编码、产生初始群体、计算适应度、复制、交换、突变、反复迭代、终止等操作。我们用Gen代表遗传（迭代）的代次，遗传算法从Gen=0开始。根据所研究问题的表达方式确定字符串长度L，接着随机产生M个初始群体。刚开始时，终止条件不会被满足，于是依次计算群体中各个个体的适应度。根据计算结果，依次进行复制、交换、突变等遗传操作。

遗传算法的思想简要给出如下：（1）初始化群体；（2）计算群体上每个个体的适应度值；（3）按由个体适应度值所决定的某个规则选择将进入下一代的个体；（4）按概率Pc进行交叉操作；（5）按概率Pc进行突变操作；（6）没有满足某种停止条件，则转第（2）步，否则进入（7）；（7）输出种群中适应度值最优的染色体作为问题的满意解或最优解。

5 遗传算法的缺点及改进

尽管遗传算法有许多优点，但目前存在的问题依然很多，如：（1）适应度值标定方式多种多样，没有一个简洁、通用的方法，不利于对遗传算法的使用；（2）遗传算法的早熟现象（即很快收敛到局部最优解而不是全局最优解）是迄今为止最难处理的关键问题；（3）快要接近最优解时在最优解附近左右摆动，收敛较慢。

因此，遗传算法通常需要解决以下问题，如确定编码方案，适应度函数标定，选择遗传操作方式及相关参数，停止准则确定等。相应的，为改进简单遗传算法的实际计算性能，很多学者的改进工作分别从参数编码、初始群体设定、适应度函数标定、遗传操作算子、控制参数的选择以及遗传算法的结构等方面提出的。

6 总结

遗传算法是将生物学原理应用于计算机科学的仿生学理论成果。由于它具有极强的解决问题的能力，引起了众多学者的兴趣与参与，已成为学术界跨学科的热门专题之一。遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多优化领域。据不完全统计，进化算法已经在16 个大领域、250 多个小领域中获得了应用。遗传算法在机器学习、过程控制、经济预测、工程优化等领域取得的成功，己引起了数学、物理学、化学、生物学、计算机科学、社会科学、经济科学及工程应用等领域专家的极大兴趣和广泛关注。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。

参考文献：

[1] Holland J H(1975).Adaptation in natural and artificial systems. University of Michigan Press.

[2] 田延硕.遗传算法的研究与应用[D].电子科技大学硕士论文.

[3] 李敏强,寇纪淞,林丹,等.遗传算法的基本理论与应用[M].科学出版社,2003.