智能优化方法东北大学王俊伟学习教案.pptx

《智能优化方法东北大学王俊伟学习教案.pptx》由会员分享，可在线阅读，更多相关《智能优化方法东北大学王俊伟学习教案.pptx（312页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1智能智能(zh nn)优化方法东北大学王俊伟优化方法东北大学王俊伟第一页，共312页。2课程课程(kchng)进度进度No.1No.1导言、伪随机数的产生方法导言、伪随机数的产生方法No.2No.2遗传算法遗传算法(GA)(GA)No.3No.3遗传算法遗传算法(GA)(GA)No.4No.4遗传算法遗传算法(GA)(GA)No.5No.5禁忌禁忌(jnj)(jnj)搜索搜索(TS)(TS)第1页/共312页第二页，共312页。3课程课程(kchng)进度进度No.6 No.6 No.6 No.6 模拟退火模拟退火模拟退火模拟退火(SA)(SA)(SA)(SA)No.7 No.7 No

2、.7 No.7 新发展起来新发展起来新发展起来新发展起来(q li)(q li)(q li)(q li)的算法的算法的算法的算法 蚁群优化蚁群优化蚁群优化蚁群优化(ACO)(ACO)(ACO)(ACO)，粒子群优化，粒子群优化，粒子群优化，粒子群优化(PSO)(PSO)(PSO)(PSO)捕食搜索（捕食搜索（捕食搜索（捕食搜索（PSPSPSPS）,群落选址算法（群落选址算法（群落选址算法（群落选址算法（CLACLACLACLA）No.8 No.8 No.8 No.8 考试考试考试考试第2页/共312页第三页，共312页。4教材教材(jioci)n n智能优化方法智能优化方法(fngf)(fng

3、f)n n汪定伟汪定伟 王俊伟王俊伟 王洪峰王洪峰 张瑞友张瑞友 郭哲郭哲 编著编著n n高等教育出版社高等教育出版社n n中英文文献中英文文献第3页/共312页第四页，共312页。5第一章第一章 导言导言(doyn)(doyn)第4页/共312页第五页，共312页。6第一章第一章 导言导言(doyn).最优化的重要性最优化的重要性一一.传统优化方法的基本步骤传统优化方法的基本步骤三步曲三步曲二二.传统优化方法的局限性传统优化方法的局限性三三.实际问题中对最优化方法的要求实际问题中对最优化方法的要求四四.智能优化算法的产生与发展智能优化算法的产生与发展五五.应用应用(yngyng)(yngyn

4、g)前景局限性和研究方向、前景局限性和研究方向、注意事项注意事项第5页/共312页第六页，共312页。7人类的一切活动人类的一切活动(hu dng)(hu dng)都是认都是认识世界和改造世界的过程识世界和改造世界的过程 即：即：认识世界认识世界 改造改造世界世界 (建模建模)()(优化优化).最优化的重要性（最优化的重要性（最优化的重要性（最优化的重要性（1 1 1 1）第6页/共312页第七页，共312页。8一切学科都是建模与优化在某个特一切学科都是建模与优化在某个特定领域中的应用定领域中的应用(yngyng)(yngyng)概念模型概念模型(定性定性)结构模型结构模型(图图)数学模型数学

5、模型 智能模智能模型型.最优化的重要性（最优化的重要性（最优化的重要性（最优化的重要性（2 2）第7页/共312页第八页，共312页。93.最优化理论的发展最优化理论的发展4.极值理论；极值理论；5.运筹学的兴起运筹学的兴起(Operation Research)；6.数学规划数学规划(guhu)：线性规划：线性规划(guhu)(LP)；非线性规划；非线性规划(guhu)(NLP)；动态规划；动态规划(guhu)(PP)；马尔托夫规划；马尔托夫规划(guhu)(MDP)；排队轮；决策；排队轮；决策论；存储论。论；存储论。7.最优化理论在国民经济中的广泛最优化理论在国民经济中的广泛应用应用.最优

