遗传算法-机器人与智能技术室-课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《遗传算法-机器人与智能技术室-课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遗传 算法 机器人 智能 技术室 课件
- 资源描述:
-
1、1/87目录o 第一章第一章绪论绪论o 第二章搜索技术第二章搜索技术o 第三章第三章知识表示知识表示o 第四章推理技术第四章推理技术 o 第五章第五章 机器学习机器学习o 第六章计算智能第六章计算智能 o 第七章数据挖掘第七章数据挖掘o 第八章第八章 智能体技术智能体技术2/87o 可求解与难求解问题o 遗传算法遗传算法o 群智能算法群智能算法3/87现实世界中的问题分类6.1 可求解与难求解问题可求解与难求解问题 计算机在有限时间内能够求解的计算机在有限时间内能够求解的(可求解问题可求解问题)计算机在有限时间内不能求解的计算机在有限时间内不能求解的(难求解问题难求解问题)计算机完全不能求解的
2、计算机完全不能求解的(不可计算问题不可计算问题)计算复杂性是指问题的一种特性,即利用计算机求解问题的计算复杂性是指问题的一种特性,即利用计算机求解问题的难易性或难易程度,其衡量标准:难易性或难易程度,其衡量标准:计算所需的步数或指令条数计算所需的步数或指令条数(即时间复杂度即时间复杂度)计算所需的存储空间大小计算所需的存储空间大小(即空间复杂度即空间复杂度)-通常表达为关于问题规模通常表达为关于问题规模n的一个函数的一个函数 O(f(n)问题的计算复杂性问题的计算复杂性4/87问题规模n计算量10 10!20 20!100 100!1000 1000!10000 10000!20!=1.216
3、1017203 =8000O(n3)O(3n)0.2秒秒4 1028秒秒=1015年年注:每秒百万次,注:每秒百万次,n=60,1015年相当于年相当于10亿亿台计算机计算一百万年台计算机计算一百万年O(n3)与与O(3n)的差别的差别 O(n!)与与O(n3)的差别的差别O(bn),O(n!)O(1),O(log n),O(n),O(n log n),O(nb)6.1 可求解与难求解问题可求解与难求解问题5/87P类问题,类问题,NP类问题,类问题,NPC类问题类问题nP类问题类问题:多项式问题多项式问题(Polynomial Problem),指计算机可以在有限时,指计算机可以在有限时间内
4、求解的问题,即:间内求解的问题,即:P类问题是可以找出一个呈现类问题是可以找出一个呈现O(na)复杂性算法的问复杂性算法的问题,其中题,其中a为常数。为常数。nNP类问题类问题:非确定性多项式问题:非确定性多项式问题(Non-deterministic Polynomial)。有些。有些问题,其答案是无法直接计算得到的,只能通过间接的猜算或试算来得到问题,其答案是无法直接计算得到的,只能通过间接的猜算或试算来得到结果,这就是非确定性问题结果,这就是非确定性问题(Non-deterministic)。虽然在多项式时间内难于。虽然在多项式时间内难于求解但不难判断给定一个解的正确性的问题,即:在多项
5、式时间内可以由求解但不难判断给定一个解的正确性的问题,即:在多项式时间内可以由一个算法验证一个解是否正确的非确定性问题,就是一个算法验证一个解是否正确的非确定性问题,就是NP类问题。类问题。nNPC问题问题:完全非确定性多项式问题:完全非确定性多项式问题(NP-Complete)。如果。如果NP问题的所问题的所有可能答案都可以在多项式时间内进行正确与否的验算的话就叫做完全非有可能答案都可以在多项式时间内进行正确与否的验算的话就叫做完全非确定性多项式问题,即确定性多项式问题,即NP-Complete问题。问题。6.1 可求解与难求解问题可求解与难求解问题6/876.1 可求解与难求解问题可求解与
6、难求解问题旅行商问题旅行商问题 对于销售员旅行问题(对于销售员旅行问题(Travelling Salesman Problem,TSP),),设有设有n个城市,城市个城市,城市I和城市和城市j之间的距离之间的距离为为d(i,j),要求找到,要求找到一条遍访每个城市一一条遍访每个城市一次而且恰好一次的次而且恰好一次的旅行线路,使其路径旅行线路,使其路径总长度为最短。总长度为最短。7/87NPC类问题求解类问题求解穷举法或称遍历法穷举法或称遍历法:对解空间中的:对解空间中的每一个可能解进行验证,直到所有每一个可能解进行验证,直到所有的解都被验证是否正确,便能得到的解都被验证是否正确,便能得到精确的
7、结果精确的结果-精确解精确解可能是可能是O(n!)或或O(an)近似解求解算法近似解求解算法-近似解近似解应该是应该是O(na)=|近似解近似解 精确解精确解|满意解:满意解:充分小时的近似解充分小时的近似解TSP问题的问题的遍历算法遍历算法TSP问题的问题的贪心算法贪心算法仿生学算法仿生学算法进化算法,遗传算法,蚁群算法,蜂群算法进化算法,遗传算法,蚁群算法,蜂群算法,6.1 可求解与难求解问题可求解与难求解问题8/87 6.2 遗传算法 生物群体的生存过程普遍遵循达尔文的物竞天择、适者生生物群体的生存过程普遍遵循达尔文的物竞天择、适者生存的进化准则;生物通过个体间的选择、交叉、变异来适应大
8、存的进化准则;生物通过个体间的选择、交叉、变异来适应大自然环境。自然环境。9/87 6.2 遗传算法 生物染色体用数学方式或计算机方式来体现就是一串数码生物染色体用数学方式或计算机方式来体现就是一串数码,仍叫染色体,有时也叫个体;适应能力用对应一个染色体的,仍叫染色体,有时也叫个体;适应能力用对应一个染色体的数值来衡量;染色体的选择或淘汰问题是按求最大还是最小问数值来衡量;染色体的选择或淘汰问题是按求最大还是最小问题来进行。题来进行。遗传算法遗传算法(Genetic AlgorichmsGAGenetic AlgorichmsGA)是模仿生物遗传学和自是模仿生物遗传学和自然选择机理,通过人工方
9、式构造的一类优化搜索算法,是对生然选择机理,通过人工方式构造的一类优化搜索算法,是对生物进化过程进行的一种数学仿真,是进化计算的一种最重要形物进化过程进行的一种数学仿真,是进化计算的一种最重要形式。式。10/876.2 遗传算法 遗传算法提出:遗传算法提出:于于2020世纪世纪6060年代由密歇根年代由密歇根(Michigan)(Michigan)大学大学Hollstien,BagleyhHollstien,Bagleyh和和RosenbergRosenberg等人在其博士论文中首先加以等人在其博士论文中首先加以研究;研究;19751975年,美国年,美国J.H.HollandJ.H.Holl
10、and教授在其著作教授在其著作“Adaptation Adaptation in Natural and Artificial Systemsin Natural and Artificial Systems”中系统地阐述了遗传算中系统地阐述了遗传算法,给出了遗传算法的基本定理和大量的数学理论证明。法,给出了遗传算法的基本定理和大量的数学理论证明。遗传算法发展:遗传算法发展:David E.GoldbergDavid E.Goldberg教授教授19891989年出版了年出版了 “Genetic AlgorichmsGenetic Algorichms”一书,这一著作通常被认为是遗传算法一书,
11、这一著作通常被认为是遗传算法的方法、理论及应用的全面系统的总结。从的方法、理论及应用的全面系统的总结。从19851985年起,国际上年起,国际上开始陆续举行遗传算法的国际会议,后来又更名为进化计算。开始陆续举行遗传算法的国际会议,后来又更名为进化计算。参加进化计算国际会议的人数及收录文章的数量、广度和深度参加进化计算国际会议的人数及收录文章的数量、广度和深度逐年扩大。从此,进化计算逐渐成为人们用来解决高度复杂问逐年扩大。从此,进化计算逐渐成为人们用来解决高度复杂问题的新思路和新方法。题的新思路和新方法。11/876.2 遗传算法 遗传算法特点:遗传算法特点:遗传算法是一种基于空间搜索的算法,它
12、通过遗传算法是一种基于空间搜索的算法,它通过自然选择、遗传、变异等操作以及达尔文适者生存的理论,模拟自自然选择、遗传、变异等操作以及达尔文适者生存的理论,模拟自然进化过程来寻找所求问题的解答。遗传算法具有以下特点:然进化过程来寻找所求问题的解答。遗传算法具有以下特点:(1)遗传算法是对参数集合的编码而非针对参数本身进行进化;遗传算法是对参数集合的编码而非针对参数本身进行进化;(2)遗传算法是从问题解的编码组开始而非从单个解开始搜索;遗传算法是从问题解的编码组开始而非从单个解开始搜索;(3)遗传算法利用目标函数的适应度这一信息而非利用导数或其遗传算法利用目标函数的适应度这一信息而非利用导数或其它
13、辅助信息来指导搜索;它辅助信息来指导搜索;(4)遗传算法利用选择、交叉、变异等算子而不是利用确定性规遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。则进行随机操作。12/876.2 遗传算法6.2.1 6.2.1 遗传算法的基本原理遗传算法的基本原理 霍兰德提出的遗传算法通常称为简单遗传算法(霍兰德提出的遗传算法通常称为简单遗传算法(SGA)。)。编码与解码编码与解码 许多应用问题的结构很复杂,但可以化为简单的位串形许多应用问题的结构很复杂,但可以化为简单的位串形式编码表示。将问题结构变换为位串形式编码表示的过程叫编式编码表示。将问题结构变换为位串形式编码表示的过程叫编码;
14、而相反将位串形式编码表示变换为原问题结构的过程叫解码;而相反将位串形式编码表示变换为原问题结构的过程叫解码或译码。把位串形式编码表示叫染色体,有时也叫个体。码或译码。把位串形式编码表示叫染色体,有时也叫个体。13/876.2 遗传算法对于对于TSP问题,可以按一条回路中城市的次序进行编码。问题,可以按一条回路中城市的次序进行编码。从城市从城市w1开始,依次经过城市开始,依次经过城市w2,wn,最后回到城市,最后回到城市w1,我们就有如下编码表示:,我们就有如下编码表示:w1 w2 wn由于是回路,记由于是回路,记wn+1=w1。它其实是。它其实是1,n的一个循环的一个循环排列。要注意排列。要注
15、意w1,w2,wn是互不相同的。是互不相同的。14/876.2 遗传算法适应度函数适应度函数 为了体现染色体的适应能力,引入了对问题中的每一个染为了体现染色体的适应能力,引入了对问题中的每一个染色体都能进行度量的函数,叫适应度函数(色体都能进行度量的函数,叫适应度函数(fitness function)。)。TSP的目标是路径总长度为最短,自然地,路径总长度的倒数的目标是路径总长度为最短,自然地,路径总长度的倒数就可作为就可作为TSP问题的适应度函数问题的适应度函数:其中其中wn+1=w1适应度函数要有效反映每一个染色体与问题的最优解染色适应度函数要有效反映每一个染色体与问题的最优解染色体之间
16、的差距。适应度函数的取值大小与求解问题对象的意义体之间的差距。适应度函数的取值大小与求解问题对象的意义有很大的关系。有很大的关系。n1j1jj21)w,d(w/1),.,(nwwwf15/876.2 遗传算法遗传操作遗传操作简单遗传算法的遗传操作主要有有三种简单遗传算法的遗传操作主要有有三种:选择选择(selection)、交叉、交叉(crossover)、变异、变异(mutation)。改进的遗传算法大量扩充了遗传操。改进的遗传算法大量扩充了遗传操作,以达到更高的效率。作,以达到更高的效率。选择操作也叫复制(选择操作也叫复制(reproduction)操作,根据个体的适应度)操作,根据个体的
17、适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。简单遗传算法采用赌轮选择机制,令简单遗传算法采用赌轮选择机制,令fi表示群体的适应度值之表示群体的适应度值之总和,总和,fi表示种群中第表示种群中第i个染色体的适应度值,它产生后代的能力个染色体的适应度值,它产生后代的能力正好为其适应度值所占份额正好为其适应度值所占份额fi/fi。16/876.2 遗传算法交叉操作的简单方式是将被选择出的两个个体交叉操作的简单方式是将被选择出的两个个体P1和和P2作为父母作为父母个体,将两者的部分码值进行交换。个体,将两者的部分码值进行交换。产
18、生一个产生一个17之间的随机数之间的随机数c,假设为,假设为3,则将,则将P1和和P2的低的低3位交换位交换1 0 0 0 1 1 1 0P1:1 1 0 1 1 0 0 1P2:1 0 0 0 1 1 1 0P1:1 1 0 1 1 0 0 1P2:1 0 0 0 1 0 0 11 1 0 1 1 1 1 0Q1:Q2:17/876.2 遗传算法变异操作的简单方式是改变数码串的某个位置上的数码。变异操作的简单方式是改变数码串的某个位置上的数码。二进制编码表示的简单变异操作是将二进制编码表示的简单变异操作是将0与与1互换:互换:0变异为变异为1,1变变异为异为0。随机产生一个随机产生一个18之
19、间的数之间的数k,假设,假设k=5,对从右往左第,对从右往左第5位变异位变异操作。操作。10100110118/876.2 遗传算法控制参数控制参数交叉发生的概率:交叉发生的概率:0.60.95 变异的概率:变异的概率:0.0010.01 种群的个数:种群的个数:30100 个体的长度:定长和变长个体的长度:定长和变长 19/876.2 遗传算法6.2.2 6.2.2 遗传算法的结构遗传算法的结构选择:由个体适应度值决定选择:由个体适应度值决定 的某个规则。的某个规则。交叉:按概率交叉:按概率Pc进行进行变异:按概率变异:按概率Pm进行进行终止条件:终止条件:完成了预先给定的进化代数完成了预先
20、给定的进化代数 种群中的最优个体在连续若干代种群中的最优个体在连续若干代 没有改进或平均适应度在连续若没有改进或平均适应度在连续若 干代基本没有改进干代基本没有改进开始开始初始化种群初始化种群选择操作选择操作终止条件终止条件否否适应度最有优个体适应度最有优个体计算适应度值计算适应度值交叉操作交叉操作变异操作变异操作结束结束20/876.2 遗传算法6.2.3 6.2.3 遗传算法的性能遗传算法的性能 遗传算法求得的解是一满意解。影响解质量的因素:遗传算法求得的解是一满意解。影响解质量的因素:种群的数量:太小缺少多样性,太多影响效率种群的数量:太小缺少多样性,太多影响效率 适应度函数:提升优良个
21、体的适应度适应度函数:提升优良个体的适应度 交叉和变异:不同的问题需构造性能更优的交叉和变异操作交叉和变异:不同的问题需构造性能更优的交叉和变异操作 交叉概率和变异概率:交叉概率和变异概率:21/87分析:对该问题虽然也可以采用枚举的方法来解决分析:对该问题虽然也可以采用枚举的方法来解决,但枚举法却但枚举法却是一种效率很低的方法是一种效率很低的方法.可运用遗传算法来求解该问题可运用遗传算法来求解该问题.解:首先对问题进行初始化,以获得初始种群解:首先对问题进行初始化,以获得初始种群;(1 1)确定编码方案:将确定编码方案:将x x编码表示为染色体的数字符号串。编码表示为染色体的数字符号串。针对
22、本题自变量针对本题自变量x x定义域定义域,取值范围为取值范围为00,31,31,考虑采用二进考虑采用二进制数来对其编码制数来对其编码,由由2 25 5=32,=32,故使用故使用5 5位无符号二进制数组成位无符号二进制数组成染色体数字字符串染色体数字字符串,用以表达变量用以表达变量x x及问题的解答过程。及问题的解答过程。例例:设有函数设有函数f(xf(x)=)=x x2 2,用遗传算法求其自变量用遗传算法求其自变量x x在区间在区间00,31 31 取整数值时的最大值。取整数值时的最大值。6.2 遗传算法22/87 (2 2)选择初始种群)选择初始种群:通过随机的方法来产生染色体的数通过随
23、机的方法来产生染色体的数字串,并组成初始种群。例如,为得到数字串的某位字串,并组成初始种群。例如,为得到数字串的某位又称之为基因又称之为基因(genes)(genes),使用计算机在,使用计算机在0 01 1之间产生之间产生随机数随机数K K,并按照数,并按照数K K的变化区域来规定基因代码如下:的变化区域来规定基因代码如下:0 0,(0 0K K0.50.5)1 1,(0.50.5K K1 1)6.2 遗传算法23/87于是于是随机生成随机生成4 4个个染色体的数字符串为:染色体的数字符串为:0110101101110001100001000010001001110011从而构造了初始种群,
24、完成了遗传算法的准备。从而构造了初始种群,完成了遗传算法的准备。6.2 遗传算法24/876.2 遗传算法染色体染色体标号标号 串串 x 适应值适应值f(x)=x2占整体的百分占整体的百分数数 1 1 0110101101 169169 14.4%14.4%2 2 1100011000 576576 49.2%49.2%3 3 0100001000 6464 5.5%5.5%4 4 1001110011 361361 30.9%30.9%总计总计(初始种群值)(初始种群值)11701170 100.0%100.0%25/87(3 3)复制)复制(选择选择)选择适应值大的串作为母本,使在下一代中
25、有更多的机会繁殖选择适应值大的串作为母本,使在下一代中有更多的机会繁殖其子孙。其子孙。要在四个种子个体中做选择,要求仍然得到四个染色体,可依要在四个种子个体中做选择,要求仍然得到四个染色体,可依据适应度概率比例制定如下规则:据适应度概率比例制定如下规则:低于低于0.1250.125以下的染色体被淘汰;以下的染色体被淘汰;在在0.1250.1250.3750.375之间的染色体被复制一个;之间的染色体被复制一个;在在0.3750.3750.6250.625之间的染色体被复制两个;之间的染色体被复制两个;在在0.6250.6250.8750.875之间的染色体被复制三个;之间的染色体被复制三个;在
展开阅读全文