最优化方法_遗传算法

《最优化方法_遗传算法》由会员分享，可在线阅读，更多相关《最优化方法_遗传算法（42页珍藏版）》请在金锄头文库上搜索。

1、遗传算法大连理工大学金博达尔文进化理论的主要论点1) 生物的所有遗传信息都包含在其染色体中，染 色体决定了生物的性状； 2) 染色体是由基因及其有规律的排列所构成的， 遗传和进化过程发生在染色体上； 3) 生物的繁殖过程是由其基因的复制过程来完成 的； 4) 通过同源染色体之间的交叉或染色体的变异会 产生新的物种，使生物呈现新的性状； 5) 对环境适应性好的基因或染色体经常比适应性 差的基因或染色体有更多的机会遗传到下一代 。遗传算法思想来源于生物进化过程, 它 是基于进化过程中的信息遗传机制和优胜 劣汰的自然选择原则的优化算法。遗传算 法用概率搜索过程在状态空间中搜索，产 生新的样本。遗传算

2、法遗传算法与自然进化的比较自然界染色体 基因 等位基因(allele) 染色体位置(locus) 基因型(genotype) 表型(phenotype)遗传算法字符串 字符,特征 特征值 字符串位置 结构 参数集,译码结构遗传算法的特点特点： 通用 鲁棒 次优解、满意解 遗传算法能解决的问题： 优化 NP完全 NP难 高度复杂的非线性问题遗传算法与传统优化算法的主要不同1) 遗传算法不是直接作用在参变量集上, 而 是利用参变量集的某种编码;2) 遗传算法不是从单个点, 而是在群体中从一 个点开始搜索;3) 遗传算法利用适应值信息, 无需导数或其它 辅助信息;4) 遗传算法利用概率转移规则, 而

3、非确定性规 则。遗传算法的发展遗传算法起源于对生物系统所进行的计算机模拟研究。早在20世纪40年代，就有学者开始研究如何利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。进入20世纪60年代，美国密执安大学的Holland教授及其学生们受到这种生物模拟技术的启发，创造出一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术遗传算法。（1）J.H.Holland20世纪70年代初，Holland教授提出了遗传算法的基本定理模式定理，从而奠定了遗传算法的理论基础。模式定理揭示了群体中优良个体（较好的模式）的样本数将以指数级规律增长，从

4、理论上保证了遗传算法用于寻求最优可行解的优化过程。1975年，Holland出版了第一本系统论述遗传算法和人工自适应系统的专著自然系统和人工系统的自适应性。20世纪80年代，Holland教授实现了第一个基于遗传算法的机器学习系统分类器系统，开创了基于遗传算法的机器学习的新概念。（2）J.D.Bagley1967年，Holland的学生Bagley在其博士论文中首次提出了“遗传算法”一词，并发表了遗传算法应用方面的第一篇论文。他发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用了双倍体的编码方法。在遗传算法的不同阶段采用了不同的概率，从而创立了自适应遗传算法的概念。（3）K.A.D

5、e Jong1975年，De Jong博士在其博士论文中结合模式定理进行了大量纯数值函数优化计算实验，树立了遗传算法的工作框架。他推荐了在大多数优化问题中都较适用的遗传算法的参数，建立了著名的De Jong五函数测试平台，定义了评价遗传算法性能的在线指标和离线指标。（4）D.J.Goldberg1989年，Goldberg出版了专著搜索、优化和机器学习中的遗传算法，该书全面地论述了遗传算法的基本原理及其应用，奠定了现代遗传算法的科学基础。（5）L.Davis1991年，Davis编辑出版了遗传算法手册一书，为推广和普及遗传算法的应用起到了重要的指导作用。（6）J.R.Koza1992年，Koz

6、a将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程的概念，并成功地将遗传编程的方法应用于人工智能、机器学习和符号处理等方面。（1）函数优化。函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例。尤其是对非线性、多模型、多目标的函数优化问题，采用其他优化方法较难求解，而遗传算法却可以得到较好的结果。（2）组合优化。随着问题的增大，组合优化问题的搜索空间也急剧扩大，采用传统的优化方法很难得到最优解。遗传算法是寻求这种满意解的最佳工具。例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。（3）生产调度问题在很多情况下，采用建立数学模

7、型的方法难以对生产调度问题进行精确求解。在现实生产中多采用一些经验进行调度。遗传算法是解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。（4）自动控制。在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已经在其中得到了初步的应用。例如，利用遗传算法进行控制器参数的优化、基于遗传算法的模糊控制规则的学习、基于遗传算法的参数辨识、基于遗传算法的神经网络结构的优化和权值学习等。（5）机器人例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人结构优化和行为协调等方面得到研究和应用。（6）图像处理遗传算法可用于

8、图像处理过程中的扫描、特征提取、图像分割等的优化计算。目前遗传算法已经在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。（7）人工生命人工生命是用计算机、机械等人工媒体模拟或构造出的具有生物系统特有行为的人造系统。人工生命与遗传算法有着密切的联系，基于遗传算法的进化模型是研究人工生命现象的重要基础理论。遗传算法为人工生命的研究提供了一个有效的工具。（8）遗传编程遗传算法已成功地应用于人工智能、机器学习等领域的编程。（9）机器学习基于遗传算法的机器学习在很多领域都得到了应用。例如，采用遗传算法实现模糊控制规则的优化，可以改进模糊系统的性能；遗传算法可用于神经网络连接权的调整和结构的优化；采

