现代优化方法PPT课件

.,1,现代优化方法,陈荣虎,.,2,概述人工神经网络(ArtificialNeuralNetwork)遗传算法禁忌搜索算法模拟退火算法蚁路算法,主要内容,.,3,现代优化方法包括人工神经网络、遗传算法、禁忌搜索算法、模拟退火算法、蚁路算法等；这些算法是根据一些直观基础而构建的，我们把它称之为启发式算法，有人称现代优化算法主要指仿生算法；牵涉到的学科广泛生物进化、人工智能、数学和物理、神经系统和统计力学等。这些算法和人工智能、计算机科学和运筹学相融合。,概述,.,4,计算复杂性与传统算法的局限旅行商问题：一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为dij，如何选择一条道路使得商人每个城市走一遍后回到起点且所走路径最短。对称距离非对称距离,概述,.,5,采用枚举法来解决非对称旅行商问题假定有n个城市，共需要(n-1)!次枚举，假定完成25个城市的总距离的计算及比较需要1秒，则当城市增加时，需要的时间如下表所示：,概述,.,6,人类对人工智能的研究可以分成两种方式对应着两种不同的技术：传统的人工智能技术心理的角度模拟基于人工神经网络的技术生理的角度模拟人工神经网络的定义是由人工神经元互联组成的网络，从微观结构和功能上对人脑的抽象、简化，是模拟人类智能的一条重要途径。反映了人脑功能的若干基本特征，如，并行信息处理、学习、联想、模式分类、记忆等。简单地讲，它是一个数学模型，可以用电子线路来实现，也可以用计算机程序来模拟，是人工智能研究的一种方法。,人工神经网络,.,7,智能的含义智能是个体有目的的行为，合理的思维，以及有效的、适应环境的综合能力。智能是个体认识客观事物和运用知识解决问题的能力。人类个体的智能是一种综合能力。,人工神经网络：概念的提出,.,8,智能的概念的八个方面,人工神经网络：概念的提出,.,9,人工智能：研究如何使类似计算机这样的设备去模拟人类的这些能力。研究人工智能的目的增加人类探索世界，推动社会前进的能力进一步认识自己,人工神经网络：概念的提出,.,10,联接主义观点核心：智能的本质是联接机制。神经网络是一个由大量简单的处理单元组成的高度复杂的大规模非线性自适应系统ANN力求从四个方面去模拟人脑的智能行为物理结构计算模拟存储与操作训练,人工神经网络：概念的提出,.,11,物理符号系统和人工神经网络系统的差别,人工神经网络：概念的提出,.,12,两种人工智能技术的比较,人工神经网络：概念的提出,.,13,信息的分布表示运算的全局并行和局部操作处理的非线性,人工神经网络：特点,.,14,人工神经网络可以根据所在的环境去改变它的行为自相联的网络异相联的网络：它在接受样本集合A时，可以抽取集合A中输入数据与输出数据之间的映射关系。“抽象”功能。不同的人工神经网络模型，有不同的学习/训练算法,人工神经网络：学习能力,.,15,基本特征的自动提取由于其运算的不精确性，表现成“去噪音、容残缺”的能力，利用这种不精确性，比较自然地实现模式的自动分类。泛化（Generalization）能力与抽象能力,人工神经网络：学习能力,.,16,信息的分布存提供容错功能由于信息被分布存放在几乎整个网络中，所以，当其中的某一个点或者某几个点被破坏时，信息仍然可以被存取。系统在受到局部损伤时还可以正常工作。并不是说可以任意地对完成学习的网络进行修改。也正是由于信息的分布存放，对一类网来说，当它完成学习后，如果再让它学习新的东西，这时就会破坏原来已学会的东西。,人工神经网络：学习能力,.,17,擅长两个方面：对大量的数据进行分类，并且只有较少的几种情况；必须学习一个复杂的非线性映射。目前应用：人们主要将其用于语音、视觉、知识处理、辅助决策等方面。在数据压缩、模式匹配、系统建模、模糊控制、求组合优化问题的最佳解的近似解（不是最佳近似解）等方面也有较好的应用。,人工神经网络：学习能力,.,18,萌芽期（20世纪40年代）人工神经网络的研究最早可以追溯到人类开始研究自己的智能的时期，到1949年止。1943年，心理学家McCulloch和数学家Pitts建立起了著名的阈值加权和模型，简称为M-P模型。发表于数学生物物理学会刊BulletinofMathematicalBiophysics1949年，心理学家D.O.Hebb提出神经元之间突触联系是可变的假说Hebb学习律。,人工神经网络：历史回顾,.,19,第一高潮期（19501968）以MarvinMinsky，FrankRosenblatt，BernardWidrow等为代表人物，代表作是单级感知器（Perceptron）。可用电子线路模拟。人们乐观地认为几乎已经找到了智能的关键。许多部门都开始大批地投入此项研究，希望尽快占领制高点。,人工神经网络：历史回顾,.,20,反思期（19691982）M.L.Minsky和S.Papert，Perceptron，MITPress，1969年异或”运算不可表示二十世纪70年代和80年代早期的研究结果认识规律：认识实践再认识,人工神经网络：历史回顾,.,21,第二高潮期（19831990）1982年，J.Hopfield提出循环网络用Lyapunov函数作为网络性能判定的能量函数，建立ANN稳定性的判别依据阐明了ANN与动力学的关系用非线性动力学的方法来研究ANN的特性指出信息被存放在网络中神经元的联接上1984年，J.Hopfield设计研制了后来被人们称为Hopfield网的电路。较好地解决了著名的TSP问题，找到了最佳解的近似解，引起了较大的轰动。,人工神经网络：历史回顾,.,22,第二高潮期（19831990）1985年，UCSD的Hinton、Sejnowsky、Rumelhart等人所在的并行分布处理（PDP）小组的研究者在Hopfield网络中引入了随机机制，提出所谓的Boltzmann机。1986年，并行分布处理小组的Rumelhart等研究者重新独立地提出多层网络的学习算法BP算法，较好地解决了多层网络的学习问题。,人工神经网络：历史回顾,.,23,再认识与应用研究期（1991）问题：应用面还不够宽结果不够精确存在可信度的问题。,人工神经网络：历史回顾,.,24,人的思维由脑完成人脑约由10111012个神经元组成，每个神经元约与104105个神经元联接，能接受并处理信息。因此，人脑是复杂的信息并行加工处理巨系统。人脑可通过自组织、自学习，不断适应外界环境的变化。其自组织、自学习性来源于神经网络结构的可塑性，主要反映在神经元之间联接强度的可变性上。,人工神经网络：基础,.,25,人(或其它生物)的神经网络示意图,人工神经网络：基础,.,26,一个神经元通过晶枝(dendrite)接收到信息后，它对这些信息进行处理，并通过它所控制的触突(synapse)传给其它神经元。,人工神经网络：基础,.,27,神经元的六个基本特征：神经元及其联接；神经元之间的联接强度决定信号传递的强弱；神经元之间的联接强度是可以随训练改变的；信号可以是起刺激作用的，也可以是起抑制作用的；一个神经元接受的信号的累积效果决定该神经元的状态；每个神经元可以有一个“阈值”。,人工神经网络：基础,.,28,人工神经元神经元是构成神经网络的最基本单元（构件）。人工神经元模型应该具有生物神经元的六个基本特性。,人工神经网络：基础,.,29,单层神经网络的结构(转自Matlab帮助文件)有些教材把它称为两层结构,人工神经网络：基础,.,30,多层神经网络的结构(转自Matlab帮助文件),人工神经网络：基础,.,31,Hopfield网络(反馈型结构),人工神经网络：基础,.,32,其它网络结构,人工神经网络：基础,.,33,人工神经网络计算过程示意图,人工神经网络：举例,.,34,神经网络在目前已有几十种不同的模型。通常可按5个原则进行神经网络的归类。按照网络的结构区分，则有前向网络和反馈网络。按照学习方式区分，则有有教师学习和无教师学习网络。按照网络性能区分，则有连续型和离散性网络，随机型和确定型网络。按照突触性质区分，则有一阶线性关联网络和高阶非线性关联网络。按对生物神经系统的层次模拟区分，则有神经元层次模型，组合式模型，网络层次模型，神经系统层次模型和智能型模型。,人工神经网络：种类及应用,.,35,常见的神经网络类型及应用,人工神经网络：种类及应用,.,36,生物进化的规律：选择、遗传和变异。借鉴了生物进化的特征，其主要特征为：进化发生在解的编码上(染色体)人为地构造函数使好的染色体的后代数超过平均数染色体保持父母的特征染色体会产生变异,遗传算法,.,37,遗传算法,生物遗传概念和遗传算法中的概念比较,.,38,例：用遗传算法求f(x)=x2，0x31，x为整数的最大值用五位二进制编码00000，1000016，1111131五位字符串称为染色体，每位称为基因，每个基因有两种状态0,1首先产生一个随机群体，如4个(通常取偶数个)x1=00000,x2=11001,x3=01111,x4=01000适应函数fitness(xi)=f(x)=x2,遗传算法,.,39,fitness(x1)=0,fitness(x2)=252,fitness(x3)=152,fitness(x4)=82定义第i个个体入选种群的概率为适应值大的染色体生存的概率较大,遗传算法,.,40,假若要产生四个个体，则根据各个体的概率，有可能是如下结构：2个11001,1个01111,1个10000采用如下方式交配,遗传算法,.,41,若y4的第一个基因发生变异，则y4=11001如满足停止规则，则结束，否则重新计算适应度函数，继续上述过程。,遗传算法,.,42,应用：各种NP-Hard优化问题,遗传算法,.,43,为了找到“全局最优解”，就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间。兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。,禁忌搜索算法(tabusearch),.,44,当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表（tabulist）”的含义。那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度（tabulength）”；如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个有兔子留守的地方优越性太突出，超过了“besttofar”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“特赦准则（aspirationcriterion）”。这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。,禁忌搜索算法(tabusearch),.,45,应用：TSP问题,禁忌搜索算法(tabusearch),.,46,温度、能量、概率分布间的关系由统计力学表明，在温度T，分子停留在状态r满足Boltzmann概率分布：在同一温度，分子停留在能量小状态的概率比停留在能量大状态的概率要大。在最小能量状态下，概率关于温度T是单调下降的。温度趋向0时，分子停留在最低能量状态的概率趋向1。,模拟退火算法(SimulatedAnnealing),.,47,1982年,KirkPatrick将退火思想引入组合优化领域，提出一种解大规模组合优化问题的算法，对NP完全组合优化问题尤其有效。这源于固体的退火过程，即先将温度加到很高,再缓慢降温(即退火)，使达到能量最低点。如果急速降温(即为淬火)则不能达到最低点。,模拟退火算法(SimulatedAnnealing),.,48,组合优化问题与退火进行比较,模拟退火算法(SimulatedAnnealing),.,49,模拟退火算法可以分解为解空间、目标函数和初始解三部分。模拟退火的基本思想:初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L对k=1，L做第(3)至第6步：产生新解S计算增量t=C(S)-C(S)，其中C(S)为评价函数若t0，然后转第2步。,模拟退火算法(SimulatedAnnealing),.,50,模拟退火算法的应用很广泛，可以较高的效率求解最大截问题(MaxCutProblem)、0-1背包问题(ZeroOneKnapsackProblem)、图着色问题(GraphColouringProblem)、调度问题(SchedulingProblem)等等。,模拟退火算法,.,51,蚂蚁在觅食过程中，会分