现代优化计算简介课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《现代优化计算简介课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 现代 优化 计算 简介 课件
- 资源描述:
-
1、第第 1313章章 智能优化计算简介智能优化计算简介 第第13章章 智能优化计算简介智能优化计算简介 本章对目前常用的几种智能优化计算算法作简单介绍,以使读者对它们有个基本认识。内容包括神经网络、遗传算法、模拟退火算法和神经网络混合优化学习策略。13.1人工神经网络与神经网络优化算法 l人工神经网络是近年来得到迅速发展的一个前沿课题。神经网络由于其大规模并行处理、容错性、自组织和自适应能力和联想功能强等特点,已成为解决很多问题的有力工具。本节首先对神经网络作简单介绍,然后介绍几种常用的神经网络,包括前向神经网络、Hopfield网络。13.1人工神经网络与神经网络优化算法 1.人工神经网络发展
2、简史l最早的研究可以追溯到20世纪40年代。1943年,心理学家McCulloch和数学家Pitts合作提出了形式神经元的数学模型。这一模型一般被简称为M-P神经网络模型,至今仍在应用,可以说,人工神经网络的研究时代,就由此开始了。l1949年,心理学家Hebb提出神经系统的学习规则,为神经网络的学习算法奠定了基础。现在,这个规则被称为Hebb规则,许多人工神经网络的学习还遵循这一规则。13.1人工神经网络与神经网络优化算法l1957年,F.Rosenblatt提出“感知器”(Perceptron)模型,第一次把神经网络的研究从纯理论的探讨付诸于工程实践,掀起了人工神经网络研究的第一次高潮。l
3、20世纪60年代以后,数字计算机的发展达到全盛时期,人们误以为数字计算机可以解决人工智能、专家系统、模式识别问题,从而放松了对“感知器”的研究。于是,从20世纪60年代末起,人工神经网络的研究进入了低潮。13.1人工神经网络与神经网络优化算法l1982年,美国加州工学院物理学家Hopfield提出了离散的神经网络模型,标志着神经网络的研究又进入了一个新高潮。1984年,Hopfield又提出连续神经网络模型,开拓了计算机应用神经网络的新途径。l1986年,Rumelhart和Meclelland提出多层网络的误差反传(Back-propagation)学习算法,简称BP算法。BP算法是目前最为
4、重要、应用最广的人工神经网络算法之一。13.1人工神经网络与神经网络优化算法l自20世纪80年代中期以来,世界上许多国家掀起了神经网络的研究热潮,可以说神经网络已成为国际上的一个研究热点。13.1人工神经网络与神经网络优化算法2.人工神经元模型与人工神经网络模型l人工神经元是一个多输入、单输出的非线性元件,如图11-1所示。l其输入、输出关系可描述为 13.1人工神经网络与神经网络优化算法l l (1)l式中,是从其他神经元传来的输入信号;是阈值;表示从神经元到神经元 的连接权值;为传递函数。)(1jjnijiijjXfyxX ),2,1(nixijijij)(f13.1 人工神经网络与神经网
5、络优化算法 yjjx0=1 fnjx1x2.xn2j1j 图11-1 13.1 人工神经网络与神经网络优化算法l人工神经网络是由大量的神经元互联而成的网络,按其拓扑结构来分,可以分成两大类:层次网络模型和互联网络模型。层次网络模型是神经元分成若干层顺序连接,在输入层上加上输入信息,通过中间各层,加权后传递到输出层后输出,其中有的在同一层中的各神经元相互之间有连接,有的从输出层到输入层有反馈;互联网络模型中,任意两个神经元之间都有相互连接的关系,在连接中,有的神经元之间是双向的,有的是单向的,按实际情况决定。13.1人工神经网络与神经网络优化算法l3.前向神经网络(1)多层前向网络一个M层的多层
6、前向网络可描述为:l网络包含一个输入层(定义为第0层)和M1个隐层,最后一个隐层称为输出层。l第 层包含 个神经元和一个阈值单元(定义为每层的第0单元),输出层不含阈值单元。lN13.1人工神经网络与神经网络优化算法第 层第 个单元到第 个单元的权值表为 。第 层(0)第 个(0)神经元的 输入定义为 ,输出定义 为 ,其中 为隐单元激励函数,常采用Sigmoid函数,即 。输入单元一般采用线性激励函数 ,阈值单元的输出始终为1。1lillij,1lljj101,1lNilillijljyx)(ljljxfy)(f1)exp(1)(xxfxxf)(j13.1人工神经网络与神经网络优化算法 目标
7、函数通常采用 (2)其中,P为样本数;为第p个样本的第j个输出分量。PpNjpjMpjPppMtyEE112,1,11)(21pjt,13.1 人工神经网络与神经网络优化算法 BP算法 BP算法是前向神经网络经典的有监督学习算法,它的提出对前向神经网络的发展起过历史性的推动作用。对于上述的M层的人工神经网络,BP算法可由下列迭代式描述,具体推导可参见神经网络的相关书目。13.1人工神经网络与神经网络优化算法 (3)PplpilpjllijllijllijllijkykkkEkk11,1,1,1,1)()()()(/)()1(13.1人工神经网络与神经网络优化算法 其中,为学习率。1111,1,
8、2),()()(1),()()(lNmljmlpmlpjlpjpjlpjlpjMlkkkxfMlkxftkyk(4)13.1人工神经网络与神经网络优化算法 实质上,BP算法是一种梯度下降算法,算法性能依赖于初始条件,学习过程易于陷入局部极小。数值仿真结果表明,BP算法的学习速度、精度、初值鲁棒性和网络推广性能都较差,不能满足应用的需要。实用中应按照需要适当改进。13.1人工神经网络与神经网络优化算法4.Hopfield 网络 1982年,Hopfield开创性地在物理学、神经生物学和计算机科学等领域架起了桥梁,提出了Hopfield 反馈神经网络模型(HNN),证明在高强度连接下的神经网络依靠
9、集体协同作用能自发产生计算行为。Hopfield 网络是典型的全连接网络,通过在网络中引入能量函数以构造动力学系统,并使网络的平衡态与能量函数的极小解相对应,从而将求解能量函数极小解的过程转化为网络向平衡态的演化过程。13.1人工神经网络与神经网络优化算法(1)离散型Hopfield 网络离散型Hopfield 网络的输出为二值型,网络采用全连接结构。令 为各神经元的输出,为各神经元与第 个神经元的连接权值,为第 个神经元的阈值,则有 nvvv,21niii,21iii13.1 人工神经网络与神经网络优化算法 (5)0,10,1)()(1iiinijjijjiiuuufvfv13.1 人工神经
10、网络与神经网络优化算法能量函数定义为 (5)则其变化量为 niniiinijjjiijvvvE1112113.1人工神经网络与神经网络优化算法 (6)也就是说,能量函数总是随神经元状态的变化而下降。0)(111ninijjjjjiiniiivvvvEE13.1人工神经网络与神经网络优化算法(2)连续型Hopfield 网络连续型Hopfield 网络的动态方程可简化描述如下:(7))(dd1iiniiiijjiiiugvIRuvTtuC13.1 人工神经网络与神经网络优化算法其中,分别为第 个神经元的输入和输出;具有连续且单调增性质的神经元激励函数;为第i个神经元到第j个神经元的连接权;为施加
11、在第i个神经元的偏置;和 为相应的电容和电阻。iivu,i)(giI0iCiQnjjiiiTQR1/1/1ijT13.1 人工神经网络与神经网络优化算法定义能量函数 (8)则其变化量 (9)niviniiininjjiijiRvvgvIvvTE101111/d)(21niiitvvEtE1dddd13.1人工神经网络与神经网络优化算法其中,tvvgCvTTtuCvTTIRuvTvTTIRuvTvTvEiiinjjjiijiinjjjiijiiinjjjinjjjiijiiinjnjjjijijidd)()(dd)(21)(212121 111111113.1人工神经网络与神经网络优化算法于是,
12、当 时,有 (10)jiijTT 0dd)(dd21 1tvvgCtEiniii13.1人工神经网络与神经网络优化算法且当 时 。因此,随时间的增长,神经网络在状态空间中的轨迹总是向能量函数减小的方向变化,且网络的稳定点就是能量函数的极小点。连续型Hopfield 网络广泛用于联想记忆和优化计算问题。0ddtvi0ddtE13.2遗传算法 l遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。l它最早由美国密执安大学的Holland教授提出,起源于20世纪60年代对自然和人工自适应系统的研究。l20世纪70年代,De Jong基于遗传算法的思想在计算机上进行了
13、大量的纯数值函数优化计算实验。l在一系列研究工作的基础上,20世纪80年代由Goldberg进行归纳总结,形成了遗传算法的基本框架。13.2遗传算法1.遗传算法概要l对于一个求函数最大值的优化问题,一般可描述为下述数学规划模型:(11)l式中,为决策变量;f(X X)为目标函数;U是基本空间;R是U的一个子集。URXX.s.t)(MaxfT21),(nxxxX13.2遗传算法遗传算法中,将n维决策变量用n个记号所组成的符号串X X来表示,即 l把每一个Xi看做一个遗传基因,它的所有可能取值称为等位基因,这样,X X就可看做是由n个遗传基因所组成的一个染色体。l染色体的长度可以是固定的,也可以是
14、变化的。l等位基因可以是一组整数,也可以是某一范围内的实数值,或者是记号。l最简单的等位基因是由0和1这两个整数组成的,相应的染色体就可表示为一个二进制符号串。),2,1(niiXT2121),(nnxxxXXXXX13.2遗传算法l这种编码所形成的排列形式X X是个体的基因型,与它对应的X X值是个体的表现型。染色体X X也称为个体X X,对于每一个个体X X,要按照一定的规则确定出其适应度。个体的适应度与其对应的个体表现型X X的目标函数值相关联,X X越接近于目标函数的最优点,其适应度越大;反之,其适应度越小。13.2遗传算法l遗传算法中,决策变量X X组成了问题的解空间。对问题最优解的
15、搜索是通过对染色体X的搜索过程来进行的,从而由所有的染色体X就组成了问题的搜索空间。l生物的进化是以集团为主体的。与此相对应,遗传算法的运算对象是由M个个体所组成的集合,称为群体。13.2遗传算法l与生物一代一代的自然进化过程相似,遗传算法的运算过程也是一个反复迭代过程,第t代群体记作P(t),经过一代遗传和进化后,得到第t+1代群体,它们也是由多个个体组成的集合,记作P(t+1)。这个群体不断地经过遗传和进化操作,并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代,这样最终在群体中将会得到一个优良的个体X,它所对应的表现型X将达到或接近于问题的最优解 。13.2遗传算法l生物的
16、进化过程主要是通过染色体之间的交叉和染色体的变异来完成的。遗传算法中最优解的搜索过程也模仿生物的这个进化过程,使用所谓的遗传算子作用于群体中,进行下述遗传操作,从而得到新一代群体。l选择(selection):根据各个个体的适应度,按照一定的规则或方法,从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。l交叉(crossover):将群体P(t)内的各个个体随机搭配成对,对每一个个体,以某个概率(称为交叉概率,crossover rate)交换它们之间的部分染色体。l变异(mutation):对群体P(t)中的每一个个体,以某一概率(称为变异概率,mutation ra
17、te)改变某一个或一些基因座上基因值为其他的等位基因。l l 13.2遗传算法2.遗传算法的特点l遗传算法是一类可用于复杂系统优化计算的鲁棒搜索算法,主要有下述几个特点:遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值本身进行优化计算,但遗传算法不是直接以决策变量的值,而是以决策变量的某种形式的编码为运算对象,从而可以很方便地引入和应用遗传操作算子。遗传算法直接以目标函数值作为搜索信息。传统的优化算法往往不只需要目标函数值,还需要目标函数的导数等其他信息。这样对许多目标函数无法求导或很难求导的函数而言,遗传算法就比较方便。l 13.2遗传算法遗传算法同时进行解空
18、间的多点搜索。传统的优化算法往往从解空间的一个初始点开始搜索,这样容易陷入局部极值点。遗传算法进行群体搜索,而且在搜索的过程中引入遗传运算,使群体又可以不断进化。这些是遗传算法所特有的一种隐含并行性。遗传算法使用概率搜索技术。遗传算法属于一种自适应概率搜索技术,其选择、交叉、变异等运算都是以一种概率的方式来进行的,从而增加了其搜索过程的灵活性。实践和理论都已证明了在一定条件下遗传算法总是以概率1收敛于问题的最优解。13.2遗传算法3.遗传算法的应用l遗传算法提供了一种求解复杂系统优化问题的通用框架,它不依赖于问题的具体领域,对问题的种类有很强的鲁棒性,所以广泛应用于很多学科。下面列举一些遗传算
19、法的主要应用领域。l函数优化函数优化是遗传算法的经典应用领域,也是对遗传算法进行性能测试评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题,用其他优化方法较难求解,而遗传算法却可以方便地得到较好的结果。l组合优化遗传算法是寻求组合优化问题满意解的最佳工具之一,实践证明,遗传算法对于组合优化问题中的NP完全问题非常有效。l 13.2遗传算法l生产调度问题生产调度问题在很多情况下所建立起来的数学模型难以精确求解,即使经过一些简化之后可以进行求解,也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为解决复杂调度问题的有效工具。l自动控制遗传算法已经在自动控制领域中得到了很好的应
20、用,例如基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等。13.2遗传算法l机器人学机器人是一类复杂的难以精确建模的人工系统,而遗传算法的起源就来自于对人工自适应系统的研究,所以机器人学自然成为遗传算法的一个重要应用领域。l图像处理图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中,如扫描、特征提取、图像分割等不可避免地存在一些误差,这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求,遗传算法在这些图像处理中的优化计算方面得到了很好的应用。13.2遗传算法
21、l人工生命人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大重要特征。人工生命与遗传算法有着密切的关系,基于遗传算法的进化模型是研究人工生命现象的重要理论基础。13.2遗传算法l遗传编程Koza发展了遗传编程的概念,他使用了以LISP语言所表示的编码方法,基于对一种树形结构所进行的遗传操作来自动生成计算机程序。l机器学习基于遗传算法的机器学习,在很多领域中都得到了应用。例如,基于遗传算法的机器学习可用来调整人工神经网络的连接权,也可以用于人工神经网络的网络结构优化设计。13.2遗传算法l4.基本遗传算法l基本遗传算法(Si
22、mple Genetic Algorithms,简称SGA)是一种统一的最基本的遗传算法,它只使用选择、交叉、变异这三种基本遗传算子,其遗传进化操作过程简单,容易理解,是其他一些遗传算法的雏形和基础,它不仅给各种遗传算法提供了一个基本框架,同时也具有一定的应用价值。13.2遗传算法 基本遗传算法的构成要素 染色体编码方法。基本遗传算法使用固定长度的二进制符号串来表示群体中的个体,其等位基因是由二值符号集0,1所组成的。初始群体中各个个体的基因值可用均匀分布的随机数来生成。13.2 遗传算法个体适应度评价。基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少
展开阅读全文