现代优化方法GA课件

《现代优化方法GA课件》由会员分享，可在线阅读，更多相关《现代优化方法GA课件（95页珍藏版）》请在金锄头文库上搜索。

1、遗传算法,1. 伪随机数在智能优化方法中的作用 随机现象是自然过程或人工过程中由多种未知因素共同作用产生的一种只可分析其统计规律却不能预测其发生的不确定现象。 这种现象表现为一系列没有规则的数值时就成为随机数。 在计算机仿真中人们通常需要用到随机数。由于真正的随机数不可获得，于是人们通常用数字计算机按照某种确定的规则，通过迭代递推运算来产生一系列近似随机分布的数列。这样产生的数列虽然不是由真实的随机现象产生的，但具有类似于随机数的统计性质，可以作为随机数来运用，因此将其称为伪随机数（Pseudo Random Number）。 产生这种伪随机数的程序就称为伪随机数发生器（ Pseudo Ran

2、dom Number Generator，简称RNG）。,伪随机数的产生,设X是0-1均匀分布的随机变量，x是X的一个取值，即一个均匀分布的伪随机数，记为xU(0,1).其中，U表示均匀分布，0,1表示分布的区间。X的密度函数为 其分布函数为,产生0-1均匀分布伪随机数的乘同余法,0-1均匀分布的伪随机数通常是由均匀分布的伪随机整数除以数列长度获得的，所以首先要讨论产生均匀随机数的方法，其好坏的标准有以下几点： （1）产生的数列具有很好的随机性和均匀性。 （2）不出现重复的数列的长度要尽可能长。 （3）产生伪随机数的计算速度要快。 （4）计算程序占用的计算机内存要尽可能少。,判断产生均匀随机数

3、方法好坏的标准：,（1）平方取中法：将一个2n位的二进制随机数自乘后，取中间的2n位作为新的随机数。其公式为： 其中， 表示第k次迭代得到的二进制随机数， 表示取中间2n位数字。 （2）倍积取中法：用一个整数常数A来乘一个n位的随机数，去中间n位作为新的随机数。其公式为 其中， 表示第k次迭代得到的随机数， 表示取中间n位数字。,产生均匀随机数的方法主要有：,（3）乘同余法：用一个整数常数A来乘一个随机数，将得到的积除以模M的余数作为新的随机数。 设A是一个整数常数，M是一个大的模数，则 其中， 表示第k次迭代得到的随机数； 表示取模运算，即取除以模的余数的运算。 根据数论的理论，可以证明：位

4、数为L的计算机，如果取模数 ，当 ， ，k为正整数； 为奇数时，可以获得最长的随机数序列长度为 。,产生均匀随机数的方法主要有：,例1：若L为6，则M=64，取A=13，S0=1；那么可以获得一个随机数序列： 1,13,41,21,17,29,57,37,33,45,9,53,49,61,25,5,1， 以上不重复的序列的长度为24=16，其分布见表 可见以上产生的随机数均匀分布在区间1,M内。,产生均匀随机数的方法主要有：,（4）混合同余法（线性同余法）：用一个整数常数A乘一个随机数再加上一个整数常数C，将得到的结果除以模M的余数作为新的随机数。 当C=0时，混合同余法退化为乘同余法。 根据

5、数论的理论可以证明：位数为L的计算机，如果取模数M=2L，当A=4k+1，k为整数；C与M互为质数时，可以获得最长的随机数序列长度为2L。,产生均匀随机数的方法主要有：,例2：若L=5，则M32，取A=13，C=5；仍取S0=1，那么可以获得一个随机数序列： 1,18,15,8,13,14,27,4,25,10,7,0,5,6,19,28,17,2,31,24,29,30,11,20,9,26,23,16,21,22,3,12,1， 以上随机数序列的不重复长度为32. 虽然混合同余法比乘同余法要多做一次加法，但在相同计算机上产生的随机数的长度是乘同余法的4倍。在对随机数的长度有较高要求时，应考

6、虑采用混合同余法。,产生均匀随机数的方法主要有：,设X是服从正态分布的随机变量 当 时，称为0-1正态分布。 若Y1，Y2,，Yn是n个独立同分布的随机变量，当n足够大时 就近似于一个正态分布。一般说来，当 n6就行。X的数学期望和方差,产生正态分布伪随机数的方法：,于是有 化为N(0,1) 将前面一些公式代入，得样本值,产生正态分布伪随机数的方法：,可以取yi为独立的同为0-1均匀分布随机变量的样本 为计算方便，取n=12,产生正态分布伪随机数的方法：,一般正态分布 的随机数,产生正态分布伪随机数的方法：,遗传算法,遗传算法简称GA（Genetic Algorithms）是1962年由美国M

7、ichigan大学的Holland教授提出的模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。 遗传算法是以达尔文的自然选择学说为基础发展起来的。,自然选择学说包括以下三个方面： （1）遗传：这是生物的普遍特征，亲代把生物信息交给子代，子代总是和亲代具有相同或相似的性状。生物有了这个特征，物种才能稳定存在。 （2）变异：亲代和子代之间以及子代的不同个体之间的差异，称为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。 （3）生存斗争和适者生存：具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，性状逐渐逐渐与祖先有所不同，演变为