6、化的重要性（最优化的重要性（最优化的重要性（最优化的重要性（3 3 3 3）第8页/共312页第九页，共312页。10如下面框图所示如下面框图所示如下面框图所示如下面框图所示选一个初始选一个初始选一个初始选一个初始(ch sh(ch sh)解解解解LP:LP:大大大大MM，二阶段法，二阶段法，二阶段法，二阶段法NLP:NLP:任意点或一个内点任意点或一个内点任意点或一个内点任意点或一个内点一一一一.传统传统传统传统(chunt(chunt ng)ng)优化方法的基本步骤优化方法的基本步骤优化方法的基本步骤优化方法的基本步骤三三三三步曲（步曲（步曲（步曲（1 1）第9页/共312页第十页，共31

7、2页。11停止判据停止判据停止判据停止判据停止规则最优性检验停止规则最优性检验停止规则最优性检验停止规则最优性检验(ji(ji nyn)nyn)LP:LP:检验检验检验检验(ji(ji nyn)nyn)数数数数当当当当00时有可能减小时有可能减小时有可能减小时有可能减小NLP:NLP:一一一一.传统传统传统传统(chunt(chunt ng)ng)优化方法的基本步骤优化方法的基本步骤优化方法的基本步骤优化方法的基本步骤三步三步三步三步曲（曲（曲（曲（2 2）第10页/共312页第十一页，共312页。12向改进方向移动向改进方向移动向改进方向移动向改进方向移动(ydng)(ydng)改进解改进解

8、改进解改进解LP:LP:转轴变换转轴变换转轴变换转轴变换(进基、退基进基、退基进基、退基进基、退基)NLP:NLP:向负梯度方向移动向负梯度方向移动向负梯度方向移动向负梯度方向移动(ydng)(ydng)(共轭梯度方向、牛顿方向共轭梯度方向、牛顿方向共轭梯度方向、牛顿方向共轭梯度方向、牛顿方向)一一一一.传统优化方法传统优化方法传统优化方法传统优化方法(fngf(fngf)的基本步骤的基本步骤的基本步骤的基本步骤三步三步三步三步曲（曲（曲（曲（3 3）第11页/共312页第十二页，共312页。13停机选择一个初始解停止准则向改进方向移动启动YN一一.传统优化方法传统优化方法(fngf)(fng

9、f)的基本步骤的基本步骤三步曲（三步曲（4 4）第12页/共312页第十三页，共312页。14对问题中目标函数、约束函数有很高的要求对问题中目标函数、约束函数有很高的要求对问题中目标函数、约束函数有很高的要求对问题中目标函数、约束函数有很高的要求(yoqi)(yoqi)有显式表达，线性、连续、可微，且高阶可微有显式表达，线性、连续、可微，且高阶可微有显式表达，线性、连续、可微，且高阶可微有显式表达，线性、连续、可微，且高阶可微;2.2.只从一个初始点出发，难以进行并行、网络计算，难以提高计算效率；只从一个初始点出发，难以进行并行、网络计算，难以提高计算效率；只从一个初始点出发，难以进行并行、网

10、络计算，难以提高计算效率；只从一个初始点出发，难以进行并行、网络计算，难以提高计算效率；二二.传统传统(chuntng)优化方法的局限性优化方法的局限性（1）第13页/共312页第十四页，共312页。15最优性达到的条件太苛刻最优性达到的条件太苛刻最优性达到的条件太苛刻最优性达到的条件太苛刻问题的函数为凸，可行域为凸；问题的函数为凸，可行域为凸；问题的函数为凸，可行域为凸；问题的函数为凸，可行域为凸；在非双凸条件下，没有在非双凸条件下，没有在非双凸条件下，没有在非双凸条件下，没有(mi y(mi y u)u)跳出局部最优解的能力。跳出局部最优解的能力。跳出局部最优解的能力。跳出局部最优解的能力

11、。二二二二.传统传统传统传统(chunt(chunt ng)ng)优化方法的局限性（优化方法的局限性（优化方法的局限性（优化方法的局限性（2 2）第14页/共312页第十五页，共312页。161.1.对问题的描述要宽松对问题的描述要宽松(目标和约目标和约束函数束函数)2.2.可以用一段程序来描述可以用一段程序来描述(程序程序中带判断中带判断(pndun)(pndun)、循环、循环)，函，函数可以非连续、非凸、非可微、数可以非连续、非凸、非可微、非显式；非显式；3.3.并不苛求最优解并不苛求最优解通常满意解、通常满意解、理想解就可以了；理想解就可以了；三三三三.实际实际实际实际(shj)(shj

12、)(shj)(shj)问题中对最优化方法的要问题中对最优化方法的要问题中对最优化方法的要问题中对最优化方法的要求（求（求（求（1 1 1 1）第15页/共312页第十六页，共312页。173.计算快速、高效计算快速、高效,可随时终止可随时终止(根根据时间定解的质量据时间定解的质量)；4.能够能够(nnggu)处理数据、信息处理数据、信息的不确定性的不确定性(如数据的模糊性，如数据的模糊性，事件的随机性事件的随机性)。三三三三.实际实际实际实际(shj)(shj)(shj)(shj)问题中对最优化方法的要求问题中对最优化方法的要求问题中对最优化方法的要求问题中对最优化方法的要求（2 2 2 2）

13、第16页/共312页第十七页，共312页。181.1975年年holland提出提出(t ch)遗传遗传算法算法2.(Genetic Algorithm)3.1977年年Glouer提出提出(t ch)禁忌搜禁忌搜索算法索算法4.(Tabn Search)四四四四.智能优化算法智能优化算法智能优化算法智能优化算法(sun f)(sun f)(sun f)(sun f)的产生与发展的产生与发展的产生与发展的产生与发展（1 1 1 1）第17页/共312页第十八页，共312页。193.1982年年Kirkpatrick提出提出(t ch)模模拟退火算法拟退火算法4.(Simulated Annea

14、ling)5.人工神经元网络人工神经元网络6.1995年年Dorigo提出提出(t ch)蚁群算蚁群算法法7.(Ant Colony Optimization)四四四四.智能优化算法智能优化算法智能优化算法智能优化算法(sun f)(sun f)(sun f)(sun f)的产生与发展的产生与发展的产生与发展的产生与发展（2 2 2 2）第18页/共312页第十九页，共312页。206.1995年年Kennedy&Eherhart提出提出(t ch)粒子群优化粒子群优化 (Particle Swarm Optimization)7.其它其它8.文化算法文化算法(Cultural Algorit

15、hm)9.人工生命算法人工生命算法(Artificial-Life Algorithm)四四四四.智能优化算法智能优化算法智能优化算法智能优化算法(sun f)(sun f)(sun f)(sun f)的产生与发展的产生与发展的产生与发展的产生与发展（3 3 3 3）第19页/共312页第二十页，共312页。21我们统称以上算法为人工生命计算我们统称以上算法为人工生命计算 (Artificial Life Computation)(Artificial Life Computation)人工生命计算人工生命计算+模糊模糊(m hu)(m hu)逻辑逻辑 (Fuzzy Logic)=(Fuzzy

16、 Logic)=软计算软计算(Soft Computation)(Soft Computation)人工生命计算人工生命计算+进化编程进化编程 =进化算法进化算法(Evolutionary (Evolutionary computation)computation)四四.智能智能(zh nn)(zh nn)优化算法的产生与发优化算法的产生与发展（展（4 4）第20页/共312页第二十一页，共312页。221.应用应用(yngyng)前景十分广阔前景十分广阔国民经济的各个领域国民经济的各个领域2.局限性局限性不能保证最优解，理不能保证最优解，理论上不完备论上不完备五五五五.应用应用应用应用(yn

17、gyng)(yngyng)(yngyng)(yngyng)前景局限性和研究方向、注意前景局限性和研究方向、注意前景局限性和研究方向、注意前景局限性和研究方向、注意事项（事项（事项（事项（1 1 1 1）第21页/共312页第二十二页，共312页。233.研究方向及注意事项研究方向及注意事项4.以应用为主，扩大面向新问题的以应用为主，扩大面向新问题的应用；不要刻意做理论研究，若应用；不要刻意做理论研究，若碰上也不拒绝碰上也不拒绝;5.算法算法(sun f)改进表现在以下几改进表现在以下几个方面：问题的描述、编码方法、个方面：问题的描述、编码方法、算法算法(sun f)构造及可行性修复构造及可行性

18、修复策略策略;6.要进行大量的上机计算；要进行大量的上机计算；五五五五.应用前景局限性和研究应用前景局限性和研究应用前景局限性和研究应用前景局限性和研究(ynji)(ynji)(ynji)(ynji)方向、注意事方向、注意事方向、注意事方向、注意事项（项（项（项（2 2 2 2）第22页/共312页第二十三页，共312页。24算例的选取，以下算例的说服力算例的选取，以下算例的说服力降序排列：网上的测试用例、文降序排列：网上的测试用例、文献中的例子、实际例子、随机产献中的例子、实际例子、随机产生的例子、自己编的例子生的例子、自己编的例子;如何检验算法的好坏：比较计算如何检验算法的好坏：比较计算速

19、度、可解规模、速度、可解规模、(从不同从不同(b tn)的随机种子出发的随机种子出发)达优率。达优率。五五五五.应用前景应用前景应用前景应用前景(qinjng)(qinjng)(qinjng)(qinjng)局限性和研究方向、注意局限性和研究方向、注意局限性和研究方向、注意局限性和研究方向、注意事项（事项（事项（事项（3 3 3 3）第23页/共312页第二十四页，共312页。25第二章第二章 伪随机数的产生伪随机数的产生(chnshng)(chnshng)第24页/共312页第二十五页，共312页。26第二章第二章 伪随机数的产生伪随机数的产生(chnshng)一一.伪随机数产生的意义伪随机

20、数产生的意义二二.产生产生U(0,1)的乘同余法的乘同余法三三.正态分布正态分布N(0,1)的产生的产生四四.逆变法与其它逆变法与其它(qt)分布随机数的产生分布随机数的产生第25页/共312页第二十六页，共312页。271.在在GA,SA,TS中都要用到；中都要用到；2.在计算机中的固有在计算机中的固有(gyu)伪随伪随机数发生器只有机数发生器只有U(0,1)且可重复且可重复性不好，没有其他分布；性不好，没有其他分布；3.自己设计的发生器，可控型好、自己设计的发生器，可控型好、可重复性好，便于仿真比较。可重复性好，便于仿真比较。一一一一.伪随机数产生伪随机数产生伪随机数产生伪随机数产生(ch

21、(ch nshng)nshng)的意义的意义的意义的意义第26页/共312页第二十七页，共312页。281.乘同余法的计算公式乘同余法的计算公式2.3.可产生随机数序列。可产生随机数序列。4.问题：怎样问题：怎样(znyng)设定设定 和和 可以使随机数序列最长？可以使随机数序列最长？二二二二.产生产生产生产生(chnshng)U(0,1)(chnshng)U(0,1)(chnshng)U(0,1)(chnshng)U(0,1)的乘同余法（的乘同余法（的乘同余法（的乘同余法（1 1 1 1）序列序列 满足以下关系式：满足以下关系式：常数常数取模取模(除以除以MM后的余数后的余数)或或取整取整

22、第27页/共312页第二十八页，共312页。29乘同余法的方法：乘同余法的方法：若若 的整数，当的整数，当 x满足以下满足以下(yxi)条件时，可以条件时，可以达到最大周期达到最大周期 (序列长度序列长度)为为3(Mod8)或或5(Mod8)的数的数；为奇数，一般取为为奇数，一般取为1。二二二二.产生产生产生产生(chnshng)U(0,1)(chnshng)U(0,1)(chnshng)U(0,1)(chnshng)U(0,1)的乘同余法的乘同余法的乘同余法的乘同余法（2 2 2 2）第28页/共312页第二十九页，共312页。30乘同余法举例说明：乘同余法举例说明：=16 =3 =1,3,

23、9,11,1,3,9,11 =5 =1,5,9,13,1,5,9,13 =3 =2,6,2,6可得整数序列可得整数序列 ，要想获得，要想获得(hud)U(0,1)，见下面，见下面二二二二.产生产生产生产生(chnshng)U(0,1)(chnshng)U(0,1)(chnshng)U(0,1)(chnshng)U(0,1)的乘同余法（的乘同余法（的乘同余法（的乘同余法（3 3 3 3）第29页/共312页第三十页，共312页。31产生产生产生产生(ch(ch nshng)U(0,1)nshng)U(0,1)步骤：步骤：步骤：步骤：；令令令令 。二二二二.产生产生产生产生(chnshng)U(0

24、,1)(chnshng)U(0,1)(chnshng)U(0,1)(chnshng)U(0,1)的乘同余法的乘同余法的乘同余法的乘同余法（4 4 4 4）第30页/共312页第三十一页，共312页。32产生产生产生产生(ch(ch nshng)U(0,1)nshng)U(0,1)举例说明：举例说明：举例说明：举例说明：=16 =16=3=3，x0=1x0=1 =1/16,3/16,9/16,11/16,1/16,3/16,9/16,11/16 =1/16,3/16,9/16,11/16,1/16,3/16,9/16,11/16=3=3，x0=2 x0=2 =2/16,6/16,2/16,6/1

25、6 =2/16,6/16,2/16,6/16 二二.产生产生(chnshng)U(0,1)(chnshng)U(0,1)的乘同余法的乘同余法（5 5）第31页/共312页第三十二页，共312页。33优秀编程举例：优秀编程举例：优秀编程举例：优秀编程举例：IF(NR(T0)NR=NR+M(MIF(NR(T0)NR=NR+M(M对应对应对应对应(duyng)(duyng)于计算机中最大整数于计算机中最大整数于计算机中最大整数于计算机中最大整数)二二.产生产生(chnshng)U(0,1)(chnshng)U(0,1)的乘同余法的乘同余法（6 6）第32页/共312页第三十三页，共312页。34三三

26、三三.正态分布正态分布正态分布正态分布N(0,1)N(0,1)N(0,1)N(0,1)的产生的产生的产生的产生(chnshng)(chnshng)(chnshng)(chnshng)（1 1 1 1）98.798.70 0n n正态分布可以用多个正态分布可以用多个正态分布可以用多个正态分布可以用多个(du(du )U(0,1)U(0,1)来近似，若来近似，若来近似，若来近似，若 n n是独立同分布，是独立同分布，是独立同分布，是独立同分布，较大，则较大，则较大，则较大，则 近近近近n n似正态分布，且满足似正态分布，且满足似正态分布，且满足似正态分布，且满足 及及及及 n n则则则则第33页/

27、共312页第三十四页，共312页。35令：令：一般一般(ybn)n取取12则：则：其中：其中：（详见下页）（详见下页）三三.正态分布正态分布N(0,1)N(0,1)的产生的产生(chnshng)(chnshng)（2 2）第34页/共312页第三十五页，共312页。36注：注：注：注：三三.正态分布正态分布N(0,1)N(0,1)的产生的产生(chnshng)(chnshng)（3 3）第35页/共312页第三十六页，共312页。371.逆变法逆变法(bin f)四四四四.逆变法与其它分布逆变法与其它分布逆变法与其它分布逆变法与其它分布(fnb)(fnb)随机数的产生随机数的产生随机数的产生随

28、机数的产生（1 1）1 10 01 1分布函数分布函数1 10 01 1密度函数密度函数=1,01,0 x1x10,0,其它其它第36页/共312页第三十七页，共312页。38 是分布函数，是分布函数，是分布函数，是分布函数，如何产生，如何产生，如何产生，如何产生(ch(ch nshng)nshng)？设设设设 ，是随机变量是随机变量是随机变量是随机变量产生产生产生产生(ch(ch nshng)nshng)，是是是是 分布函数分布函数分布函数分布函数逆变法的目的：产生逆变法的目的：产生逆变法的目的：产生逆变法的目的：产生(ch(ch nshng)nshng)分布的随机数分布的随机数分布的随机数

29、分布的随机数四四四四.逆变法与其它分布逆变法与其它分布逆变法与其它分布逆变法与其它分布(fnb)(fnb)随机数的产生随机数的产生随机数的产生随机数的产生（2 2）第37页/共312页第三十八页，共312页。39逆变法逆变法(bin f)的步骤：的步骤：已知已知 ，或由，或由 求求 即即 ，令，令推导推导产生产生用用 得到得到四四.逆变法逆变法(bin f)与其它分布随机数的与其它分布随机数的产生（产生（3）第38页/共312页第三十九页，共312页。402.负指数分布的产生负指数分布的产生3.4.5.负指数函数的密度负指数函数的密度(md)函数：函数：四四四四.逆变法与其它分布逆变法与其它分

30、布逆变法与其它分布逆变法与其它分布(fnb)(fnb)随机数的产生随机数的产生随机数的产生随机数的产生（4 4）第39页/共312页第四十页，共312页。41负指数函数负指数函数(zh sh hn sh)的分的分布函数的产生过程：布函数的产生过程：令令 产生产生则则 即即四四四四.逆变法与其它逆变法与其它逆变法与其它逆变法与其它(qt)(qt)分布随机数的产生分布随机数的产生分布随机数的产生分布随机数的产生（5 5）第40页/共312页第四十一页，共312页。42产生产生(chnshng)是负指数分布的。是负指数分布的。四四四四.逆变法与其它逆变法与其它逆变法与其它逆变法与其它(qt)(qt)

31、分布随机数的产生分布随机数的产生分布随机数的产生分布随机数的产生（6 6）第41页/共312页第四十二页，共312页。43第三章第三章 遗传算法遗传算法第42页/共312页第四十三页，共312页。44第三章第三章 遗传算法遗传算法 一一.导言导言二二.Holland.Holland的基本的基本GAGA三三.计算举例计算举例四四.Holland.Holland的结构理论的结构理论五五.GA.GA的各种的各种(zhn)(zhn)变形变形六六.应用应用七七.学习学习GAGA的几点体会的几点体会第43页/共312页第四十四页，共312页。451.1.遗传算法遗传算法遗传算法遗传算法(GA)(GA)的产

32、生的产生的产生的产生2.2.1975 1975年，年，年，年，HollandHolland提出提出提出提出GAGA3.3.著名著名著名著名(zhmng)(zhmng)的书：的书：的书：的书：4.4.Adaptation in Natural and Artificial SystemsAdaptation in Natural and Artificial Systems5.5.(中文名称：自然与人工系统的自适应性中文名称：自然与人工系统的自适应性中文名称：自然与人工系统的自适应性中文名称：自然与人工系统的自适应性)6.6.后来，后来，后来，后来，DeJongDeJong和和和和Goldber

33、gGoldberg做了大量工作，使做了大量工作，使做了大量工作，使做了大量工作，使GAGA更更更更加完善。加完善。加完善。加完善。一一一一.导言导言导言导言(doyn)(doyn)(doyn)(doyn)（1 1 1 1）第44页/共312页第四十五页，共312页。462.2.遗传算法遗传算法遗传算法遗传算法(GA)(GA)的来源：的来源：的来源：的来源：3.3.生物的进化：自然选择、适者生存生物的进化：自然选择、适者生存生物的进化：自然选择、适者生存生物的进化：自然选择、适者生存4.4.生物的遗传和变异生物的遗传和变异生物的遗传和变异生物的遗传和变异5.5.(GA)(GA)缺点：无人缺点：无

34、人缺点：无人缺点：无人(w rn)(w rn)的主动性的主动性的主动性的主动性 ；6.6.解决方法有以下三个：解决方法有以下三个：解决方法有以下三个：解决方法有以下三个：7.7.定向培育定向培育定向培育定向培育8.8.随机算法随机算法随机算法随机算法9.9.网格法网格法网格法网格法一一一一.导言导言导言导言(doyn)(doyn)(doyn)(doyn)（2 2 2 2）第45页/共312页第四十六页，共312页。47定向培育定向培育(dngxingpiy)过程如下：过程如下：第一：一个种群，大量的生物第一：一个种群，大量的生物个体；个体；第二：选择具有需要特性的若第二：选择具有需要特性的若干

35、个体；干个体；第三：进行繁殖；第三：进行繁殖；第四：重复第二，直到满意为第四：重复第二，直到满意为止。止。一一一一.导言导言导言导言(doyn)(doyn)(doyn)(doyn)（3 3 3 3）第46页/共312页第四十七页，共312页。48随机算法：在解空间随机产生多随机算法：在解空间随机产生多个个(du)解，选择最好的解，选择最好的网格法：根据最好解的几何分布，网格法：根据最好解的几何分布，来不断的缩小搜索范围。来不断的缩小搜索范围。一一一一.导言导言导言导言(doyn)(doyn)(doyn)(doyn)（4 4 4 4）第47页/共312页第四十八页，共312页。493.遗传算法的

36、基本思想遗传算法的基本思想4.根据问题的目标函数根据问题的目标函数(hnsh)构构造适值函数造适值函数(hnsh)(Fitness Function)；5.产生一个初始种群产生一个初始种群(100-1000)；6.根据适值函数根据适值函数(hnsh)的好坏，的好坏，不断选择繁殖；不断选择繁殖；7.若干代后得到适值函数若干代后得到适值函数(hnsh)最好的个体即最优解。最好的个体即最优解。一一一一.导言导言导言导言(doyn)(doyn)(doyn)(doyn)（5 5 5 5）第48页/共312页第四十九页，共312页。504.遗传算法的构成要素遗传算法的构成要素5.种群种群(zhn qn)(

37、Population),种群种群(zhn qn)大小大小(Pop-size)6.基因表达法基因表达法编码方法编码方法7.(Encoding Scheme;Gene Representation)一一一一.导言导言导言导言(doyn)(doyn)(doyn)(doyn)（6 6 6 6）第49页/共312页第五十页，共312页。51遗传算子遗传算子(Genetic Operator)：交叉交叉(Crossover)，变异，变异(Mutation)选择策略选择策略:一般为正比选择一般为正比选择停止准则停止准则(zhnz)(Stopping Rule/Criterion):一般是指定最大代数一般是指

38、定最大代数一一一一.导言导言导言导言(doyn)(doyn)(doyn)(doyn)（7 7 7 7）第50页/共312页第五十一页，共312页。521.算法算法(sun f)框架与步骤框架与步骤2.见下页见下页3.二二二二.Holland.Holland.Holland.Holland的基本的基本的基本的基本(jbn)GA(jbn)GA(jbn)GA(jbn)GA（1 1 1 1）第51页/共312页第五十二页，共312页。53二二二二.Holland.Holland.Holland.Holland的基本的基本的基本的基本(jbn)GA(jbn)GA(jbn)GA(jbn)GA（2 2 2

39、2）产生初始种群产生初始种群开始开始判断停止条件判断停止条件输出输出计算适值函数计算适值函数选择选择遗传运算遗传运算更新种群更新种群停止停止Y YN N评估评估(在解空间做在解空间做)向改进方向移动向改进方向移动(在编码空间做在编码空间做)第52页/共312页第五十三页，共312页。542.解空间与编码空间的转换解空间与编码空间的转换3.遗传运算遗传运算(yn sun)是对编码是对编码空间操作的，所以要进行空间操作的，所以要进行4.两个空间的转换。两个空间的转换。5.见下页示意图见下页示意图6.二二二二.Holland.Holland.Holland.Holland的基本的基本的基本的基本(j

40、bn)GA(jbn)GA(jbn)GA(jbn)GA（3 3 3 3）第53页/共312页第五十四页，共312页。55二二.Holland.Holland的基本的基本(jbn)GA(jbn)GA（4 4）解解空空间间编码编码编码空间编码空间011001100011001100011110011011110011遗传运算遗传运算后代后代011000000011000000011110001011110001解空间解空间选择选择解解码码计算适值，评估计算适值，评估适值适值第54页/共312页第五十五页，共312页。563.3.各个各个(gg)步骤的实现步骤的实现4.4.初始种群的产生初始种群的产生

41、5.5.编码方法编码方法6.6.适值函数适值函数7.7.遗传运算遗传运算8.8.选择策略选择策略9.9.停止准则停止准则二二二二.Holland.Holland.Holland.Holland的基本的基本的基本的基本(jbn)GA(jbn)GA(jbn)GA(jbn)GA（5 5 5 5）第55页/共312页第五十六页，共312页。57初始初始(ch sh)种群的产生种群的产生随机产生随机产生(依赖于编码方法依赖于编码方法)；种群的大小种群的大小(依赖于计算机的计依赖于计算机的计算能力和计算复杂度算能力和计算复杂度)。例：例：0,1编码编码 产生产生 ，0.5，=1；0.5，=0二二二二.Ho

42、lland.Holland.Holland.Holland的基本的基本的基本的基本(jbn)GA(jbn)GA(jbn)GA(jbn)GA（6 6 6 6）第56页/共312页第五十七页，共312页。58编码编码(bin m)方法方法二进制二进制编码编码(bin m)二进制编码二进制编码(bin m)，用，用0，1字符串表达。字符串表达。例：例：0110010，适用以下三种情，适用以下三种情况况背包问题：背包问题：1，背；，背；0，不背，不背二二.Holland.Holland的基本的基本(jbn)GA(jbn)GA（7 7）第57页/共312页第五十八页，共312页。59II.II.实优化：

43、实优化：III.III.精度高时编码长，一般不采精度高时编码长，一般不采用此法而用实值函数。用此法而用实值函数。IV.IV.指派问题指派问题V.V.二进制编码缺点：编码长不利二进制编码缺点：编码长不利于计算；于计算；VI.VI.二进制编码优点：便于位值计二进制编码优点：便于位值计算，包括算，包括(boku)的实数范围的实数范围大大 二二.Holland.Holland的基本的基本(jbn)GA(jbn)GA（8 8）第58页/共312页第五十九页，共312页。60适值函数适值函数根据目标根据目标(mbio)函数设计函数设计用适值函数用适值函数 标定标定(Scaling)目标目标(mbio)函数

44、函数采用方法采用方法 或或 。遗传运算遗传运算(遗传算法的精髓遗传算法的精髓)交叉和变异交叉和变异下面我们就介绍一下交叉和变下面我们就介绍一下交叉和变异异二二二二.Holland.Holland.Holland.Holland的基本的基本的基本的基本(jbn)GA(jbn)GA(jbn)GA(jbn)GA（9 9 9 9）第59页/共312页第六十页，共312页。61I.交叉交叉(Crossover)II.单切点交叉单切点交叉III.随机产生随机产生(chnshng)一个断点一个断点(Cutting Point)1，n-1IV.例：例：V.二二.Holland.Holland的基本的基本(jb

45、n)GA(jbn)GA（1010）011 011 0011 0011101 101 01100110011 011 0110 0110101 101 00110011单切点交叉单切点交叉第60页/共312页第六十一页，共312页。62b.b.双切点交叉双切点交叉(交换交换(jiohun)中中间段间段)c.c.例：例：d.d.不是所有点都交叉，设定一个交不是所有点都交叉，设定一个交叉概率叉概率 ，一，一e.e.般为般为0.9二二.Holland.Holland的基本的基本(jbn)GA(jbn)GA（11 11）011 011 00 00 1111101 101 01 1001 10011 01

46、1 01 01 1111101 101 00 00 1010双切点交叉双切点交叉第61页/共312页第六十二页，共312页。63II.II.变异变异(biny)(Mutation)III.III.初始种群中没有需要的基因，初始种群中没有需要的基因，在种群中按变异在种群中按变异(biny)IV.IV.概率概率 任选若干位基因改变位任选若干位基因改变位值值01或或10，V.V.有意想不到的结果，有意想不到的结果，一般设一般设定得比较小，在定得比较小，在VI.VI.5%以下。以下。二二二二.Holland.Holland.Holland.Holland的基本的基本的基本的基本(jbn)GA(jbn)

47、GA(jbn)GA(jbn)GA（12121212）第62页/共312页第六十三页，共312页。64选择策略选择策略最常用的正比最常用的正比(zhngb)选择选择(Proportional Selection)对于个体对于个体 ，适值，适值 ，选择概率，选择概率如下式可计算如下式可计算NPNumber of Population二二二二.Holland.Holland.Holland.Holland的基本的基本的基本的基本(jbn)GA(jbn)GA(jbn)GA(jbn)GA（13131313）第63页/共312页第六十四页，共312页。65得到选择得到选择(xunz)概率后，我们采概率后，

48、我们采用旋轮法用旋轮法(Roulette Wheel)令令 ，随机产生随机产生 当当 ，选择，选择(xunz)个个体体二二二二.Holland.Holland.Holland.Holland的基本的基本的基本的基本(jbn)GA(jbn)GA(jbn)GA(jbn)GA（14141414）转轮转轮NPNP次次NP*NP*次做交叉次做交叉；NP*NP*次做变异；次做变异；NP*(1-)NP*(1-)不变不变第64页/共312页第六十五页，共312页。66如下图所示如下图所示:注：注：优良种得到较多的繁殖机会，优良种得到较多的繁殖机会，后代很后代很像像 ；而很可能而很可能(knng)失去失去繁殖的

49、机会。繁殖的机会。二二二二.Holland.Holland.Holland.Holland的基本的基本的基本的基本(jbn)GA(jbn)GA(jbn)GA(jbn)GA（15151515）第65页/共312页第六十六页，共312页。67停止停止(tngzh)准则准则指定最大代数指定最大代数(NGNumber of Max Generation)很少用很少用，麻烦，麻烦二二二二.Holland.Holland.Holland.Holland的基本的基本的基本的基本(jbn)GA(jbn)GA(jbn)GA(jbn)GA（16161616）第66页/共312页第六十七页，共312页。68例例1：

50、，NP=5简单简单(jindn)分析：分析：编码为五位的编码为五位的0，1编码，推导如下编码，推导如下设编码长度设编码长度L，取决于，取决于 ，即，即编码精度编码精度若要求编码精度为若要求编码精度为1，则由，则由C=5三三三三.计算计算计算计算(j sun)(j sun)(j sun)(j sun)举例（举例（举例（举例（1 1 1 1）第67页/共312页第六十八页，共312页。69 ，最大值，最大值，最大值，最大值 ，最小值，最小值，最小值，最小值三三三三.计算计算计算计算(j sun)(j sun)(j sun)(j sun)举例（举例（举例（举例（2 2 2 2）10010010103