运筹学与最优化方法第10章

null第 十 章 第 十 章 智能优化计算简介 第十章 智能优化计算简介 第十章 智能优化计算简介 本章对目前常用的几种智能优化计算算法作简单介绍，以使读者对它们有个基本认识。内容包括神经网络、遗传算法、模拟退火算法和神经网络混合优化学习策略。 10.1 人工神经网络与神经网络优化算法 10.1 人工神经网络与神经网络优化算法 人工神经网络是近年来得到迅速发展的一个前沿课题。神经网络由于其大规模并行处理、容错性、自组织和自适应能力和联想功能强等特点，已成为解决很多问题的有力工具。本节首先对神经网络作简单介绍，然后介绍几种常用的神经网络，包括前向神经网络、Hopfield网络。 10.1 人工神经网络与神经网络优化算法 10.1 人工神经网络与神经网络优化算法 10.1.1 人工神经网络发展简史 最早的研究可以追溯到20世纪40年代。1943年，心理学家McCulloch和数学家Pitts合作提出了形式神经元的数学模型。这一模型一般被简称M-P神经网络模型，至今仍在应用，可以说，人工神经网络的研究时代，就由此开始了。 1949年，心理学家Hebb提出神经系统的学习规则，为神经网络的学习算法奠定了基础。现在，这个规则被称为Hebb规则，许多人工神经网络的学习还遵循这一规则。 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法1957年，F.Rosenblatt提出“感知器”(Perceptron)模型，第一次把神经网络的研究从纯理论的探讨付诸工程实践，掀起了人工神经网络研究的第一次高潮。 20世纪60年代以后，数字计算机的发展达到全盛时期，人们误以为数字计算机可以解决人工智能、专家系统、模式识别问题，而放松了对“感知器”的研究。于是，从20世纪60年代末期起，人工神经网络的研究进入了低潮。 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法1982年，美国加州工学院物理学家Hopfield提出了离散的神经网络模型，标志着神经网络的研究又进入了一个新高潮。1984年，Hopfield又提出连续神经网络模型，开拓了计算机应用神经网络的新途径。 1986年，Rumelhart和Meclelland提出多层网络的误差反传(back propagation)学习算法，简称BP算法。BP算法是目前最为重要、应用最广的人工神经网络算法之一。 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法自20世纪80年代中期以来，世界上许多国家掀起了神经网络的研究热潮，可以说神经网络已成为国际上的一个研究热点。 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法10.1.2 人工神经元模型与人工神经网络模型 人工神经元是一个多输入、单输出的非线性元件，如图10-1所示。 其输入、输出关系可描述为 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法 (10-1-1) 式中， 是从其它神经元传来的输入信号； 是阈值； 表示从神经元到神经元 的连接权值； 为传递函数。 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法人工神经网络是由大量的神经元互连而成的网络，按其拓扑结构来分，可以分成两大类：层次网络模型和互连网络模型。层次网络模型是神经元分成若干层顺序连接，在输入层上加上输入信息，通过中间各层，加权后传递到输出层后输出，其中有的在同一层中的各神经元相互之间有连接，有的从输出层到输入层有反馈；互连网络模型中，任意两个神经元之间都有相互连接的关系，在连接中，有的神经元之间是双向的，有的是单向的，按实际情况决定。 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法10.1.3 前向神经网络 (1)多层前向网络 一个M层的多层前向网络可描述为： ①网络包含一个输入层（定义为第0层）和M-1个隐层，最后一个隐层称为输出层； ②第层包含 个神经元和一个阈值单元（定义为每层的第0单元），输出层不含阈值单元； 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法③第 层第 个单元到第个单元的权值表为 ； ④第 层（ >0）第 个（ >0）神经元的输入定义为 ，输出定义为 ，其中 为隐单元激励函数，常采用Sigmoid函数，即 。输入单元一般采用线性激励函数 ，阈值单元的输出始终为1； 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法⑤ 目标函数通常采用： （10-1-2） 其中P为样本数， 为第p个样本的第j个输出分量。 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法⑵ BP算法 BP算法是前向神经网络经典的有监督学习算法，它的提出，对前向神经网络的发展起过历史性的推动作用。对于上述的M层的人工神经网络，BP算法可由下列迭代式描述，具体推导可参见神经网络的相关书目。 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法 （10-1-3） 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法 (10-1-4) 其中， 为学习率。 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法实质上，BP算法是一种梯度下降算法，算法性能依赖于初始条件，学习过程易于陷入局部极小。数值仿真结果表明，BP算法的学习速度、精度、初值鲁棒性和网络推广性能都较差，不能满足应用的需要。实用中按照需要适当改进。 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法10.1.4 Hopfield 网络 1982年，Hopfield开创性地在物理学、神经生物学和计算机科学等领域架起了桥梁，提出了Hopfield 反馈神经网络模型(HNN)，证明在高强度连接下的神经网络依靠集体协同作用能自发产生计算行为。Hopfield 网络是典型的全连接网络，通过在网络中引入能量函数以构造动力学系统，并使网络的平衡态与能量函数的极小解相对应，从而将求解能量函数极小解的过程转化为网络向平衡态的演化过程。 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法(1)    离散型Hopfield 网络 离散型Hopfield 网络的输出为二值型，网络采用全连接结构。令 为各神经元的输出， 为各神经元与第 个神经元的连接权值， 为第 神经元的阈值，则有 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法 （10-1-5） 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法能量函数定义为 则其变化量为 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法 （10-1-6） 也就是说，能量函数总是随神经元状态的变化而下降的。 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法(2) 连续型Hopfield 网络 连续型Hopfield 网络的动态方程可简化描述如下： （10-1-7） 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法其中， 分别为第 神经元的输入和输出， 具有连续且单调增性质的神经元激励函数，为第i神经元到j第神经元的连接权， 为施加在第i神经元的偏置， 和 为相应的电容和电阻， 。 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法定义能量函数 （10-1-8） 则其变化量 (10-1-9) 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法其中， 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法于是，当 时， (10-1-10) 10.1 人工神经网络与神经网络优化算法10.1 人工神经网络与神经网络优化算法且当 时 。 因此，随时间的增长，神经网络在状态空间中的轨迹总是向能量函数减小的方向变化，且网络的稳定点就是能量函数的极小点。 连续型Hopfield 网络广泛用于联想记忆和优化计算问题。 10.2 遗传算法 10.2 遗传算法 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它最早由美国密执安大学的Holland教授提出，起源于上世纪60年代对自然和人工自适应系统的研究。上世纪70年代，De Jong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。 10.2 遗传算法10.2 遗传算法在一系列研究工作的基础上，上世纪80年代由Goldberg进行归纳 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf ，形成了遗传算法的基本框架。 10.2 遗传算法10.2 遗传算法10.2.1 遗传算法概要 对于一个求函数最大值的优化问题，一般可描述为下述数学规划模型： (10-2-1) 10.2 遗传算法10.2 遗传算法式中， 为决策变量，f(X)为目标函数，U是基本空间，R是U的一个子集。 遗传算法中，将n维决策向量用n个记号 所组成的符号串X来表示： 10.2 遗传算法10.2 遗传算法把每一个 看作一个遗传基因，它的所有可能取值称为等位基因，这样，X就可看作是由n个遗传基因所组成的一个染色体。染色体的长度可以是固定的，也可以是变化的。等位基因可以是一组整数，也可以是某一范围内的实数值，或者是记号。最简单的等位基因是由0和1这两个整数组成的，相应的染色体就可表示为一个二进制符号串。 10.2 遗传算法10.2 遗传算法这种编码所形成的排列形式X是个体的基因型，与它对应的X值是个体的表现型。染色体X也称为个体X，对于每一个个体X，要按照一定的规则确定出其适应度。个体的适应度与其对应的个体表现型X的目标函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。 10.2 遗传算法10.2 遗传算法遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的，从而由所有的染色体X就组成了问题的搜索空间。 生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体。 10.2 遗传算法10.2 遗传算法与生物一代一代的自然进化过程相似，遗传算法的运算过也是一个反复迭代过程，第t代群体记做P(t),经过一代遗传和进化后，得到第t+1代群体，它们也是由多个个体组成的集合，记做P(t+1)。这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现型X将达到或接近于问题的最优解 。 10.2 遗传算法10.2 遗传算法生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成的。遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用所谓的遗传算子(genetic operators)作用于群体P(t)中，进行下述遗传操作，从而得到新一代群体P(t+1)。 10.2 遗传算法10.2 遗传算法选择(selection):根据各个个体的适应度，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。 交叉(crossover):将群体P(t)内的各个个体随机搭配成对，对每一个个体，以某个概率(称为交叉概率，crossover rate)交换它们之间的部分染色体。 10.2 遗传算法10.2 遗传算法变异(mutation):对群体P(t)中的每一个个体，以某一概率(称为变异概率，mutation rate)改变某一个或一些基因座上基因值为其它的等位基因。 10.2 遗传算法10.2 遗传算法10.2.2 遗传算法的特点 遗传算法是一类可用于复杂系统优化计算的鲁棒搜索算法，与其他一些优化算法相比，主要有下述几个特点： 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值本身进行优化计算，但遗传算法不是直接以决策变量的值，而是以决策变量的某种形式的编码为运算对象，从而可以很方便地引入和应用遗传操作算子。 10.2 遗传算法10.2 遗传算法遗传算法直接以目标函数值作为搜索信息。传统的优化算法往往不只需要目标函数值，还需要目标函数的导数等其它信息。这样对许多目标函数无法求导或很难求导的函数，遗传算法就比较方便。 10.2 遗传算法10.2 遗传算法遗传算法同时进行解空间的多点搜索。传统的优化算法往往从解空间的一个初始点开始搜索，这样容易陷入局部极值点。遗传算法进行群体搜索，而且在搜索的过程中引入遗传运算，使群体又可以不断进化。这些是遗传算法所特有的一种隐含并行性。 10.2 遗传算法10.2 遗传算法遗传算法使用概率搜索技术 。遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。实践和理论都已证明了在一定条件下遗传算法总是以概率1收敛于问题的最优解。 10.2 遗传算法10.2 遗传算法10.2.3 遗传算法的发展 上世纪60年代，美国密植安大学的Holland教授及其学生们受到生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统计算优化的自适应概率优化技术-----遗传算法。下面是在遗传算法的发展进程中一些关键人物所做出的一些主要贡献。 10.2 遗传算法10.2 遗传算法J.H.Holland 20世纪60年代，Holland认识到了生物的遗传和自然进化现象与人工自适应系统的相似关系，运用生物遗传和进化的思想来研究自然和人工自适应系统的生成以及它们与环境的关系，提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制，以群体的方法进行自适应搜索，并且充分认识到了交叉、变异等运算策略在自适应系统中的重要性。 10.2 遗传算法10.2 遗传算法20世纪70年代，Holland提出了遗传算法的基本定理---模式定理(Schema Theorem),奠定了遗传算法的理论基础。1975年，Holland出版了第一本系统论述遗传算法和人工自适应系统的专著《自然系统和人工系统的自适应性（Adaptation in Natural and Artificial Systems）》。 10.2 遗传算法10.2 遗传算法20世纪80年代，Holland实现了第一个基于遗传算法的机器学习系统----分类器系统，开创了基于遗传算法学习的新概念，为分类器系统构造出了一个完整的框架。 10.2 遗传算法10.2 遗传算法J.D.Bagley 1967年，Holland的学生Bagley在其博士论文中首次提出了“遗传算法”一词，并发表了遗传算法应用方面的第一篇论文。他发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用了双倍体的编码方法。这些都与目前遗传算法中所使用的算子和方法类似。他还敏锐地意识到了在遗传算法执行的不同阶段可以使用不同的选择率，这将有利于防止遗传算法的早熟现象，从而创立了自适应遗传算法的概念。 10.2 遗传算法10.2 遗传算法K.A.De Jong 1975年，De Jong在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。他推荐了在大多数优化问题中都比较适用的遗传算法参数，还建立了著名的De Jong 五函数测试平台，定义了评价遗传算法性能的在线指标和离线指标。 10.2 遗传算法10.2 遗传算法D.J.Goldberg 1989年，Goldberg出版了专著《搜索、优化和机器学习中的遗传算法》。该书系统总结了遗传算法的主要研究成果，全面而完整地论述了遗传算法的基本原理及其应用。 10.2 遗传算法10.2 遗传算法L.Davis 1991年，Davis编辑出版了《遗传算法手册》，书中包含了遗传算法在科学计算、工程技术和社会经济中的大量应用实例，该书为推广和普及遗传算法的应用起到了重要的指导作用。 10.2 遗传算法10.2 遗传算法J.R.Koza 1992年，Koza将遗传算法应用于计算机程序的优化设计及自动生成，，提出了遗传编程的概念。Koza成功地将提出的遗传编程方法应用于人工智能、机器学习、符号处理等方面。 10.2 遗传算法10.2 遗传算法10.2.4 遗传算法的应用 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面列举一些遗传算法的主要应用领域。 10.2 遗传算法10.2 遗传算法函数优化。函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能测试评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。 10.2 遗传算法10.2 遗传算法组合优化。遗传算法是寻求组合优化问题满意解的最佳工具之一，实践证明，遗传算法对于组合优化问题中的NP完全问题非常有效。 10.2 遗传算法10.2 遗传算法生产调度问题。生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为解决复杂调度问题的有效工具。 10.2 遗传算法10.2 遗传算法自动控制。遗传算法已经在自动控制领域中得到了很好的应用，例如基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等。 10.2 遗传算法10.2 遗传算法机器人学。机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人学自然成为遗传算法的一个重要应用领域。 10.2 遗传算法10.2 遗传算法图象处理。图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 ，遗传算法在这些图像处理中的优化计算方面得到了很好的应用。 10.2 遗传算法10.2 遗传算法人工生命。人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。。自组织能力和自学习能力是人工生命的两大重要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础。 10.2 遗传算法10.2 遗传算法遗传编程。Koza发展了遗传编程的概念，他使用了以LISP语言所表示的编码方法，基于对一种树形结构所进行的遗传操作来自动生成计算机程序。 机器学习。基于遗传算法的机器学习，在很多领域中都得到了应用。例如基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可以用于人工神经网络的网络结构优化设计。 10.2 遗传算法10.2 遗传算法10.2.5 基本遗传算法 基本遗传算法（Simple Genetic Algorithms,简称SGA）是一种统一的最基本的遗传算法，它只使用选择、交叉、变异这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。 10.2 遗传算法10.2 遗传算法⑴    基本遗传算法的构成要素 ① 染色体编码方法。基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二值符号集{0，1}所组成的。初始群体中各个个体的基因值可用均匀分布的随机数来生成。 10.2 遗传算法10.2 遗传算法②个体适应度评价。基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。 ③遗传算子。基本遗传算法使用下述三种遗传算子：选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异算子或均匀变异算子。 10.2 遗传算法10.2 遗传算法④基本遗传算法的运行参数。基本遗传算法有下述4个运行参数需要提前设定：群体大小M，即群体中所含个体数目，一般取为20~100；遗传运算的终止进化代数T，一般取为100~500； 交叉概率Pc， 一般取为0.4~0.99； 变异概率Pm，一般取为0.0001~0.1。 10.2 遗传算法10.2 遗传算法⑤基本遗传算法的形式化定义 基本遗传算法可定义为一个8元组： (10-2-2) 10.2 遗传算法10.2 遗传算法式中，C---个体的编码方法； E---个体适应度评价函数； P0---初始群体； M---群体大小； Φ---选择算子； Γ---交叉算子； T---遗传运算终止条件。 10.2 遗传算法10.2 遗传算法⑵ 基本遗传算法的实现 ①个体适应度评价 在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。个体适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一代群体中的数量。为正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或领，不能是负数。 10.2 遗传算法10.2 遗传算法为满足适应度取非负值的要求，基本遗传算法一般采用下面两种方法之一将目标函数值变换为个体的适应度。 方法一：对于目标函数是求极大化，方法为： (10-2-3) 10.2 遗传算法10.2 遗传算法式中， 为一个适当地相对比较小的数，它可用下面几种方法之一来选取:预先指定的一个较小的数；进化到当前代为止的最小目标函数值；当前代或最近几代群体中的最小目标值。 10.2 遗传算法10.2 遗传算法②比例选择算子 比例选择实际上是一种有退还随机选择,也叫做赌盘(Roulette Wheel)选择,因为这种选择方式与赌博中的赌盘操作原理非常相似。 比例选择算子的具体执行过程是：先计算出群体中所有个体的适应度之和；其次计算出每个个体的相对适应度的大小，此值即为各个个体被遗传到下一代群体中的概率；最后再使用模拟赌盘操作（即0到1之间的随机数）来确定各个个体被选中的次数。 10.2 遗传算法10.2 遗传算法③单点交叉算子 单点交叉算子是最常用和最基本的交叉操作算子。单点交叉算子的具体执行过程如下：对群体中的个体进行两两随机配对；对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点；对每一对相互配对的个体，依设定的交叉概率 在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新个体。 10.2 遗传算法10.2 遗传算法④基本位变异算子 基本位变异算子的具体执行过程为：对个体的每一个基因座，依变异概率 指定其为变异点；对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替，从而产生出一个新的个体。 10.2 遗传算法10.2 遗传算法⑶ 遗传算法的应用步骤 遗传算法提供了一种求解复杂系统优化问题的通用框架。对于具体问题，可按下述步骤来构造： ①确定决策变量及其各种约束条件，即确定出个体的表现型X和问题的解空间； ②建立优化模型，即描述出目标函数的类型及其数学描述形式或量化方法； 10.2 遗传算法10.2 遗传算法③确定表示可行解的染色体编码方法，即确定出个体的基因型X及遗传算法的搜索空间； ④确定解码方法，即确定出由个体基因型X到个体表现型X的对应关系或转换方法； ⑤确定个体适应度的量化评价方法，即确定出由目标函数值 到个体适应度的转换规则； 10.2 遗传算法10.2 遗传算法⑥设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法； ⑦确定遗传算法的有关运行参数，即确定出遗传算法的 等参数。 10.2 遗传算法10.2 遗传算法10.2.6 遗传算法的模式定理 Holland提出的模式定理（schema theorem）,是遗传算法的基本原理，从进化动力学的角度提供了能够较好地解释遗传算法机理的一种数学工具，同时也是编码策略、遗传策略等分析的基础。 10.2 遗传算法10.2 遗传算法模式定理：在选择、交叉、变异算子的作用下，那些低阶、定义长度短、超过群体平均适应值的模式的生存数量，将随着迭代次数的增加以指数规律增长。 10.3 模拟退火算法 10.3 模拟退火算法 模拟退火算法(simulated annealing,简称SA)的思想最早是由Metropolis等(1953)提出的，1983年Kirkpatrick等将其用于组合优化。SA算法是基于Monte Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。 10.3 模拟退火算法10.3 模拟退火算法模拟退火算法在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优解能概率性地跳出并最终趋于全局最优解。模拟退火算法是一种通用的优化算法，目前已在工程中得到了广泛应用。 10.3 模拟退火算法10.3 模拟退火算法10.3.1 物理退火过程和Metropolis准则 简单而言，物理退火过程由以下三部分组成： ⑴加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将溶解为液体，从而消除系统原先可能存在的非均匀态，使随后进行的冷却过程以某一平衡态为起点。溶解过程与系统的熵增过程联系，系统能量也随温度的升高而增大。 10.3 模拟退火算法10.3 模拟退火算法⑵等温过程。物理学的知识告诉我们，对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态。 ⑶冷却过程。目的是使粒子的热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。 10.3 模拟退火算法10.3 模拟退火算法Metropolis等在1953年提出了重要性采样法，即以概率接受新状态。具体而言，在温度t,由当前状态i产生新状态j，两者的能量分别为 ，若 则接受新状态j为当前状态；否则，若概率 大于 区间内的随机数则仍旧接受新状态j为当前状态，若不成立则保留i为当前状态，其中k为Boltzmann常数。 10.3 模拟退火算法10.3 模拟退火算法这种重要性采样过程在高温下可接受与当前状态能量差较大的新状态，而在低温下基本只接受与当前能量差较小的新状态，而且当温度趋于零时，就不能接受比当前状态能量高的新状态。这种接受准则通常称为Metropolis准则。 10.3 模拟退火算法10.3 模拟退火算法10.3.2 模拟退火算法的基本思想和步骤 1983年Kirkpatrick等意识到组合优化与物理退火的相似性，并受到Metropolis准则的启迪，提出了模拟退火算法。模拟退火算法是基于Monte Carlo 迭代求解策略的一种随机寻优算法，其出发点是基于物理退火过程与组合优化之间的相似性，SA由某一较高初温开始，利用具有概率突跳特性的Metropolis抽样策略在解空间中进行随机搜索，伴随温度的不断下降重复抽样过程，最终得到问题的全局最优解。 10.3 模拟退火算法10.3 模拟退火算法标准模拟退火算法的一般步骤可描述如下： ⑴给定初温 ，随机产生初始状态 ，令 ； ⑵Repeat: ①Repeat 产生新状态 ； 10.3 模拟退火算法10.3 模拟退火算法 Until 抽样稳定准则满足； ②退温 ，并令 ； Until 算法终止准则满足； ⑶输出算法搜索结果。 10.3 模拟退火算法10.3 模拟退火算法10.3.3 模拟退火算法关键参数和操作的设定 从算法流程上看，模拟退火算法包括三函数两准则，即状态产生函数、状态接受函数、温度更新函数、内循环终止准则和外循环终止准则，这些环节的设计将决定SA算法的优化性能。此外，初温的选择对SA算法性能也有很大影响。 10.3 模拟退火算法10.3 模拟退火算法⑴状态产生函数 设计状态产生函数（邻域函数）的出发点应该是尽可能保证产生的候选解遍布全部的解空间。通常，状态产生函数由两部分组成，即产生候选解的方式和候选解产生的概率分布。 10.3 模拟退火算法10.3 模拟退火算法⑵状态接受函数 状态接受函数一般以概率的方式给出，不同接受函数的差别主要在于接受概率的形式不同。设计状态接受概率，应该遵循以下原则： ①在固定温度下，接受使目标函数值下降的候选解的概率要大于使目标值上升的候选解的概率； 10.3 模拟退火算法10.3 模拟退火算法②随温度的下降，接受使目标函数值上升的解的概率要逐渐减小； ③当温度趋于零时，只能接受目标函数值下降的解。 状态接受函数的引入是SA算法实现全局搜索的最关键的因素，SA算法中通常采用min[1,exp(-△C/t)]作为状态接受函数。 10.3 模拟退火算法10.3 模拟退火算法⑶初温 初始温度、温度更新函数、内循环终止准则和外循环终止准则通常被称为退火历程(annealing schedule)。实验表明，初温越大，获得高质量解的几率越大，但花费的计算时间将增加。因此，初温的确定应折衷考虑优化质量和优化效率，常用方法包括： 10.3 模拟退火算法10.3 模拟退火算法①均匀抽样一组状态，以各状态目标值的方差为初温。 ②随机产生一组状态，确定两两状态间的最大目标值差 ，然后依据差值，利用一定的函数确定初温。譬如 ，其中 为初始接受概率 ③利用经验公式给出。 10.3 模拟退火算法10.3 模拟退火算法⑷温度更新函数 温度更新函数，即温度的下降方式，用于在外循环中修改温度值。 目前，最常用的温度更新函数为指数退温函数，即，其中且其大小可以不断变化。 10.3 模拟退火算法10.3 模拟退火算法⑸内循环终止准则 内循环终止准则，或称Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目。在非时齐SA算法理论中，由于在每个温度下只产生一个或少量候选解，所以不存在选择内循环终止准则的问题。 10.3 模拟退火算法10.3 模拟退火算法而在时齐SA算法理论中，收敛条件要求在每个温度下产生候选解的数目趋于无穷大，以使相应的马氏链达到平稳概率分布，显然在实际应用算法时这是无法实现的。常用的抽样准则包括： ①检验目标函数的均值是否稳定； ②连续若干步的目标值变化较小； ③按一定的步数抽样。 10.3 模拟退火算法10.3 模拟退火算法⑹外循环终止准则 外循环终止准则，即算法终止准则，用于决定算法何时结束。设置温度终值是一种简单的方法。SA算法的收敛性理论中要求温度终值趋于零，这显然不合实际。通常的做法是： 10.3 模拟退火算法10.3 模拟退火算法①设置终止温度的阈值； ②设置外循环迭代次数； ③算法收敛到的最优值连续若干步保持不变； ④检验系统熵是否稳定。 10.4 神经网络权值的混合优化学习策略 10.4 神经网络权值的混合优化学习策略 鉴于GA、SA的全局优化特性和通用性，即优化过程无需导数信息，我们可以基于实数编码构造BPSA、BPGA混合优化学习策略，以提高前向网络学习的速度、精度，特别是避免陷入局部极小的能力。 10.4 神经网络权值的混合优化学习策略10.4 神经网络权值的混合优化学习策略10.4.1 BPSA混合学习策略 在BPSA混合学习策略中，采用以BP为主框架，并在学习过程中引入SA策略。这样做，既利用了基于梯度下降的有指导学习来提高局部搜索性能，也利用了SA的概率突跳性来实现最终的全局收敛，从而可提高学习速度和精度。 BP-SA混合学习策略的算法步骤如下： 10.4 神经网络权值的混合优化学习策略10.4 神经网络权值的混合优化学习策略 ⑴    随机产生初始权值 ，确定初温 ，令 ⑵    利用BP计算 。 利用SA进行搜索： ① 利用SA状态产生函数产生新权值 ， ，其中 为随机扰动。 10.4 神经网络权值的混合优化学习策略10.4 神经网络权值的混合优化学习策略② 计算 的目标函数值与 的目标函数值之差 。 ③ 计算接受概率 。 ④ 若 ，则取 ；否则 保持不变。 10.4 神经网络权值的混合优化学习策略10.4 神经网络权值的混合优化学习策略(4) 利用退温函数 进行退温，其中 为退温速率。 若 对应的目标函数满足要求精度 ，则终止算法并输出结果；否则，令 ，转步骤⑵。 10.4 神经网络权值的混合优化学习策略10.4 神经网络权值的混合优化学习策略10.4.2 BPGA混合学习策略 神经网络的连接权包含着神经网络系统的全部知识。反向传播的BP神经网络(back propagation network)的学习算法是基于梯度下降的，因而具有以下缺点：网络训练速度慢、容易陷入局部极小值、全局搜索能力差等。而遗传算法的搜索遍及整个解空间，因此容易得到全局最优解，而且遗传算法不要求目标函数连续、可微，甚至不要求目标函数有显函数的形式，只要求问题可计算。10.4 神经网络权值的混合优化学习策略10.4 神经网络权值的混合优化学习策略因此，将擅长全局搜索的遗传算法和局部寻优能力较强的BP算法结合起来，可以避免陷入局部极小值，提高算法收敛速度，很快找到问题的全局最优解。 BP算法和遗传算法结合训练神经网络权重的主要步骤为： 10.4 神经网络权值的混合优化学习策略10.4 神经网络权值的混合优化学习策略(1) 以神经网络节点之间的连接权重和节点的阈值为参数，采用实数编码。采用三层神经网络，设输入节点数为p，输出节点数为q，隐层节点数为r，则编码长度n为： （10-4-1） 10.4 神经网络权值的混合优化学习策略10.4 神经网络权值的混合优化学习策略 (2)设定神经网络节点连接权重的取值范围 ,产生相应范围的均匀分布随机数赋给基因值，产生初始群体； (3)对群体中个体进行评价。将个体解码赋值给相应的连接权(包括节点阈值)，引入学习样本计算出学习误差E，个体的适应度定义为： . （10-4-2） 10.4 神经网络权值的混合优化学习策略10.4 神经网络权值的混合优化学习策略(4)对群体中的个体执行遗传操作： ① 选择操作。采用比例选择算子，若群体规模为M，则适应度为的个体被选中进入下一代的概率为： . （10-4-3） 10.4 神经网络权值的混合优化学习策略10.4 神经网络权值的混合优化学习策略② 交叉操作。由于采用实数编码，故选择算术交叉算子。父代中的个体 和 以交叉概率 进行交叉操作，可产生的子代个体为： （10-4-4） 和 （10-4-5） 其中a为参数 。 10.4 神经网络权值的混合优化学习策略10.4 神经网络权值的混合优化学习策略 ③ 变异操作。 采用均匀变异算子。个体 的各个基因位以变异概率 发生变异，即按概率用 区间中的均匀分布随机数代替原有值。 ⑸ 引入最优保留策略。 10.4 神经网络权值的混合优化学习策略10.4 神经网络权值的混合优化学习策略⑹ 判断满足遗传算法操作终止条件否？不满足则转步骤⑶。否则转步骤⑺。 ⑺ 将遗传算法搜索的最优个体解码，赋值给神经网络权重(包括节点阈值)，继续采用BP算法优化神经网络的权重和阈值。 10.4 神经网络权值的混合优化学习策略10.4 神经网络权值的混合优化学习策略10.4.3 GASA混合学习策略 采用三层前馈网络，GA和SA结合训练神经网络权重的步骤如下： ⑴ 给定模拟退火初温 ，令 ； ⑵ 以神经网络节点之间的连接权重和节点的阈值为参数，采用实数编码。采用三层神经网络，设输入节点数为p，输出节点数为q，隐层节点数为r，则编码长度n为： 10.4 神经网络权值的混合优化学习策略10.4 神经网络权值的混合优化学习策略 （10-4-6） ⑶ 设定神经网络节点连接权重的取值范围 ，产生相应范围的均匀分布随机数赋给基因值，产生初始群体； ⑷ 对群体中个体进行评价。将个体解码赋值给相应的连接权(包括节点阈值)，引入学习样本计算出学习误差E，个体的适应度定义为： . （10-4-7） 10.4 神经网络权值的混合优化学习策略10.4 神经网络权值的混合优化学习策略⑸ 对群体中的个体执行遗传操作： ① 选择操作。采用比例选择算子，若群体规模为M，则适应度为 的个体 被选中进入下一代的概率为： . （10-4-8） 10.4 神经网络权值的混合优化学习策略10.4 神经网络权值的混合优化学习策略 ② 交叉操作。由于采用实数编码，故选择算术交叉算子。父代中的个体 和 以交叉概率 进行交叉操作，可产生的子代个体为： （10-4-9） 和 （10-4-10） 其中a为参数 。 10.4 神经网络权值的混合优化学习策略10.4 神经网络权值的混合优化学习策略 ③ 变异操作。采用均匀变异算子。个体 的各个基因位以变异概率 发生变异，即按概率 用区间 中的均匀分布随机数代替原有值。 ⑹ 引入最优保留策略。 ⑺ 对群体中每一个个体引入模拟退火操作： 10.4 神经网络权值的混合优化学习策略10.4 神经网络权值的混合优化学习策略① 利用SA状态产生函数产生新基因值 ， ，其中 为随机扰动。 ② 计算 的目标函数值与 的目标函数值之差 。 ③ 计算接受概率 。 10.4 神经网络权值的混合优化学习策略10.4 神经网络权值的混合优化学习策略④ 若 ，则取 ；否则 保持不变。 ⑤ 引入最优保留策略。 ⑥ 利用退温函数 进行退温，其中 为退温速率。 10.4 神经网络权值的混合优化学习策略10.4 神经网络权值的混合优化学习策略 ⑻ 判断满足遗传算法操作终止条件否？不满足则转步骤⑷。否则转步骤⑼。 ⑼ 将遗传算法搜索的最优个体解码，赋值给神经网络权重(包括节点阈值)。 10.5 应用举例 10.5 应用举例 略.