下载文档原格式
什么是遗传算法遗传算法的基本意思就是说象人的遗传一样，有一批种子程序，它们通过运算得到一些结果，有好有坏，把好的一批取出来，做为下一轮计算的初值进行运算，反复如此，最终得到满意的结果。
举个例子，假如有一个动物群体，如果你能让他们当中越强壮的越能优先交配和产籽，那么千万年后，这个动物群体肯定会变得更加强壮，这是很容易理解的。
同样，对于许多算法问题，特别是NP问题，比如说最短路径，如果有400个城市，让你找出最短的旅游路线，采用穷举比较，复杂度为O（n！），这时，你可以先随机产生100种路径，然后让他们之中路程越短的那些越能优先互相交换信息(比如每条里面随机取出10个位置互相交换一下),那么循环几千次后，算出来的路径就跟最短路径非常接近了（即求出一个近似最优解）。
遗传算法的应用还有很多，基本思想都一样，但实现上可能差别非常大。
现在有许多搞算法的人不喜欢遗传算法，因为，它只给出了一种“有用”的方法，却不能保证有用的程度，与此相反，能保证接近最优程度的概率算法更受青睐。
遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。
它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。
遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。
它是现代有关智能计算中的关键技术之一。
1.遗传算法与自然选择 达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。
这种学说认为，生物要生存下去，就必须进行生存斗争。
生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。
在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。
遗传算法（GeneticAlgorithms）遗传算法前引：1、TSP问题1.1 TSP问题定义旅⾏商问题（Traveling Salesman Problem，TSP）称之为货担郎问题，TSP问题是⼀个经典组合优化的NP完全问题，组合优化问题是对存在组合排序或者搭配优化问题的⼀个概括，也是现实诸多领域相似问题的简化形式。
1.2 TSP问题解法传统精确算法：穷举法，动态规划近似处理算法：贪⼼算法，改良圈算法，双⽣成树算法智能算法：模拟退⽕，粒⼦群算法，蚁群算法，遗传算法等遗传算法：性质：全局优化的⾃适应概率算法2.1 遗传算法简介遗传算法的实质是通过群体搜索技术，根据适者⽣存的原则逐代进化，最终得到最优解或准最优解。
它必须做以下操作：初始群体的产⽣、求每⼀个体的适应度、根据适者⽣存的原则选择优良个体、被选出的优良个体两两配对，通过随机交叉其染⾊体的基因并随机变异某些染⾊体的基因⽣成下⼀代群体，按此⽅法使群体逐代进化，直到满⾜进化终⽌条件。
2.2 实现⽅法根据具体问题确定可⾏解域，确定⼀种编码⽅法，能⽤数值串或字符串表⽰可⾏解域的每⼀解。
对每⼀解应有⼀个度量好坏的依据，它⽤⼀函数表⽰，叫做适应度函数，⼀般由⽬标函数构成。
确定进化参数群体规模、交叉概率、变异概率、进化终⽌条件。
案例实操我⽅有⼀个基地，经度和纬度为（70，40）。
假设我⽅飞机的速度为1000km/h。
我⽅派⼀架飞机从基地出发，侦察完所有⽬标，再返回原来的基地。
在每⼀⽬标点的侦察时间不计，求该架飞机所花费的时间（假设我⽅飞机巡航时间可以充分长）。
已知100个⽬标的经度、纬度如下表所列:3.2 模型及算法求解的遗传算法的参数设定如下：种群⼤⼩M=50；最⼤代数G=100;交叉率pc=1，交叉概率为1能保证种群的充分进化；变异概率pm=0.1，⼀般⽽⾔，变异发⽣的可能性较⼩。
编码策略:初始种群：⽬标函数：交叉操作：变异操作：选择：算法图：代码实现：clc,clear, close allsj0=load('data12_1.txt');x=sj0(:,1:2:8); x=x(:);y=sj0(:,2:2:8); y=y(:);sj=[x y]; d1=[70,40];xy=[d1;sj;d1]; sj=xy*pi/180; %单位化成弧度d=zeros(102); %距离矩阵d的初始值for i=1:101for j=i+1:102d(i,j)=6370*acos(cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*...cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2)));endendd=d+d'; w=50; g=100; %w为种群的个数，g为进化的代数for k=1:w %通过改良圈算法选取初始种群c=randperm(100); %产⽣1，...，100的⼀个全排列c1=[1,c+1,102]; %⽣成初始解for t=1:102 %该层循环是修改圈flag=0; %修改圈退出标志for m=1:100for n=m+2:101if d(c1(m),c1(n))+d(c1(m+1),c1(n+1))<...d(c1(m),c1(m+1))+d(c1(n),c1(n+1))c1(m+1:n)=c1(n:-1:m+1); flag=1; %修改圈endendendif flag==0J(k,c1)=1:102; break %记录下较好的解并退出当前层循环endendendJ(:,1)=0; J=J/102; %把整数序列转换成[0,1]区间上实数即染⾊体编码for k=1:g %该层循环进⾏遗传算法的操作for k=1:g %该层循环进⾏遗传算法的操作A=J; %交配产⽣⼦代A的初始染⾊体c=randperm(w); %产⽣下⾯交叉操作的染⾊体对for i=1:2:wF=2+floor(100*rand(1)); %产⽣交叉操作的地址temp=A(c(i),[F:102]); %中间变量的保存值A(c(i),[F:102])=A(c(i+1),[F:102]); %交叉操作A(c(i+1),F:102)=temp;endby=[]; %为了防⽌下⾯产⽣空地址，这⾥先初始化while ~length(by)by=find(rand(1,w)<0.1); %产⽣变异操作的地址endB=A(by,:); %产⽣变异操作的初始染⾊体for j=1:length(by)bw=sort(2+floor(100*rand(1,3))); %产⽣变异操作的3个地址%交换位置B(j,:)=B(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw(3)+1:102]);endG=[J;A;B]; %⽗代和⼦代种群合在⼀起[SG,ind1]=sort(G,2); %把染⾊体翻译成1，...,102的序列ind1num=size(G,1); long=zeros(1,num); %路径长度的初始值for j=1:numfor i=1:101long(j)=long(j)+d(ind1(j,i),ind1(j,i+1)); %计算每条路径长度endend[slong,ind2]=sort(long); %对路径长度按照从⼩到⼤排序J=G(ind2(1:w),:); %精选前w个较短的路径对应的染⾊体endpath=ind1(ind2(1),:), flong=slong(1) %解的路径及路径长度xx=xy(path,1);yy=xy(path,2);plot(xx,yy,'-o') %画出路径以上整个代码中没有调⽤GA⼯具箱。
遗传算法一、遗传算法的简介及来源1、遗传算法简介遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《自然系统和人工系统的自适应》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。
遗传算法模仿了生物的遗传、进化原理, 并引用了随机统计理论。
在求解过程中, 遗传算法从一个初始变量群体开始, 一代一代地寻找问题的最优解, 直至满足收敛判据或预先设定的迭代次数为止。
它是一种迭代式算法。
2、遗传算法的基本原理遗传算法是一种基于自然选择和群体遗传机理的搜索算法, 它模拟了自然选择和自然遗传过程中发生的繁殖、杂交和突变现象。
在利用遗传算法求解问题时, 问题的每个可能的解都被编码成一个“染色体”,即个体, 若干个个体构成了群体( 所有可能解) 。
在遗传算法开始时, 总是随机地产生一些个体( 即初始解) , 根据预定的目标函数对每个个体进行评价, 给出了一个适应度值。
基于此适应度值, 选择个体用来繁殖下一代。
选择操作体现了“适者生存”原理, “好”的个体被选择用来繁殖, 而“坏”的个体则被淘汰。
然后选择出来的个体经过交叉和变异算子进行再组合生成新的一代。
这一群新个体由于继承了上一代的一些优良性状,因而在性能上要优于上一代, 这样逐步朝着更优解的方向进化。
因此, 遗传算法可以看作是一个由可行解组成的群体逐代进化的过程。
3、遗传算法的一般算法（1）创建一个随机的初始状态初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的情况不一样，在那里问题的初始状态已经给定了。
（2）评估适应度对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。
1 遗传算法1.1 遗传算法的定义遗传算法(GeneticAlgorithm，GA)是近多年来发展起来的一种全新的全局优化算法，它是基于了生物遗传学的观点，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
它通过自然选择、遗传、复制、变异等作用机制，实现各个个体的适应性的提高，从而达到全局优化。
遗传算法151解决一个实际问题通常都是从一个种群开始，而这个种群通常都是含有问题的一个集合。
这个种群是由一定数目的个体所构成的，利用生物遗传的知识我们可以知道这些个体正好组成了我们知道的染色体，也就是说染色体是由一个个有特征的个体组成的。
另外我们还知道，遗传算法是由染色体组成，而染色体是由基因组成，可以这么说，基因就决定了个体的特性，所以对于遗传算法的最开始的工作就需要进行编码工作。
然后形成初始的种群，最后进行选择、交叉和变异的操作。
1.2遗传算法的重要应用在现实应用中，遗传算法在很多领域得到很好的应用，特别是在解决多维并且相当困难的优化问题中时表现出了很大的优势。
在遗传算法的优化问题的应用中，其中最为经典的应用就是我们所熟悉的函数优化问题，它也是对遗传算法的性能进行评价的最普遍的一种算法;另外的一个最重要的应用，也就是我们本文所研究的应用—组合优化问题，一般的算法很难解决组合优化问题的搜索空间不断扩大的局面，而组合优化问题正好是解决这种问题的最有效的方法之一，在本文的研究中，比如求解TSP问题、VRP问题等方面都得到了很好的应用;另外遗传算法在航空控制系统中的应用、在图像处理和模式识别的应用、在生产调度方面的应用以及在工人智能、人工生命和机器学习方面都得到了很好的应用。
其实在当今的社会中，有关于优化方面的问题应用于各行各业中，因此有关于优化问题已经变得非常重要，它对于整个社会的发展来说都是一个不可改变的发展方向，也是社会发展的一个非常重要的需要。
1.3 遗传算法的特点遗传算法不同于传统的搜索与优化方法，它是随着问题种类的不同以及问题规模的扩大，能以有限的代价来很好的解决搜索和优化的方法。
它的特点[9]主要如下:(1)智能性。
应用遗传算法求解问题时，在编码方案、适应度函数以及遗传算子群定后，遗传算法能够利用进化过程中获得的信息自行组织搜索。
它具有自组织、自适应和自学习的能力，因此，利用遗传算法的方法，可以解决那些复杂的非结构化的问题。
(2)群体搜索特性。
遗传算法采用同时对搜索空间中的多个解进行评估的方法，同时处理群体中多个个体，这样就避免了传统方法中采用单点搜索时所产生的局部某个单峰的极值点。
它使遗传算法具有较好的全局搜索的性能。
(3)不需要辅助信息。
遗传算法不需要求导或者其他辅助的知识。
而只是需要影响搜索方向的目标函数和适应度函数。
(4)遗传算法的本质并行性。
它具有固定的并行性和并行计算的能力。
(5)遗传算法强调概率转化规则，而不是确定的转化规则。
(6)遗传算法具有可扩展的能力。
它易于同其他的技术结合起来使用。
1.4 基本遗传操作1）.编码编码(Encoding)就是要把问题的参数或者解转化成为遗传中的染色体或者个体。
遗传算法不能直接的处理解空间里的数据，因此，我们必须通过编码把把它们表示成遗传里的基因结构数据模型。
在遗传算法编码过程中我们必须考虑编码规则:完备性、健壮性、非冗余性。
DeJong在文献[’。
]里提出了两条非常实用的编码的方法:第一种方法被叫做有意义的积木块的方法;第二种方法被叫做最小的字符串的方法。
前一种方法它在求解问题的过程中利用了低阶和短定义长度的模式，所以说它的实现过程很简单，很容易实现，而后一种方法则是通过对所求问题能够表示成最小的编码字符串，从而实现它的编码。
对于实际应用问题，如果要寻求一种对某一个问题描述最为方便、遗传算法效率最高的编码方案，则必须通过对编码方法、交叉方法、变异方法等进行统一的考虑。
遗传算法中编码的方法有好多种，比如:二进制编码方法、格雷码编码方法、符号编码方法、实数编码方法、多参数级联编码方法等。
对于在实际应用中的不同问题，应选择相应或合适的编码方案。
尤其在几年来，遗传算法在求解高维或者复杂优化问题的时候大多数采用实数编码方案。
这是因为实数编码能够使得问题解的表示比较自然。
而月很容易引入相关领域的知识，所以一说它的使用将是越来越广泛[”]。
高遗传算法的计算效率和全局的收敛性。
选择通常分为两步[‘3]:首先是计算适应度，可以通过按比例的适应度计算(ProportionalFitnessAssignment)或基于排序的适应度计算(Rank一basedFitnessAssignment)等方法;其次根据实际的选择，按照适应度进行父代的选择，父代选择的算法有好多种，通常我们选择算子有:适应度比例选择、联赛选择方法、最佳个体保存方法、期望值方法。
2) 交叉在中学我们都学过生物，从那时我们就了解到，不管是人类还是生物，在进化的过程中，他们产生新的个体都是通过交配两个同源的染色体而形成的。
遗传算法就是根据生物体的这个特点利用了交叉算法来形成新的个体的。
在整个遗传算法中，交叉操作是最主要的一个步骤，所以说交叉算子的设计与实现与你所研究的问题密切相关。
交叉算子的设计要与个体编码的设计统一考虑。
通过交叉操作可以得到新一代的个体，新个体继承了父代个体的特征。
将群体中的各个体随机搭配成对，对每一个个体，以交叉概率交换他们的部分染色体。
3)变异通过所学的生物学知识可以知道在生物的遗传进化过程当中，某个细胞由于在分裂复制的过程中可能会产生一些差错，一比如说A变异成了B，所以就有可能会导致个体上的一些基因发生了突变，这种突变会带来了新的染色体，从而形成了新的物种。
人类中的一些疑难杂病，其实就是基因突变所引起的。
我们都知道产生这种变异的可能性是非常小的，但是它却是存在的，而且他能够产生一个新的个体或者物种。
遗传算法就是根据生物体的这个特点利用了变异算法来形成新的个体的。
变异操作[l5珠口生物进化过程中类似，必须首先要确定一个个体，当然这个个体来源于某个种群，其次对这个个体通过变异概率去随机更改基因值。
遗传算法中变异发生的概率很低，所以说变异为新个体产生了机会，而变异操作仅仅是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，维持了种群的多样性，防止它出现早熟现象。
在标准遗传算法当中使用变异操作主要有以下两个好处:第一:它的变异能够产生新的种群，继而就维持群体的多样性，而且还能预防种群出现早熟的现象。
第二:如果没有变异算子，遗传算法的局部搜索能力很差，正是有了变异操作从而提高了遗传算法过程中的局部搜索的能力。
遗传算法通过交叉操作和变异操作这两个既相互配合而又相互竞争的操作使遗传算法具有兼顾全局和局部的均衡搜索能力。
因此，如何有效地配合这两种操作，是目前遗传算法研究中的一个重要内容。
1.5 遗传算法的基本框架从上面的知识我们可以明显的知道，每一代个体要想传到下一代必须要包括三个主要的过程，他们分别是:选择操作(selectionoPerator)、交叉操作(Ssove:operator)、变异操作(Mutationoperator)。
另外在整个遗传算法过程中，还要注意了下边几个基本的操作:比如说编码的确定、怎样设定它的初始种群、怎样设计它的适应度函数等其它的操作。
1.6 遗传算法的运算步骤对于用基本的遗传算法求解一个问题的运算一般大致分为六个步骤:SteP1:根据问题确定染色体，生成初始种群，该步其实是一个初始化的过程，在该步中只要设置一些参数就行了;steP2:计算种群中各个个体的适应度，适应度函数一般是要以目标函数来确定的;SteP3:选择操作，选择操作就是建立在对个体的适应度进行评价的基础上;steP4:交叉操作，在整个遗传算法中，交叉操作是最主要的一步交叉算子的设计要与个体编码的设计统一考虑;SteP5:变异操作，变异操作首先必须在群体中选择一个个体，对于选中的这个个体以变异概率随机改变染色体结构数据中的某个串的值，;steP6:终止条件判断，若进化代数与最大进化代数相等的话，则整个算法就结束，否则进化代数的次数加1，然后转到stepZ进行循环操作。
2.初始化种群的生成种群是由一定数量的个体组成的，种群规模是由种群中的个体的数目组成。
种群规模是遗传算法几个控制参数之一。
在遗传操作过程中，需要中群型的操作，所以一定要准备一个由若干个初始解组成的初始种群。
在初始种群中的每一个个体都是通过随机地方法产生的，也就是我们平时所讲的进化的初始代。
初始种群的选择对发挥遗传算法的效能产生重大影响。
一般我们选择种群规模都在几十到几百之间取值，种群规模的选择跟问题的难度成正比例关系。
初始种群的设置一般可采用以下规则I’2]:(l)首先要确定分布范围，这个分布范围是根据整个问题的最优解来确定的，最后对初始种群进行设定。
(2)通过随机函数产生一定量的个体，从产生的个体中挑选最优的个体加入到种群中。
3.适应度及参数设置适应度(Fitness)是各个个体对它的环境所适应的程度。
适应度评价是对解质量的一种衡量。
适应度函数一般是要以目标函数来确定的。
适应度的好坏直接决定了个体的好坏，因为遗传算法在求解问题(搜索问题的时候)不需要其它的信息。
所以可以这么说适应度也可以作为评判遗传操作的依据。
怎样确定一个个体的适应度，必须进行下面两个操作:第一，，计算目标函数值，这里的目标值的对象是某个经过编码后所得到的个体;第二，根据上面过程所求得的目标函数值，通过一定的规则，从而求出这个个体的适应度。
对于遗传算法的一些参数的设置，应该通常考虑以下的参数:串的长度、种群的规模、交叉概率、变异概率等，这些参数直接关系到遗传算法的性能的好坏。
通常情况下，尤其在简单遗传算法中，这些参数都是人为设定不变的。
可是对于复杂的遗传算法，这个时候可能会增加算法的复杂性程度以及会降低算法的效率，所以我们这个时候也必须要对参数进行相应的改进。
4.选择选择其实是用来确定重组或者交叉个体、以及被选个体将产生多少个子代个体。
只有对个体的适应度进行评价才能进行选择操作。
因此，选择操作也是遗传算法中一个很重要的环节。
因为选择操作不仅可以避免基因的遗漏，‘而且还能提高遗传算法的计算效率和全局的收敛性。
选择通常分为两步[‘3]:首先是计算适应度，可以通过按比例的适应度计算(ProportionalFitnessAssignment)或基于排序的适应度计算(Rank一basedFitnessAssignment)等方法;其次根据实际的选择，按照适应度进行父代的选择，父代选择的算法有好多种，通常我们选择算子有:适应度比例选择、联赛选择方法、最佳个体保存方法、期望值方法。
