基于人工神经网络的图的顶点覆盖问题的算法研究

《基于人工神经网络的图的顶点覆盖问题的算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、华中科技大学硕士学位论文摘要入工神经两络舆有大撬摸并行处鹫、容错往帮学习能力等特性，在联想记忆、模式识剐、组合优化以及各种寤适应系统中，有糟广泛酹应掰。80年代中期，Hopfield提出了一种全曩连堑神经阏络模型，并桶用所定义的许簿能鳖函数，成功蟪求解了计算复杂度为NP完全垄的优化问题。在这种模羹中，根据能量涵数的定义，每一个神经元就可以髑运算放大器来实现，整个网络就是一个动力学系。所甄，人工神经网络成为入们研究组合优纯问题的强有力的工其。组合最优化是一个新兴的领域，它与数学簸优纯一样是运筹学的～个组成部分，而且是偏重j堂z用的数学领域。，本文简述了人工神经两络在图与组合优纯问题研究

2、中的进展情况，并对神经网络能薰函数的动力学性质迸行了分析，讨论了方程的特征向量与网络稳定住的关系。本文对图与优化组合同题中的一个典受问粮，郎图的顶点覆盏问题的算法进行了研究。图的顶点覆盖问题是一个困难的NP一完全问题，并且有许多良好的应用。本文在已有的应用Hopfield神经网络模型来求解蘑的顶点覆盏问题的罄础上，给蹬了一种改进酌带动羹因子的新型的Hopfield神经网络算法，并进行了理论分析此算法产生最小顶点覆盏。实验仿真结果表明，本算法其有较商的收敛速度和求解精度。本文提出的算法对予解决图与组合优纯中的其他问题如图的划分问题、图的最大独立集问题、图的最大独立团问题等具有一定的参考

3、价值。关键词：毒枣经骥络}缀合优纯}§2鬟函数?霸鸶囊i潺。毒)一，夕～华中科技大学硕士学位论文AbstraetAxtiticialneurainetworksareverypowerfulusedinassociativememory,paaemclassifcation,combinatorialoptimizationandadaptivesystemwithitscharacteristicsofmassivelyparallelprocessing，fault-torlanceandself-learning．1nmiddleeighties，aninterconnecti

4、oncontinuous—timecontinuous—statenetworkWaspresentbyHopfield．HesucceededinsolvingoptimizationproblemthatthecomputationalcomplexdegreeisNPwithmodifyingenergyfunction．Inthisnetwork’Smodel，neuronscanbemadeinanalogcircuitthatconsistofsomeamplifiers，risistancesandcapacitorsaccordingtomodifyingenergy

5、function．TheartificialneuralnetworksthatmadeinanalogcircuitCanbeanalyzedandemulatedwithpropertiesofdynamicsystem．Soartificialneurainetworksbecomeallimportanttoolinsolvingcombinationaloptimizationproblem．Combinatorialoptimizationisanewfiledandisanimportantpartofoperationreaserchlikemathematicopt

6、imization，what’Smore，itpaysattentiontoapplicationfield。Thispaperintroducestheprogressofartificialnetworksincombinatorialoptimization，analyzingthedynamiccharacterofneuralnetworksenergyfianction，discussingtherelationshipbetweencharactervectorandnetworkstability．Inthispaper’onetypicalproblem，graph

7、veaicescoveringproblemisstudingbasedonartificialneuralnetork，GraphverticescoveringproblemisanNPcompleteproblem，havinggoodapplications．ThispaperpresentsallimprovedHopfieldneuralnetworkalgorithmwitilmomentumfactorbasedontheproposedH