遗传算法介绍

遗传算法介绍：遗传算法（简称GA），是以自然选择和遗传理论为基础的，将生物进化过程中适者生存规则与群体内部染色体的随机信息交换机制相结合的高效全局寻优搜索算法。与以往的优化算法相比，GA具有很突出的优点[1]：1）GA不是从单个点，而是从多个点构成的群体开始搜索；2）在搜索最优解的过程中，只需要由目标函数值得到适应值信息，而不需要导数等其它辅助信息；3）在搜索过程不容易陷入局部最优极值。在遗传算法中，将问题空间中的决策变量通过一定编码方法表示成遗传空间的一个个体，它是一个基因型串的结构数据；同时，将目标函数值转为适应值，它是用来评价个体的好坏的，并作为以后遗传操作的依据。遗传操作包括三个基本操作：选择、交叉和变异。选择是用来实施适者生存的原则,即把当前群体中的个体按与适应值成比例的概率复制到新的群体中，构成交配池，交配池则是指当前代与下一代之间的中间群体。选择的作用效果是提高群体的平均适应值，由于选择没有产生新个体，所以群体中最好个体的适应值不会因选择操作而有所改进。交叉可以产生新的个体，它首先使从交配池中的个体随机配对，然后将两两配对的个体按某种方式相互交换部分基因。变异是对个体的某一个或某一些基因值按某一较小概率进行改变。从产生新个体的能力方面来说，交叉是产生新个体的主要方法，它决定了遗传算法的全局搜索能力；而变异只是产生新个体的辅助方法，但也必不可少，因为它决定了遗传算法的局部搜索能力。交叉和变异相配合,共同完成对搜索空间的全局和局部搜索。[2]参考文献[1]刘勇,康立山,陈毓屏.遗传算法(非数值并行算法(第二册))[M].北京:科学出版社,1997.[2]刘国华,包宏,李文超.用MATLAB实现遗传算法程序[A].北京科技大学,2001GA一般过程：[3]（1）编码：解释空间中的解数据x，作为遗传算法的表现型形式。从表现型到基因型的映射称为编码。GA在进行搜索之前先将解空间的数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合就构成了不同的点。（2）初始群体的生成：随机产生N个初始串结构数据，每个串结构作为初始点开始迭代。设置进化代数计数器t，设置最大进化代数T，随机生成M个个体作为初始群体P（0）。（3）适应度值评价监测：适应度函数表明个体或解的优劣性。对于不同的问题，适应度函数的定义方式不同。根据具体问题，计算群体P（t）中各个个体的适应度。（4）选择：将选择算子作用域群体。（5）交叉：将交叉算子作用于群体。群体P(t)经过选择、交叉、变异运算后得到下一（6）变异：将变异算子作用于群体。代群体P(t+1)（7）终止条件判断：若t≤T，则t←t+1，转到（2）；若t＞T，则已进化过程中所得到的具有最大适应度的个体作为最有输出，终止运算。遗传算法的基本操作：[4]（1）选择：选择的目的是为了从当前的群体中选出优良的个体，使它们有机会作为附带为下一代繁殖子孙。根据各个个体的适应度值，按照一定的规则或方法从上一代群体中选择出一些优良的个体遗传到下一代群体中。GA通过选择运算体现这一思想，进行选择的原则是适应性强的个体（即适应度值高）为下一代贡献一个或多个后代的概率大。（2）交叉：交叉操作时GA中最主要的遗传操作。通过交叉操作可以得到新一代个体，新个体组合了父辈个体的特性。将群体内的各个个体随机搭配成对，对每一个个体，以某个交叉概率(Pc)交换它们之间的部分染色体。交叉体现了信息交换的一种思想。（3）变异：对群体中每一个个体，以某个变异概率(Pm)改变某一个或某一些基因座上的基因值为其他的基因值（如0→1或1→0）。通生物界一样，GA中的变异发生的概率很低，变异为新个体的产生提供了机会。参考文献[3]雷英杰,张善文,李续武,周创明.MATLAB遗传算法工具箱及应用[M].西安电子科技大学出版社.2004.[4]雷英杰,张善文,李续武,周创明.MATLAB遗传算法工具箱及应用[M].西安电子科技大学出版社.2004.遗传算法和BP神经网络结合解决基于智能计算的影响河流水质的因素分析：考虑到BP神经网络的各层之间都有权值和阀值，不妨使用这些权值和阀值按顺序级联起来成一条染色体，再生成N个这样的染色体。也就是把权值和阀值作为要用遗传算法优化的参数。神经网络结构的选择尚无一种统一而完整的理论指导，一般只能由经验选定，因此优化网络结构的思想不容易实现，考虑到神经网络除了结构需要考虑之外，还有它的权值和阈值在应用时也需要考虑进去，既然BP神经网络的结构难以进行优化，不妨使用擅长全局搜索的遗传算法优化神经网络的权值和阀值，从而弥补BP神经网络结构难以优化的缺陷，优化好的权值和阈值在BP神经网络的应用中同样可以提高最终训练（预测）结果的可信度。编码时可以将BP神经网络的权值和阀值按照输入层与隐含层的权值、输入层与隐含层的阀值、隐含层到输出层的权值、隐含层到输出层的阀值的顺序连接起来形成一个染色体，接着产生N个这样的染色体。每个权值和阀值的编码长度固定为一个值，比如定为10，一条染色体的权值（阀值此时也算作权值）的个数是固定的，有计算公式[(IN+1)*HN+(HN+1))OUT]可推导出（IN为输入层节点个数，HN为隐层神经元个数，OUT为输出层神经元个数）。考虑到若采用实数编码，交叉变异时意义并不大，编码最好采用二进制编码。激励函数可以参考BP神经网络中常用的一些激励函数，如f(x)=1/(1+exp(-x))等。【我自己总结的GA和BP结合的原因及过程，纯自己的语言】【因为我们直接借用了别人的GA和BP结合的想法，老师让我们写别人怎么做的，再写自己怎么做的，我想说的是，我们就是借用了别人的想法，也就是说我认为没必要写出别人是如何做的，因为我们的想法和别人是一样的，直接突出自己的即可，我认为是。】