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

期刊：

作者：Xiaoyun XIA , Xue PENG , Weizhi LIAO

发表时间：11 Jun 2021

DOI：

微信链接：

导读

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

文章精要

相关内容推荐：

Frontiers of Computer Science

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

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

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

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

明升中国学术前沿期刊网