遗传算法地原理及MATLAB程序实现

遗传算法的原理1.1遗传算法的基本思想遗传算法（geneticalgorithms,GA）是一种基丁自然选择和基因遗传学原理，借鉴了生物进化优胜劣汰的自然选择机理和生物界繁衍进化的基因重组、突变的遗传体系的全局自适应概率搜寻算法。遗传算法是从一组随机产生的初始解（种群）开始，这个种群由经过基因编码的必然数目的个体组成，每个个体其实是染色体带有特色的实体。染色体作为遗传物质的主要载体，其内部表现（即基因型）是某种基因组合，它决定了个体的外面表现。所以，从一开始就需要实现从表现型到基因型的照射，即编码工作。初始种群产生后，依据优胜劣汰的原理，逐代演化产生出愈来愈好的近似解。在每一代，依据问题域中个体的适应度大小选择个体，并借助丁自然遗传学的遗传算子进行组合交义和变异，产生出代表新的解集的种群。这个过程将致使种群像自然进化同样，后代种群比前代更加适应环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。计算开始时，将实责问题的变量进行编码形成染色体，随机产生必然数目的个体，即种群，并计算每个个体的适应度值，尔后经过停止条件判断该初始解是否是最优解，若是则停止计算输出结果，若不是则经过遗传算子操作产生新的一代种群，回到计算集体中每个个体的适应度值的部分，尔后转到停止条件判断。这一过程循环执行，直到知足优化准则，最后产生问题的最优解。图1-1给出了遗传算法的基本过程。1.2遗传算法的特色1.2.1遗传算法的长处遗传算法拥有十分强的鲁棒性，比起传统优化方法，遗传算法有以下长处：1.遗传算法以控制变量的编码作为运算对象。传统的优化算法经常直接利用控制变量的实质值的自己来进行优化运算，但遗传算法不是直接以控制变量的值，而是以控制变量的特定形式的编码为运算对象。这类对控制变量的编码办理方式，能够模拟自然界中生物的遗传和进化等机理，也使得我们能够方便地办理各种变量和应用遗传操作算子。2.遗传算法拥有内在的实质并行性。它的并行性表现在两个方面，一是遗传（开始■初始化，输入原始参数及给定参数，gen=1染色体编码，产生初始集体*计算种群中每个个体的适应值「L二停止条件的判断？N------1------gen=gen+1选择----x-交错Y变异新种群——?输出结果（结束）图i-i简单遗传算法的基本过程算法的外在并行性，最简单的方式是让多台计算机各自进行独立种群的演化计算，最后选择最优个体。能够说，遗传算法适合在目前全部的并行机或散布式系统进步行并行计算办理。二是遗传算法的内在并行性，由丁遗传算法采纳种群的方式组织搜寻，因此可同时搜寻解空间内的多个地域，并互相交流信息。这样就使得搜索效率更高，也防备了使搜寻过程陷丁局部最优解。3.遗传算法直接以目标函数值作为搜寻信息。在简单遗传算法中，基本上不用搜寻空间的知识和其余辅助信息，而仅用目标函数即适应度函数来评估个体解

的利害，且适应度函数不受连续可微的拘束，对该函数和控制变量的拘束很少。对适应度函数唯一的要求就是对丁输入能够计算出可比较的输出。4.遗传算法是采纳概率的变迁规则来指导它的搜寻方向，其搜寻过程朝着搜空间的更优化的解地域搬动，它的方向性使得它的效率远远高丁一般的随机算遗传算法在解空间内进行充分的搜寻，但不是盲目的穷举或尝试，由于选择

索法。操作以适应度为依据，所以它的搜寻性能经常优丁其余优化算法。5.原理简单，操作方便，占用内存少，适用丁计算机进行大规模计算，特别适合办理传统搜寻方法难以解决的大规模、非线性组合复杂优化问题。6.由丁遗传基因申码的不连续性，所以遗传算法办理非连续混杂整数规划时有其独到的优胜性，并且使得遗传算法对某些病态结构问题拥有很好的办理能力。7.遗传算法同其余算法有较好的兼容性。如能够用其余的算法求初始解；在每一代种群，能够用其余的方法求解下一代新种群。1.2.2遗传算法的缺点但是，遗传算法也存在一些缺点。1.遗传算法是一类随机搜寻型算法，而非确立性迭代过程描述，这类方式必然会较低的计算效率。对简单遗传算法的数值试验表示，算法经常出现过早收敛现象。遗传和变异的完整随机性固然保证了进化的搜寻功能，但是这类随机变化也使得好的优异个体的性态被过早破坏，降低了各代的平均适应值。2.遗传算法的实现2.1初始参数种群规模

