（系统工程专业论文）基于Hopfield网络的最小集合覆盖问题研究.pdf

学位论文数据集 中图分类号 了尸 学科分类号 k 6 0 论文编号 c 归| 0 2 , 7 0 铲。 密级 ) f h 学位授予单位代码 1 0 0 1 0 学位授予单位名称北京化工大学 作者姓名 缘沛 学号 2 耐o t o 5 o v 获学位专业名称 象我之子毫 获学位专业代码 o8 ，6 ) 课题来源 厶选 研究方向 蜘冬 乞波铋盔 论文题目 隽孑蜊两佟加磊小蝴盖；习璺磁 关键词 枷7 6 刎兹小绦啦掐优化j 习强 论文答辩日期 k 刀6 、多 事论文类型 劣2 必厮宕 学位论文评阅及答辩委员会情况 姓名职称 工作单位学科专长 指导教师 翔步移缓怕未似天秀 对融鬓、癌f 磊套 评阅人1 纠嬲劲硷罐：怕觚礅髻够移劾 评阅人2 玄字 评阅人3 评阅人4 评阕人5 。 一 一 答辩委员蝴 夏咯名7 - a c t , 氖- 5 t , 9 , 4 7 , 坎以 堕乳冬蝴褒袖设嚷概勾 答辩委员1 甜舷薹蓟段强jb 参f - - j 规则) 的神经网络学习方法【l l 】【”】。进一步推动了神经网络的研究和 发展，从而迎来了人t 神经网络研究的第一次高潮。 随着人工神经网络研究的进一步深入，加之人们在认识人脑和思维方式等方面的 局限性，自然而然的出现了各种一时难以解决的问题。由于当时v o nn e u m a u n 型数字 计算机正处于发展的全盛时期，人工智能得到迅速发展并取得了显著的成就，掩盖了 发展新型模拟计算机和人工智能技术的必要性和迫切性。神经网络与人工智能之间几 乎完全不同的工作方式，既引起了不少人工智能专家的兴趣，也引发了多方面的争论。 1 9 6 9 年，在对以感知器为代表的人工神经网络进行了数年研究的基础上，著名人工智 能专家m i n s k y 和p a p e n 出版了感知器一书【l4 1 。在书中，这两位专家证明了当时的 感知器只能作线性划分，而对于非线性的分类则无能为力，甚至连最简单的x o r 问题 也不能解决。即使引入隐含层神经元可能会解决非线性分类的问题，但却不能找到一 个有效的算法来对神经网络进行训练。因此，m i n s k y 断言感知器没有什么科学价值。 这种结论对于人工神经网络的研究无疑是一个沉重的打击。加上当时的技术水平无法 为人工神经网络的实现和应用提供有效的支持，而人工智能却伴随着当时数字计算机 的飞速发展取得了显著的成果。这使得在其后的十几年| 日j ，人工神经网络的研究人数 明显减少，陷入低潮。 值得指 j 的是，尽管人工神经网络的研究陷入低潮，仍然有一部分学者在i 簪持不 懈地进行研究。也就在感知器一书出版的同一年，g r o s s b e r g 等提出了自适应共振 第- 二幸人t 神绛网络简介 理论( a r t ) 模型【”】。并且在以后的几年中都由此模型进行改进发展出了三个版 本：a r t l ，a r t 2 和a r t 3 1 1 6 】- 【l8 1 。1 9 7 2 年，k o h o n e n 提出了自组织映射( s o m ) 理论模型 【1 9 】【2 3 1 ，并称其为“联想存贮器”。与此同时，a n d e r s o n 也提出了一个类似的神经网络模 型f 2 4 1 ，称为“交互存贮器”( b s b ) 。在此基础上，r 本学者中野馨在联想记忆等方面做 出了出色的工作【2 5 1 。再加上福岛雅夫的认知机理论【2 6 】【3 0 1 ，w e r b o s 的误差反传算法( b p 算法) 【3 1j - 【3 3 1 ，a m a r i 在神经网络数学理论的贡献【3 4 】【3 5 1 等等，为神经网络同后进一步的发 展奠定了理论基础。 7 0 年代后期，在人工智能模拟人的某些认知活动取得进展的同时，人们也突出地 感觉到虽然超级计算机在大型复杂计算方面显示出强大的实力，但与人的自然智能相 比，仍然存在着明显的差距。人能够轻松的识别各种复杂的事物，具有联想记忆，自 适应，自我学习等能力。而这正是数字计算机所难以逾越的障碍。因此，人们再度将 目标转到人工神经网络的研究上，希望通过对人脑神经系统的结构、信息加工、记忆 和学习机制的研究与探索，找到再现人脑的功能的新思路和新方法。另一方面，其它 科学领域出现的新的理论和新的发现，特别是复杂系统研究所取得的进展，如耗散结 构理论，协同学以及混沌动力学等在客观上对人工神经网络的再度兴起也起到了积极 的促进作用。 1 9 8 2 年，美国物理学家h o p f i e l d 提出一个用于联想记忆和优化计算的新的神经网 络模型一h o p f i e l d 神经网络模型3 6 】，引入了能量函数的概念，通过它来分析网络的动力 学性质，并给出了网络稳定判据。在此基础上，1 9 8 4 年，h o p f i e l d 将神经元的响应函 数由二值响应改为模拟响应，提出了连续神经网络模型【3 7 l ，其中神经元的动态方程可 用运算放大器来实现，使得可以用电子线路来仿真神经网络模型，也为神经网络的硬 件实现和神经计算机的研制奠定了基础。次年，h o p f i e l d 和t a n k 利用h o p f i e l d 神经网络， 对求解著名的n p 完全问题( n p h a r dp r o b l e m ) - - 旅行商问题( t r a v e l i n gs a l e s m a n p r o b l e m ) ”进行了成功的探索【3 引。尽管还有些不足之处，但h o p f i e l d ：神经网络在许多方 面所显现出的巨大潜力无疑重新燃起了人们对神经网络的新的希望，有力地推动了神 经网络的研究。同时吸引了越来越多的人投入到神经网络的研究中来。j 下是由于众多 专家学者的不懈的努力，神经网络的新模型不断提出，研究进一步深入，迎来了人工 神经网络研究的新高潮。 与此同时，一批有影响的神经网络研究成果相继出现。f e l d m a n n 和b a l l a r d 提出的 连接主义网络模型【3 9 】- 【4 ，指出了传统的人工智能“计算”和生物“计算”的区别，并给出 了并行分布处理的计算原则。1 9 8 5 年，h i n t o n 和s e j n o w s k y 借用统计物理学的概念和方 法，提出t b o l t z m a n n ；l 模型f 4 2 】- 【4 5 1 。在该模型中，首次采用了多层网络的学习算法， 在学习过程中应用模拟退火技术来保证整个系统趋于全局稳定点。1 9 8 6 年，r u m e l h a r t 和m c c l e l l a n d 等人提出并行分布处t 早_ ( p a r a l l e ld i s t r i b u t e dp r o c e s s i n g ，简称p d p ) 理谢4 6 | ， 致力于认知微观结构的探索，同时发展了多层网络的误差反向传播( b a c k p r o p a g m i o n ， 9 北京化t 人学硕 j 学位论文 简称b p ) 算法。b p 算法根据学习误差的大小，从后向前修正各层神经元之间的连接权 值。经过不断的学习和修正，可使学习误差极小化，从而达到学习的目的。b p 算法的 实践证明，人工神经网络具有很强的运算能力，可以解决许多具体问题。b p 算法已成 为迄今为止应用最为普遍的神经网络学习算法。此外，这一时期的出色的工作还 有：k o s k o 提出了最早用于学习的双向联想记忆网络【47 1 。神经网络计算机的先驱 h e c h t n i e l s e n 贝1 j 提出了另一种反向传播络( c o u n t e r - p r o p a g a t i o n ) 模型1 4 引，可用于图像 压缩和统计分析等。h o l l a n d 提出的分类系冽4 9 】类似于以规则为基础的专家系统，其发 现和改进规则的学习算法是对专家系统的重要发展。1 9 8 8 年，蔡少堂等人提出了细胞 神经网络模型【5 0 】，与一般的神经网络一样，它是一个大规模非线性模拟系统，同时又 具有细胞自动机的动力学特征。所有这些，都对神经网络的模型和理论的发展做出了 很大的贡献。 在神经网络模型和理论不断取得进展的同时，神经网络的实际应用也r 益广泛。 在许多领域，如模式识别，优化计算，专家系统，信号处理，自动控制和地球物理等， 都有成功的应用实例。在神经网络的硬件实现方面，也取得了可喜的成果。 随着神经网络的迅速发展，1 9 8 7 年在美国圣地亚哥召开了第一届神经网络国际会 议，并成立了国际神经网络学会( i n n s ) 。自1 9 8 8 年起，i n n s 和i e e e 联合召开每年一 次的国际学术会议( 1 9 9 2 年改为两年一次) 。1 9 9 0 年，i e e e 神经网络会刊问世，加上各 种学术刊物的神经网络特刊，专辑相继推出，进一步推动了人工神经网络的研究和发 展。在国际研究潮流的推动和影响下，八十年代后期，我国人工神经网络的研究开始 起步。1 9 9 0 年1 0 月，中国自动化学会、计算机学会、心理学会、电子学会、生物物理 学会、物理学会和通信学会等八家学会联合召开了“中国神经网络首界学术大会”。会 议中所探讨的内容涉及脑功能和生物神经网络模型、神经生理与认知生理模型、人工 神经网络模型、神经网络理论、新的学习算法、神经网络和组合优化、人工智能、信 息处理、自动控制以及模式识别等。1 9 9 2 年度的国际神经网络学术会议在北京召丌， 表明我国的神经网络研究已在国际上占有一定的地位。近年来，国内从事这方面研究 的队伍f 1 益壮大，涌现出一大批具有很高水平的学者，取得了许多理论和应用成果 5 1 1 。 5 3 1 。 2 4 神经元网络理论概述 2 4 1 神经网络的概念及特点 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r ko ra n n ) 简称为神经网络，它是在 第二章人t 神绛网络简介 用现代神经生物学和认识科学对人类信息处理研究所获成果的基础上提出来的，是由 大量简单的处理单元按一定规则广泛互连而成的网络，是由基本处理单元即神经元、 神经元之间的连接方式、以及训练规则等三要素所决定的，是被用来描述或模拟人脑 的功能而提出的一种人工模型。 关于神经网络的概念，人们从多个方面加以了概括。a l e k s a n d e 和m o r t o n 于1 9 9 0 在其书中指出【”】：所谓神经网络是一种大规模并行分布式的处理系统，它具有与人脑 相似的功能，如能存储知识，并利用它们进行学习；完成学习的程序被称为学习算法， 它是按照一定规则去改变连接权值，以便达到预期的目标。 神经网络具有的特点包含大规模并行计算能力、非线性、可靠性及容错性、自组 织及自适应性、学习能力、分布式存储、存储与计算相结合、联想能力等。它能模拟 人脑的思维，把大量的神经元连成一个复杂的网络，利用己知样本对网络进行训练， 即类似于人脑的学习；让网络存储变量间的非线性关系，即类似于人脑的记忆功能：然 后利用存储的网络信息对未知样本进行分类或预测，即类似于人脑的联想功能。 神经网络主要的优点可归纳为以下三个方面： 第一，具有自学习功能。例如实现图像识别时，若先把许多不同的图像样板和相 应的识别结果输入人工神经网络，网络就会通过自学习功能，进而逐渐学会识别类似 的图像。自学习功能对于预测有特别重要的意义。预期未来的人工神经网络计算机将 为人类提供经济预测、市场预测、教益预测，其前途是很远大的。 第二，具有联想存储功能。人的大脑是具有联想功能的。如果当你想起你一位故 友，你就会联想起他的许多事情。用人工反馈型网络可以实现这种联想。 第三，具有高速寻找优化解的能力。寻找一个复杂问题的优化解，往往需要很大 的计算量，利用一个针对某问题而设计的反馈型人工神经网络，发挥计算机的高速运 算能力，可能很快找到优化解。 2 4 2 神经元网络的研究内容 神经网络的研究内容相当广泛，主要的研究工作包括以下几个方面： 1 生物网络原型研究：从生理学、心理学、解剖学、脑科学、病理学等生物科学 方面研究神经细胞、神经网络、神经系统的生物原型结构及功能机理： 2 建立理论模型：根据生物原型的研究，建立神经元、神经网络的理论模型，其中 包括概念模型、知识模型、物理化学模型、数学模型等，它是生物原型的科学抽象， 也称为广义模型； 3 网络模型与算法研究：在理论模型研究的基础上构造具体的神经网络模型，以实 现计算机模拟或准备制作硬件，包括网络学习算法的研究，它是广义模型的物理实现 鼙 北京化r 人学顾i ：学位论文 或数学描述，也称为技术模型： 4 人工神经网络应用系统：在网络模型与算法研究的基础上，利用人工神经元组成 实际的应用系统，如为完成信号处理或模式识别的功能、构造专家系统、制成机器人 等，可制作专门的硬件来实现等。 人工神经网络的研究内容侧重于网络模型与算法和应用系统两个方面。 2 4 3 神经元网络常见的类型及应用 神经网络从不同的角度可分为不同的类型。按照性能可分为连续型与离散型网 络，确定性和随机性神经网络；按照结构可分为反馈神经网络与前向神经网络；按照学 习方式可分为有监督学习与无监督学习：另外按照连接突触性质可分为一阶线性关联 网络与高阶非线性关联网络闪。迄今为止，在人工神经网络研究领域中，有代表性的 网络模型己有数十种，而学习算法的类型更是难以统计。为便于了解，几种较为常见 的神经网络类型的详细情况介绍如下： 前向网络：较为典型的代表有：1 ) m p 神经元模型；2 ) 单层神经网络；3 ) 多层前向网络。 4 ) a d a l i n e 网络等： 反馈网络：典型代表包含：1 ) h o p f i e l d 网络；2 ) 双联想记忆网络等； 随机网络：包含：1 ) b o l t z m a n 机；2 ) c a u c h y 机等； 自组织网络：包含：1 ) h a m m i n g 网络；2 ) 自组织特征映射网络；3 ) 认知机；4 ) 自适应共 振a r t 网络等； 其他类型：包含：1 ) 脑模型联接控制器；2 ) 模糊人工神经网络；3 ) 分形人工神经网络；4 ) 遗传算法构造的人工神经网络等。 人工神经网络所具有的非线性特性、大量的并行分布结构以及学习和归纳能力使 其在诸如建模、时序序列分析、模式识别、信号处理以及控制等方面得到广泛的应用。 尤其面对缺少物理或统计理解、观察数据中存在着统计变化、数据由非线性机制产生 等棘手问题，神经网络能够提供较为有效的解决方法。随着神经网络技术的发展，其 用途r 益广泛，具体而言主要用于解决一下几类问题： l 、传感器信息处理 第一：章人t 神经嗍络简介 2 、优化问题计算 神经网络的大部分模型是非线性动态系统，若将所计算问题的目标函数与网络某 种能量函数对应起来，网络动态向能量函数极小值方向移动的过程可视作优化问题的 解算过程。这方面的应用包括组合优化、条件约束优化等一类求解问题，如任务分配、 货物调度、路径选择、组合编码、排序、系统规划、交通管理以及图论中各类问题的 解算等。 3 、信息的智能化处理 神经网络适宜于处理具有残缺结构和含有错误成分的模式，能够在信源信息含 糊、不确定、不完整，存在矛盾及假象等复杂环境中处理模式，突破传统专家系统的 障碍。它根据己学会的知识和处理问题的经验对复杂问题做出合理的判断决策，或对 未来过程做出有效的预测和估计。这方面的主要应用是：自然语言处理、市场分析、预 测估计、系统诊断、事故检查、密码破译、语言翻译、逻辑推理、知识表达、智能机 器人、模糊评判等。 4 、神经元控制 神经元控制是最近几年形成的一个分支，其发展迅速而平稳。所有控制理论都存 在一个共同的局限性：就是要求预先知道被控制对象的数学模型，但实际上许多对象具 有复杂的不确定性和时变性，也还有复杂的非线性。例如有的是己知但难于用数学语 言描述，有的是未知非线性，这会造成无法建模或很难建模。虽然在控制理论中有系 统辩识的手段，但是对于非线性时变系统尚无成熟的和系统的辩识理论及方法，所以 要实行有效的实时控制就很难了。人工神经元网络可以表示任意非线性关系并具有学 习能力，因而给解决这一类问题提供了新思想和新方法。 1 9 6 0 年，gw i d r o w 和m e h o f 首先把神经网络引入控制系统。2 0 世纪6 0 年代初， 美国“阿波罗”登月计划中，k i l m e r 和m c c l l o c h 等人根据脊椎动物神经系统中网状结构 的工作原理，提出了一个k m b 模型，以使登月车在远距离复杂环境中具有一定的自制 能力。神经网络在控制方面的研究丌始集中于在自适应控制和智能机器人控制，逐渐 发展到专家系统和模糊神经元系统方面。 5 、信号处理 神经网络的自学习和自适应能力使其成为对各类信号进行多用途加工处理的一 种天然工具，尤其在处理连续时序模拟信号方面有很自然的适应性。这方面的主要应 用有：自适应滤波、时序预测、谱估计和快速傅立叶变换、信号增强降噪、噪声相消、 信号特征检测等。 北京化t 人学硕i ：学位论文 2 5 人工神经元模型 人的大脑中存在着大量的彼此复杂联结组合的神经细胞，神经细胞具有激发和非 激活两种状态。利用这种结构进行数学建模，在计算机中模拟人脑神经细胞的活动， 便构成了人工神经元网络。人工神经元网络是由多数的神经元以及联结神经元的神经 连接( 权值) 构成。如图2 1 所示，神经元网络中单一神经元的状态可以用下式来表示： v + 1 ) = 厂( v ，( ，) 一9 ) ( 2 - 1 ) j 图2 - 1神经元模璎 f i g u r e 2 1 n e u r o nm o d e l 鳓号神经元通过神经元连接权睨对第i 号神经元的输出电位产生影响，1 ，( ，+ 1 ) 是第i 号神经元的输出信号，只是阈值，伪神经元的激活函数。对于激活函数，一般情 况下多采用以下三种基本形式： v 0 u ll ( a ) ， 矿 o l u u t ( c ) 1 4 ( b ) 第一二章人t 神经m 络简介 图2 - 2 ( a ) m c c u l l o c h p i t t s 函数( b ) s i g m o i d 函数( c ) 迟滞m c c u l l o c h p i t t s 函数 f i g u r e2 - 2 ( a ) m c c u l l o c h - p i t t sf u n c t i o n ( b ) s i g m o i df u n c t i o n ( c ) h y s t e r e s i sm c c u l l o c h p i t t sf u n c t i o n ( a ) m c c u l l o c h p i t t s 函数： 这是激活函数中最简单的一种，由m c c u l l o c h p i t t s 于1 9 4 3 年提出。神经元的输出 电位是由输入信号之和u ，的高低直接决定。 _ 亏厂c u ，= 三孑：三； 。2 2 ， ( b ) s i g m o i d 函数： s i g m o i d 函数是单调递增的连续函数，此种函数模式可以进行微分变换。 m ) 2 百，o ) f i g u r e5 - 5t h er e l a t i o n s h i p sb e t w e e n 8a n ds t e a d ys t a t e s ( a 8 、 根据图5 5 ，我们从仿真结果可以看到，在仅 夕的情况下，随着p 的增大， 北京化t 人学硕l j 学位论文 稳定状态下顶点个数会陡然增大，但是当, 8 1 0 0 ，即a 与夕的比值小于5 0 之后， 夕值的变化对稳定状态下顶点个数值没有显著影响。 基于以上分析，我们得出如下三个结论： 1 在a 时，随着值的增大，对稳定状态中顶点个数具有显著的影响，而当仅与 夕的比值大于一定值的时候，夕的增大对顶点个数的影响会逐渐趋缓。 2 在6 t 1 0 时，随着p 的增大，稳定状态下顶点的个数值具有显著减少的趋势。 另外，在研究图5 - 6 的变化趋势当中发现的规律恰好和5 2 2 节当中的变化趋势相 互印证。在图5 5 中，从1 0 变化到1 0 0 的过程当中，稳定状态下顶点个数值发生 显著的增大变化，这个区间正好对应着p 5 0 这个区间，恰好与图5 - 6 中p 5 0 时， 稳定状态下顶点个数值的显著变化相对应。 同理，图5 - 6 的变化趋势和5 2 1 节当中的变化趋势也是相互印证的。由于口由 1 0 逐渐增大至5 0 0 ，相当于p 从1 0 变化到5 0 0 ，而根据本节的结论2 可知，这个区 间恰好是p 值变化对稳定状态下顶点个数值具有显著影响的区间。 综合5 2 1 ，5 2 2 和本节的研究，我们可以得出如下的结论： p 值是决定稳定状态下顶点个数值的一个重要的决定参数，在p 值恒定的情况 下，改变口，的值并不会对稳定状态下顶点个数值产生显著影响。 5 2 4 参数d 的变化对稳定状态的影响 在前面的几个章节，我们研究了口，值的变化与最终稳定状态下顶点个数值的 变化关系，在这一节里，我们将研究参数d 的变化与稳态顶点个数值之间的关系。 由式( 4 1 7 ) 可知，参数d 位于能量函数的惩罚项中，如果选择一个恰当的值，当 超图中有一条边未被覆盖时，惩罚项的值将会增大。考虑两个极限的情况。 1 如果d 非常小，即d = 0 时，假如超图当中某一条边没有被覆盖，则惩罚项不能够 体现出惩罚作用。 2 如果d 非常大，例如d = k + l 时，则对于每一条边都会施加惩罚，同样也失去了惩 罚项进行有选择的惩罚的意义。 因此，讨论d 值的变化与稳态顶点个数值的关系具有非常重要的意义。 在进行仿真实验室，取口= 2 0 ，= 1 0 ，d 的值从o 0 2 到5 0 变化，计算步长设 置为o 0 2 。所选取的随机图是p = 0 0 1 ，顶点数分别为9 0 ，1 0 0 ，1 1 0 ，1 2 0 的四个标准图， 详细参数参照表5 1 。对于每一步仿真运算，仍然足取1 0 0 次收敛的稳定状态下顶点 个数的平均值，最终的仿真结果如图5 7 所示： 3 9 北京化丁人学硕f ：学位论义 1 4 0 9 0 点l o o 点1 l o 点一1 2 0 点 n onq,-mnq_cdnh on o o hc do h _西 o n _ ooo hh-_d nnn _qq v a i h eo fd 图5 - 7 稳定状态解与d 的关系 f i g u r e5 - 7t h er e l a t i o n s h i p sb e t w e e nd a n ds t e a d ys t a t e s 根据图5 7 的仿真结果，我们可以发现，在d 从o 0 2 到5 0 的变化过程当中，经 历了两个阶段。 1 当0 0 2 d 2 0 时，随着d 的增长，最终稳定状态下顶点个数值受到非常 大的影响，并且呈近似线性的增长趋势。 2 当d 2 0 时，所取得的稳定状态下顶点个数值为超图的总顶点数，即，所 有顶点都被包含在解集当中。 讨论 考察x ，= 2 妒d 。一口，此项为每个神经元的输入量的表达式，它的大小表示某 e m 个顶点所在的边数的多少。而在神经元网络计算时，神经元网络的输入值大于0 时， 此神经元的状态将被置l 。这也符合人类的推理过程，即包含在较多的边上的点，优 先被考虑包含在最终解集当中。结合图5 7 ，我们可以认为，如果d 偏大的话，会人 为增大每个神经元的输入值，结果造成了每个神经元的输入累加均大于0 ，这就意味 着，每一个神经元的状态都将被置l ，这也恰恰与图5 7 中d 2 0 时的趋势相吻合。 通过对d 值与解集状态相对关系的研究，我们获得了非常重要的信息，即如何选 取d 的初始值，以及d 取值的可选区间。 5 3 本章小结 本章对标准离散型h o p f i e l d 神经元网络进行了程序仿真实现，验证了标准离散型 h o p f i e l d 神经元网络在非稳定状念下，在运行过程中网络的能量将呈梯度下降趋势。 另外，以随机生成的标准超图库为基础，对m s c 问题的能量函数中，乜，d 三个 第五章基十h o p f i e l d 旧络的m s c 问题的程序实现 可变参数的变化对最终收敛的稳定状态下顶点个数的影响进行了研究。 首先研究了在其他两个参数保持恒定的情况下，单独变化个参数对最终稳态顶点 个数值的影响。并且发现了当a p 时，n 值的变化与稳态顶点个数值具有近似线性的 关系，而当a 1 0 时，稳态顶点个数值将随p 的变化发生显著变化这一规律。 在5 2 4 节当中，我们也对m s c 问题能量函数中惩罚项当中的可变参数d 进行了 研究，并且根据趋势图的变化情况，结合决定h o p f i e l d 网络结构的输入值的表达式， 对变化趋势进行分析，揭示了趋势图与输入值表达式的逻辑含义所具有的一致性。 值得注意的是，虽然调整参数可以影响离散型h o p f i e l d 神经元网络最终稳定状态 下解的大小，但针对于每一次的收敛过程，网络只能够收敛到一个稳定状态，即一个 极小值。标准离散型h o p f i e l d 神经元网络虽然能够收敛到一个稳定的极小点，但是却 不能够从局部最小点跳出，无法继续搜索其他的极小点，这就造成了局部最小问题。 在下一章当中，我们将研究离散型h o p f i e l d 神经元网络的局部最小问题，并对跳 出局部最小的方法进行讨论。 4 l 北京化t 人学硕i ：学位论文 第六章跳局部极小点的算法研究 第六章跳出局部极小点的算法研究 6 1 神经元网络的局部最小问题 对于所有的神经网络模型，当用其于解决优化问题时，如果采用能量梯度下降的 方式，则存在一个普遍的问题，那就是局部最小值问题1 5 j 。因为一旦网络的状态到达 一个极小点，那么能量的变化率就成为零，从而网络的状态将不再发生变化，也就是 说，尽管还有可能有更优的极小点存在，但是神经网络的计算陷入了一个极小值谷底， 即局部最小，而且不能够从此谷底跳出。如果神经元网络动态运行到达一个极小点， 本次收敛过程将结束。下面我们用图6 1 来说明局部最小问题。 图6 1 局部最小不意图 f i g u r e 6 一lm a po fl o c a lm i n i m u m 在图中横坐标表示的是网络的状态，纵坐标表示的是网络的能量，可以看出，能 量图中每个低谷便对应网络的一个局部最小值，因为网络是沿着梯度下降的方向运 行，所以无论网络的初始点在哪里，网络都将最终收敛的相应的最低点( b ，c ，d ，e ) ， 也就是网络的局部最小值，比如网络的初始状态在a 点，则网络便会沿着梯度下降方 向运行，所以网络将首先达到b 点，而b 点就是一个局部最小值，也就是说在b 点网络 将达到稳定状态，即： j f 竺= 0 ( 6 1 ) d t 当网络达到稳定以后，如果没有外部的作用网络将无法从局部稳定状态跳出，从 而也就不能到达网络的全局最小值e 点，所以得到的解也就不是全局最优解。为了解 决这个问题，许多该领域的研究者提出了不同的方法，其中比较成功的有：随机 h o p f i e l d 口- x j 络是一个比较成功的算法，在该模型中给每个神经元的输入加入了随机因 4 3 鑫奎进 北京化t 人学硕i j 学位论文 子，从而也可以尽量避免局部最小值 6 3 1 ，另外一种比较成功的解决局部最小值问题的 算法是模拟退火算法( s a ) ，在该方法中，在网络到达极小值时，利用随机概率来使得 网络可以尽可能的跳出局部最小点，而收敛于近似全局最优解。但是，由于这些方法 都存在随机因素，就不可避免的出现一个问题，就是网络的运行是无方向性的，从而 需要耗费大量的时间，这个问题尤其在处理大规模的问题时，显得尤为突出。例如， 在模拟退火算法中，尽管得到的解是近似最优解，但是有时用的时间往往比穷举法所 用的时间还要长，从而使得该算法往往难以在实际中得以应用，在很大的程度上失去 了其意义。 在6 2 节当中，我们将介绍其他研究者针对m s c 问题所采用的模拟退火算法以及 h o p f i e l d 神经元网络算法。 6 2 以往研究者的算法实现及分析 在以往的文献当中，除了经典的贪婪算法之外，介绍解决m s c 问题的算法比较少， 其中比较成功的有s a 模拟退火算法以及k a z n a c h e ya n dj a g o t a 6 2 1 的基于离散型 h o p f i e l d 神经元网络的二分搜索算法，被称作h s c n 。这两个算法均按照一定规则使收敛 过程能够跳出局部最小点。下面将简要介绍贪婪算法以及这两种致力于解决局部最小 的算法。 6 2 1 贪婪算法( g 2 ) 在这里我们将介绍一种经典的贪婪算法【6 2 1 ，我们称其为g 2 。这个算法的思想是， 从边的集合当中，抽取一个最大的边的集合m ，使得这个边的集合当中，任意两条边 都没有共同的顶点，这个边的集合中的所有顶点构成了一个集合覆盖s 。因为如果有 一条未被顶点集合s 覆盖的边e 存在，则e l ) m 应该是最大的边的集合，这与集合m 为最大的边的集合相矛盾。我们将g 2 算法进行了程序实现，描述如下： a l g o r i t h mg 2 i n p u t ：h y p e r g r a p hh ( y ，e ) o u t p u t ：s e tc o v e rs 1 弘彩 2 f o ri = lt om 3 1 f ( e ir 、s = 矽) 4 s = s u 耐 5 r e t u r ns 很显然，第2 步的外层循环的时f h j 复杂度为d ( 所) ，内层循环中第4 步的时l 日j 复杂 第六帝跳局部极小点的算法研究 度为d 0 ) ，所以，g 2 算法的时间复杂度为o ( m n ) 。值得注意的是，经过仿真实验证明， g 2 算法是这罩仿真对比当中运行速度最快的一个，但是仿真的结果却不理想。 6 2 2 模拟退火算法( s a ) 模拟退火算法( s i m u l a t e d a n n e a l i n g ) 的思想最早是m e t r o p o l i s 等提出的，1 9 8 3 年 k i r k p a t r i c k 等意识到组合优化与物理退火的相似性，将其用于组合优化问题。模拟退 火算法的主要思想是：在某一初始温度下，伴随着温度参数的不断下降，结合概率突 跳特性在解空间中随机寻找目标函数的全局最优解，即处在局部优解的时候，能够概 率性地跳出，以期望找到全局最优解。 模拟退火算法是一种通用的优化算法，它的算法简要描述如下： a l g o r i t h ms a ( 正万) i n p u t ：h y p e r g r a p hh ( v , e ) o u t p u t ：s e tc o v e rs 1 【g e ta ni n i t i a ls e tc o v e rsa n dg e ta ni n i t i a lt e m p e r a t u r et 0 】 2 w h i l e ( t 8 ) 奢 3 【p i c kar a n d o mn e i g h b o rs o f 司 4 i f ( i ss e tc o v e r ) ( i m p r o v i n gs t a t e ) 8 r e c o r dc u r r e n ts t a t es = s 9 e l s e ( w o r s e n i n gs t a t e ) 10 r e c o r dt h ew o r s e n i n gs t a t es = s w i t ht h ep r o b a b i l i t ye 叫门 。 1 1 s e t ，= r t ( r e d u c et e m p e r a t u r e ) ( 0 r 1 ) 12 r e t u r n s e tc o v e rsf o rs a 】 在算法中t 用来模拟原本在退火算法当中的退火温度，随着t 的减小，接受非正解 的概率p 将趋近于0 。厂是小于1 的正常数，用来控制退火温度。下面我们计算一下使用 退火算法解决m s c 问题时的时间复杂度。第3 步到第1 1 步的循环中，由于只有在t 0 ，所以z x e l o ，世2 0 。 为了使能量的变化量丝在至少在第f 号神经元状态变化z 下，具有梯度下降的 趋势，即 丝 0 ( 6 7 ) 令 口+ 2 口盯巧口。， d = + 万a t , ( 6 8 ) 2 口d 其中，万是一个正常数，用来控制网络参数变化的程度。将式( 6 8 ) 代入式( 6 3 ) ， 第i 号神经元的状态变化能量变化r 所引起的网络能量变化，可以表示为 业= 一纠 9 ， l p = l j 很显然 丝=协纠lz0l e = l 慨 j 由式( 6 1 0 ) 可知，通过式( 6 8 ) 的启发式学习之后，使用新的d 值更新神经元网络的 结构参数，可以使原本陷入的局部最小点的低谷，转变为梯度下降过程中的一个点， 从而使离散型h o p f i e l d 神经元网络能够继续沿能量梯度下降的方向运行，从而可以跃 出局部最小点的低谷，继而寻找下一个局部最小点。 同时，值得注意的是，式( 6 8 ) 也可以作为确定d 值的依据。 6 3 2 基于参数d 跳出局部极小的程序仿真实现 在第四章对最小集合覆盖问题进行离散型h o p f i e l d 网络建模的基础七，并且根据 6 3 1 节提出的改变参数d 从而帮助离散型h o p f i e l d 神经元网络跳出局部最小点低谷的 理论方法，在这一节当中，我们将进行算法的程序仿真实现。 在各类组合优化问题中，有的问题有明确的条件使得网络的运行在达到这个条件 时，使之结束，比如八争后问题( n - q u e e n s ) f d 题。在该问题中，当网络的能量为零时 北京化t 人学帧f j 学位论文 表示网络找到了一个解。但是有的问题却没有如此的收敛判定条件，即网络没有一个 明确的条件决定网络运行结束，最小集合覆盖问题就属于这类问题。因此，我们在算 法中设置了一个常量( 1 e a r nl i m i t ) 来限制跳出局部最小的次数，在算法运行过程中，如 果对网络参数的更新次数达到了l e a r nl i m i t ，那么我们就使算法终止。通常，根据可 以接受的运算时间以及问题的复杂程度来决定l e a r nl i m i t 的大小。对于最小集合覆盖 问题，我们经过事先的试算，发现离散型h o p f i e l d 神经元网络可以在l o 次学习之内找 到比较好的结果，所以我们选取2 0 作为仿真计算时的最大学习次数。基于此限制，我 们的算法可以描述如下： a l g o r i t h ma h n n ( n ，岛万) i n p u t ：k - c a r d i n a l i t yh y p e r g r a g hh ( e e ) o u t p u t ：s e tc o v e rs 1 1 e a r n t i m e s = o - l e a r n l i m i t = 2 0 , 口= 2 0 ，= 1 0 ，d = ( k + 1 ) 2 2 m a ph y p e r g r a p hi n t oa h n n 3 r a n d o m i z ei n i t i a ls t a t e sf o rn e u r o n ss a y 0o r1 】 4 w h i l e ( 1 e a r n t i m e s l e a r n l i m i t ) 5 s = s t a b l es t a t e sa f t e rp r o p e r g a t en e u r o nn e t w o r k s 6 i f ( s t a b l es t a t es i ss e tc o v e r ) 7 i “l s ii ss m a l l e rt h a nc u r r e n tm i n i m u ms ) 8 s = s b e s t d = d 9 e l s e 10 r a n d o m l ya d da b s e n tv e r t i c e si n t os u n t i ls b e c o m e sa s e tc o v e r 11 【c a l c u l a t en e wdf o l l o w i n gt h eu p d a t i n gl a w 12 r e m a p t h eh y p e r g r a p hi n t oa h n nw i t ht h es a m e 口，b u tn e w d 】 1 3 ，阳，咒f i 埘p s + + 1 4 r e t u r n s t a b l es t a t ef o ra h n nw i t hsa n db e s t d a h i 算法的时间复杂度 参考6 2 2 节当中对h s c n 算法时间复杂度的研究，同理可知，a h n n 算法的第5 步 时问复杂度为o ( n s ) ，s 是每个神经元计算所需的时i 日j ；第6 步的时问复杂度为d ( 朋玎) ；第 7 步时间复杂度为d ( 刀) ；第1 0 步的时间复杂度o ( m n 气而第1 1 步，也就是跳出局部最 小的启发式算法，具体分析如下： 在第l l 步当中，我们对所有神经元都按照式( 6 8 ) 进行计算，进而去掉明显不合理 的d 值项，然后在候选的神经元所对应的d 值当中随机抽耿一个作为本次更新网络参数 的d 值。因此，第1 1 步的理论时间复杂度f f ；j o ( m n 2 ) 。但是，在算法设计的时候，我们特 别注意利用已经存在的网络参数，从而避免完全重新计算，经过修改后第1 l 步的实际 时问复杂度为d ( 2 ) 。因此，第1 0 步的时间复杂度成为内层循环的最大项，综上所述： 5 2 第六章足；) t l l ；局部极小点的算法研究 a h i 州算法的时间复杂度是o ( 2 0 m n ? ) 。 从时间复杂度方面来看，a h n n 算法时间复杂度比s a 算法矛d h s c n 算法都高很多， 并不是因为第1 1 步的核心部分算法消耗时间长，而是因为每次收敛结束需要验证结果 是否为f 解并且在第1 0 步消耗了过多的时问。 在图( 6 6 ) 中给出了该算法的流程图。可以看出，在该算法中包括两个阶段，第一 个阶段( p h a s ei ) 是离散型h o p f i e l d 网络的运行阶段，在这个阶段中，网络按照标准的 h o p f i e l d m 络能量梯度下降的方式，到达稳定状态；第二个阶段( p h a s e l i ) 是基于参数d 的跳出局部极小的启发式算法计算阶段。在整个算法中，两个阶段交替执行，直到学 习次数达到预定的常数口e a r nl i m i o 。 b e g i n 一 k 。一 6 3 3 实验数据分析 r u nh n nw i t hp r e s e n t w e i g h t sa n dt h r e s h o l d s u n t i li tr e a c h e sa s t e a d y s t a t e ( p h a s e l ) r 上 t h er e s u l tl s b e t t e rt h a nt h e l a s t ? 、_ 面= i 。s t u d y i n gl a w 。t h e n u p d a t es t r u c t u r e p a r a m e t e r so fa n n ，( p h a s e i i ) 一i 一一 w h e t h e r t 0e n d n t h ea l g o r i t h m ? 。 y e n d 图6 - 6 程序流程图 f i g u r e 6 - 6p r o g r a mf l o wc h a t 在6 3 1 节理论证明以及6 3 2 节中仿真程序实现的基础之上，本节将对a h n n 仿真 算法的能量趋势进行