求解sat问题的拟人退火算法

《求解sat问题的拟人退火算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Seediscussions,stats,andauthorprofilesforthispublicationat:https://www.researchgate.net/publication/292549417PersonificationannealingalgorithmforsolvingSATproblemArticle·February2002CITATIONSREADS9783authors,including:DefuZhangXiamenUniversity75PUBLIC

2、ATIONS1,206CITATIONSSEEPROFILESomeoftheauthorsofthispublicationarealsoworkingontheserelatedprojects:Anovelforecastingmethodbasedonmulti-orderfuzzytimeseriesandtechnicalanalysisViewprojectAllcontentfollowingthispagewasuploadedbyDefuZhangon12April2016.

3、Theuserhasrequestedenhancementofthedownloadedfile.第25卷第2期计算机学报Vol.25No.22002年2月CHINESEJ1COMPUTERSFeb.2002求解SAT问题的拟人退火算法张德富黄文奇汪厚祥(华中科技大学计算机学院武汉430074)摘要该文利用一个简单的变换,将可满足性(SAT)问题转换为一个求相应目标函数最小值的优化问题,提出了一种用于跳出局部陷阱的拟人策略.基于模拟退火算法和拟人策略,为SAT问题的高效近似求解得出了拟人退火算

4、法(PA),该方法不仅具有模拟退火算法的全局收敛性质,而且具有一定的并行性、继承性.数值实验表明,对于本文随机产生的测试问题例,采用拟人策略的模拟退火算法的结果优于局部搜索算法、模拟退火算法以及近来国际上流行的WALKSAT算法,因此拟人退火算法是可行的和有效的.关键词SAT问题,模拟退火算法,拟人中图法分类号:TP18PersonificationAnnealingAlgorithmforSolvingSATProblemZHANGDe2FuHUANGWen2QiWANGHou2Xiang(S

5、choolofComputerScience,HuazhongUniversityofScienceandTechnology,Wuhan430074)AbstractThesatisfiability(SAT)problemiscoretopicofthefieldsofartificialintelligenceandcomputerscience.Therefore,algorithmstosolvetheSATproblemplayanimportantroleinthedevelopm

6、entofcomputingtheoryandsystems.TraditionalalgorithmstreattheSATproblemasaconstraineddecisionproblem.Inthispaper,wetransformtheSATproblemintoaglobaloptimizationproblemtotheobjectivefunctionbyasimpletransformation,thusmanyalgorithmscanbeusedtosolveit.T

7、heSAalgorithmisageneralstochasticsearchalgorithmforcombinatorialoptimizationproblems,however,thisalgorithmneedoftencosttoomuchtimeforfindingasolution,whichpreventsitfrombeingappliedtomanypracticalproblems.HowtoimprovethisalgorithmforsolvingtheSATprob

8、lemiswhatthispaperconcerns.Inthispaper,thepersonificationstrategiesobtainedbyobservingandlearningfromthesocialandnaturephenomenaarepresented.Thesestrategiesaregenerallystraightforwardandintuitive,andarehelpfulforthesearchprocessjumpingoutoflocalminim