n:种群数目影响遗传算法的有效性。种群数目太小，不能够供给足

够的采样点；种群规模太大，会增添计算量，使收敛时间增添。一般种群数目在

20到160之间比较适合。交义概率

Pc:

Pc控制着互换操作的频率，

Pc太大，会使高适应值的结构很

快被破坏掉，

Pc太小会使搜寻阻滞不前，一般

Pc取

0.5~1.0

。变异概率

Pm:

Pm

是增大种群多样性的第二个要素，

Pm

太小，不会产生新的基因块，

Pm

太大，会使遗传算法变为随机搜寻，一般

Pm

取

0.001~0.1

。进化代数t:表示遗传算法运转结束的一个条件。一般的取值范围100~1000。当个体编码较长时，进化代数要取小一些，不然会影响算法的运转效率。进化代数的采用，还能够采纳某种判断准则，准则成马上，即停止。2.2染色体编码利用遗传算法进行问题求解时，一定在目标问题实质表示与染色体位申结构之间建立一个联系。对丁给定的优化问题，由种群个体的表现型会集所组成的空间称为问题空间，由种群基因型个体所组成的空间称为编码空间。由问题空间向编码空间的照射称作编码，而由编码空间向I可题空间的照射成为解码。依据遗传算法的模式定理，DeJong进一步提出了较为客观明确的编码评估准则，称之为编码原理。详尽能够概括为两条规则：有意义积木块编码规则：编码应当易丁生成与所求问题相关的且拥有低阶、短定义长度模式的编码方案。(2)最小字符集编码规则：编码应使用能使问题获得自然表示或描述的拥有最小编码字符集的编码方案。常用的编码方式有两种：二进制编码和浮点数(实数)编码。二进制编码方法是遗传算法中最常用的一种编码方法，它将问题空间的参数用字符集10组成染色体位申，吻合最小字符集原则，便丁用模式定理解析，但存在照射偏差。采纳二进制编码，将决策变量编码为二进制，编码申长

m取决丁需要的精

度。比方，

Xi的值域为

a.bi，而需要的精度是小数点后

5位，这要求将

x得值域最少分为bai106份。设

X所需要的字申长为

m,则有：2m1

b

ai

106

2mi

(2.1)那么二进制编码的编码精度为

^，将

x由二进制转为十进制可按下2mi

1式计算：Xadecimal(substringi)(2.2)此中，decimal(substringi)表示变量x的子申substringi的十进制值。染色体编码N的总申长mmi。i1若没有规定计算精度，那么可采纳定长二进制编码，即

m能够自己确立。二进制编码方式的编码、解码简单易行，使得遗传算法的交义、变异等操作现方便。但是，当连续函数失散化时，它存在照射偏差。再者，当优化问题所精度越高，若是一定保证解的精度，则使得个体的二进制编码申很长，进而

实求的致使搜索空间急剧扩大，计算量也会增添，计算时间也相应的延长。浮点数(实数)编码方法能够解决二进制编码的这些缺点。该方法中个体的每个基因都要用参数所给定区间范围内的某一浮点数来表示，而个体的编码长度则等丁其决策变量的总数。遗传算法中交义、变异等操作所产生的新个体的基因也一定保证在参数指定区间范围内。当个体的基因值是由多个基因组成时，操作一定在两个基因之间的分界字节处进行，而不是在某一基因内的中间字节

值交义分开处进行。2.3适应度函数适应度函数是用来权衡个体利害，胸襟个体适应度的函数。适应度函数值越的个体越好，反之，适应值越小的个体越差。在遗传算法中依据适应值对个体

大进行选择，以保证适应性能好的个体有更多的时机生殖后代，

