遗传算法

Matlab 中的fimincon函数优化

还是蛮简单的，而且 python 中有现成的遗传算法工具箱可用。实现的关键则是如何进行编码，这个码就是函数的参数，参数的个数就是染色体中基因的个数， 选择交叉变异，无非就是改变基因的值而不改变染色体的长度，然后产生新的染色体，将新的染色体重的值以参数的形式带入到函数中求得新的函数值

第1章 绪论1.1 从生物进化到遗传算法1.2 遗传算法的描述1.3 表示方案的实例1.3.1 工程设计的最优化1.3.2 人工蚁问题1.4 遗传算法的特点1.5 遗传算法的发展简史1.6 遗传算法的研究内容及前景1.7 遗传算法的应用第2章 遗传算法的基本原理2.1 复杂系统的适应过程2.1.1 复杂系统的适应性2.1.2 适应过程的数学模型2.2 遗传算法的基本描述2.2.1 整体优化问题2.2.2 遗传算法的基本流程2.2.3 遗传编码2.2.4 适应函数（评价函数）2.2.5 遗传算子2.2.6 群体设定2.2.7 初始化群体2.2.8 终止循环的条件2.2.9 标准遗传算法的流程2.2.10 控制参数和选择2.2.11 遗传算法的性能评估2.3 遗传算法的模式理论2.3.1 模式与模式空间2.3.2 模式生存模型2.3.3 双臂赌机分析2.3.4 基因模块假设2.3.5 模式处理与隐含并行性2.3.6 模式处理与遗传算子的性能2.4 遗传算法与其他搜索技术的比较2.4.1 启发式随机搜索技术的基本功能2.4.2 局域搜索技术2.4.3 模拟退火算法2.4.4 遗传算法搜索2.4.5 启发式搜索技术比较2.5 遗传算法计算实例2.5.1 单调连续函数2.5.2 One-Max函数2.5.3 皇家大道问题2.6 遗传算法杂交率与变异率关系的研究2.6.1 研究方法简述2.6.2 算例2.6.3 应用2.6.4 结论第3章 遗传算法数学机理分析3.1 遗传算法的基本定理3.2 隐含并行性3.3 Walsh模式变换3.3.1 Walsh函数3.3.2 用Walsh函数表示模式平均适应度3.3.3 Walsh系数与异位显性（epistasis）3.4 非均匀Walsh模式变换3.5 最小欺骗问题3.6 遗传算法欺骗问题的分析与设计……第4章 解连续优化问题的遗传算法第5章 分布式遗传算法研究第6章 遗传算法的实现技术第7章 遗传算法应用实例参考文献

《遗传算法原理与应用实例》主要结合应用实例系统讨论、介绍遗传算法原理及其应用，主要内容包括：遗传算法的基本原理和数学机理、解决连续问题优化的遗传算法和分布式遗传算法、遗传算法的实现技术、遗传算法应用实例，并给出了两个典型的遗传算法源程序。《遗传算法原理与应用实例》在详细介绍遗传算法理论与方法的同时，还给_出了基于遗传算法的费托合成反应动力学模型参数优化的详细设计应用。

1.2 遗传算法的原理 遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的

遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作:适应度高的个体被遗传到下一代群体中的概率大。遗传算法（Genetic Algorithm，GA）最早是由美国的John holland于20世纪70年代提出,该算法是根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。该算法通过数学的方式,利用计算机仿真运算,将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时,相对一些常规的优化算法,通常能够较快地获得较好的优化结果。遗传算法已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。遗传算法的起源可追溯到20世纪60年代初期。1967年,美国密歇根大学J.Holland教授的学生Bagley在他的博士论文中首次提出了遗传算法这一术语。并讨论了遗传算法在博弈中的应用,但早期研究缺乏带有指导性的理论和计算工具的开拓。1975年,J.Holland等提出了对遗传算法理论研究极为重要的模式理论,出版了专著《自然系统和人工系统的适配》,在书中系统阐述了遗传算法的基本理论和方法,推动了遗传算法的发展。20世纪80年代后,遗传算法进入兴盛发展时期，被广泛应用于自动控制、生产计划、图像处理、机器人等研究领域。由于遗传算法不能直接处理问题空间的参数,因此必须通过编码将要求解的问题表示成遗传空间的染色体或者个体。这一转换操作就叫做编码，也可以称作（问题的）表示。

算的遗传算法是一种利用自然遗传规律来搜索最优解的数学优化工具。其基本过程及原理简单概括如下： 遗传算法是具有“生成＋检测”迭代过程的搜索算法，是一种群体型操作。操作以群体中的所有个体为对象。它有三个基本操作算子：选择、变异和交叉。遗传算法中包含五个基本要素：参数编码；初始群体设定；适应度函数设计；遗传操作设计；控制参数设定（主要指群体大小和使用遗传操作的概率等）。这五个要素构成了遗传算法的核心内容。参数编码就是将优化问题变量通过一定的变换映射到染色体基因上面。初始群体设定应使其具有足够的规模和随机性。遗传算法根据染色体基因值来计算染色体适应度，并根据适应度值决定染色体的交配概率，适应度大的染色体交配概率大。染色体交配之后应对染色体进行变异，这样可以避免算法过早收敛。变异之后的群体就是子代，它将作为下一代群体的父代，进行同样的遗传操作，如此循环。在算法执行过程中，控制参数的设定直接影响算法的精度和效率，因此选定合适的控制参数是提高算法效率的关键之一。一般采用观察法来选定合适的控制参数

