【摘 要】
：
蚁群算法是一种基于种群的启发式搜索算法,主要用于解决组合优化问题。该算法采用分布式并行计算的机制,易与其他算法相结合,具有较强的鲁棒性和发现较好解的优点。由于蚁群
【出 处】
：
中国科学院研究生院 中国科学院大学
论文部分内容阅读
蚁群算法是一种基于种群的启发式搜索算法,主要用于解决组合优化问题。该算法采用分布式并行计算的机制,易与其他算法相结合,具有较强的鲁棒性和发现较好解的优点。由于蚁群算法存在较高的时间复杂度,当求解大规模问题时,需要较长的搜索时间,收敛速度较慢。蚁群算法具有天然的并行性,适合进行并行计算。计算机技术的飞速发展特别是多核处理器技术的发展为蚁群算法在多核环境中的并行化研究奠定了基础。
本文在研究了并行计算技术、蚁群算法的基本原理及其并行化的国内外现状后,提出了一种多核环境中蚁群算法的并行方案。文中对基本蚁群算法进行了三点改进:在路径转移规则中增加了调节机制、将信息素限制在一定的范围之内和只允许一次循环迭代中最好的一只蚂蚁释放信息素。算法改进后通过OpenMP技术把算法中最为耗时的路径搜索和信息素更新部分分解成多个线程在处理器的多个内核上并行执行。算法并行化后在选取的TSPLIB数据库中五个标准的TSP问题实例上进行了实验。实验内容包括:改进蚁群算法与基本蚁群算法在串行执行时的比较和改进算法的并行执行方式和串行执行方式的比较。实验结果表明:本文提出的改进算法能够明显提高基本算法获得全局最优解的质量,而改进算法并行化后又能进一步缩短执行时间,加快收敛速度,同时还能够充分利用多核处理器中的多个内核资源。本文提出的多核环境中蚁群算法的并行方案相对于串行基本蚁群算法而言,无论在获得全局最优解的质量,还是在收敛速度上都有了明显的改善,为多核环境中解决大规模组合优化问题提供了一种可行的途径。
其他文献
在传统机器学习中，为了保证训练得到的分类模型具有高准确性和可靠性，都有两个基本的假设：(1)用于学习的训练样本与新的测试样本满足独立同分布条件；(2)必须有足够可利用的训练样
随着各个行业对计算能力需求的不断增长，云计算得到了迅猛的发展。云计算通过网络把多个成本相对较低的计算实体整合成一个具有强大计算能力的系统，将大量计算资源统一管理和调
命名实体识别是指识别出句子中具有特定含义的名词,它是信息抽取、自动问答、机器翻译等自然语言处理任务的基础工作之一。手机3D动画自动生成技术由陆汝钤院士于2008年提出,
网络与信息处理技术的飞速发展使人类进入了大数据时代，数据量呈指数级增长，各行各业都面临海量数据处理的压力。自治区某物联网系统中的应用日志还停留在手工排查阶段，排查日志
随着超级计算技术的发展，超级计算能力有了大幅提升。与此同时，以资源聚合为目标的超级计算环境建设方兴未艾，从网格计算到云计算，如何将分布的超级计算资源整合在一起，对外提供统
工作流技术最早出现在生产组织和办公自动化领域,其目的是为了实现企业经营过程的计算机化或者半计算机化。随着计算机技术的不断发展,工作流技术也得到了飞速的发展,并在各
因特网的普及和视频点播等新业务的出现导致网络流量急剧增加,此时传统的网络流量特征已经不再适用于网络流量预测。研究人员对局域网、因特网的流量进行测量后发现,网络流量
随着互联网的飞速发展,网络应用层出不穷。为了更好的了解用户使用的网络应用类别和分析网络提供给用户的服务质量,网络服务供应商(ISP)的管理人员的一项重要任务就是识别和
协议是指两个或者两个以上的参与者为完成某一项特定任务相互约定的执行步骤和执行规则.协议的定义包含三层含义：⑴协议至少有两个参与者；⑵协议在参与者之间表现为消息交换和
过去我国把发展“数字海洋”技术列入了“十五”计划中,并策划了国家海洋科学技术发展的计划。目前,一个急需面对的问题是如何去研究和发展关于海洋界中信息技术与可视化的理