2022年遗传算法及Matlab说明 .pdf

《2022年遗传算法及Matlab说明 .pdf》由会员分享，可在线阅读，更多相关《2022年遗传算法及Matlab说明 .pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、其MATLAB实现者：老牛 网友评论17 条 浏览次数602 (1)遗传算法简介(2)遗传算法的MATLAB 实现(3)应用举例(4)遗传算法优化神经网络方向在工业工程中 ,许多最优化问题性质十分复杂,很难用传统的优化方法来求解.自 1960 年以来 ,人们对求解这类难解问题日益增加 .一种模仿生物自然进化过程的、被称为“ 进化算法（ evolutionary algorithm ） ” 的随机优化技术在解这类优化难题中显示了优于传统优化算法的性能。目前，进化算法主要包括三个研究领域：遗传算法、进化规划和进化策略。其中遗传算法是迄今为止进化算法中应用最多、比较成熟、广为人知的算法。一、遗传算法

2、简介遗传算法（ Genetic Algorithm, GA ）最先是由美国Mic-hgan 大学的 John Holland 于 1975 年提出的。遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有 “ 生存 +检测 ” 的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定等5 个要素组成了遗传算法的核心内容。遗传算法的基本步骤：遗传算法是一种基于

3、生物自然选择与遗传机理的随机搜索算法，与传统搜索算法不同，遗传算法从一组随机产生的称为 “ 种群 (Population)”的初始解开始搜索过程。种群中的每个个体是问题的一个解，称为“ 染色体 (chromosome)” 。染色体是一串符号， 比如一个二进制字符串。这些染色体在后续迭代中不断进化，称为遗传。在每一代中用“ 适值(fitness)”来测量染色体的好坏，生成的下一代染色体称为后代（offspring ） 。后代是由前一代染色体通过交叉(crossover)或者变异（ mutation）运算形成的。在新一代形成过程中，根据适度的大小选择部分后代，淘汰部分后代。从而保持种群大小是常数。

4、适值高的染色体被选中的概率较高，这样经过若干代之后，算法收敛于最好的染色体，它很可能就是问题的最优解或次优解。主要步骤如下所示：(1)编码： GA 在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。(2)初始群体的生成：随机产生 N 个初始串结构数据，每个串结构数据称为一个个体，N 个个体构成了 个群体。 GA以这 N 个串结构数据作为初始点开始迭代。(3)适应性值评估检测：适应性函数表明个体或解的优劣性。对于不同的问题，适应性函数的定义方式也不同。(4)选择：选择的目的是为了从当前群体个选出优良的个体，使它们有机会作为父代为下一代繁殖

5、子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 12 页 - - - - - - - - - 达尔文的适者生存原则。(5)交叉：交叉操作是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个体，新个体组合了其父辈个体的特性。交叉体现了信息交换的思想。(6)变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。

6、同生物界一样，GA 中变异发生的概率很低，通常取值在0.0010.01 之间。变异为新个体的产中提供了机会。实际上，遗传算法中有两类运算：遗传运算：交叉和变异进化运算：选择GA 的计算过程流程图遗传算法的特点GA 是对问题参数的编码组进行计算，而不是针对参数本身。GA 的搜索是从问题解的编码组开始搜素、而不是从单个解开始。GA 使用目标函数值（适应度）这一信息进行搜索，而不需导数等其他信息。GA 算法使用的选择、交叉、变异这三个算子都是随机操作，而不是确定规则。举例图解说明计算流程二、遗传算法的MATLAB 实现需要如下主函数：编码和种群生成function pop = initializeg