遗传算法负荷分解的原理是通过模拟生物进化过程中的自然选择、交叉变异等机制,逐步优化任务分配方案,从而达到负载均衡的目的。具体来说,遗传算法负荷分解的步骤如下：1、将任务分解为多个子任务,每个子任务的处理时间不同。2、将处理器分为多个组,每个组包含多个处理器。3、将每子任务随分配给一个处理器。4、计算每个组的负载均衡度,即各组中处理器的平均负载差异。5、对于不平衡的组,采用自然选择、交叉和变异等遗传算法操作,生成新的任务分配方案。6、重复步骤4和5,直到达到预设的负载均衡度要求。在遗传算法负荷分解中,自然选择操作是根据适应度函数来选择优秀的个体,交叉操作是将两个个体的染色体进行交叉,生成新的个体,变异操作是对个体的染色体进行随机变异,引入新的基因。通过这些操作,遗传算法能够不断优化任务分配方案,提高系统的负载均衡度,从而提高系统的性能。

遗传算法有相当大的引用。遗传算法在游戏中应用的现状在遗传编码时, 一般将瓦片的坐标作为基因进行实数编码, 染色体的第一个基因为起点坐标, 最后一个基因为终点坐标, 中间的基因为路径经过的每一个瓦片的坐标。在生成染色体时, 由起点出发, 随机选择当前结点的邻居节点中的可通过节点, 将其坐标加入染色体, 依此循环, 直到找到目标点为止, 生成了一条染色体。重复上述操作, 直到达到指定的种群规模。遗传算法的优点：1、遗传算法是以决策变量的编码作为运算对象，可以直接对集合、序列、矩阵、树、图等结构对象进行操作。这样的方式一方面有助于模拟生物的基因、染色体和遗传进化的过程，方便遗传操作算子的运用。另一方面也使得遗传算法具有广泛的应用领域，如函数优化、生产调度、自动控制、图像处理、机器学习、数据挖掘等领域。2、遗传算法直接以目标函数值作为搜索信息。它仅仅使用适应度函数值来度量个体的优良程度，不涉及目标函数值求导求微分的过程。因为在现实中很多目标函数是很难求导的，甚至是不存在导数的，所以这一点也使得遗传算法显示出高度的优越性。3、遗传算法具有群体搜索的特性。它的搜索过程是从一个具有多个个体的初始群体P(0)开始的，一方面可以有效地避免搜索一些不必搜索的点。另一方面由于传统的单点搜索方法在对多峰分布的搜索空间进行搜索时很容易陷入局部某个单峰的极值点，而遗传算法的群体搜索特性却可以避免这样的问题，因而可以体现出遗传算法的并行化和较好的全局搜索性。4、遗传算法基于概率规则，而不是确定性规则。这使得搜索更为灵活，参数对其搜索效果的影响也尽可能的小。5、遗传算法具有可扩展性，易于与其他技术混合使用。以上几点便是遗传算法作为优化算法所具备的优点。遗传算法的缺点：遗传算法在进行编码时容易出现不规范不准确的问题。

遗传算法是基于生物学的，理解或编程都不太难。下面是遗传算法的一般算法：　　创建一个随机的初始状态　　初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的情况不一样，在那里问题的初始状态已经给定了。　　评估适应度　　对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。不要把这些“解”与问题的“答案”混为一谈，可以把它理解成为要得到答案，系统可能需要利用的那些特性。　　繁殖(包括子代突变)　　带有较高适应度值的那些染色体更可能产生后代(后代产生后也将发生突变)。后代是父母的产物，他们由来自父母的基因结合而成，这个过程被称为“杂交”。　　下一代　　　　如果新的一代包含一个解，能产生一个充分接近或等于期望答案的输出，那么问题就已经解决了。如果情况并非如此，新的一代将重复他们父母所进行的繁衍过程，一代一代演化下去，直到达到期望的解为止。　　并行计算　　　　非常容易将遗传算法用到并行计算和群集环境中。一种方法是直接把每个节点当成一个并行的种群看待。然后有机体根据不同的繁殖方法从一个节点迁移到另一个节点。另一种方法是“农场主/劳工”体系结构，指定一个节点为“农场主”节点，负责选择有机体和分派适应度的值，另外的节点作为“劳工”节点，负责重新组合、变异和适应度函数的评估。

遗传算法基本原理：遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。遗传算法的基本步骤如下：（1）初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。（2）个体评价：计算群体P(t)中各个个体的适应度。（3）选择运算：将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。（4）交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。（5）变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。（6）终止条件判断：若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。什么是遗传算法遗传算法根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。该算法通过数学的方式，利用计算机仿真运算，将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时，相对一些常规的优化算法，通常能够较快地获得较好的优化结果。遗传算法已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。

