经典-智能优化方法课件PPT-东北大学+王俊伟.ppt

1,智能优化方法AI-BasedOptimizationMethods,ByWangJunweiPhDNortheasternUniversityChina2007,2,课程进度,No.1导言、伪随机数的产生方法No.2遗传算法(GA)No.3遗传算法(GA)No.4遗传算法(GA)No.5禁忌搜索(TS),3,课程进度,No.6模拟退火(SA)No.7新发展起来的算法蚁群优化(ACO)，粒子群优化(PSO)捕食搜索（PS）,群落选址算法（CLA）No.8考试,4,教材,智能优化方法汪定伟王俊伟王洪峰张瑞友郭哲编著高等教育出版社中英文文献,5,第一章导言,6,第一章导言,.最优化的重要性一.传统优化方法的基本步骤三步曲二.传统优化方法的局限性三.实际问题中对最优化方法的要求四.智能优化算法的产生与发展五.应用前景局限性和研究方向、注意事项,7,人类的一切活动都是认识世界和改造世界的过程即：认识世界改造世界(建模)(优化),.最优化的重要性（1）,8,一切学科都是建模与优化在某个特定领域中的应用概念模型(定性)结构模型(图)数学模型智能模型,.最优化的重要性（2）,9,最优化理论的发展极值理论；运筹学的兴起(OperationResearch)；数学规划：线性规划(LP)；非线性规划(NLP)；动态规划(PP)；马尔托夫规划(MDP)；排队轮；决策论；存储论。最优化理论在国民经济中的广泛应用,.最优化的重要性（3）,10,如下面框图所示选一个初始解LP:大M，二阶段法NLP:任意点或一个内点,一.传统优化方法的基本步骤三步曲（1）,11,停止判据停止规则最优性检验LP:检验数当0时有可能减小NLP:,一.传统优化方法的基本步骤三步曲（2）,12,向改进方向移动改进解LP:转轴变换(进基、退基)NLP:向负梯度方向移动(共轭梯度方向、牛顿方向),一.传统优化方法的基本步骤三步曲（3）,13,一.传统优化方法的基本步骤三步曲（4）,14,对问题中目标函数、约束函数有很高的要求有显式表达，线性、连续、可微，且高阶可微;2.只从一个初始点出发，难以进行并行、网络计算，难以提高计算效率；,二.传统优化方法的局限性（1）,15,最优性达到的条件太苛刻问题的函数为凸，可行域为凸；在非双凸条件下，没有跳出局部最优解的能力。,二.传统优化方法的局限性（2）,16,对问题的描述要宽松(目标和约束函数)可以用一段程序来描述(程序中带判断、循环)，函数可以非连续、非凸、非可微、非显式；并不苛求最优解通常满意解、理想解就可以了；,三.实际问题中对最优化方法的要求（1）,17,计算快速、高效,可随时终止(根据时间定解的质量)；能够处理数据、信息的不确定性(如数据的模糊性，事件的随机性)。,三.实际问题中对最优化方法的要求（2）,18,1975年holland提出遗传算法(GeneticAlgorithm)1977年Glouer提出禁忌搜索算法(TabnSearch),四.智能优化算法的产生与发展（1）,19,1982年Kirkpatrick提出模拟退火算法(SimulatedAnnealing)人工神经元网络1995年Dorigo提出蚁群算法(AntColonyOptimization),四.智能优化算法的产生与发展（2）,20,1995年Kennedy算法改进表现在以下几个方面：问题的描述、编码方法、算法构造及可行性修复策略;要进行大量的上机计算；,五.应用前景局限性和研究方向、注意事项（2）,24,算例的选取，以下算例的说服力降序排列：网上的测试用例、文献中的例子、实际例子、随机产生的例子、自己编的例子;如何检验算法的好坏：比较计算速度、可解规模、(从不同的随机种子出发)达优率。,五.应用前景局限性和研究方向、注意事项（3）,25,第二章伪随机数的产生,26,第二章伪随机数的产生,一.伪随机数产生的意义二.产生U(0,1)的乘同余法三.正态分布N(0,1)的产生四.逆变法与其它分布随机数的产生,27,在GA,SA,TS中都要用到；在计算机中的固有伪随机数发生器只有U(0,1)且可重复性不好，没有其他分布；自己设计的发生器，可控型好、可重复性好，便于仿真比较。,一.伪随机数产生的意义,28,乘同余法的计算公式可产生随机数序列。问题：怎样设定和可以使随机数序列最长？,二.产生U(0,1)的乘同余法（1）,29,乘同余法的方法：若的整数，当x满足以下条件时，可以达到最大周期(序列长度)为3(Mod8)或5(Mod8)的数；为奇数，一般取为1。,二.产生U(0,1)的乘同余法（2）,30,乘同余法举例说明：=16=3=1,3,9,11,1,3,9,11=5=1,5,9,13,1,5,9,13=3=2,6,2,6可得整数序列，要想获得U(0,1)，见下面,二.产生U(0,1)的乘同余法（3）,31,产生U(0,1)步骤：；令。,二.产生U(0,1)的乘同余法（4）,32,产生U(0,1)举例说明：=16=3，x0=1=1/16,3/16,9/16,11/16,1/16,3/16,9/16,11/16=3，x0=2=2/16,6/16,2/16,6/16,二.产生U(0,1)的乘同余法（5）,33,优秀编程举例：IF(NR(T0)NR=NR+M(M对应于计算机中最大整数),二.产生U(0,1)的乘同余法（6）,34,三.正态分布N(0,1)的产生（1）,正态分布可以用多个U(0,1)来近似，若是独立同分布，较大，则近似正态分布，且满足及则,35,令：一般n取12则：其中：（详见下页）,三.正态分布N(0,1)的产生（2）,36,注：,三.正态分布N(0,1)的产生（3）,37,逆变法,四.逆变法与其它分布随机数的产生（1）,38,是分布函数，如何产生？设，是随机变量产生，是分布函数逆变法的目的：产生分布的随机数,四.逆变法与其它分布随机数的产生（2）,39,逆变法的步骤：已知，或由求即，令推导产生用得到,四.逆变法与其它分布随机数的产生（3）,40,负指数分布的产生负指数函数的密度函数：,四.逆变法与其它分布随机数的产生（4）,41,负指数函数的分布函数的产生过程：令产生则即,四.逆变法与其它分布随机数的产生（5）,42,产生是负指数分布的。,四.逆变法与其它分布随机数的产生（6）,43,第三章遗传算法,44,第三章遗传算法,一.导言二.Holland的基本GA三.计算举例四.Holland的结构理论五.GA的各种变形六.应用七.学习GA的几点体会,45,遗传算法(GA)的产生1975年，Holland提出GA著名的书：AdaptationinNaturalandArtificialSystems(中文名称：自然与人工系统的自适应性)后来，DeJong和Goldberg做了大量工作，使GA更加完善。,一.导言（1）,46,遗传算法(GA)的来源：生物的进化：自然选择、适者生存生物的遗传和变异(GA)缺点：无人的主动性；解决方法有以下三个：定向培育随机算法网格法,一.导言（2）,47,定向培育过程如下：第一：一个种群，大量的生物个体；第二：选择具有需要特性的若干个体；第三：进行繁殖；第四：重复第二，直到满意为止。,一.导言（3）,48,随机算法：在解空间随机产生多个解，选择最好的网格法：根据最好解的几何分布，来不断的缩小搜索范围。,一.导言（4）,49,遗传算法的基本思想根据问题的目标函数构造适值函数(FitnessFunction)；产生一个初始种群(100-1000)；根据适值函数的好坏，不断选择繁殖；若干代后得到适值函数最好的个体即最优解。,一.导言（5）,50,遗传算法的构成要素种群(Population),种群大小(Pop-size)基因表达法编码方法(EncodingScheme;GeneRepresentation),一.导言（6）,51,遗传算子(GeneticOperator)：交叉(Crossover)，变异(Mutation)选择策略:一般为正比选择停止准则(StoppingRule/Criterion):一般是指定最大代数,一.导言（7）,52,算法框架与步骤见下页,二.Holland的基本GA（1）,53,二.Holland的基本GA（2）,54,解空间与编码空间的转换遗传运算是对编码空间操作的，所以要进行两个空间的转换。见下页示意图,二.Holland的基本GA（3）,55,二.Holland的基本GA（4）,56,各个步骤的实现初始种群的产生编码方法适值函数遗传运算选择策略停止准则,二.Holland的基本GA（5）,57,初始种群的产生随机产生(依赖于编码方法)；种群的大小(依赖于计算机的计算能力和计算复杂度)。例：0,1编码产生，0.5，=1；个体数()，即分类方法数个体总数。因模板因子、个体因子分别为(0，1，)、(0，1)。,四.Holland的结构理论（3）,78,模板理论引理1：在正比选择下，模板在第代的期望个体数为：其中是第代模板中所有个体的适值均值与种群中所有个体的适值均值的比，是第代的个体数。如例1中：0，=1.4858，=2，=3,四.Holland的结构理论（4）,79,证明：,四.Holland的结构理论（5）,80,注释:种群的适值和为：，则选择概率为：为中的个体总数，且下标随遗传的进行而变化；,四.Holland的结构理论（6）,81,为模板中所有个体的适值均值;为种群的适值均值只要均值1，则好的种群的个体会越来越多。问题：以上证明没有考虑交叉变异，那么交叉变异会不会破坏种群模板？概率有多大？,四.Holland的结构理论（7）,82,引理2：第代以概率做交叉，对长度为的概型，则在第代中个体数为概型的概率下界为：其中为第代个体为的概率。,四.Holland的结构理论（8）,83,引理2的证明证明：交叉破坏的条件做了交叉：交叉点在内:配偶不在中：则不被破坏的概率：,四.Holland的结构理论（9）,84,思考：若不属于概型，是否能产生后代为概型？答案：可以,四.Holland的结构理论（10）,85,引理3：若第代以做变异，对于一个阶数为的模板,则在第代仍为的概率的下界为：证明：对于，当=1，不破坏的概率为当1，不破坏的概率为取其泰勒展开式的第一项：,四.Holland的结构理论（11）,86,主定理(概型定理)：第代以概率和做交叉和变异时，长度为，阶数为，适值均值比为的概型在第代的期望个体数的下界为：当时，随代数的增加而增加。,四.Holland的结构理论（12）,87,其它编码方法顺序编码：用1到N的自然数的不同顺序来编码，此种编码不允许重复，即且，又称自然数编码。该法适应范围很广：指派、旅行商问题，单机调度。合法性问题：是否符合采用的编码规则的问题,五.GA的各种变形（1）,88,实数编码特征：方便运算简单，但反映不出基因的特征整数编码应用于新产品投入，时间优化，伙伴挑选例：3212345对顺序编码来说是不合法的，而对整数编码来说是合法的；010200不合法的01编码；,五.GA的各种变形（2）,89,练习（1）,对于编码长度为7的01编码，判断以下编码的合法性(1)1020110,(2)101100,(3)0110010,(4)0000000,(5)2134576.,90,练习（2）,对于编码长度为7的顺序编码，判断以下编码的合法性(1)7120435,(2)136247,(3)2135476,(4)8143257,(5)2132576.,91,练习（3）,对于编码长度为7的实数编码，判断以下编码的合法性(1)3.51.9271.81.70,(2)89.054.78214.36.9,(3)0110010,(4)0000000,(5)2134576.,92,遗传运算中的问题在顺序编码遗传运算的过程中会遇见不合法的编码，应战的策略有二:拒绝或修复。例如：经交叉后，后代编码不合法2134567211256743125764334576我们采用下面的修复策略使以上的编码合法。,五.GA的各种变形（3）,93,顺序编码的合法性修复：交叉修复策略它分为以下几种部分映射交叉顺序交叉循环交叉,五.GA的各种变形（4）,94,部分映射交叉(PMX)(PartiallyMappedCrossover)PMX步骤：选切点X,Y；交换中间部分；确定映射关系；将未换部分按映射关系恢复合法性。,五.GA的各种变形（5）,95,PMX例题：,五.GA的各种变形（6）,96,顺序交叉(OX)OrderCrossoverOX步骤：选切点X,Y；交换中间部分；从切点Y后第一个基因起列出原序，去掉已有基因；Y后第一个位置起填入。,五.GA的各种变形（7）,97,OX例题：,五.GA的各种变形（8）,98,OX的特点：较好的保留了相邻关系、先后关系满足了TSP问题的需要，但不保留位值特征。,五.GA的各种变形（9）,99,循环交叉(CX)CycleCrossover基本思想：子串位置上的值必须与父母的相同位置上的位值相等。CX步骤：选的第一个元素作为的第一位，选的第一个元素作为的第一位；,五.GA的各种变形（10）,100,到中找的第一个元素赋给的相对位置，重复此过程，直到上得到的第一个元素为止，称为一个循环；对最前的基因按、基因轮替原则重复以上过程；重复以上过程，直到所有位都完成。,五.GA的各种变形（11）,101,CX例题：,五.GA的各种变形（12）,102,CX的特点：与OX的特点不同的是，CX较好的保留了位值特征，适合指派问题；而OX较好的保留了相邻关系、先后关系满足了TSP问题的需要。,五.GA的各种变形（13）,103,练习,P1：61289547103P2：10741362859PMX：C1：C2：OX：C1：C2:,104,练习（2）,P1：61289547103P2：10741362859CX：C1：C2：,105,变异的修复策略换位变异(最常用)例：43125674512367移位变异：任选一位移到最前例：43125675431267,五.GA的各种变形（14）,106,实数编码的合法性修复交叉单切点交叉,五.GA的各种变形（15）,切点,107,双切点交叉(与单切点交叉类似)该方法最大的问题：如何在实优化中保持可行性。,五.GA的各种变形（16）,108,凸组合交叉约束是个凸集，可行性可以保持，问题是分散性太差，向中间汇集的问题需要解决。,五.GA的各种变形（17）,109,变异位值变异：任选一位加，例：,五.GA的各种变形（18）,110,向梯度方向变异缺点：只能用于目标函数可微的问题例:,五.GA的各种变形（19）,111,适值函数的标定(Scaling),五.GA的各种变形（20）,112,标定的目的：使适值函数不会太大，有一定差别选择压力的概念：选择压力是种群好、坏个体被选中的概率之差，差大称为选择压力大。,五.GA的各种变形（21）,113,局部搜索、广域搜索与选择压力的关系局部搜索与广域搜索是GA中的一对矛盾，好的算法要将以上二者综合考虑。算法开始重广域搜索，选择压力小；随迭代进行，逐步偏重于局部搜索，选择压力大。,五.GA的各种变形（22）,114,适值的标定方法线性标定：函数表达式,为目标函数，为适值函数,五.GA的各种变形（23）,115,对，=1，=，函数表达式：+，对，=-1，=,函数表达式：+，,五.GA的各种变形（24）,116,动态线性标定(最常用)优点：计算容易不占用时间函数表达式：，为迭代指标最常用极大化：=1,函数表达式：,五.GA的各种变形（25）,117,加入的意义：加入使最坏个体仍有繁殖的可能，随而减小的取值：，调节和，从而来调节,五.GA的各种变形（26）,118,引入目标的目的：调节选择压力，即好坏个体选择概率的差，使广域搜索范围宽保持种群的多样性，而局域搜索细保持收敛性。如下图表示：开始：希望选择压力小后来：希望选择压力大,五.GA的各种变形（27）,119,幂律标定：函数表达式：的取值，1时选择压力加大=Re，它们依据概率Rp来决定是复制它们自己(clone)还是交配(mate)。,294,ALA,Step7:减少能量（ReduceEnergy）：所有的生物将减少能量Le。如果某个人工生物的能量少有Ld，则它将死掉，同时从人工环境中移走。Step8:增长代数（Increasinggenernation）：代数增加1；如果代数小于结束的代数，返回Step2；否则结束计算。,295,ALA,韩国学者Bo-SukYang等人在Optimumdesignofshortjournalbearingsbyartificialli