饱和动态神经网络求解最大团问题研究

论文摘要

最大团问题是一个经典的图论问题,其目标是找出给定的某个图的最大完全子图。最大团问题从提出以来,许多学者都进行过大量的研究,并应用于模式识别、聚类分析、图着色、超大规模电路设计等许多领域。由于最大团问题是一个NP难问题,一种合适的解决它的办法是设计各种各样的启发式算法。人工神经网络启发式算法即是其中之一。Pekergin等人于1999年提出了一种称之为是饱和线性动态网络算法(SLDN算法)的神经网络求解最大团的算法。受此算法启发,本文中,我们提出了一种新的最大团问题的神经网络求解算法,其主要特点是在SLDN算法的基础上引入了非线性自反馈环。本文主要工作如下:1、回顾了最大团问题和神经网络的基本概念、研究背景及研究现状。阐述了使用神经网络求解最大团问题的研究历史和取得的一些研究成果。2、详细描述了饱和线性动态网络算法。由于饱和线性动态网络算法主要采用的是梯度下降类型的优化技术,从而有可能陷入局部最优。这是饱和线性动态网络算法在求解最大团问题时存在的主要缺点。3、提出了一种新的最大团问题的神经网络求解算法。新算法主要是在SLDN算法的基础上引入了非线性自反馈。仿真实验发现自反馈的引入能够在一定程度上防止神经网络陷入局部最优,统计结果也表明新算法的整体性能要优于SLDN算法。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 最大团问题概述
• 1.2 人工神经网络概述
• 1.3 神经网络解最大团问题简介
• 1.4 本文工作与论文结构
• 2 最大团问题与神经网络
• 2.1 最大团问题及定义
• 2.1.1 一些基本概念
• 2.1.2 图论中最大团问题的定义
• 2.1.3 最大团问题的0-1 优化描述
• 2.2 最大团问题相关研究方法
• 2.2.1 确定性算法
• 2.2.2 启发式算法
• 2.3 神经网络发展及神经元模型
• 2.4 神经网络结构
• 2.5 神经动力学
• 2.6 本章小结
• 3 神经网络解最大团问题
• 3.1 几种递归神经网络及模型
• 3.1.1 Hopfield 神经网络模型
• 3.1.2 Cohen-Grossberg 定理
• 3.1.3 盒中脑状态模型
• 3.2 饱和线性动态网络算法
• 3.3 用带非线性自反馈的神经网络解最大团问题
• 3.4 各种网络间的关系
• 3.5 实验结果及分析
• 3.6 本章小结
• 4 总结与展望
• 致谢
• 参考文献
• 附录