function [x fx string]=fun_SuiJiSuanFa2(N,genLenth,Pc,Pm,downbound,upbound,generation)%[x fx string]=fun_SuiJiSuanFa2(6,16,0.7,0.01,-3,3,100)%f 表示函数%N表示染色体种群大小%genLenth表示染色体长度%Pc表示交叉概率%Pm表示突变概率%downbound%upbound%generation循环代数%进制编码,此处编写为二进制num=2;initdata=randi([0 num-1],N,genLenth);%二进制编码的权值weight=(num).^(genLenth/2-1:-1:0);weights=repmat(weight,N,1);%保存每代的最好值和平均值,meanally=zeros(1,generation);maxally=zeros(1,generation);Nowx=zeros(generation,genLenth);for k=1:generation%解码后的整数allx1=sum(initdata(:,1:genLenth/2).*weights,2);allx2=sum(initdata(:,genLenth/2+1:end).*weights,2);%映射到取值范围delt=(upbound-downbound)/(num^(genLenth/2)-1);allx1=allx1.*delt+downbound;allx2=allx2.*delt+downbound;%染色体的适应性ally=f(allx1,allx2);%平均值，最大值meanally(k)=mean(ally);maxally(k)=max(ally);%找下标，确定是哪条染色体index=find(ally==maxally(k));Nowx(k,:)=initdata(index(1),:);%最大值没有提高就取上次的if(k>=2&&maxally(k)<maxally(k-1))maxally(k)=maxally(k-1);Nowx(k,:)=Nowx(k-1,:);end%染色体的适应性比率ratio=ally./sum(ally);%交叉,变异%？？交叉几个，从第几个开始。%此处只交叉1个（总共才6个），随机给一个。sumRatio=cumsum(ratio);data=zeros(N,genLenth);for i=1:N/2Select1=find(sumRatio>=rand);Select2=find(sumRatio>=rand);data(2*i-1,:)=initdata(Select1(1),:);data(2*i,:)=initdata(Select2(1),:);if(rand<Pc)%交叉location=randi([1,genLenth]);temp=data(2*i-1,location:end);data(2*i-1,location:end)=data(2*i,location:end);data(2*i,location:end)=temp;else%变异if(rand<Pm)location=randi([1,genLenth]);data(2*i-1,location)=1-data(2*i-1,location);endif(rand<Pm)location=randi([1,genLenth]);data(2*i,location)=1-data(2*i,location);endendendinitdata=data;endfx=max(maxally);lastIndex=find(maxally==fx);string=Nowx(lastIndex(1),:);x(1)=sum(string(1:genLenth/2).*weight).*(upbound-downbound)/(num^(genLenth/2)-1)+downbound;x(2)=sum(string(1+genLenth/2:end).*weight).*(upbound-downbound)/(num^(genLenth/2)-1)+downbound;%绘制性能图%figure,hold on;clf;figure(1),hold on;plot((1:k)",meanally,"b.-");plot((1:k)",maxally,"r.:");endfunction fun=f(x,y)fun=(1-x).^2.*exp(-x.^2-(1+y).^2)-(x-x.^3-y.^3).*exp(-x.^2-y.^2);%fun=-(x-1).^2-3.*(y-2).^2+100;end

在VRP问题中，假设有一个供求关系系统，车辆从仓库取货，配送到若干个顾客处。车辆受到载重量的约束，需要组织适当的行车路线，在顾客的需求得到满足的基础上，使代价函数最小。代价函数根据问题不同而不同，常见的有车辆总运行时间最小，车辆总运行路径最短等。 这个问题基于以下假设： 定义 为需要服务的两个顾客编号， 为配送中心的车辆编号， 为顾客和仓库的集合。 参数： : 从顾客 到顾客 的行驶距离 ：顾客 的需求量 ：车辆的最大载重量 决策变量： ：当车辆 被分配从顾客 运行到顾客 时，取1；否则取0 在给定了参数和定义了决策变量之后，VRP问题可以用数学模型表示为：给定车辆负载为400，各个节点的坐标和需求如下(节点0为配送中心)： 对于个体采用自然数编码，0代表配送中心，1--n代表顾客；不同车辆的配送路线之间用0分隔（即每辆车都从仓库出发）；对于有n个顾客，k辆车的VRP问题来说，染色体长度为n+k+1。 例如配送中心有3辆车为8个客户服务，一条可能的染色体如下： 0, 7, 0, 1, 2, 3, 5, 0, 8, 4, 6, 0 这条染色体表示的三辆车的行驶路线为: 第一辆车：0-7-0 第二辆车：0-1-2-3-5-0 第三辆车：0-8-4-6-0 利用分割符0，还原各条子路径 参考了大连海事大学硕士学位论文《基于电动汽车的带时间窗的路径优化问题研究》中的交叉操作，生成新的个体，具体描述如下图： 用2-opt算法对各条子路径进行局部优化 输出计算结果： 迭代过程如下图所示： 总共使用了4辆车，各自的行驶路径如下：

