遗传是一种基于生物自然选择与遗传机理的随机搜索算法

《遗传是一种基于生物自然选择与遗传机理的随机搜索算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、遗传是一种基于生物自然选择与遗传机理的随机搜索算法。遗传算法的常用形式是Goldberg提出的。和传统搜索算法不同，遗传算法从一组随机产生的初始解，称为“种群”，开始搜索过程。种群中的每个个体是问题的一个解，称为“染色体”。染色体是一串符号。这些染色体在后续不断进化，称为遗传。在每一代中用“适值”来测量染色体的好坏。生成的下一代称为后代。后代是由前一代染色体通过交叉或变异运算形成的。新一代形成中，根据适值的大小选择部分后代，淘汰部分后代，从而保持种群大小是常数。适值高的染色体被选中的概率较高。这样，经过若干代之后，算法收敛与最

2、好的染色体，它很可能就是问题的最优解或次优解。设P（t）和C（t）分别表示第t代的双亲和后代，遗传算法可描述如下：遗传算法过程：Begint←0;初始化P（t）；评估P（t）；While不满足终止条件doBegin重组P（t）获得C（t）；评估C（t）；从P（t）和C（t）中选择P(t+1)；t←t+1；EndEnd通常初始化是随机产生的。重组包括交叉和变异来获得后代。实际上，遗传算法有两种分类运算：（1）遗传运算：交叉和变异；（2）进化运算：选择。交叉是最主要的遗传运算，它同时对两个染色体操作，组合二者的特性产生新的后代。遗

3、传算法的性能在很大程度上取决于采用的交叉算法的性能。交叉率定义为各代中交叉产生的后代数与种群中的个体数的比。变异则是一种运算，它在染色体上自发的产生随机的变化。变异率定义为种群中变异基因数在总基因数中的百分比。变异率控制了新基因导入种群的比例。遗传算法在几个基本方面不同于传统优化算法。Goldberg总结为以下几点：（1）遗传算法运算的是解集的编码，而不是解集本身。（2）遗传算法的搜索始于解的一个种群，而不是单个解。（3）遗传算法只使用报酬信息，而不使用导数或其他辅助知识。（4）遗传算法采用概率的，而不是确定的状态转移规则。遗

4、传算法初始种群No传统方法单初始点改进（依赖问题）终止终止吗？改进（依赖问题）终止终止吗？No以上图形是传统优化方法与遗传算法的比较。作为一种新的优化技术，遗传算法受到了广泛注意。它在解优化问题时有以下三点优点：（1）遗传算法对所解的优化问题没有太多的数学要求。（2）进化算子的各态历经性使得遗传算法能够非常有效的进行概率意义上的全局搜索。（3）遗传算法对于各种特殊问题可以提供极大的灵活性来混合构造领域独立的启发式，从而保证算法的有效性。计算染色体适值的过程由以下三步构成：步骤1：将染色体的基因型转换为表现型，即将二进制串转换为

5、十进制值：xk=（xk1，xk2），k=1,2，......,pop-size，这里，pop-size表示种群大小。步骤2：计算目标函数值f（xk）。步骤3：将目标函数值转换成适值。对于极大化问题，可简单地取目标值为适值：eval(vk)=f(xk),k=1,2......,pop-size.适值函数起了测定染色体对目标的适应性的作用。多数情况下，采用转轮法作为选择方法，它是一种正比选择策略，能够根据与适值成正比的概率选出新的种群。转轮法由以下四步构成:(1)对各个染色体vk计算适值eval（vk），eval（vk）=f（x）

6、；k=1,2，.....,pop-size(2)计算种群中所有染色体的适值和：F=(3)对各染色体vk,,计算选择概率pk，pk=(eval(vk))/F,k=1,2，.....,pop-size(4)对各染色体vk，计算累积概率qk，qk=;k=1,2，.....,pop-size选择过程就是旋转转轮pop-size次，每次选出一个染色体来构造新的种群。单断点交叉法是随机的选择一个断点，交换双亲上断点的右端，生成新的后代。对于两个染色体，若随机断点选在第17个基因，于是有：交叉过程Bejink←0；Whilek≤10dork

7、←[0,1]分布随机数；Ifrk<0.25then;选vk交叉的双亲之一；endk←k+1；endend变异以等于变异率的概率改变一个或几个基因。假设v1的第16个基因被选来变异，该基因为1，故将其变为0.于是变异后染色体为V1=[100110110100101101000000010111001]↓V2=[100110110100101100000000010111001]对于一些混合遗传过程，有Begint←0;初始化P（t）；评估P（t）；While不满足终止条件do重组P（t）获得C（t）；局部爬山C（t）；评估C（t

8、）；从P（t）和C（t）中选择P(t+1)；t←t+1；endendGen，Ida和Yokata首次提出了求解可靠性优化的简单遗传算法。该问题被许多学者用作基准问题。问题的目标是在受限于A类失效的子系统中具有并联冗余单元的三个非线性约束的条件下使系统可靠性达到最大。问题可表达