遗传算法

1 遗传算法1.1 遗传算法的定义遗传算法(GeneticAlgorithm，GA)是近多年来发展起来的一种全新的全局优化算法，它是基于了生物遗传学的观点，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

它通过自然选择、遗传、复制、变异等作用机制，实现各个个体的适应性的提高，从而达到全局优化。

遗传算法151解决一个实际问题通常都是从一个种群开始，而这个种群通常都是含有问题的一个集合。

这个种群是由一定数目的个体所构成的，利用生物遗传的知识我们可以知道这些个体正好组成了我们知道的染色体，也就是说染色体是由一个个有特征的个体组成的。

另外我们还知道，遗传算法是由染色体组成，而染色体是由基因组成，可以这么说，基因就决定了个体的特性，所以对于遗传算法的最开始的工作就需要进行编码工作。

然后形成初始的种群，最后进行选择、交叉和变异的操作。

1.2遗传算法的重要应用在现实应用中，遗传算法在很多领域得到很好的应用，特别是在解决多维并且相当困难的优化问题中时表现出了很大的优势。

在遗传算法的优化问题的应用中，其中最为经典的应用就是我们所熟悉的函数优化问题，它也是对遗传算法的性能进行评价的最普遍的一种算法;另外的一个最重要的应用，也就是我们本文所研究的应用—组合优化问题，一般的算法很难解决组合优化问题的搜索空间不断扩大的局面，而组合优化问题正好是解决这种问题的最有效的方法之一，在本文的研究中，比如求解TSP问题、VRP问题等方面都得到了很好的应用;另外遗传算法在航空控制系统中的应用、在图像处理和模式识别的应用、在生产调度方面的应用以及在工人智能、人工生命和机器学习方面都得到了很好的应用。

其实在当今的社会中，有关于优化方面的问题应用于各行各业中，因此有关于优化问题已经变得非常重要，它对于整个社会的发展来说都是一个不可改变的发展方向，也是社会发展的一个非常重要的需要。

1.3 遗传算法的特点遗传算法不同于传统的搜索与优化方法，它是随着问题种类的不同以及问题规模的扩大，能以有限的代价来很好的解决搜索和优化的方法。

什么是遗传算法遗传算法的基本意思就是说象人的遗传一样，有一批种子程序，它们通过运算得到一些结果，有好有坏，把好的一批取出来，做为下一轮计算的初值进行运算，反复如此，最终得到满意的结果。

举个例子，假如有一个动物群体，如果你能让他们当中越强壮的越能优先交配和产籽，那么千万年后，这个动物群体肯定会变得更加强壮，这是很容易理解的。

同样，对于许多算法问题，特别是NP问题，比如说最短路径，如果有400个城市，让你找出最短的旅游路线，采用穷举比较，复杂度为O（n！），这时，你可以先随机产生100种路径，然后让他们之中路程越短的那些越能优先互相交换信息(比如每条里面随机取出10个位置互相交换一下),那么循环几千次后，算出来的路径就跟最短路径非常接近了（即求出一个近似最优解）。

遗传算法的应用还有很多，基本思想都一样，但实现上可能差别非常大。

现在有许多搞算法的人不喜欢遗传算法，因为，它只给出了一种“有用”的方法，却不能保证有用的程度，与此相反，能保证接近最优程度的概率算法更受青睐。

遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。

它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。

遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。

它是现代有关智能计算中的关键技术之一。

1.遗传算法与自然选择 达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。

这种学说认为，生物要生存下去，就必须进行生存斗争。

生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。

在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。

遗传算法的基本运算过程如下：a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。

b)个体评价：计算群体P(t)中各个个体的适应度。

c)选择运算:将选择算子作用于群体。

选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。

选择操作是建立在群体中个体的适应度评估基础上的。

d)交叉运算：将交叉算子作用于群体。

遗传算法中起核心作用的就是交叉算子。

e)变异运算：将变异算子作用于群体。

即是对群体中的个体串的某些基因座上的基因值作变动。

群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。

f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。

遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。

每个个体实际上是染色体(chromosome)带有特征的实体。

染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。

因此，在一开始需要实现从表现型到基因型的映射即编码工作。

由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。

这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