周辉（青岛海洋大学海洋地球科学学院，青岛　266003）何樵登（长春地质学院地球物理系，长春　130026）摘要　各向异性介质参数反演通常为非线性优化问题。非线性反演方法可以分为两大类：随机搜索方法，如Monte Carlo法、模拟退火和遗传算法及基于非线性最小平方理论的非线性解析反演方法。遗传算法能寻找到全局最优解，但它为一种较费时的方法。非线性解析反演方法能给出一个与初始模型有关的局部最优解。然而，这种方法具有较快的收敛速度。遗传算法与非线性解析反演方法相结合的反演方法利用这两种反演方法的优点而克服其缺点。因此，结合反演方法既能快速收敛，又能寻找到全局最优解。如何合理地将遗传算法和非线性解析反演方法结合是十分重要的。本文提出一种结合方案，即在连续若干次遗传算法迭代后作一次非线性解析反演。理论算例表明结合反演方法具有上述特点。关键词　遗传算法　非线性解析反演　非线性结合反演　各向异性介质1　引言遗传算法为随机搜索类方法之一，它以概率论为理论基础，用于求解多极值复杂优化问题[9]。遗传算法不要求已知模型空间中后验概率密度的形状并能广泛搜索模型空间。遗传算法模拟自然选择和遗传规律，并遵循适者生存的原则。遗传算法由Holland在1975年提出[4]。Berg首先将遗传算法应用于地球物理优化问题[1]。Stoffa等系统地研究了种群大小、交叉概率、选择概率和变异概率对多参数优化问题收敛性和收敛速度的影响[11]。Sen等讨论了在选择概率中引入温度参数的作用并提出一些退火方案[10]。周辉等则研究了目标函数与收敛速度和解的精度的关系[16]。基于最小平方优化理论的非线性反演方法是两大类反演方法之一。当给定的初始模型位于目标函数全局最优解所在的峰谷附近时，这种下降类方法能给出正确解而与初始模型位置无关。下降类算法研究得较深入，应用较广。Tarantola提出一种基于广义最小二乘法的多维多偏移距声波地震波形解释的一般性非线性地震波形反演方法[12]。随后，Tarantola将该理论推广于各向同性介质的弹性波反演[13]。Gauthier等用理论数据验证了Tarantola提出的方法的正确性[2]。稍后，Tarantola研究非线性解析法反射波弹性反演的策略，指出以纵横波的波阻抗和密度作为反演参数，才尽可能使反演参数之间相互独立[14]。Pan用τ—P变换研究层状声学介质中平面波地震记录非线性解析反演的理论和可行性[6]。为了更多地利用地震数据中的信息，包括VSP资料中反射和转换信息，Mora作了一些工作[5]。当仅用反射数据时反演主要解决引起反射的P波和S波的波阻抗突变。当利用转换数据时，则能分辨大尺度的P波和S波速度变化。Sambridge等改进了修改模型的方法[8]。在子空间中，可同时得到P波、S波波阻抗和密度。周辉等将非线性梯度反演方法推广于多维、多道、多分量任意弹性各向异性介质参数的反演[17]。非线性解析反演方法和遗传算法结合的反演方法利用非线性解析反演和遗传算法的优点，克服它们的缺点。因此，结合反演方法不仅能搜索到全局最优解，而且能较快地收敛。Porsani等在遗传算法和广义线性反演方法相结合方面作了一些研究[7]。本文讨论各向异性介质的非线性解析反演方法和遗传算法与非线性解析反演方法相结合的结合反演方法[17]。对于遗传算法读者可参考遗传算法的相关文献[3,9～11]。2　各向异性介质参数非线性解析反演方法2.1　共轭梯度法反演的目的是利用地面或井中测得的位移场ui（xr,t）求取地下介质密度分布ρ（x）和弹性参数分布Cijkl（x）。ρ（x）、Cijkl（x）称为模型参数。x为研究介质中或边界上任一点，x=（x1,x2,x3）,xr为接收点。反演的目标是使目标函数岩石圈构造和深部作用取极小值。其中Cd、Cm分别为数据（波场）和模型参数的协方差算子。m0为先验模型参数，m为反演过程中求得的模型参数。由于模型参数有多个，故用向量表示。ucal为给定m的波动方程正演记录，uobs为观测波场，上角标t表示转置。地震记录u和模型参数m之间的函数关系为岩石圈构造和深部作用g为非线性算子，（2）式为波动方程的算子形式。记第n次迭代时的模型参数为mn，则有岩石圈构造和深部作用及共轭梯度法的迭代公式[15]岩石圈构造和深部作用其中Gn为g对mn的Frechet导数，ηn为一常数，可由多种方法计算[5,8]。梯度 为模型空间的对偶空间中的一个元素。模型空间和其对偶空间以模型参数的协方差算子Cm=Diag（Cp，Cc）由式（4d）相联系。在后面将给出 和 的表达式。式（4）为梯度反演方法的基本公式。当该公式中的每一量都已知时，迭代就可进行。在这些变量中，最关键的是梯度向量。2.2　目标函数在最小二乘理论中，权函数是协方差算子逆的核。假设数据集中的误差是不相关的，它仅取决于时间或源和接收器的位置，那么有[14]岩石圈构造和深部作用其中σ为数据的均方差。2.3　各向异性介质中的弹性波动方程令fi（x,t;xs）是第s次激发的内体力密度，Ti（x,t;xs）是地球表面S的应力矢量分量，ni（x）是表面的单位法向分量。那么与第s次激发相应的位移由以下微分方程组给出[15]岩石圈构造和深部作用2.4　梯度向量式（4）中梯度向量的分量为[17]岩石圈构造和深部作用其中，T为地震记录的长度， 为反向传播场，满足岩石圈构造和深部作用其中，t∈[T,0]， 满足终了时间条件。3　结合反演方法3.1　遗传算法和非线性解析反演方法的优缺点遗传算法是利用概率论来求解多极值复杂优化问题的一种随机搜索方法，由一组随机选取的模型开始，不需要更多的先验信息，广泛而有效地对模型空间的最优部分采样。尽管遗传算法是基于自然选择、遗传规律，搜索模型空间的最优部分而求得最优解，但它是一种计算量很大的方法。由于地震模型空间大，用全局最优化方法估计各向异性介质参数的地震波形反演十分费时。目标函数的梯度信息是非线性解析反演方法修改模型参数的依据，它能给出一个接近初始模型的一个局部最优解。如果初始模型选择得合适，即当初始模型处在全局最优解所在的目标函数低谷时，非线性解析反演方法能收敛于全局最优解。然而，恰好给出一个接近全局最优解的初始模型的概率是非常小的，尤其对没有模型参数的任何先验信息的情况。但应强调的是，非线性解析反演方法具有较快的收敛速度。发挥非线性解析反演方法快速收敛和遗传算法能搜索到全局最优解的优点，而克服前者仅能寻找到局部最优解和后者运算量大的缺点是很有意义的。非线性解析反演方法和遗传算法相结合的反演方法可达到上述目的。在结合反演方法中，遗传算法的作用是提供接近全局最优解的模型，非线性解析反演的作用是尽快求出全局最优解。因此，结合反演方法具有搜索到全局最优解的能力和比遗传算法收敛速度快的特点。3.2　结合方案遗传算法在优化过程中连续不断地搜索整个模型空间。在每次迭代结束后，得到一个本代的最优模型。根据遗传算法的数学原理[3]，最优模型的数量在下一代中得以增加，同时经交叉和变异作用又有新的模型产生。在下一代种群中，最优模型可能与前一代的相同，也有可能劣于前一代的最优模型。所有这些最优模型可能在目标函数的同一低谷处，也有可能在其它低谷处。遗传算法寻找最优模型要经过多次迭代才能确定一个极值。遗传算法的随机性导致遗传算法是一种费时的方法。然而正是遗传算法的这种随机性保证了它能搜索到全局最优解。如果将每次遗传算法迭代的最优解作为非线性解析反演的初始模型，非线性解析反演可以找出与初始模型毗邻的局部最优解。由于非线性解析反演是一种确定性的方法，它按目标函数的梯度方向修改模型，所以非线性解析反演方法只需几次迭代即可收敛。非线性解析反演求得的解是否为全局最优解，非线性解析反演方法本身是无法得以保证的。只有当遗传算法提供接近全局最优解的初始模型时，非线性解析方法反演才能收敛到全局最优解。结合反演方法中遗传算法和非线性解析反演方法的匹配方式是十分重要的。非线性解析反演方法得到接近遗传算法提供的初始模型的局部最优解后，在以后若干代中因遗传算法的随机性而使其最优解与该局部最优解相同。如果每次遗传算法迭代后作非线性解析反演，那么结合反演的结果在几代内都是相同的。显然其中的一些非线性解析反演是没有必要的。因此，结合方式应为在连续多次遗传算法迭代后作一次非线性解析反演，然后将非线性解析反演的结果作为下一代种群中的一个母本模型。图1为结合反演的框图。图1　结合反演框图4　算例为了验证结合反演方法的优越性，对一维多层横向各向同性介质参数的反演理论实例作了分析。图2是目标函数值与迭代次数的关系图。在该结合反演算例中每次遗传算法迭代后就作一次非线性解析反演迭代。结合反演的误差在开始几次迭代中下降很快，尤其在前3次。结合反演方法在第10次迭代达到的较小误差，遗传算法在第42次迭代才达到。结合反演的误差比遗传算法的跳跃得严重。这是因为非线性解析反演得到的模型在遗传算法中作为母代参加繁衍。这个模型因遗传算法的随机性常常被新的模型替代。这两个模型可能位于目标函数两个不同的低谷中，因此非线性解析反演的结果不同。尽管结合反演的目标函数有些振荡，但也存在连续几次迭代目标函数几乎不变的现象。这意味着这几次迭代的最优模型是很接近的。在这种情况下非线性解析反演不能提供较大的改进。所以，此时的非线性解析反演是没有必要的，否则只能增加计算量。图2　结合反演（实线）和遗传算法（虚线）的误差与迭代次数的关系结合反演中每次遗传算法迭代后作一次非线性解析反演迭代图3是另一个例子。在该结合反演例子中，每五次遗传算法迭代作一次非线性解析反演。在这里遗传算法占主要地位。此时结合反演的误差函数明显比遗传算法的小。结合反演的误差在第5次迭代末突然下降，并在第10次迭代时的小误差，遗传算法在42代才达到。遗传算法始终没有到达结合反演的最小误差。结合反演的误差在后期迭代过程中平稳下降，这是遗传算法占主导地位的原因。从该例可知，若遗传算法与非线性解析反演方法比较合理地结合，结合反演方法比遗传算法具有快得多的收敛速度。5　结论非线性结合反演方法扬遗传算法和非线性解析反演方法之长，抑其之短，它是一种具有较快收敛速度的全局反演方法。在结合反演中遗传算法和非线性解析反演方法的结合方式是重要的。从算例可得出，五次遗传算法迭代后作一次非线性解析反演的结合反演的效果明显优于每次遗传算法迭代后都作非线性解析反演的结合反演的效果。但是在结合反演中连续作多少次遗传算法迭代及连续迭代次数在整个迭代过程中的可变性还有待于进一步研究。图3　结合反演（实线）和遗传算法（虚线）的误差与迭代次数的关系结合反演中每五次遗传算法迭代后作一次非线性解析反演迭代在结合反演中遗传算法的作用是提供接近全局最优解的初始模型。结合反演的运算速度主要取决于遗传算法的运算速度。均匀设计理论可以应用于遗传算法以加快随机搜索的速度。与遗传算法相同，其它随机搜索方法也可用来与非线性解析反演方法形成结合反演方法。参考文献[1]E.Berg.Simple convergent genetic algorithm for inversion of multiparameter data.SEG60 Expanded Abstracts,1990，Ⅱ，1126～1128.[2]O.Gauthier,J.Virieux and A.Tarantola.Two-dimensional nonlinear inversion of seismic waveforms:Numerical results.Geophysics,1986,51,1387～1403.[3]D.E.Goldberg.Genetic Algorithms in Search,Optimiztion,and Machine Learning.Addison-Wesley,Reading,MA,1989.[4]J.H.Holland.Adaptation in Natural and Artifical Systems.The University of Michigan Press,Ann Arbor,1975.[5]P.Mora.2D elastic inversion of multi-offset seismic data.Geophysics,1988,52,2031～2050.[6]G.S.Pan,R.A.Phinney,and R.I.Odom.Full-waveform inversion of plane-wave seismograms in stratified acoustic media:Theory and feasibility.Geophysics,1988,53,21～31.[7]M.J.Porsani,P.L.Stoffa,M.K.Sen,et al..A combined Genetic and linear inversion algorithm for seismic wave-form inversion.SEG63 Expanded Abstracts,1993,692～695.[8]M.S.Sambridge,A.Tatantola and Kennet.An alternative strategy for nonlinear inversion of seismic waveforms.Geophysical Prospecting,1991,39,723～736.[9]M.Sambridge,and G.Drijkoningen.Genetic algorithms in seismic waveform inversion.Geophys.J.Int.,1992,109,323～342.[10]M.K.Sen,P.L.Stoffa.Rapid sampling of model space using genetic algorithms:examples from seismic waveform inversion.Geophys.J.Int.,1992,109,323～342.[11]P.L.Stoffa,M.K.Sen.Nonlinear multiparametre optimization using genetic algorithms:Inversion of plane-wave seismograms.Geophysics,1991,56,1794～1810.[12]A.Tarantola.Inversion of seismic reflection data in the acoustic approximation.Geophysics,1984（a）,49,1259～1266.[13]A.Tarantola.The seismic reflection inverse problem.In:F.Santosa,Y.-H.Pao,W.W.System,and C.Holland Eds.Inverse problems of acoustic and elastic waves.Soc.Industr.Appl.Math.,1984（b）,104～181.[14]A.Tarantola.A strategy for nonlinear elastic inversion of seismic reflection data.Geophysics,1986,51,1893～1903.[15]A.Tarantola.Inverse problem theory:Methods for data fitting and model parameter estimation.Elsevier Science Publ.Co.Inc.,1987.[16]周辉，何樵登.遗传算法在各向异性介质参数反演中的应用.长春地质学院学报，1995,25，增刊1,62～67.[17]周辉.各向异性介质波动方程正演及其非线性反演方法研究.长春地质学院博士论文，1995.

