本文主要研究内容
作者袁福宇（2019）在《若干支配集优化问题求解的方法研究》一文中研究指出：支配集是图论中的重要概念,支配集的许多变种问题,如独立支配集、连通支配集、完全支配集等,在科学研究和工程实践的许多领域有着广泛应用,包括编码理论、图像处理、数值分析、密码学、信息检索,以及通信基础设施的布局、城市交通路线规划等。人们在研究过程中发现,支配集的这些变种问题,往往是NP(非确定性多项式,Non-deterministic Polynomial)困难问题,即在多项式时间内难以获得最优解。近年来,启发式算法和进化算法在求解支配集及其变种问题上取得了较好的效果,尽管如此,它们在求解多约束、多变量以及高度非线性等性质的复杂优化问题时,尤其是对大规模图的实例仍有不足。因此,本文针对性地就支配集及其变种问题的求解方面提出有效的优化算法,其中包括:最小支配集问题、最小独立支配集问题,以及最小完全支配集问题的搜索算法求解。在求解的过程中,我们引入了进化算法和局部搜索等策略,针对这些支配集的问题设计高效的求解算法。经过在基准测试数据上进行的一系列实验表明,所提出的算法具有显著效果。本文的主要工作包括以下几个方面:(1)最小支配集(Minimum Dominating Set,简记为MDS)问题是支配集问题的一个重要子问题。对于经典的最小支配集问题,以往的启发式求解方法能够得到可以接受的解,但是现实生活中往往是大规模的组合优化问题,面对这样问题,这些启发式算法的求解表现差强人意。基于上述情况,我们重点关注在大规模实例上求解最小支配集问题的方法研究。通过对大规模实例的分析,结合支配集问题的特点,提出了一个快速高效地求解最小支配集问题的算法FastMDS。在FastMDS算法的求解过程中,首先在预处理过程中对问题进行了有效化简,在初始化过程中采用了低复杂度的策略,在算法迭代过程中引入随机算子对顶点进行选择。通过一系列的实验表明,我们所提出的FastMDS算法,较目前主流的启发式问题求解算法更为高效。(2)最小完全支配集(Minimum Total Dominating Set,简记为MTDS)问题是经典支配集问题的变体。在本文中,我们提出一种结合局部搜索和遗传算法的混合进化算法来求解最小完全支配集问题。在算法中采用一种新颖的评分启发式方法,以提高搜索效率并获得了更好的解决方案。针对MTDS问题求解,在初始化阶段,首先创建一个包括一些初始解的种群,使算法能够搜索更多区域。在局部搜索阶段,通过迭代地交换顶点来优化初始解决方案,并使用基于修复的交叉算子创建新的解来使算法搜索更多可行的区域。为了证明算法的有效性和性能,我们在经典的基准DIMACS上进行了一系列的实验,实验结果表明,我们提出的算法较其他算法具有更好的性能。(3)最小独立支配集(Minimum Independent Dominating Set,简记为MIDS)问题是一个经典的组合优化问题,并在现实生活中得到了广泛的应用。针对MIDS问题求解,设计了一种新的基于禁忌策略的局部搜索算法和两阶段移除策略,包括双检查移除策略和随机多样性移除策略。双检查移除策略对刚刚移除的顶点的第二层邻域进行检查并确认是否对该顶点进行移除,以打破独立性的限制;当候选解的质量经过多次迭代后仍然没有得到改善时,可以采用随机多样性移除策略,该策略动态贪婪地删除大量的顶点,然后将随机游走引入到添加顶点的修复过程中,以逃离次优的搜索空间。我们在DIMACS和BHOSLIB两个经典的基准上进行了一系列的实验,实验结果表明,我们所提出的算法在求解MIDS问题上明显优于目前的启发式算法。
Abstract
zhi pei ji shi tu lun zhong de chong yao gai nian ,zhi pei ji de hu duo bian chong wen ti ,ru du li zhi pei ji 、lian tong zhi pei ji 、wan quan zhi pei ji deng ,zai ke xue yan jiu he gong cheng shi jian de hu duo ling yu you zhao an fan ying yong ,bao gua bian ma li lun 、tu xiang chu li 、shu zhi fen xi 、mi ma xue 、xin xi jian suo ,yi ji tong xin ji chu she shi de bu ju 、cheng shi jiao tong lu xian gui hua deng 。ren men zai yan jiu guo cheng zhong fa xian ,zhi pei ji de zhe xie bian chong wen ti ,wang wang shi NP(fei que ding xing duo xiang shi ,Non-deterministic Polynomial)kun nan wen ti ,ji zai duo xiang shi shi jian nei nan yi huo de zui you jie 。jin nian lai ,qi fa shi suan fa he jin hua suan fa zai qiu jie zhi pei ji ji ji bian chong wen ti shang qu de le jiao hao de xiao guo ,jin guan ru ci ,ta men zai qiu jie duo yao shu 、duo bian liang yi ji gao du fei xian xing deng xing zhi de fu za you hua wen ti shi ,you ji shi dui da gui mo tu de shi li reng you bu zu 。yin ci ,ben wen zhen dui xing de jiu zhi pei ji ji ji bian chong wen ti de qiu jie fang mian di chu you xiao de you hua suan fa ,ji zhong bao gua :zui xiao zhi pei ji wen ti 、zui xiao du li zhi pei ji wen ti ,yi ji zui xiao wan quan zhi pei ji wen ti de sou suo suan fa qiu jie 。zai qiu jie de guo cheng zhong ,wo men yin ru le jin hua suan fa he ju bu sou suo deng ce lve ,zhen dui zhe xie zhi pei ji de wen ti she ji gao xiao de qiu jie suan fa 。jing guo zai ji zhun ce shi shu ju shang jin hang de yi ji lie shi yan biao ming ,suo di chu de suan fa ju you xian zhe xiao guo 。ben wen de zhu yao gong zuo bao gua yi xia ji ge fang mian :(1)zui xiao zhi pei ji (Minimum Dominating Set,jian ji wei MDS)wen ti shi zhi pei ji wen ti de yi ge chong yao zi wen ti 。dui yu jing dian de zui xiao zhi pei ji wen ti ,yi wang de qi fa shi qiu jie fang fa neng gou de dao ke yi jie shou de jie ,dan shi xian shi sheng huo zhong wang wang shi da gui mo de zu ge you hua wen ti ,mian dui zhe yang wen ti ,zhe xie qi fa shi suan fa de qiu jie biao xian cha jiang ren yi 。ji yu shang shu qing kuang ,wo men chong dian guan zhu zai da gui mo shi li shang qiu jie zui xiao zhi pei ji wen ti de fang fa yan jiu 。tong guo dui da gui mo shi li de fen xi ,jie ge zhi pei ji wen ti de te dian ,di chu le yi ge kuai su gao xiao de qiu jie zui xiao zhi pei ji wen ti de suan fa FastMDS。zai FastMDSsuan fa de qiu jie guo cheng zhong ,shou xian zai yu chu li guo cheng zhong dui wen ti jin hang le you xiao hua jian ,zai chu shi hua guo cheng zhong cai yong le di fu za du de ce lve ,zai suan fa die dai guo cheng zhong yin ru sui ji suan zi dui ding dian jin hang shua ze 。tong guo yi ji lie de shi yan biao ming ,wo men suo di chu de FastMDSsuan fa ,jiao mu qian zhu liu de qi fa shi wen ti qiu jie suan fa geng wei gao xiao 。(2)zui xiao wan quan zhi pei ji (Minimum Total Dominating Set,jian ji wei MTDS)wen ti shi jing dian zhi pei ji wen ti de bian ti 。zai ben wen zhong ,wo men di chu yi chong jie ge ju bu sou suo he wei chuan suan fa de hun ge jin hua suan fa lai qiu jie zui xiao wan quan zhi pei ji wen ti 。zai suan fa zhong cai yong yi chong xin ying de ping fen qi fa shi fang fa ,yi di gao sou suo xiao lv bing huo de le geng hao de jie jue fang an 。zhen dui MTDSwen ti qiu jie ,zai chu shi hua jie duan ,shou xian chuang jian yi ge bao gua yi xie chu shi jie de chong qun ,shi suan fa neng gou sou suo geng duo ou yu 。zai ju bu sou suo jie duan ,tong guo die dai de jiao huan ding dian lai you hua chu shi jie jue fang an ,bing shi yong ji yu xiu fu de jiao cha suan zi chuang jian xin de jie lai shi suan fa sou suo geng duo ke hang de ou yu 。wei le zheng ming suan fa de you xiao xing he xing neng ,wo men zai jing dian de ji zhun DIMACSshang jin hang le yi ji lie de shi yan ,shi yan jie guo biao ming ,wo men di chu de suan fa jiao ji ta suan fa ju you geng hao de xing neng 。(3)zui xiao du li zhi pei ji (Minimum Independent Dominating Set,jian ji wei MIDS)wen ti shi yi ge jing dian de zu ge you hua wen ti ,bing zai xian shi sheng huo zhong de dao le an fan de ying yong 。zhen dui MIDSwen ti qiu jie ,she ji le yi chong xin de ji yu jin ji ce lve de ju bu sou suo suan fa he liang jie duan yi chu ce lve ,bao gua shuang jian cha yi chu ce lve he sui ji duo yang xing yi chu ce lve 。shuang jian cha yi chu ce lve dui gang gang yi chu de ding dian de di er ceng lin yu jin hang jian cha bing que ren shi fou dui gai ding dian jin hang yi chu ,yi da po du li xing de xian zhi ;dang hou shua jie de zhi liang jing guo duo ci die dai hou reng ran mei you de dao gai shan shi ,ke yi cai yong sui ji duo yang xing yi chu ce lve ,gai ce lve dong tai tan lan de shan chu da liang de ding dian ,ran hou jiang sui ji you zou yin ru dao tian jia ding dian de xiu fu guo cheng zhong ,yi tao li ci you de sou suo kong jian 。wo men zai DIMACShe BHOSLIBliang ge jing dian de ji zhun shang jin hang le yi ji lie de shi yan ,shi yan jie guo biao ming ,wo men suo di chu de suan fa zai qiu jie MIDSwen ti shang ming xian you yu mu qian de qi fa shi suan fa 。
论文参考文献
论文详细介绍
论文作者分别是来自东北师范大学的袁福宇，发表于刊物东北师范大学2019-07-08论文，是一篇关于组合优化问题论文,最小支配集论文,最小独立支配集论文,最小完全支配集论文,局部搜索论文,进化算法论文,东北师范大学2019-07-08论文的文章。本文可供学术参考使用，各位学者可以免费参考阅读下载，文章观点不代表本站观点，资料来自东北师范大学2019-07-08论文网站，若本站收录的文献无意侵犯了您的著作版权，请联系我们删除。
标签：组合优化问题论文; 最小支配集论文; 最小独立支配集论文; 最小完全支配集论文; 局部搜索论文; 进化算法论文; 东北师范大学2019-07-08论文;