遗传算法(GENETIC ALGORITHM，GA）一、遗传算法的特点:1、遗传算法的操作对象是一组可行解,而非单个可行解；搜索轨道有多条,而非单条，因而具有良好的并行性。

2、遗传算法只需要利用目标的取值信息，而无需梯度等高价值信息，因而适用于任何大规模、高度非线性的不连续多峰函数的优化以及无解析表达式的目标函数的优化，具有很强的通用性。

3、遗传算法择优机制是一种软选择，加上其良好的并行性,使它具有良好的全局优化和稳健性。

4、遗传算法操作的可行解是经过编码化的（通常采用二进制编码），目标函数解释为编码化个体(可行解）的适应值，因而具有良好的可操作性和简单性.二、遗传算法的发展与现状遗传算法的产生归功于美国的Michigan大学的Holland在20世纪60年代末、70年代初的开创性，其本意是在人工适应系统中设计的一种基于自然演化原理搜索机制。

大约在同一时代，Foegl和Rechenberg及Schwefel,引入了另两种基于自然演化原理的算法，演化程序（evolutionary programming）和演化策略（evolution strategies)。

这三种算法构成了目前演化计算（evolutionary computation）领域的三大分支，它们从不同层次、不同角度模拟自然演化原理，以达到求解问题的目的.Holland不仅设计了遗传算法的模拟与操作原理,更重要的是他运用统计策略理论对遗传算法的搜索机理进行了理论分析,建立了著名的Schema定理和隐含并行(implicit parallelism）原理，为遗传算法奠定了基础。

遗传算法应用于函数优化始于De Jone的在线（one-line）和离线（off-line）指标仍是目前衡量遗传算法性能的主要手段。

1、遗传算法在神经网络、模糊系统和机器学习中的应用神经网络的学习包含两个优化过程，分别是网络连接权重的优化和网络拓扑结构的优化。

优化连接权重最著名的方法是Rumelhart提出的基于梯度下降法的反向传播法（backpropagation，BP).BP算法的最大弱点是局部极小问题和无法学习网络拓扑结构。

遗传算法（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）评估适应度对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。

什么是遗传算法遗传算法的基本意思就是说象人的遗传一样，有一批种子程序，它们通过运算得到一些结果，有好有坏，把好的一批取出来，做为下一轮计算的初值进行运算，反复如此，最终得到满意的结果。

举个例子，假如有一个动物群体，如果你能让他们当中越强壮的越能优先交配和产籽，那么千万年后，这个动物群体肯定会变得更加强壮，这是很容易理解的。

同样，对于许多算法问题，特别是NP问题，比如说最短路径，如果有400个城市，让你找出最短的旅游路线，采用穷举比较，复杂度为O（n！），这时，你可以先随机产生100种路径，然后让他们之中路程越短的那些越能优先互相交换信息(比如每条里面随机取出10个位置互相交换一下),那么循环几千次后，算出来的路径就跟最短路径非常接近了（即求出一个近似最优解）。

遗传算法的应用还有很多，基本思想都一样，但实现上可能差别非常大。

现在有许多搞算法的人不喜欢遗传算法，因为，它只给出了一种“有用”的方法，却不能保证有用的程度，与此相反，能保证接近最优程度的概率算法更受青睐。

遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。

它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。

遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。

它是现代有关智能计算中的关键技术之一。

1.遗传算法与自然选择 达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。

这种学说认为，生物要生存下去，就必须进行生存斗争。

生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。

在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。

遗传算法总结简介遗传算法（Genetic Algorithm，简称GA）是一种基于生物进化过程中的遗传机制和自然选择原理的优化方法。

它模拟了自然界的进化过程，通过对问题空间中的个体进行选择、交叉和变异等操作，逐步搜索并优化解的过程。

遗传算法被广泛应用于解决各种优化、搜索和机器学习问题。

基本原理遗传算法的基本原理是通过模拟自然选择和遗传机制，寻找问题空间中的最优解。

其主要步骤包括初始化种群、选择操作、交叉操作、变异操作和确定终止条件等。

1.初始化种群：遗传算法的第一步是生成一个初始种群，其中每个个体代表一个可能的解。

个体的编码可以使用二进制、整数或实数等形式，具体根据问题的特点而定。

2.选择操作：选择操作通过根据适应度函数对种群中的个体进行评估和排序，选择较优的个体作为下一代种群的父代。

通常采用轮盘赌选择、竞争选择等方法来进行选择。

3.交叉操作：交叉操作模拟了生物遗传中的交配过程。

从父代个体中选择一对个体，通过交叉染色体的某个位置，生成下一代个体。

交叉操作可以通过单点交叉、多点交叉或均匀交叉等方式进行。

4.变异操作：变异操作引入了种群中的一定程度的随机性，通过改变个体的染色体或基因，以增加种群的多样性。

变异操作可以是位变异、部分反转、插入删除等方式进行。

5.确定终止条件：遗传算法会循环执行选择、交叉和变异操作，直到满足一定的终止条件。

常见的终止条件有达到最大迭代次数、找到最优解或达到计算时间限制等。

优点和局限性优点•遗传算法可以在大规模问题空间中进行全局搜索，不受问题的线性性和连续性限制。

它适用于解决多目标和多约束问题。

•遗传算法具有自适应性和学习能力，通过不断的进化和优胜劣汰过程，可以逐步收敛到最优解。

•遗传算法易于实现和理解，可以直观地表示问题和解决方案。

局限性•遗传算法需要选择合适的编码方式和适应度函数，以及调整交叉和变异的概率等参数。

这些参数的选择对算法的性能和结果有较大影响，需要经验和调整。

遗传算法的应用一、什么是遗传算法？遗传算法是一种全局概率搜索优化算法。

遗传算法( Gnectci Algortihms) ，是一种模拟自然界生物进化过程的全局随机搜索算法，由美国Mcihigna大学的Hollnad 教授于60 年代首先提出。

它将计算机科学与进化论思想有机结合起来，借助于生物进化机制与遗传学原理，根优胜劣汰和适者生存的原则，通过模拟自然界中生物群体由低级、简单到高级、复杂的生物进化过程，使所要解决的问题从初始解逐渐逼近最优解或准最优解。

作为一种新的全局优化搜索算法，遗传算法因其简单易用，对很多优化问题能够较容易地解出令人满意的解，适用于并行分布处理等特点而得到深入发展和广泛应用，已在科学研究和工程最优化领域中展现出独特魅力.二、遗传算法的发展：从20世纪40年代，生物模拟就成为了计算科学的一个组成部分；20世纪50年代中期创立了仿生学；进入60年代后，美国密切根大学教授Holland及其学生创造出遗传算法。

三、遗传算法的特点：遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。

遗传算法具有进化计算的所有特征，同时又具有自身的特点：（1）搜索过程既不受优化函数的连续性约束，也没有优化函数导数必须存在的要求。

（2）遗传算法采用多点搜索或者说是群体搜索，具有很高的隐含并行性，因而可以提高计算速度。

（3）遗传算法是一种自适应搜索技术，其选择、交叉、变异等运算都是以一种概率方式来进行，从而增加了搜索过程的灵活性，具有较好的全局优化求解能力。

（4）遗传算法直接以目标函数值为搜索信息，对函数的性态无要求，具有较好的普适性和易扩充性。

（5）遗传算法更适合大规模复杂问题的优化。

四、遗传算法的原理和方法：（1）编码：编码是把一个问题的可行解从其解空间转换到GA 所能处理的搜索空间的转换方法。

而解码是由GA 解空间向问题空间的转换。

编码机制直接影响着算法的整体性能，也决定了种群初始化和各种遗传算子的设计等各种过程。

遗传算法简述及代码详解声明：本文内容整理自网络，认为原作者同意转载，如有冒犯请联系我。

遗传算法基本内容遗传算法为群体优化算法，也就是从多个初始解开始进行优化，每个解称为一个染色体，各染色体之间通过竞争、合作、单独变异，不断进化。

遗传学与遗传算法中的基础术语比较染色体：又可以叫做基因型个体(individuals)群体/种群(population)：一定数量的个体组成，及一定数量的染色体组成，群体中个体的数量叫做群体大小。

初始群体：若干染色体的集合，即解的规模，如30，50等，认为是随机选取的数据集合。

适应度(fitness)：各个个体对环境的适应程度优化时先要将实际问题转换到遗传空间，就是把实际问题的解用染色体表示，称为编码，反过程为解码/译码，因为优化后要进行评价（此时得到的解是否较之前解优越），所以要返回问题空间，故要进行解码。

SGA采用二进制编码，染色体就是二进制位串，每一位可称为一个基因；如果直接生成二进制初始种群，则不必有编码过程，但要求解码时将染色体解码到问题可行域内。

遗传算法的准备工作:1) 数据转换操作，包括表现型到基因型的转换和基因型到表现型的转换。

前者是把求解空间中的参数转化成遗传空间中的染色体或者个体(encoding)，后者是它的逆操作(decoding)2) 确定适应度计算函数，可以将个体值经过该函数转换为该个体的适应度，该适应度的高低要能充分反映该个体对于解得优秀程度。

非常重要的过程。

遗传算法基本过程为:1) 编码，创建初始群体2) 群体中个体适应度计算3) 评估适应度4) 根据适应度选择个体5) 被选择个体进行交叉繁殖6) 在繁殖的过程中引入变异机制7) 繁殖出新的群体，回到第二步实例一：（建议先看实例二）求 []30,0∈x 范围内的()210-=x y 的最小值1) 编码算法选择为"将x 转化为2进制的串"，串的长度为5位（串的长度根据解的精度设 定，串长度越长解得精度越高）。