来源:Frontiers of Computer Science 发布时间:2021/8/9 16:42:00
选择字号:
FCS |计算机科学前沿研究:蚁群优化算法关于最大独立集问题的求解分析

论文标题:On the analysis of ant colony optimization for the maximum independent set problem (蚁群优化算法关于最大独立集问题的求解分析)

期刊: Frontiers of Computer Science

作者:Xiaoyun XIA , Xue PENG , Weizhi LIAO

发表时间:11 Jun 2021

DOI:10.1007/s11704-020-9464-7

微信链接:点击此处阅读微信文章

导读

蚁群优化算法(ACO)是求解复杂组合优化问题的一类通用优化算法。随机性作为蚁群算法的一个重要特征,使得从理论的角度来理解和分析蚁群算法变得尤为困难。本文研究了一个简单ACO算法关于NP完全的最大独立集问题(MISP)的运行时间。首先,针对任意MISP实例,给出了在不同信息素值和启发式信息下ACO算法求解MISP的运行时间上界。其次,证明了蚁群优化算能够在期望多项式运行时间内获得MISP问题的(Δ+1)/2的近似比,其中Δ是给定图的最大度数。最后,证明了蚁群优化算法在某些实例上要优于局部搜索算法。

文章精要

相关内容推荐:

融合节点流行度的属性网络半监督非负矩阵三分解社区发现 2021 15(4):154324

使用迭代神经网络进行嵌套关系抽取 2021 15(3):153323

面向生物医学实体对齐的集成学习模型 2021 15(3):153321

提升面部年龄识别的实用方法 2021 15(3):153318

【FCS 人工智能专栏】面向社交的众包的任务分配 2021 15(2):152316

【FCS 人工智能专栏】知识图谱中的实体集扩展:异质信息网络的视角 2021 15(1):151307

【FCS 人工智能专栏】物联网环境中用户下一步访问位置预测 2021 15(1):151306

【FCS 人工智能专栏】智慧城市中基于稀疏表示模型的时间序列预测框架 2021 15(1):151305

【FCS 人工智能专栏】词翻译在神经网络句子对齐中的应用研究 2021 15(1):151302

【FCS 人工智能专栏】基于点态流形正则化的半监督学习 2021 15(1):151303

【FCS 人工智能专栏】SSDBA:一种基于伸缩距离的社交网络链路预测算法 2021 15(1):151301

【FCS 优秀青年科学家论坛】生物启发的视觉计算 2021 15(1):151304


Frontiers of Computer Science


Frontiers of Computer Science (FCS)是由教育部主管、高等教育出版社和北京航空航天大学共同主办、SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊,双月刊,全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华教授,共同主编为熊璋教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库(CSCD)核心库等收录,为 CCF 推荐期刊;两次入选“中国科技期刊国际影响力提升计划”;入选“第4届中国国际化精品科技期刊”;入选“中国科技期刊卓越行动计划项目”。

《前沿》系列英文学术期刊

由教育部主管、高等教育出版社主办的《前沿》(Frontiers)系列英文学术期刊,于2006年正式创刊,以网络版和印刷版向全球发行。系列期刊包括基础科学、生命科学、工程技术和人文社会科学四个主题,是我国覆盖学科最广泛的英文学术期刊群,其中13种被SCI收录,其他也被A&HCI、Ei、MEDLINE或相应学科国际权威检索系统收录,具有一定的国际学术影响力。系列期刊采用在线优先出版方式,保证文章以最快速度发表。

高等教育出版社入选“中国科技期刊卓越行动计划”集群化项目。Frontier系列期刊中:13种被SCI收录;1种被A&HCI收录;6种被Ei收录;2种被MEDLINE收录;11种中国科技核心期刊;16种被CSCD收录。

中国学术前沿期刊网

http://journal.hep.com.cn

 
 
 
特别声明:本文转载仅仅是出于传播信息的需要,并不意味着代表本网站观点或证实其内容的真实性;如其他媒体、网站或个人从本网站转载使用,须保留本网站注明的“来源”,并自负版权等法律责任;作者如果不希望被转载或者联系转载稿费等事宜,请与我们接洽。


 
 
 

 

 
 打印  发E-mail给: 
    
 
相关新闻 相关论文

图片新闻
多波段观测揭示磁星快速射电暴可能起源 新型沸石分子筛合成领域取得突破性进展
热带森林“赢家”更小更快 《自然》2024年十大人物公布
>>更多
 
一周新闻排行
 
编辑部推荐博文