使优异特点得以遗传。一般而言，适应度函数是由目标函数变换而成的。由丁在遗传算法中依据适应度排序的状况来计算选择概率，这就要求适应度函数计算出的函数值(适应度)不能够小丁零。所以，在某些状况下，将目标函数变换成最大化问题形式并且函数值非负的适应度函数是必需的，并且在任何状况下总是希望越大越好，但是好多实质问题中，目标函数有正有负，所以经常用到从目标函数到适应度函数的变换。考虑以下一般的数学规划问题：minf(x)s.t.g(x)0minh(X)hmax变换方法⑴对丁最小化问题，建立适应度函数F(x)和目标函数f(x)的照射关系:Cmaxf(x)f(x)Cmaxmax(2.3)F(x)0f(x)Cmax式中，Cmax既能够是特定的输入值，也能够采用到目前为止所获得的目标函数f(x)的最大值。(2)对丁最大化问题，一般采纳下述方法:f(x)Cminf(x)CminF(x)(2.4)0f(x)Cm.式中，Cmin既能够是特定的输入值，也能够采用到目前为止所获得的目标函数(x)的最小值。变换方法二:⑴对丁最小化问题，建立适应度函数f(x)和目标函数f(x)的照射关系:1,F(x)ccf(x)0°'(2.5)(2)对丁最大化问题，一般采纳下述方法:F(x)1(2.6)-------------------c0,cf(x)01cf(x)式中，c为目标函数界线的守旧预计值。2.4拘束条件的办理在遗传算法中一定对拘束条件进行办理，但目前还没有办理各种拘束条件的一般方法，依据详尽问题可选择以下三种方法，其罚函数法、搜寻空间限制法和可行解变换法。2.4.1罚函数法罚函数的基本思想是对在解空间中无对应可行解的个体计划其适应度时，处以一个罚函数，进而降低该个体的适应度，使该个体被选遗传到下一代集体中的概率减小。能够用下式对个体的适应度进行调整：F(x)xU(2.7)F(x)F(x)P(x)xU此中，F(x)为原适应度函数，F'(x)为调整后的新的适应度函数，P(x)为罚函数，U为拘束条件组成的会集。怎样确立合理的罚函数是这类办理方法难点之所在，在考虑罚函数时，既要胸襟解对拘束条件不知足的程度，由要考虑计算效率。2.4.2搜寻空间限制法搜寻空间限制法的基本思想是对遗传算法的搜寻空间的大小加以限制，使得搜寻空间中表示一个个体的点与解空间中的表示一个可行解的点有一一对应的关系。对一些比较简单的拘束条件经过适合编码使搜寻空间与解空间一一对应，限制搜寻空间能够提升遗传算法的效率。在使用搜寻空间限制法时一定保证交义、变异此后的解个体在解空间中有对应解。2.4.3可行解变换法可行解变换法的基本思想：在由个体基因型到个体表现型的变换中，增添使其知足拘束条件的办理过程，其搜寻个体基因型与个体表现型的多对一变换关系，扩大了搜寻空间，使进化过程中所产生的个体总能经过这个变换而转变为解空间中知足约束条件的一个可行解。可行解变换法对个体的编码方式、交义运算、变异运算等无特别要求，但运转收效降落。2.5遗传算子遗传算法中包含了3个模拟生物基因遗传操作的遗传算子：选择(复制)、交义(重组)和变异(突变)。遗传算法利用遗传算子产生新一代集体来实现群体进化，算子的设计是遗传策略的主要组成部分，也是调整和控制进化过程的基本工具。2.5.1选择操作中传算法中的选择操作就是用来确立怎样从父代集体中按某种方法采用哪些个体遗传到下一代集体中的一种遗传运算。

遗传算法使用选择

(复制)

算子来对集体中的个体进行优胜劣汰操作：适应度较高的个体被遗传到下一代集体中的概率较大；适应度较低的个体被遗传到下一代集体中的概率较小。选择操作建立在对个体适应度进行评论的基础之上。选择操作的主要目的是为了防备基因缺失、提高全局收敛性和计算效率。常用的选择方法有转轮法、排序选择法、两两克争法。轮盘赌法。简单的选择方法为轮盘赌法：平时以第i个个体入选种群的概率以及集体规模的上限来确立其生计与裁减，这类方法称为轮盘赌法。轮盘赌法是一种正比选择策略，能够依据与适应函数值成正比的概率选出新的种群。轮盘赌法由以下五步组成：计算各染色体Vk适应值F(vQ；计算种群中全部染色体的适应值的和；nFallF(vk)(2.6)k13.计算各染色体Vk的选择概率p<evalM)P1,2,K,n

k—

,k

(2.7)Fall4.计算各染色体Vk的累计概率Ck；kCkPj,k1,2,K,n(2.8)5.在［0,1］区间内产生一个平均散布的伪随机数

r,若

rq,则选择第一个染色体Vi；不然，选择第

k个染色体，使得

qk