9、用遗传算法设计的分类器系统可用于学习式多机器人路径规划。基 本概 念 1. 适应度与适应度函数适应度(fitness)就是借鉴生物个体对环境的适应程度, 而对所求解问题中的对象设计的一种表征优劣的测度。适应度函数(fitness function)就是问题中的全体对象与其适应度之间的一个对应关系, 即对象集合到适应度集合的一个映射。 它一般是定义在 论域空间上的一个实数值函数。 2. 染色体及其编码遗传算法以生物细胞中的染色体(chromosome)代表问题中的个体对象。而一个染色体可以看作是由若干基因组成的位串, 所以需要将问题中的个体对象编码为某种位串的形式。这样,原个体对象也就相当于生命

10、科学中所称的生物体的表现型 (phenotype), 而其编码即“染色体”也就相当于生物体的基因型(genotype)。遗传算法中染色体一般用字符串表示, 而基因也就是字符串中的一个个字符。例如,假设数字9是某问题中的 个体对象, 则我们就可以用它的二进制数串1001作为它的染色体编码。 3. 种群种群(population)就是模拟生物种群而由若干个染色体组成的群体, 它一般是整个论域空间的一个很小的子集。 遗传算法就是通过在种群上实施所称的遗传操作,使其不断更新换代而实现对整个论域空间的搜索。 4. 遗传操作遗传算法中有三种关于染色体的运算: 选择-复制、交叉和变异,这三种运算被称为遗传操

11、作或遗传算子(genetic operator)。 基本遗传算法的构成要素 选择算子(selection) ：又称为复制算子。按照某种策略 从父代中挑选个体进入下一代，如使用比例选择、轮盘 式选择。 交叉算子(crossover)：又称为杂交算子。将从群体中选 择的两个个体，按照某种策略使两个个体相互交换部分 染色体，从而形成两个新的个体。如使用单点一致交叉 。 变异算子(mutation)：按照一定的概率（一般较小），改 变染色体中某些基因的值。轮盘式选择 首先计算每个个体 i 被选中的概 率 然后根据概率的大小将将圆盘分 为 n个扇形，每个扇形的大小为 。选择时转动轮盘，参考点r落 到扇形

12、i则选择个体i 。.p1 p2pir单点一致交叉 首先以概率pc从种群中随机地选择两个个体p1 、p2。在1, 2, . . . ,l内随机选择一个数i,作为交叉的位置，称为交叉点。然后将两个个体交 叉点后面的部分交换。 例如：0110 101100 0110 0110011100 011001 1100 101100选择/交叉操作举例10220201No OffspringPt. of interchange CrossoverParentsOffspring1110#0#1#0111#0001#11#010#1000#00#110#01#10#100100100#011161711110#

13、11#0001#0#0001#11#00#11#00#110#01#10#000#01111#01#10#变异操作简单的变异操作过程如下: 每个位置的字符变量都有一个变异概率, 各位置互相独立。通过随机过程选择发生变异的位置：产生一个新结构 , 其中 是从对应位置 的字符变量的值域中随机选 择的一个取值。 可以同样得到。一致变异以概率pm对种群中所有个体的每一位进行变异。 对于个体pi的第j位，在0,1的范围内随机地生 成一个数r, 如果 r pm , 则对第j位取反，否则 保持第j位不变。反转操作简单反转操作的步骤如下:1) 从当前群体中随机选择一个结构1) 从中随机选择两个数i和j, 并定

14、义i = mini,j, j=maxi,j; 3) 颠倒a中位置i、j之间的部分, 产生新的结构基本遗传算法的构成要素运行参数N：群体大小，即群体中包含的个体的数量。T：遗传算法终止的进化代数。Pc：交叉概率，一般取为 0.40.99。Pm：变异概率，一般取为 0.00010.1 。基本遗传算法1. 随机产生一个由固定长度字符串组成的初始群体; 2. 对于字符串群体，迭代地执行下述步骤，直到选种标准被 满足为止： 1) 计算群体中的每个个体字符串的适应值; 2) 应用下述三种操作(至少前两种)来产生新的群体: 复制: 把现有的个体字符串复制到新的群体中。 杂交: 通过遗传重组随机选择两个现有的

15、子字符串, 产生新的字符串。 变异: 将现有字符串中某一位的字符随机变异。 3. 把在后代中出现的最高适应值的个体字符串指定为遗传算 法运行的结果。这一结果可以是问题的解(或近似解)。基本遗传算法流程图GEN=0概率地选择遗传操作随机创建初始群体计算群体中每个个体的适应值i:=0显示结果结束GEN:=GEN+1是是否（转下页）i=N?GEN=M？1概率地选择遗传操作根据适应值选 择一个个体完成交叉i:=i+1i:=i+1复制个体p(r)选择（接上页）基于适应值选 择两个个体把新的两个孩 子加到群体中p(c)交叉变异p(m)把新的孩子加 入到群体中完成变异根据适应值选 择一个个体把变异后个体 加

16、入到群体中1遗传算法的特点与优势 由上所述, 我们看到,遗传算法模拟自然选择和有性繁殖、 遗传变异的自然原理, 实现了优化搜索和问题求解。与图搜索相比, 遗传算法的主要特点是: 遗传算法一般是直接在解空间搜索, 而不像图搜索那样一般是在问题空间搜索, 最后才找到解(如果搜索成功的话)。 遗传算法的搜索随机地始于搜索空间的一个点集,所以遗传算法是一种随机搜索算法。 遗传算法总是在寻找优解(最优解或次优解), 所以遗传算法是一种优化搜索算法。 遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集(种群)的搜索，因而它实际是一种并行搜索, 适合大规模并行计算, 而且这种种群 到种群的搜索有能力跳出局部最优解。