8、新的物种。,遗传算法的基本原理,简 介,遗传算法将“优胜劣汰，适者生存”的生物进化原理引入优化参数形成的编码串联群体中，按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，使适适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。遗传算法的算法简单，可并行处理，并能到全局最优解。,遗传算法的基本原理,基本思想,基本概念 1. 个体与种群 个体就是模拟生物个体而对问题中的对象 （一般就是问题的解）的一种称呼，一个个 体也就是搜索空间中的一个点。 种群(population)就是模拟生物种群而由

9、若 干个体组成的群体, 它一般是整个搜索空间 的一个很小的子集。,2. 适应度与适应度函数 适应度(fitness)就是借鉴生物个体对环境的 适应程度,而对问题中的个体对象所设计的 表征其优劣的一种测度。 适应度函数(fitness function)就是问题中 的全体个体与其适应度之间的一个对应关系。 它一般是一个实值函数。该函数就是遗传算 法中指导搜索的评价函数。,3. 染色体与基因 染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。 例如： 个体 染色体 9 - 1001 （2，5，6）- 010 101 110,4. 遗传操

10、作 亦称遗传算子(genetic operator)，就是关于染色体的运算。遗传算法中有三种遗传操作: 选择-复制(selection-reproduction) 交叉(crossover，亦称交换、交配或杂交) 变异(mutation，亦称突变),选择-（复制） 通常做法是：对于一个规模为N的种群S,按每个染色体xiS的选择概率P(xi)所决定的选中机会, 分N次从S中随机选定N个染色体, 并进行复制。,交叉 就是互换两个染色体某些位上的基因。,s1=01000101, s2=10011011 可以看做是原染色体s1和s2的子代染色体。,例如, 设染色体 s1=01001011, s2=10

11、010101, 交换其后4位基因, 即,变异 就是改变染色体某个(些)位上的基因。 例如, 设染色体 s=11001101 将其第三位上的0变为1, 即 s=11001101 11101101= s。 s也可以看做是原染色体s的子代染色体。 在遗传算法中使用变异算子主要有以下两个目的： （1）改善遗传算法的局部搜索能力。 （2）维持群体多样性，防止出现早熟现象。,4.2 基本遗传算法,算法中的一些控制参数： 种群规模 最大换代数 交叉率(crossover rate)就是参加交叉运算的染色体个数占全体染色体总数的比例，记为Pc,取值范围一般为0.40.99。 变异率(mutation rate

12、)是指发生变异的基因位数所占全体染色体的基因总位数的比例，记为Pm，取值范围一般为0.00010.1。,基本遗传算法 步1 在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T； 步2 随机产生U中的N个个体s1, s2, , sN，组成初始种群S=s1, s2, , sN，置代数计数器t=1； 步3 计算S中每个个体的适应度f() ； 步4 若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。,步5 按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1； 步6 按交叉

13、率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；,步7 按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3； 步8 将群体S3作为新一代种群，即用S3代替S，t = t+1，转步3；,（1）遗传算法是对参数的编码进行操作，而非对参数本身，这就是使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念，模仿自然界中生物的遗传和进化等机理； （2）遗传算法同时使用多个搜索点的搜索信息。传统的优化方法往往是从解空间的单个初始点开始最优解的迭代搜索过程，

14、单个搜索点所提供的信息不多，搜索效率不高，有时甚至使搜索过程局限于局部最优解而停滞不前。,遗传算法的特点,遗传算法从由很多个体组成的一个初始群体开始最优解的搜索过程，而不是从一个单一的个体开始搜索，这是遗传算法所特有的一种隐含并行性，因此遗传算法的搜索效率较高。 （3）遗传算法直接以目标函数作为搜索信息。传统的优化算法不仅需要利用目标函数值，而且需要目标函数的导数值等辅助信息才能确定搜索方向。而遗传算法仅使用由目标函数值变换来的适应度函数值，就可以确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助信息。,遗传算法的特点,遗传算法可应用于目标函数无法求导数或导数不存在的函数的优化

15、问题，以及组合优化问题等。 （4）遗传算法使用概率搜索技术。遗传算法的选择、交叉、变异等运算都是以一种概率的方式来进行的，因而遗传算法的搜索过程具有很好的灵活性。随着进化过程的进行，遗传算法新的群体会更多地产生出许多新的优良的个体。,遗传算法的特点,（5）遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜索； （6）遗传算法对于待寻优的函数基本无限制，它既不要求函数连续，也不要求函数可微，既可以是数学解析式所表示的显函数，又可以是映射矩阵甚至是神经网络的隐函数，因而应用范围较广； （7）遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计算速度，适合大规模复杂问题的优化。,

16、遗传算法的特点,（1）函数优化。 函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例。尤其是对非线性、多模型、多目标的函数优化问题，采用其他优化方法较难求解，而遗传算法却可以得到较好的结果。,遗传算法的应用领域,（2）组合优化。 随着问题的增大，组合优化问题的搜索空间也急剧扩大，采用传统的优化方法很难得到最优解。遗传算法是寻求这种满意解的最佳工具。例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。,（3）生产调度问题 在很多情况下，采用建立数学模型的方法难以对生产调度问题进行精确求解。在现实生产中多采用一些经验进行调度。遗传算法是解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。,遗传算法的应用领域,（4）自动控制。 在自动控制