irqk建立。2）排序选择法。排序选择法的主要思想是：对集体中的全部个体按其适应度大小进行排序，基丁这个排序来分配各个个体被选中的概率。排序选择方法的详尽操作过程是：对集体中的全部个体按其适应度大小进行降序排序。依据详尽求解问题，设计一个概率分配表，将各个概率值按上述摆列序次分配给各个个体。以各个个体所分配到的概率值作为其能够被遗传到下一代的概率，基丁这些概率值用轮盘赌法来产生下一代集体。3）两两克争法。锦标赛选择法的基本做法是：在选择时先随机的在种群中选择k个个体进行锦标赛式的比较，从中选出适应值最好的个体进入下一代，复用这类方法进行直到下一代个体数为种群规模时为止。这类方法也使得适应值好的个体在下一代具有较大的“生计”时机，同时它只好使用适应值的相对值作为选择的标准，而与适应值的数值大小不可直接比率，所以，它能较好的防备超级个体的影响，必然程度的防备过早收敛现象和阻滞现象。2.5.2交义操作在遗传算法中，交义操作是起核心作用的遗传操作，它是生成新个体的主要方式。交义操作的基本思想是经过对两个个体之间进行某部分基因的互换来实现产生新个体的目的。常用交义算子有：单点交义算子、两点交义算子和多点交义算子、平均交义算子和算术交义算子等等。1）单点交义算子交义过程分两个步骤：第一对配对库中的个体进行随机配对；

其次，在配对个体中随机设定交义地址，配对个体相互互换部分信息。个体41001111——?1001000新个体个体丞0011000——?0011111新个体S交错占图2-1单点交错表示2）两点交义算子详尽操作是随机设定两个交义点，互换两个父代在这两点间的基因申，分别生成两个新个体。3）多点交义算子多点交义的思想源丁控制个体特定行为的染色体表示信息的部分不必包含丁周边的子申中，多点交义的破坏性能够促进解空间的搜寻，

而不是促进过早的

收敛。4）平均交义算子平均交义式指经过设定障蔽字来决定新个体的基因继承两个个体中那个个体的对应基因，当障蔽字中的位为0时，新个体A继承旧个体A中对应的基因，当障蔽字位为1时，新个体A继承旧个体B中对应的基因，由此可生成一个完整的新个体A，同理可生成新个体B。旧个体A001111旧个体E111100障蔽字010101f新个体A011110图2-2均与交错表示图2.5.3变异操作变异操作是指将个体染色体编码申中的某些基因座的基因值用该基因座的其余等位基因来代替，进而形成一个新的个体。变异运算是产生新个体的辅助方法，它和选择、交义算子结合在一起，保证了遗传算法的有效性，使遗传算法具有局部的随机搜索能力，提升遗传算法的搜寻效率；同时使遗传算法保持种群的多样性，以防备出现早熟收敛。在变异操作中，为了保证个体变异后不会与其父体产生太大的差别，保证种群发展的牢固性，变异率不能够取太大，若是变异率大丁0.5,遗传算法就变为随机搜寻，遗传算法的一些重要的数学特点和搜寻能力也就不存在了。变异算子的设计包含确立变异点的地址和进行基因值代替。操作的方法有基本位变异、平均变异、界线变异、非平均变异等。1)基本位变异

