基于opencl求解最大团问题的并行算法研究

《基于opencl求解最大团问题的并行算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、—．Ｖ、＿广二？＇、－分类号ＴＰ３１１．５＞；挙号２０１３０７０３０２３学校代码Ｍ４８８＞礙级硕±学位论文？？＇■，一？．Ａ基于ＯｐｅｎＣＬ求解巧大团问题的并行算法研究，．Ｉ‘＇．、．，１？ｔ？学位申请人：学科专业：软件工程．＇指导教师■：５ｆｅｌ｜答辩日期：２０１６年５月２１日■■－，■Ｓ－．－＇相斷＇？■ｋ？？？．．Ｉ々乂（＊？、，，＾■Ｖ■■＇．去在；＇片；■＇、＇、心＇．ADissertation

2、SubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofMasterinEngineeringAparallelalgorithmforSolvingMCPonOpenCLMasterCandidate：LiLiMajor：SoftwareEngineeringSupervisor：AssociateProf.ZhangKaiWuhanUniversityofScienceandTechnologyWuhan,Hubei430081,P.R.ChinaMay,2016摘要最大团问题是图论中一个经典的组合优化问题，许多生活中的

3、实际问题可以都可以转化为对该问题的求解，如信号传输、故障诊断等，因此，对最大团问题的研究具有重要的理论意义和应用价值。然而，最大团问题是一个NP完全问题，目前没有任何算法能够在多项式时间求出该问题的最优解。近年来，国内外许多学者提出了各种求解最大团问题的算法，精确算法在问题规模较小的时候效果较好，但是问题规模一旦变大，求解问题的时间复杂度越来越高，精确算法显得无能为力。此外，遗传算法等近似算法也被用于求解最大团问题。标准的遗传算法存在着搜索效率不高和过早收敛的问题。通过对求解最大团问题的遗传算法的研究，我们对标准的遗传算法进行了一定改进。由于最大团问题具有指数级的解空间，无论是精确算法还

4、是近似算法，尤其在问题规模很大的情况下，无法在较短的时间内求出问题的解。当前基于OpenCL的高性能并行计算技术成为研究热点。本文将遗传算法和OpenCL相结合，提出一种基于OpenCL的并行遗传算法来求解最大团问题，通过设计出并行的选择算子、交叉算子、变异算子等，大大地提高了算法的效率。实验结果表明，和传统基于CPU的各类算法相比，本文提出的算法可以显著地减少计算时间的同时，并且可以找到大多数图例的最大团。关键词：最大团；NP完全问题；遗传算法；OpenCLIAbstractMaximumCliqueProblem(MCP)isoneofclassicalcombinatorialop

5、timizationproblemsingraphtheory.Manypracticalproblemsfromlifecanbeformulatedtoit.Therefore,studyingtheMCPisfullofsignificancebothintheoryandinpractice.However,theMCPisNP-completeproblemandthereisnoeffectivealgorithmtosolveitinpolynomialtime.Inrecentyears,manyscholarshaveproposedvariousalgorithmsf

6、orsolvingMCP.Exactalgorithmiseffectiveforsolvingsmallinstances,butwhenthescaleofthegraphbecomeslarger,itwouldcostmuchtimetofindMC,andmoreoveritcannotfindMCinreasonabletime.Apartfromexactalgorithms,someapproximationalgorithmsarealsoproposedforMCP,suchasgeneticalgorithm(GA).Standardgeneticalgorithm

7、shaveproblemsoflowsearchingefficiencyandprematureconvergence.BasedonstudyinggeneticalgorithmssolvingforMCP,wemadesomeimprovementsofstandardGA.However,becauseoftheexponentialsizeofthesolutionspace,especiallywhenthescale