智能控制技术——遗传算法

智能控制技术,遗传算法,主要内容,2,3. 遗传算法 3.1 遗传算法概述 3.2 遗传学相关概念 3.3 简单遗传算法 3.4 遗传算法应用举例 3.5 遗传算法的设计与实现,3,3.1 遗传算法概述,3.1.1 几种优化方法,传统的优化方法（局部优化） 共轭梯度法、拟牛顿法、单纯形方法 全局优化方法（智能优化算法） 漫步法（Random Walk）、模拟退火法、GA,4,3.1 遗传算法概述,3.1.1 几种优化方法,智能优化方法,1）不依赖于初始条件； 2）不与求解空间有紧密关系，对解域，无可微或连续的要求。求解稳健，但收敛速度慢。能获得全局最优。适合于求解空间不知的情况。,传统的优化方法,1）依赖于初始条件。 2）与求解空间有紧密关系，促使较快地收敛到局部解，但同时对解域有约束，如可微或连续。利用这些约束，收敛快。 3）有些方法，如Davison-Fletcher-Powell直接依赖于至少一阶导数；共轭梯度法隐含地依赖于梯度。,5,3.1 遗传算法概述,3.1.2 遗传算法的生物学基础,达尔文的进化论,英国的博物学家达尔文通过研究提出了被恩格斯赞誉为“19世纪自然科学三大发现”之一的生物进化学说。,6,3.1 遗传算法概述,3.1.2 遗传算法的生物学基础,达尔文的进化论（自然选择学说）,（）遗传(heredity) “种瓜得瓜，种豆得豆”，亲代把生物信息交给子代，子代按照所得信息而发育、分化，子代总是和亲代具有相同或相似的性状。 （）变异（variation） 亲代和子代之间以及子代的不同个体之间总有差异。变异是随机发生的，变异的选择和积累是生命多样性的根源。 （）生存斗争和适者生存由于弱肉强食和生存斗争不断进行，其结果是适者生存，不适者被淘汰，通过一代代的选择作用，物种变异朝着一个方向积累，演变为新的物种。,7,3.1 遗传算法概述,3.1.2 遗传算法的生物学基础,桦尺蛾的例子,1850年，人们发现了第一只黑色桦尺蛾 19世纪末,黑色桦尺蛾占了95%以上,浅灰色桦尺蛾从99%降到5%以下,8,3.1 遗传算法概述,3.1.3 遗传算法,遗传算法（Genetic Algorithm，简称 GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程以及Mendel遗传学的计算机算法。 它由美国 Holland 教授1975年提出。,9,3.1 遗传算法概述,3.1.3 遗传算法,基于模仿生物界遗传学的遗传过程，把问题的参数用基因来表示，把问题的解用染色体来表示代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体。 这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代，后代随机化地继承父代的最好特征，并也在生存环境的控制支配下继续这一过程。 群体的染色体都将逐渐适应环境，不断进化，最后收敛到一组最适应环境的类似个体，即得到问题最优解。,基本思想,10,3.1 遗传算法概述,3.1.3 遗传算法,遗传算法不是直接作用在参变量集上而是利用参变量集的某种编码 遗传算法不是从单个点，而是从一个点的群体开始搜索； 遗传算法利用适应值信息，无须导数或其它辅助信息； 遗传算法利用概率转移规则，而非确定性规则。,与传统的优化算法相比，遗传算法主要有以下几个不同之处,11,3.1 遗传算法概述,3.1.3 遗传算法,它在搜索过程中不容易陷入局部最优，即使所定义的适应函数是不连续的、非规则的或有噪声的情况下，它也能以很大的概率找到整体最优解； 由于它固有的并行性，遗传算法非常适用于大规模并行计算机。,遗传算法特别的优越性,12,3.1 遗传算法概述,3.1.3 遗传算法,遗传算法特别的优越性,主要内容,13,3. 遗传算法 3.1 遗传算法概述 3.2 遗传学相关概念 3.3 简单遗传算法 3.4 遗传算法应用举例 3.5 遗传算法的设计与实现,14,3.2 遗传学相关概念,3.2.1 个体与种群,个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。 种群(population)就是模拟生物种群而由若干个体组成的群体, 它一般是整个搜索空间的一个很小的子集。,15,3.2 遗传学相关概念,3.2.2 适应度与适应度函数,适应度(fitness)就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。 适应度函数(fitness function)就是问题中的全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。,16,3.2 遗传学相关概念,适应度函数的重要性 适应度函数的选取直接影响遗传算法的收敛速度以及能否找到最优解。 一般而言，适应度函数是由目标函数变换而成的，对目标函数值域的某种映射变换称为适应度的尺度变换（fitness scaling）。,17,3.2 遗传学相关概念,适应度函数的设计 单值、连续、非负、最大化 合理、一致性 计算量小 通用性强,18,3.2 遗传学相关概念,几种常见的适应度函数 直接转换 若目标函数为最大化问题：Fit ( f (x) )= f (x) 若目标函数为最小化问题：Fit ( f (x) )= - f (x),19,3.2 遗传学相关概念,几种常见的适应度函数 乘幂尺度变换与指数尺度变换,20,3.2 遗传学相关概念,3.2.3 染色体与基因,染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。 例如： 个体 染色体 9 - 1001 （2，5，6）- 010 101 110,21,二进制编码方法 二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集是由二进制符号0和1所组成的二值符号集0，1，它所构成的个体基因型是一个二进制编码符号串。 (1) 编码 假设某一参数的取值范围是umax, umin，我们用长度为 的二进制编码符号串来表示该参数，则它总共能够产生 2 种不同的编码，参数编码时的对应关系如下： 00000000000000000 umin 00000000000000011 umin + 1111111111111111=21 umax 二进制编码的编码精度为：,3.2 遗传学相关概念,22,(2) 解码 假设某一个体的编码是： x: b b-1 b-2 b2 b1 则对应的解码公式为：,例如，对于x 0, 1023，若用 10 位长的二进制编码表示该参数的话，下述符号串： x：0010101111 就可表示一个个体， 它所对应的参数值是 x175。 编码精度为 = 1。,3.2 遗传学相关概念,23,(3) 二进制编码方法的优点： 编码、解码操作简单易行； 交叉、变异等遗传操作便于实现； 符合最小字符集编码原则（使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案。）； 便于利用模式定理对算法进行理论分析。,3.2 遗传学相关概念,24,浮点数编码方法 (1) 二进制编码的缺点 二进制编码存在着连续函数离散化时的映射误差。 个体编码串的长度较短时，可能达不到精度要求；个体编码串的长度较长时，虽然能提高编码精度，但却会使遗传算法的搜索空间急剧扩大。 二进制编码不便于反映所求问题的特定知识，这样也就不便于开发针对问题专门知识的遗传运算算子，人们在一些经典优化算法的研究中所总结出的一些宝贵经验也就无法在这里加以利用，也不便于处理非平凡约束条件。 (2) 浮点数编码方法 个体的每个基因值用某一范围内的一个浮点数来表示； 个体的编码长度等于其决策变量的个数。 这种编码方法使用的是决策变量的真实值，所以浮点数编码方法也叫做真值编码方法。,3.2 遗传学相关概念,25,例如，如果一个优化问题含有5个变量 xi (i1,2,5)，每个变量都有其对应的上下限uimin , uimax，则： 表示一个体的基因型， 其对应的表现型是：x： 5.80，6.90，3.50，3.80，5.00T。,3.2 遗传学相关概念,26,(3) 注意事项： 在浮点数编码方法中:必须保证基因值在给定的区间限制范围内；遗传算法中所使用的交叉、变异等遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限制范围内。 当用多个字节来表示一个基因值时，交叉运算必须在两个基因的分界字节处进行，而不能在某个基因的中间字节分隔处进行。,3.2 遗传学相关概念,27,(4) 浮点数编码方法的优点： 适合于在遗传算法中表示范围较大的数； 适合于精度要求较高的遗传算法； 便于较大空间的遗传搜索； 改善了遗传算法的计算复杂性，提高了运算效率； 便于遗传算法与经典优化方法的混合使用； 便于设计针对问题的专门知识的知识型遗传算子； 便于处理复杂的决策变量约束条件。,3.2 遗传学相关概念,28,二进制编码与浮点数编码的比较 在交叉操作时，二进制编码比浮点数编码产生新个体的可能性多，而且产生的新个体不受父个体所构成的超体的限制； 在变异操作时，二进制编码的种群稳定性比浮点数编码差。,3.2 遗传学相关概念,29,符号编码方法 (1) 编码方法 个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。 这个符号集可以是一个字母表，如 A, B, C, D, ； 也可以是一个数宇序号表，如 1, 2, 3, 4, 5, ； 还可以是一个代码表，如 Al, A2, A3, A4, A5, 等等。,3.2 遗传学相关概念,30,例如 ：对于旅行商问题，假设有n个城市分别记为 C1, C2, , Cn ，将各个城市的代号按其被访问的顺序连接在一起，就可构成一个表示旅行路线的个体，如： X： C1, C2, , Cn 若将各个城市按其代号的下标进行编号，则这个个体也可表示为： X：1，2， ，n 旅行商问题(Traveling Salesman Problem，简称TSP)可描述为；已知n个城市之间的相互距离。现有一推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短? ,3.2 遗传学相关概念,31,(2) 符号编码的主要优点： 符合有意义积木块编码原则。 便于在遗传算法中利用所求解问题的专门知识。 便于遗传算法与相关近似算法之间的混合使用。 但对于使用符号编码方法的遗传算法，一般需要认真设计交叉、变异等遗传运算的操作方法，以满足问题的各种约束要求，这样才能提高算法的搜索性能。,3.2 遗传学相关概念,32,3.2 遗传学相关概念,3.2.2 遗传操作,亦称遗传算子(genetic operator)，就是关于染色体的运算。遗传算法中有三种遗传操作: 选择-复制(selection-reproduction) 交叉(crossover，亦称交换、交配或杂交) 变异(mutation，亦称突变),33,3.2 遗传学相关概念,34,3.2 遗传学相关概念,主要内容,35,3. 遗传算法 3.1 遗传算法概述 3.2 遗传学相关概念 3.3 简单遗传算法 3.4 遗传算法应用举例 3.5 遗传算法的设计与实现,36,3.3 简单遗传算法,3.3.1 遗传算法基本步骤,（1）把问题的解表示成 “染色体”。 在算法中就是以二进制编码的串，给出一群 “染色体”，也就是假设的可行解,（2）把这些可行解置于问题的 “环境” 中，按适者生存的原则，选取较适应环境的“染色体”进行复制，并通过交叉、变异过程产生更适应环境的新一代 “染色体” 群,（3）经过这样的一代一代地进化，最后就会收敛到最适应环境的一个 “染色体” 上，它就是问题的最优解,基本步骤概述,37,3.3 简单遗传算法,3.3.1 遗传算法基本步骤,具体步骤,选择编码策略，把参数集合（可行解集合）转换染色体结构空间； 定义适应度函数，便于计算适应值； 确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数； 随机产生初始化