变异基本位变异操作是指对个体编码申中以变异概率Pm随机指定的某一位或某几位基因作变异运算，所以其发挥的作用比较慢，作用的收效也不显然。基本位变异算子的详尽执行过程是：对个体的每一个基因座，依变异概率Pm指定其为变异点。对每一个指定的变异点，对其基因值做取反运算或用其余等位基因值来取代，进而产生出一个新个体。平均变异平均变异操作是指分别用吻合某一范围内平均散布的随机数，以某一较小的概率来代替个体编码申中各个基因座上的原有基因值。平均变异的详尽操作过程是：挨次指定个体编码申中的每个基因座为变异点。2.对每一个变异点，以变异概率Pm从对应基因的取值范围内取一随机数来代替原有基因值。假设有一个个体为Vk[V1V2KVkKVm]，若Vk为变异点，其取值范围为[Vk,min,Vk,max],在该点对个体Vk进行平均变异操作后，可获得一个新的个体：Vk[V1V2KVkKVm],此中变异点的新基因值是'VkVk,min「(Vk,maxVk,min)(2.9)式中，r为[0,1]范围内吻合平均概率散布的一个随机数。平均变异操作特别适合应用丁遗传算法的早期运转阶段，它使得搜寻点能够在整个搜寻空间内自由地移动，进而可以增添集体的多样性。2.5.4倒位操作所谓倒位操作是指颠倒个体编码申中随机指定的二个基因座之间的基因排列序次，进而形成一个新的染色体。倒位操作的详尽过程是：1.在个体编码申中随机指定二个基因座作为倒位点；2.以倒位概率颠倒这二个倒位点之间的基因摆列序次。2.6搜寻停止条件遗传算法的停止条件有以下两个，知足任何一个条件搜寻就结束。1)遗传操作中连续多次前后两代集体中最优个体的适应度相差在某个任意小的正数所确立的范围内，即知足：0|FnewRd|(2.10)式中，Fnew为新产生的集体中最优个体的适应度；Fad为前代集体中最优个体的适应度。2)达到遗传操作的最大进化代数to详尽数学规划问题的遗传算法实现利用遗传算法求解以下数学规划问题：min2x222f(x〔，X2)X1322g〔(x1,X2)x1X25(3.1)s.th1(x1,x2)x12x240x1,x210,x1N3.1初始化针对上述I可题利用MATLAB编写遗传算法程序求解，程序的主函数是GA.m。第一，确立程序初始化中所需要的参数和对应的值。此中求解精度是指决策变量的求解精度，由丁题目中没有给出，所以这是我自己设定的参数。程序中涉及到得参数名称、符号和相应的值以下表所小。表3-1遗传算法初始化参数参数名称符号值最大进化代数tmax100种群规模n100交义概率Pc0.8变异概率Pm0.1求解精度dec104变量上限值xmax10变量下限值xmin03.2染色体编码本程序采纳二进制编码，将决策变量编码为二进制，其申长取决丁问题要求的求解精度，但本题并无给出精度要求，可是限制了xi为整数，不如假设求解精度为10,两个变量均采纳二进制编码，X1为整数这个限制条件在可在计算出小数值后作四舍五入取整办理，所以可依据假设的求解精度将决策变量的值域分成105份,则有：xxmin'm15m(3.2)x2'(xmaxxmin)102i由丁全部变量的求解精度同样，那么，决策变量的申长m〔20、m220,丁是染色体的总长mm〔m240,求解二进制编码申长的程序时len.m。那么，二进制编码精度为1006(3.3)20—9.53681021依据二进制编码的申长以及种群规模可生成初始种群，为计算种群中的各个个体的适应值，应先将基因型变换成表现型，其程序为coding.m第一，将二进制值变换为十进制值，其公式为m1(bib2KbQi1(3.4)2x灯i1那么，对应的变量值为XXmin(3.5)3.3计算适应值第一确立适应度函数。依据目标函数和拘束条件可选择适应度函数的变换方式。由丁目标函数f(x)0,为了防备出现适应值大丁1的状况，丁是依据目标函数的特色在设计适应度函数时，在分母上加上2,分子上剩以4,如式(3.1)所示；乂依据优化问题的拘束条件，利用拘束条件办理方法中的罚函数法设计了相应的罚函数c,那么适应度函数为F(x)4(3.6)f(x)c2此中，cmax{0,g1(x1,x2)5}max{0,|h1(x1,x2)41},10000。依据上述方法计算种群中各个个体的适应值，若是适应值趋近丁1,那么对应的个体即为最正确个体，计算适应值的程序是fitness.m。3.4遗传算子3.4.1选择操作本程序选择轮盘赌法来实现选择操作。依据从前计算的各个个体的适应值，利用式(2.6)计算种群中全部个体的适应值的和Fall;尔后依据如式(2.7)、(2.8)计算每个个体的选择概率p和累计概率q。旋转轮盘100次(种群规模)，每次生成一个0到1的随机数r，用这个随机数与种群中的个体的积累概率q作比较，若是这个随机数落在了这个概率区问，那么就保留该个体，这就完整模拟了轮盘赌的思想，若个体的选择概率大，那么它被选到遗传到下一代的概率也就大一些。选择操作的程序是selec.m。3.4.2交义操作对经过选择操作产生的集体作交义操作。本程序采纳平均交义的方式，第一打乱种群中全部个体的原有摆列序次，这样表现了随机抽取的观点，尔后把种群分成两部分new_genA和new_genB；分别从这两个部分选择一个个体配成对进行均匀交义，其程序为cross.m。3.4.3变异操作对经过交义操作产生的集体作变异操作。本程序采纳基本位变异方法实现变异操作，依据变异概率对新种群中的个体推行基本位变异，详尽程序为mut.m。在最先编写的程序中还包含倒位操作，详尽程序是inverse.m,原理近似丁基本位变异，可是详尽操作上有差别。在调试时，我比较了有倒位操作和没有倒位操作作用丁程序对计算结果的影响，在有倒位操作时并无改进算法在搜寻到最优解方面的性能，丁是我在最后的程序中取掉了这一操作。3.5搜寻停止判断本程序采纳了达到最大进化代数时停止搜寻的方法，由丁本问题比较简单，所以采纳此法是可行的。但是，对丁复杂的问题，也许要求更加有效的判断手段，所以这是需要改进的地方。3.6运转调试调试阶段解决了两个问题：第一，最正确个体的适应值很快就达到一个牢固的值而不再变化；