7、a(num,bounds,evalFN,evalOps,options) % pop- the initial, evaluated, random population % num- the size of the population, i.e. the number to create % bounds - the number of permutations in an individual (e.g., number %of cities in a tsp % evalFN - the evaluation fn, usually the name of the .m file fo

8、r evaluation % evalOps- any options to be passed to the eval function defaults % options- options to the initialize function, ie. eps, float/binary, prec %where eps is the epsilon value and the second option is 1 for %orderOps, prec is the precision of the variables defaults 1e-6 1 交叉function c1,c2

9、= arithXover(p1,p2,bounds,Ops) % Arith crossover takes two parents P1,P2 and performs an interpolation % along the line formed by the two parents. % % function c1,c2 = arithXover(p1,p2,bounds,Ops) % p1- the first parent ( solution string function value ) % p2- the second parent ( solution string fun

10、ction value ) % bounds- the bounds matrix for the solution space % Ops- Options matrix for arith crossover gen #ArithXovers 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 12 页 - - - - - - - - - 选择normGeomSelect： NormGeomSelect is a ranking selection function ba

11、sed on the normalized geometric distribution. （基于正态分布的序列选择函数）变异functionnewPop = normGeomSelect(oldPop,options) % NormGeomSelect is a ranking selection function based on the normalized % geometric distribution.% % functionnewPop = normGeomSelect(oldPop,options) % newPop- the new population selected f

12、rom the oldPop % oldPop- the current population % options - options to normGeomSelect gen probability_of_selecting_best 一些辅助函数：f2b ：Return the binary representation of the float number fval（将浮点数转化为二进制数）b2f：Return the float number corresponing to the binary representation of bval. （将二进制数转化为浮点数）nonUni

13、fMutation ： Non uniform mutation changes one of the parameters of the parent based on a non-uniform probability distribution.This Gaussian distribution starts wide, and narrows to a point distribution as the current generation approaches the maximum generation. （基于非均一概率分布进行非均一变异）maxGenTerm：Returns 1

14、, i.e. terminates the GA when the maximal_generation is reached. （当迭代次数大于最大迭代次数时，终止遗传算法，返回为 1，否则返回为0。 ）roulette：roulette is the traditional selection function with the probability of surviving equal to the fittness of i / sum of the fittness of all individuals 三、应用举例1.计算下列函数的最大值。f(x)=x+10*sin(5x)+7c

15、os(4x) , x0,9 方式 1gademo 方式 2step 1 编写目标函数gademo1eval1.m function sol, val = gaDemo1Eval(sol,options) x=sol(1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 12 页 - - - - - - - - - val = x + 10*sin(5*x)+7*cos(4*x); step 2 生成初始种群，大小为10 initPop=initializega(10,0

16、, 9,gademo1eval1,1e-6,1); step 325 次遗传迭代x, endPop,bpop,trace = ga(0 9,gademo1eval1,initPop,. 1e-6 1 1,maxGenTerm,25,. normGeomSelect,0.08,. arithXover,2,. nonUnifMutation,2, 25 ,3) % Output Arguments: %x- the best solution found during the course of the run %endPop- the final population %bPop- a tra

17、ce of the best population (解的变化 ) %traceInfo- a matrix of best and means of the ga for each generation (种群平均值的变化) % % Input Arguments: %bounds - a matrix of upper and lower bounds on the variables %evalFN- the name of the evaluation .m function %evalOps - options to pass to the evaluation function (

18、NULL) %startPop- a matrix of solutions that can be initialized %from initialize.m %opts- epsilon, prob_ops ,display change required to consider two solutions different, prob_ops 0 if you want to apply the %genetic operators probabilisticly to each solution, 1 if you are supplying a deterministic num

19、ber of operatorapplications and display is 1 to output progress 0 forquiet. (1e-6 1 0) %termFN- name of the .m termination function (maxGenTerm) %termOps- options string to be passed to the termination function(100). %selectFN- name of the .m selection function (normGeomSelect) %selectOpts- options

20、string to be passed to select after %select(pop,#,opts) (0.08) %xOverFNS- a string containing blank seperated names of Xover.m files (arithXover heuristicXover 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 12 页 - - - - - - - - - simpleXover) %xOverOps- A matri

21、x of options to pass to Xover.m files with the first column being the number of that xOver to perform similiarly for mutation (2 0;2 3;2 0) %mutFNs- a string containing blank seperated names of mutation.m files (boundaryMutation multiNonUnifMutation . %nonUnifMutation unifMutation) %mutOps- A matrix

22、 of options to pass to Xover.m files with the first column being the number of that xOver to perform similiarly for mutation (4 0 0;6 100 3;4 100 3;4 0 0) 2.求 sin(x) 在 0 到 3.14 之间的最大值. function sol, val = sin1(sol,options) x=sol(1); val =sin(x); initPop=initializega(10,0, 3.14,sin1,1e-6,1); x, endPo

23、p,bpop,trace = ga(0 3.14,sin1,initPop,. 1e-6 1 1,maxGenTerm,25,. normGeomSelect,0.08,. arithXover,2,. nonUnifMutation,2, 25 ,3) 3. binaryExample.m 二元函数例子二进制编码方式 1 binaryExample 方式 2 function sol,val = gaMichEval(sol,options) val = 21.5 + sol(1) * sin(4*pi*sol(1) + sol(2)*sin(20*pi*sol(2); % global b

24、ounds % Setting the seed back to the beginning for comparison sake rand(seed,0) % Crossover Operators xFns = simpleXover; xOpts = .4; % Mutation Operators mFns = binaryMutation; mOpts = 0.005; % Termination Operators termFns = maxGenTerm; termOps = 200; % 200 Generations 名师资料总结 - - -精品资料欢迎下载 - - - -

25、 - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 12 页 - - - - - - - - - % Selection Function selectFn = roulette selectOps = ; % Evaluation Function evalFn = gaMichEval; evalOps = ; % Bounds on the variables bounds = -3, 12.1; 4.1, 5.8; % GA Options epsilon float/binar display gaOpts=1e-6 0

26、 1; % Generate an intialize population of size 20 startPop = initializega(20,bounds,gaMichEval,1e-6 0); x endPop bestPop trace=ga(bounds,evalFn,evalOps,startPop,gaOpts,. termFns,termOps,selectFn,selectOps,xFns,xOpts,mFns,mOpts); % x is the best solution found x % endPop is the ending population endP

27、op % trace is a trace of the best value and average value of generations trace clf plot(trace(:,1),trace(:,2); hold on plot(trace(:,1),trace(:,3); % Lets increase the population size by running the defaults % rand(seed,0) termOps=100; x endPop bestPop trace=ga(bounds,evalFn,evalOps,gaOpts,termFns,te

28、rmOps,. selectFn,selectOps); % x is the best solution found x % endPop is the ending population %endPop % trace is a trace of the best value and average value of generations 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 12 页 - - - - - - - - - %trace % Plot the

29、 best over time clf plot(trace(:,1),trace(:,2); % Add the average to the graph hold on plot(trace(:,1),trace(:,3); 4. floatExample.m 二元函数例子浮点编码global bounds % Setting the seed to the same for binary rand(seed,156789) % Crossover Operators xFns = arithXover heuristicXover simpleXover; xOpts = 1 0; 1

30、3; 1 0; % Mutation Operators mFns = boundaryMutation multiNonUnifMutation nonUnifMutation unifMutation; mOpts = 2 0 0;3 200 3;2 200 3;2 0 0; % Termination Operators termFns = maxGenTerm; termOps = 200; % 200 Generations % Selection Function selectFn = normGeomSelect; selectOps = 0.08; % Evaluation F

31、unction evalFn = gaMichEval; evalOps = ; % Bounds on the variables bounds = -3 12.1; 4.1 5.8; % GA Options epsilon float/binar display gaOpts=1e-6 1 1; % Generate an intialize population of size 20 startPop = initializega(20,bounds,gaMichEval,1e-6 1) x endPop bestPop trace=ga(bounds,evalFn,evalOps,s

32、tartPop,gaOpts,. termFns,termOps,selectFn,selectOps,xFns,xOpts,mFns,mOpts); % x is the best solution found x % endPop is the ending population endPop % bestPop is the best solution tracked over generations bestPop 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共

33、12 页 - - - - - - - - - % Plot the best over time clf plot(trace(:,1),trace(:,2); % Add the average to the graph hold on plot(trace(:,1),trace(:,3); % Lets increase the population size by running the defaults x endPop bestPop trace=ga(bounds,evalFn,evalOps,gaOpts); % x is the best solution found x %

34、endPop is the ending population endPop % bestPop is the best solution tracked over generations bestPop % Plot the best over time clf plot(trace(:,1),trace(:,2); % Add the average to the graph hold on plot(trace(:,1),trace(:,3); 5. 求解货郎担问题（TSP）orderBasedExample.m 6. 求解非线性规划问题max f(x) s.t. gi(x)=0 g2(

35、x)=x12/4-x22+1=0 分析：取加法形式的适值函数：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 12 页 - - - - - - - - - val(x)=f(x)+p(x) 惩罚函数p(x)由两部分组成，可变乘法因子和违反约束乘法，其表达式如下：其中 ri 是约束 i 的可变惩罚系数。步骤如下：function sol,eval=f552(sol,options) x1=sol(1); x2=sol(2); r1=0.1; r2=0.8; %约束条件g1=

36、x1-2*x2+1; g2=x1.2/4-x2.2+1; %加惩罚项的适值if (g1=0)&(g2=0) eval=(x1-2).2+(x2-1).2; else eval=(x1-2).2+(x2-1).2+r1*g1+r2*g2; end eval=-eval; % %维数 n=2 %设置参数边界bounds = ones(2,1)*-1 1;%? %遗传算法优化p,endPop,bestSols,trace=ga(bounds,f552); p %性能跟踪plot(trace(:,1),trace(:,3),b-) hold on plot(trace(:,1),trace(:,2),

37、r-) xlabel(Generation); ylabel(Fittness); legend(解的变化 ,种群平均值的变化); 四遗传算法优化神经网络方向神经网络的设计要用到遗传算法，遗传算法在神经网络中的应用主要反映在3 个方面：网络的学习，网络的结构设计，网络的分析。1遗传算法在网络学习中的应用名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 12 页 - - - - - - - - - 在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用(1)学习规则

38、的优化用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。(2)网络权系数的优化用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。2遗传算法在网络设计中的应用用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3 种：(1)直接编码法这是把神经网络结构直接用二进制串表示，在遗传算法中，“ 染色体 ” 实质上和神经网络是一种映射关系。通过对“ 染色体 ” 的优化就实现了对网络的优化。(2)参数化编码法参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、 各层互连方式等信息。一般对进化后的优化

39、“ 染色体 ” 进行分析，然后产生网络的结构。(3)繁衍生长法这种方法不是在“ 染色体 ” 中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“ 染色体 ” 中；然后， 由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。3遗传算法在网络分析中的应用遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首

40、先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 12 页 - - - - - - - - - 附：遗传算法优化神经网络结构的算法（针对神经网络编码怎么具体实现【上面三部分】？）神经

41、网络结构包括网络的拓扑结构(连接方式 )和接点转移函数两方面.人们总是期望以简单的网络结构实现所需的信号处理功能,并尽可能达到较高的性能指标.利用遗传算法设计神经网络可根据某些性能评价准则如学习速度,泛化能力或结构复杂程度等搜索结构空间中满足问题要求的最佳结构.利用遗传算法设计神经网络的关键问题之一仍然是如何选取编码方案.借助遗传算法优化神经网络结构的算法步骤如下:1)随机产生若干个不同结构的神经网络,对每个结构编码,每个码链对应一个网络结构,N 个码链构成种群.2)利用多种不同的初始连接权值分别对每个网络进行训练.3)计算在每个对应码链下神经网络的误差函数,利用误差函数或其他策略(如网络的泛

42、化能力或结构复杂度)确定每个个体的适应度函数.4)选择若干适应度函数值最大的个体构成父本.5)利用交叉 ,变异等遗传操作算子对当前一代群体进行处理,产生新一代群体.6)重复上述2)-5)步骤 ,直到群体中的某个个体(对应一个网络结构)能满足要求为止.VS：遗传算法的基本步骤我们习惯上把Holland1975 年提出的GA 称为传统的GA。它的主要步骤如下：编码： GA 在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。初始群体的生成：随机产生N 个初始串结构数据，每个串结构数据称为一个个体，N 个个体构成了一个群体。GA以这 N 个串结

43、构数据作为初始点开始迭代。适应性值评估检测：适应性函数表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。交换：交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，GA 中变异发生的

44、概率很低，通常取值在0.0010.01 之间。变异为新个体的产生提供了机会。GA 的计算过程为：选择编码方式名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 12 页 - - - - - - - - - 产生初始群体计算初始群体的适应性值如果不满足条件 选择交换变异计算新一代群体的适应性值 遗传算法的特点遗传算法作为一种快捷、简便、容错性强的算法，在各类结构对象的优化过程中显示出明显的优势。与传统的搜索方法相比，遗传算法具有如下特点：搜索过程不直接作用在变量上，而是在参数

45、集进行了编码的个体。此编码操作， 使得遗传算法可直接对结构对象（集合、序列、矩阵、树、图、链和表）进行操作。搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法，降低了陷入局部最优解的可能性，并易于并行化。采用概率的变迁规则来指导搜索方向，而不采用确定性搜索规则。对搜索空间没有任何特殊要求（如连通性、凸性等），只利用适应性信息，不需要导数等其它辅助信息，适应范围更广。：一是用于网络连接权的进化；二是用于网络结构的进化名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 12 页 - - - - - - - - -