论文标题：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