高手解释下，这个选择、交叉、变异各是采用了什么方法?????我也很想知道这段程序呀。这个是基于实数编码的遗传算法优化PID参数。

原来看过个C的遗传算法，不好意思le #include <stdio.h> #include <stdlib.h> #include <math.h> /* Change any of these parameters to match your needs */ #define POPSIZE 50 /* population size */ #define MAXGENS 1000 /* max. number of generations */ #define NVARS 3 /* no. of problem variables */ #define PXOVER 0.8 /* probability of crossover */ #define PMUTATION 0.15 /* probability of mutation */ #define TRUE 1 #define FALSE 0 int generation; /* current generation no. */ int cur_best; /* best individual */ FILE *galog; /* an output file */ struct genotype /* genotype (GT), a member of the population */ { double gene[NVARS]; /* a string of variables */ double fitness; /* GT"s fitness */ double upper[NVARS]; /* GT"s variables upper bound */ double lower[NVARS]; /* GT"s variables lower bound */ double rfitness; /* relative fitness */ double cfitness; /* cumulative fitness */ }; struct genotype population[POPSIZE+1]; /* population */ struct genotype newpopulation[POPSIZE+1]; /* new population; */ /* replaces the */ /* old generation */ /* Declaration of procedures used by this genetic algorithm */ void initialize(void); double randval(double, double); void evaluate(void); void keep_the_best(void); void elitist(void); void select(void); void crossover(void); void Xover(int,int); void swap(double *, double *); void mutate(void); void report(void); /***************************************************************/ /* Initialization function: Initializes the values of genes */ /* within the variables bounds. It also initializes (to zero) */ /* all fitness values for each member of the population. It */ /* reads upper and lower bounds of each variable from the */ /* input file `gadata.txt". It randomly generates values */ /* between these bounds for each gene of each genotype in the */ /* population. The format of the input file `gadata.txt" is */ /* var1_lower_bound var1_upper bound */ /* var2_lower_bound var2_upper bound ... */ /***************************************************************/ void initialize(void) { FILE *infile; int i, j; double lbound, ubound; if ((infile = fopen("gadata.txt","r"))==NULL) { fprintf(galog," Cannot open input file! "); exit(1); } /* initialize variables within the bounds */ for (i = 0; i < NVARS; i++) { fscanf(infile, "%lf",&lbound); fscanf(infile, "%lf",&ubound); for (j = 0; j < POPSIZE; j++) { population[j].fitness = 0; population[j].rfitness = 0; population[j].cfitness = 0; population[j].lower[i] = lbound; population[j].upper[i]= ubound; population[j].gene[i] = randval(population[j].lower[i], population[j].upper[i]); } } fclose(infile); } /***********************************************************/ /* Random value generator: Generates a value within bounds */ /***********************************************************/ double randval(double low, double high) { double val; val = ((double)(rand()%1000)/1000.0)*(high - low) + low; return(val); } /*************************************************************/ /* Evaluation function: This takes a user defined function. */ /* Each time this is changed, the code has to be recompiled. */ /* The current function is: x[1]^2-x[1]*x[2]+x[3] */ /*************************************************************/ void evaluate(void) { int mem; int i; double x[NVARS+1]; for (mem = 0; mem < POPSIZE; mem++) { for (i = 0; i < NVARS; i++) x[i+1] = population[mem].gene[i]; population[mem].fitness = (x[1]*x[1]) - (x[1]*x[2]) + x[3]; } } /***************************************************************/ /* Keep_the_best function: This function keeps track of the */ /* best member of the population. Note that the last entry in */ /* the array Population holds a copy of the best individual */ /***************************************************************/ void keep_the_best() { int mem; int i; cur_best = 0; /* stores the index of the best individual */ for (mem = 0; mem < POPSIZE; mem++) { if (population[mem].fitness > population[POPSIZE].fitness) { cur_best = mem; population[POPSIZE].fitness = population[mem].fitness; } } /* once the best member in the population is found, copy the genes */ for (i = 0; i < NVARS; i++) population[POPSIZE].gene[i] = population[cur_best].gene[i]; } /****************************************************************/ /* Elitist function: The best member of the previous generation */ /* is stored as the last in the array. If the best member of */ /* the current generation is worse then the best member of the */ /* previous generation, the latter one would replace the worst */ /* member of the current population */ /****************************************************************/ void elitist() { int i; double best, worst; /* best and worst fitness values */ int best_mem, worst_mem; /* indexes of the best and worst member */ best = population[0].fitness; worst = population[0].fitness; for (i = 0; i < POPSIZE - 1; ++i) { if(population[i].fitness > population[i+1].fitness) { if (population[i].fitness >= best) { best = population[i].fitness; best_mem = i; } if (population[i+1].fitness <= worst) { worst = population[i+1].fitness; worst_mem = i + 1; } } else { if (population[i].fitness <= worst) { worst = population[i].fitness; worst_mem = i; } if (population[i+1].fitness >= best) { best = population[i+1].fitness; best_mem = i + 1; } } } /* if best individual from the new population is better than */ /* the best individual from the previous population, then */ /* copy the best from the new population; else replace the */ /* worst individual from the current population with the */ /* best one from the previous generation */ if (best >= population[POPSIZE].fitness) { for (i = 0; i < NVARS; i++) population[POPSIZE].gene[i] = population[best_mem].gene[i]; population[POPSIZE].fitness = population[best_mem].fitness; } else { for (i = 0; i < NVARS; i++) population[worst_mem].gene[i] = population[POPSIZE].gene[i]; population[worst_mem].fitness = population[POPSIZE].fitness; } } /**************************************************************/ /* Selection function: Standard proportional selection for */ /* maximization problems incorporating elitist model - makes */ /* sure that the best member survives */ /**************************************************************/ void select(void) { int mem, i, j, k; double sum = 0; double p; /* find total fitness of the population */ for (mem = 0; mem < POPSIZE; mem++) { sum += population[mem].fitness; } /* calculate relative fitness */ for (mem = 0; mem < POPSIZE; mem++) { population[mem].rfitness = population[mem].fitness/sum; } population[0].cfitness = population[0].rfitness; /* calculate cumulative fitness */ for (mem = 1; mem < POPSIZE; mem++) { population[mem].cfitness = population[mem-1].cfitness + population[mem].rfitness; } /* finally select survivors using cumulative fitness. */ for (i = 0; i < POPSIZE; i++) { p = rand()%1000/1000.0; if (p < population[0].cfitness) newpopulation[i] = population[0]; else { for (j = 0; j < POPSIZE;j++) if (p >= population[j].cfitness && p<population[j+1].cfitness) newpopulation[i] = population[j+1]; } } /* once a new population is created, copy it back */ for (i = 0; i < POPSIZE; i++) population[i] = newpopulation[i]; } /***************************************************************/ /* Crossover selection: selects two parents that take part in */ /* the crossover. Implements a single point crossover */ /***************************************************************/ void crossover(void) { int i, mem, one; int first = 0; /* count of the number of members chosen */ double x; for (mem = 0; mem < POPSIZE; ++mem) { x = rand()%1000/1000.0; if (x < PXOVER) { ++first; if (first % 2 == 0) Xover(one, mem); else one = mem; } } } /**************************************************************/ /* Crossover: performs crossover of the two selected parents. */ /**************************************************************/ void Xover(int one, int two) { int i; int point; /* crossover point */ /* select crossover point */ if(NVARS > 1) { if(NVARS == 2) point = 1; else point = (rand() % (NVARS - 1)) + 1; for (i = 0; i < point; i++) swap(&population[one].gene[i], &population[two].gene[i]); } } /*************************************************************/ /* Swap: A swap procedure that helps in swapping 2 variables */ /*************************************************************/ void swap(double *x, double *y) { double temp; temp = *x; *x = *y; *y = temp; } /**************************************************************/ /* Mutation: Random uniform mutation. A variable selected for */ /* mutation is replaced by a random value between lower and */ /* upper bounds of this variable */ /**************************************************************/ void mutate(void) { int i, j; double lbound, hbound; double x; for (i = 0; i < POPSIZE; i++) for (j = 0; j < NVARS; j++) { x = rand()%1000/1000.0; if (x < PMUTATION) { /* find the bounds on the variable to be mutated */ lbound = population[i].lower[j]; hbound = population[i].upper[j]; population[i].gene[j] = randval(lbound, hbound); } } } /***************************************************************/ /* Report function: Reports progress of the simulation. Data */ /* dumped into the output file are separated by commas */ /***************************************************************/ void report(void) { int i; double best_val; /* best population fitness */ double avg; /* avg population fitness */ double stddev; /* std. deviation of population fitness */ double sum_square; /* sum of square for std. calc */ double square_sum; /* square of sum for std. calc */ double sum; /* total population fitness */ sum = 0.0; sum_square = 0.0; for (i = 0; i < POPSIZE; i++) { sum += population[i].fitness; sum_square += population[i].fitness * population[i].fitness; } avg = sum/(double)POPSIZE; square_sum = avg * avg * POPSIZE; stddev = sqrt((sum_square - square_sum)/(POPSIZE - 1)); best_val = population[POPSIZE].fitness; fprintf(galog, " %5d, %6.3f, %6.3f, %6.3f ", generation, best_val, avg, stddev); } /**************************************************************/ /* Main function: Each generation involves selecting the best */ /* members, performing crossover & mutation and then */ /* evaluating the resulting population, until the terminating */ /* condition is satisfied */ /**************************************************************/ void main(void) { int i; if ((galog = fopen("galog.txt","w"))==NULL) { exit(1); } generation = 0; fprintf(galog, " generation best average standard "); fprintf(galog, " number value fitness deviation "); initialize(); evaluate(); keep_the_best(); while(generation<MAXGENS) { generation++; select(); crossover(); mutate(); report(); evaluate(); elitist(); } fprintf(galog," Simulation completed "); fprintf(galog," Best member: "); for (i = 0; i < NVARS; i++) { fprintf (galog," var(%d) = %3.3f",i,population[POPSIZE].gene[i]); } fprintf(galog," Best fitness = %3.3f",population[POPSIZE].fitness); fclose(galog); printf("Success "); } /***************************************************************/给个旅行商的链接吧~~http://search.csdn.net/search/tsp/1/lt/?keytype=title

