当前位置:文档之家› 计算智能-遗传算法模板

计算智能-遗传算法模板


§1. 概述
总结:
计算智能是一种智力方式的低层认知,它与人工智能的区 别只是认知层次从中层下降到低层而已。中层系统含有知识(精 品),低层系统则没有。 若一个系统只涉及数值(低层)数据,含有模式识别部分,不 应用人工智能意义上的知识,而且能够呈现出:①计算适应性; ②计算容错性;③接近人的速度;④误差率与人相近,则该系 统就是计算智能系统。 若一个智能计算系统以非数值方式加上知识(精品)值,即成 为人工智能系统。
图灵测试
上述两种对话的区别在于,第一种可明显地感到回答者是从知 识库里提取简单的答案,第二种则具有分析综合的能力,回答 者知道观察者在反复提出同样的问题。
§2. 遗传算法
遗传算法是源于达尔文生物进化理论的“自然选择 ”、“适者生存”法则而提出的一种搜索寻优算法。基 本思想:将每个可能的问题解表示成“染色体”,从而 得到一个由染色体组成的“群体”,这个群体被限制在 问题特定的环境里,根据预定的目标函数对每个个体进 行评价,给出了一个合适度值。开始时总是随即地产生 一些个体,即侯选解,利用遗传算法对这些个体按”适 者”有更多的机会生存的原则进行交叉组合产生后代, 后代由于继承了父代的一些优良性状,因而明显优于上 一代,这样“染色体”的群体将逐步朝着更优解的方向 进化。
计算智能
计算智能涉及神经计算、模糊计算、进化计算和人 工生命等领域,这些研究领域体现出生命科学与信息 科学的紧密结合,也是广义人工智能力图研究和摹仿 人类和动物智能(主要是人类的思维过程和智力行为) 的重要进展。
把计算智能理解为智力的低层认知,它主要取决于 数值数据而不依赖于知识。人工智能是在计算智能的 基础上引入知识而产生的智力中层任知。生物智能, 尤其是人类智能,则是最高层的智能。即CIAIBI。
000……00=0 000……01=1 ∶ ∶ ∶∶ 111……11=2l-1 → B B – A l x=A + ———— .∑xi.2i-1 2l – 1 i=1 → A → A + 其中Bຫໍສະໝຸດ - A = ———— 2l - 1
假设某一个体的编码是:X:xlxl-1xl-2…x2x1 则二进制编码所对应的解码公式为 缺点:长度较大
§2.2 遗传算法的求解步骤
例 , x 属 于 [0,1023] 用 长 度 为 10 的 二 进 制 进 行 编 码 , 则 x=0010101111,表示一个个体,对应175,编码精度为1.
3.常用的编码方法: ⑵.浮点数编码 个体的每个染色体用某一范围内的一个浮点数来表示,个 体的编码长度等于其变量的个数。
⑶.格雷码
连续的两个整数所对应的编码值之间只有一个码位是不相
2.交叉
是GA中最主要的遗传操作,其工作于选择过程结束后产生的下一代群体。 交叉操作应用于从这一群体中随机选择的一系列个体对(串对)。 SGA采用的是单点交换。设串长为L,交换操作将随机选择一个交换点 (对应于从1到L-1的某个位置序号),紧接着两串交换点右边的子串互换,从 而产生了两个新串。例如,设A1,A2为要交换的串,交换点被随机选择为7 (串长为10)。 A1=1000011111 A2=1111111011 交换得新串A1',A2': A1'=1000011011 A2'=1111111111 当然,并非所有选中的串对都会发生交换。这些串对发生交换的概率是Pc。 Pc为事先指定的0-1之间的值,称为交换率。
§2.2 遗传算法的求解步骤
一.遗传算法的特点
遗传算法是一种基于空间搜索的算法,它通过自然选择、遗 传、变异等操作以及达尔文适者生存的理论,模拟自然进化过程 来寻找所求问题的解答。遗传算法具有以下特点:
1. 遗传算法是对参数集合的编码而非针对参数本身进行进化;
2. 遗传算法是从问题解的编码组开始而非从单个解开始搜索; 3. 遗传算法利用目标函数的适应度这一信息而非利用导数或其 它辅助信息来指导搜索; 4. 遗传算法利用选择、交叉、变异等算子而不是利用确定性规
§2. 遗传算法
遗传算法的基本过程: begin 1. 选择适当表示,生成初始群体; 2. 评估群体; 3. While 未达到要求的目标 do begin 1. 选择作为下一代群体的各个体; 2. 执行交换和突变操作; 3. 评估群体; end end
§2. 遗传算法
对于一个SGA算法来说主要涉及以下内容: · 编码和初始群体生成; · 群体的评价; · 个体的选择; · 交换; · 突变;
图灵测试
图灵测试一词来源于计算机科学和密码学的先驱阿 兰· 麦席森· 图灵:1950年设计出这个测试,其内容是, 如果电脑能在5分钟内回答由人类测试者提出的一系 列问题,且其超过30%的回答让测试者误认为是人类 所答,则电脑通过测试。 2014 年 6 月 7 日 是 计 算 机 科 学 之 父 阿 兰 · 图 灵 ( Alan Turing )逝世 60 周年纪念日。这一天,在英国皇家学 会举行的“ 2014 图灵测试”大会上,聊天程序“尤 金· 古斯特曼”( Eugene Goostman )首次“通过”了 图灵测试。
例如:10100110 对从右往左的第5位进行变异操作 10110110
四.控制参数
1.交叉概率和变异概率
并不是所有被选择了的染色体都要进行交叉操作和变异操作,而是以一定
的概率进行,一般在程序设计中交叉发生的概率要比变异发生的概率选取得大
若干个数量级,交叉概率取0.6至0.95之间的值;变异概率取0.001至0.01之间的 值。
则进行随机操作。
§2.2 遗传算法的求解步骤
最主要的特点体现在下述两个方面:
.智能性
进化算法的智能性包括自组织、自适应和自学习等。应用进化算法求 解问题时,在确定了编码方案、适应值函数和遗传算子以后,算法将利用进 化过程中获得的信息自行组织搜索。进化算法的这种智能性特征同时赋予 了它具有根据环境的变化自动发现环境的特性和规律的能力。 .本质并行性 进化算法的本质并行性表现在两个方面:一是进化算法是内在并行的, 即进化算法本身非常适合大规模并性。二是进化算法的内含并行性,由于 进化算法采用种群的方式组织搜索,因而它可以搜索解空间内的多个区域, 并相互交流信息。
计算智能
§1. 概述 §2. 遗传算法 §3. 粒子群算法 §4. 神经网络
§1. 概述
什么是计算智能,它与传统的人工智能的区别?
第一个对计算智能的定义是由贝兹德克(Bezdek)于 1992年提出的。他认为,从严格意义上讲,计算智能 取决于制造者提供的数值数据,而不依赖于知识;另 一方面,人工智能则应用知识精品。
同的,其余码位都完全相同。
(4).符号编码 用无实际意义的符号进行编码,如{A,B,C,D},或{1,2, 3,4,5,6}
二.适应度函数 为了体现染色体的适应能力而引入的对问题中的每一个染色体 都能进行度量的函数。通过适应度函数来决定染色体的优、劣程 度,它体现了自然进化中的优利劣汰原则。
例如:
2.种群规模
指种群的染色体总数,它对算法的效率有明显的影响,规模太小不得于 进化,而规模太大将导致程序运行时间长。对不同的问题可能有各自适合的种 群规模,通常种群规模为30至100。
3.个体长度
有定长和变长两种。它对算法的性能也有影响。
举例:
来说明遗传算法的一个进化循环。设每一串的长度为10,共有4个串组成第一 代群体(POP1),目标函数(适应函数)为各位值之和
3.变异 一般在交换后进行。突变操作的对象是个体(即串),旨在改 变串中的某些位的值,即由0变为1,或由1变为0。并非所有位都 能发生变化,每一位发生变化的概率是Pm。Pm为事先指定的0- 1之间的某个值,称为变异率。串中每一位的突变是独立的,即某 一位是否发生突变并不影响其它位的变化。变异的作用是引进新 的遗传物质或恢复已失去的遗传物质。例如,若群体的各串中每 一位的值均为0,此时无论如何交换都不能产生有1的位,只有通 过突变。
三.遗传操作
简单遗传算法的遗传操作主要有三种:选择(selection)、交叉(crossover)、变 异(mutation)。改进的遗传算法大量扩充了遗传操作,以达到更高的效率。
1.选择操作
也叫复制操作,对自然界“适者生存”的模拟。根据个体的适应度函数值所度 量的优、劣程度决定它在下一代是被淘汰还是被遗传。 一般地说,选择将使适应度较大(优良)个体有较大的存在机会,而适应度较 小(低劣)的个体继续存在的机会也较小。简单遗传算法采用赌轮选择机制, 令Σfi表示群体的适应度值之总和,fi表示种群中第i个染色体的适应度值,它产 生后代的能力正好为其适应度值所占份额fi/Σfi。
实例1:3-PRR并联定位平台的运动学标定
工作空间:±50mm,±10°
PRO/E中的机械设计图
3-PRR并联平台实物样机
实例1:3-PRR并联定位平台运动学模型
由并联平台矢量约束关系
lOP lPCi lOAi l Ai Bi lBiCi
可得到动平台在工作空间内任 意位姿下,三个直线超声电机 的运动学逆解
对优化问题,适应度函数就是目标函数。
TSP的目标是路径总长度为最短,路径总长度的倒数就可以为TSP的适应度函 数:
适应度函数要有效反映每一个染色体与问题的最优解染色体之
间的差距,一个染色体与问题的最优解染色体之间的差距小,则对
应的适应度函数值之差就小,否则就大。遗传算法中的适应度函数 以越大越接近最优解为准,这与他轮盘概率选择下一代相关。
实例1:3-PRR并联定位平台运动学标定
令上式等号左边为Ei,i=1,2,3
选取N组位形,求得相应电机输出,驱动电机 到理论位置测得实际平台位形,基于粒子群算 法求得使J小于一定误差时的
实例1:3-PRR并联定位平台运动学标定
1. Zhang Q, Mills J K, Cleghorn W L, et al. Dynamic model and input shaping control of a flexible link parallel manipulator considering the exact boundary conditions[J]. Robotica, 2015, 33(06): 1201-1230. 2.周丽平, 张泉, 孙志峻. 直线超声电机驱动的平面 3-PRR 并联平台的运动学标定 [J]. 机器人 , 2014, 36(4): 485490.
相关主题