遗传算法简介

姓名：彭帅                     学号：17021210850

参考：http://blog.csdn.net/emiyasstar__/article/details/6938608/

【嵌牛导读】：我们经常会遇到求一个函数最大或最小值的问题，即优化问题，对简单的一元函数可以通过其导数来判断最值，然而在对一些复杂函数求最值时，求导的方法往往是不可行的，遗传算法是一种较好的优化算法，不会因函数形式复杂而不适用。本文对遗传算法进行了简要介绍。

【嵌牛鼻子】：优化算法

【嵌牛提问】：怎样理解遗传算法？

【嵌牛正文】：

       遗传算法是一种基于自然选择和基因遗传学原理的优化搜索方法，它在计算机上模拟生物的进化过程和基因的操作，并不需要对象的特定知识，也不需要对象的搜索空间是连续可微的，它具有全局寻优的能力。一些用常规的优化算法有效解决的问题，采用遗传算法寻优技术往往能得到较好的效果。

先对其中一些概念进行介绍：

目标函数：需要求出最值的函数。

染色体：对目标函数自变量进行编码得到的序列。

选择：选择是从一个旧的种群中选择生命力强的个体单位产生新种群的过程。这是一个优胜劣汰的过程。选择操作是建立在群体中个体的适应度评估基础上的，它是在模仿自然选择现象。在自然群体中，适应度是由一个生物为继续生存而捕食、生长和繁殖后代的过程中克服障碍的能力决定的。在选择过程中适应度是该个体被选择或淘汰的决定性因素。

交叉：在自然界生物进化过程中起核心作用的是生物遗传基因的重组和变异。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体染色体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。

变异：尽管复制和交叉操作很重要，在遗传算法中是第一位的，但不能保证不会遗漏一些重要的遗传信息。在人工遗传系统中，变异用来防止这种不可弥补的遗漏。

遗传算法引入变异的目的有两个:一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。

用流程图来表示遗传算法：

用通俗易懂的方法解释一下遗传算法：

遗传算法的实现过程实际上就像自然界的进化过程那样。首先寻找一种对问题潜在解进行“数字化”编码的方案。（建立表现型和基因型的映射关系。）然后用随机 数初始化一个种群（那么第一批袋鼠就被随意地分散在山脉上。），种群里面的个体就是这些数字化的编码。接下来，通过适当的解码过程之后，（得到袋鼠的位置 坐标。）用适应性函数对每一个基因个体作一次适应度评估。（袋鼠爬得越高，越是受我们的喜爱，所以适应度相应越高。）用选择函数按照某种规定择优选 择。（我们要每隔一段时间，在山上射杀一些所在海拔较低的袋鼠，以保证袋鼠总体数目持平。）让个体基因交叉变异。（让袋鼠随机地跳一跳）然后产生子 代。（希望存活下来的袋鼠是多产的，并在那里生儿育女。）遗传算法并不保证你能获得问题的最优解，但是使用遗传算法的最大优点在于你不必去了解和操心如何 去“找”最优解。（你不必去指导袋鼠向那边跳，跳多远。）而只要简单的“否定”一些表现不好的个体就行了。（把那些总是爱走下坡路的袋鼠射杀。）

典型的遗传算法实现：

（1）初始化编码。遗传算法的运算对象是表示个体的符号串，所以必须把变量xi编码为符号串。

（2）初始群体的产生。遗传算法是对群体进行的进化操作，需要准备一些表示起始搜索点的初始群体数据。每个体通过随机方法产生。

（3）适应度计算。遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传机会的大小。本课题中，目标函数是以求最值为优化目标，故可直接利用目标函数值作为个体的适应度。

（4）选择运算。把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。本课题中，采用轮盘赌选择法来决定进入下一代的个体。轮盘赌：顾名思义，轮盘赌操作即将每个个体按适应度大小作为轮盘扇区的大小的参考依据，模拟轮盘旋转的过程进行选择。

（5）交叉。交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某两个个体之间的部分染色体。本题中采用单点交叉方法，其具体操作过程是：①先对群体进行依次配对；②其次随机设置交叉点位置；③最后再相互交换配对染色体之间的部分基因。

（6）变异。变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进行改变，它也是产生新个体的一种操作方法。

遗传算法是一种强有力的、应用范围十分广泛的随机搜索优化技术，传统的优化技术在解决许多复杂问题时十分困难。但遗传算法对解决这些复杂问题是十分有效的。通过本次课程设计我了解了遗传算法的基本步骤（选择—繁衍—变异），应用各式各样的函数对其性能进行了测试，感受到了遗传算法在解决复杂问题时的优秀性能。遗传算法的应用也是十分广泛的，是管理科学、运算学、工业与系统工程领域许多研究和工程实践人员的研究课题。其优点是十分明显的。它具有与问题领域无关切快速随机的搜索能力；搜索从群体出发，具有潜在的并行性；可以进行多个个体的同时比较；搜索使用评价函数启发；过程简单使用概率机制进行迭代，具有随机性；具有可扩展性，容易与其他算法结合。然而遗传算法还有诸多需要改进的地方，如：遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码；另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验；没有能够及时利用网络的反馈信息,故算法的；搜索速度比较慢，要得要较精确的解需要较多的训练时间；算法对初始种群的选择有一定的依赖性，能够结合一些启发算法进行改进；算法的并行机制的潜在能力没有得到充分的利用，这也是当前遗传算法的一个研究热点方向。