1.在遗传编码时, 一般将瓦片的坐标作为基因进行实数编码, 染色体的第一个基因为起点坐标, 最后一个基因为终点坐标, 中间的基因为路径经过的每一个瓦片的坐标。在生成染色体时, 由起点出发, 随机选择当前结点的邻居节点中的可通过节点, 将其坐标加入染色体, 依此循环, 直到找到目标点为止, 生成了一条染色体。重复上述操作, 直到达到指定的种群规模。2.神经网络的搭建，输入，隐藏与输出的设置。应用到遗传算法中，我们制定一个规则，什么样的坦克是好坦克：比如杀一个坦克+15，按存活时间+10，死亡后-25；这样判别优秀的坦克基因；然后遗传给下一代重新训练。将遗传算法与宠物养成游戏相结合，不仅可以增加游戏可玩性，给玩家带来新鲜的游戏体验，丰富玩家渴求惊喜与刺激的游戏心理，又可以丰富遗传算法的应用领域与辐射面。

例如：[1,2,3]，[1,3,2]，[3,2,1]均是函数 3x+4y+5z<100 的可行解（代进去成立即为可行解），那么这些可行解在遗传算法中均称为“染色体”。可行解由 3 个元素构成，每个元素都称为染色体的一个基因。 遗传算法在运行过程中会进行 N 次迭代，每次迭代都会生成若干条染色体。适应度函数会给本次迭代中生成的所有染色体打个分，来评判这些染色体的适应度，然后将适应度低的染色体淘汰，只保留适应度高的染色体，从而讲过若干次迭代后染色体的质量将越来越好。 遗传算法每次迭代会生成 N 条染色体，在遗传算法中一次迭代被称为一次进化。每次进化新的染色体生成的方法——交叉。 每一次进化完成后，都要计算每一条染色体的适应度+适应度概率。在交叉过程中就需要根据这个概率来选择父母染色体。适应度高的染色体被选中的概率越高。（这就是遗传算法能够保留优良基因的原因） 交叉能保证每次进化留下优良的基因，但它仅仅是对原有的结果集进行选择，基因还是那么几个，只不过交换了它们的顺序。这只能保证 N 次进化后，计算结果更接近于局部最优解，而永远没办法达到全局最优解（？？？？？），为了解决这个问题，需引入变异。 假设每次进化都需要生成 N 条染色体，那么每次进化中，通过交叉方式需要生成 N-M 条，剩余的 M 条染色体通过复制上一代适应度最高的 M 条染色体而来。 本文的目标是使所有任务的总处理时间最少，时间越短适应度越大。适应度 = 1 / 所有任务的总处理时间 将任务从 0 开始编号，用一个一维数组存储每个任务的时长 tasks[i] ：表第 i 个任务的长度。 第 0 个任务的长度为 2； 第 1 个任务的长度为 4； 第 2 个任务的长度为 6； 第 3 个任务的长度为 8； 将处理器节点从 0 开始编号，用一个一维数组存储每个处理器的处理速度（单位时间内可处理的长度） nodes[i] 表第 i 个节点的处理速度。 第 0 个节点的处理速度为 2； 第 1 个节点的处理速度为 1。 timeMatrix[i][j] 表第 i 个任务在第 j 个节点上处理的话，所需处理时间。 一个可行解就是一个染色体，就是一个一维数组 chromosome[i]=j 表将第 i 个任务分配到节点 j 上处理（任务编号从 0 开始；节点编号从 0 开始） 将任务 0 分配给 3 号节点处理； 将任务 1 分配给 2 号节点处理； 将任务 2 分配给 1 号节点处理； 将任务 3 分配给 0 号节点处理。 记录本次进化生成的 N 条染色体的适应度，将染色体从 0 开始编号。 adaptablility[i] 表第 i 个染色体的适应度 selectionProbability[i] 表第 i 个染色体的适应度概率，所有染色体的适应度概率和为 1 。 java中PriorityQueue优先级队列使用方法 第 2 次迭代结果 第 100 次迭代结果

这是个50维的极小值优化问题，首先要明白遗传算法是适合二进制处理的。因此首先要将每一维的实值xi编码为长度为T的二进制串，这样子基因长度就为50T。评估适应值，可以将基因中对应的xi的二进制串转化为实值，然后代入函数求值，将该值作为适应值。具体之中的遗传算法过程可以采用经典的方法，这里不做解释。另外的，实值转为二进制串的，这个有挺多方法，我这里介绍一种方法：