最小延时问题的并行混合元启发式算法

发布时间：2020-08-07 23:38

【摘要】：最小延时问题是旅行商问题的变体,目的是求解路线中所有客户的累计等待时间,最小延时问题相比于旅行商问题更难以解决。目前的求解方法,只能在客户数量较小时具有较高的性能,当客户数量变大时算法很难兼顾运行时间与求解质量。基于上述问题,对如何在较短时间内获得大数据量最小延时问题的优质解这一问题进行以下研究。1.对于大数据量的最小延时问题,目前主要使用元启发式算法求解,在此基础上提出一种混合元启发式算法。将遗传算法与变邻域搜索算法细粒度结合,在遗传算法的框架内实现变邻域搜索。当算法陷入局部最优解时,可以在遗传算法的交叉过程中改变子代染色体的邻域结构;并对遗传算法的变异过程进行改进,子代染色体可以在增加多样性的同时有较大概率发生优化。然后对算法进行数据预处理,通过为每个染色体构建基因节点索引列表,降低生成子代染色体的时间复杂度。2.为了进一步加快算法运行,使用GPU实现算法的并行化,并根据GPU运行特点对并行算法做出改进。将并行算法的交叉与变异过程以线程束为单位分开同步运行,每个线程具有固定的染色体选取位置与生成位置。算法整体上以线程块为单位并行运行,以保证并行算法避免产生线程发散问题并且减少线程通信开销,同时实现染色体的动态选择。此外将算法与扰动机制相结合,增强并行算法全局搜索能力,并使用多重改进方式生成最终解。通过上述方法进一步提升算法性能。为验证算法的实际运行情况,对算法进行对比实验,测试数据的节点个数从51到10150不等。实验结果表明,提出的算法在CPU环境中,相对于其它元启发式算法,可以在较短的时间内取得优质解;在CPU-GPU环境中,当数据规模较大时,并行算法可以取得明显的加速效果,数据规模越大,加速效果越明显。并且该并行算法相较于实验中其它的并行算法,具有更好的性能。因此,对于大数据量的最小延时问题,并行混合元启发式算法可以在相对较短的时间内获得优质解。
【学位授予单位】：河北大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP301.6
【图文】：

基本图展示

图 2-2 当节点数=11 时的最小延时问题中，并没有将返回仓库作为限制条件考虑在内，在这种，意味着 ( 1) 0sl n 。时问题的描述公式与旅行商问题十分相似，但却比旅行

-opt操作

【相似文献】

相关期刊论文 前10条

1 郭戈;贾二娜;;网络化控制系统中的延时问题:分析与展望[J];控制与决策;2009年01期

2 王浩;;关于力士德SC3620行走延时问题处理[J];流体传动与控制;2017年03期

3 黄郴;数据库的延时问题及技术解决办法[J];图书情报工作;2001年03期

4 刘振鹏;薛雷;张彬;王雪峰;;最小延时问题GPU并行加速变邻域搜索方法[J];科学技术与工程;2018年29期

5 甘朝钦,张寒峥;IP网络性能与分组传送延时问题及其解决方案[J];电信科学;2003年10期

6 周强;;60MN卧式钢管热挤压机挤压力延时问题简析[J];科技风;2018年03期

7 Gordon oliver;解决当今全球语音网络的延时问题[J];当代通信;2004年17期

8 来五星,李巍华,史铁林,杨叔子;远程监测诊断系统中延时问题处理[J];计算机应用;2000年05期

9 解宝琦;贺万华;;增加DNS缓存服务器消除延迟[J];网络安全和信息化;2017年01期

10 汪国华;;今天你“PUSH”了吗?[J];个人电脑;2007年04期

相关重要报纸文章 前1条

1 唐建生;煤矿井下职工超点延时问题须解决[N];陕西日报;2008年

相关硕士学位论文 前2条

1 薛雷;最小延时问题的并行混合元启发式算法[D];河北大学;2019年

2 贾二娜;信道受限的网络化控制系统延时问题研究[D];大连海事大学;2008年

本文编号：2784689