基于参数分析的带边中断动态网络流元启发式算法研究

论文摘要

带边中断动态网络最大流问题(Maximum Total Flow with Flexible Arc Outages,MaxTFFAO)是从港口的日常设备维护作业中产生的优化问题。该问题将煤炭从矿山开采,经铁路运输,至码头前沿的整个过程抽象为一个网络,对网络中的设备进行维护时,网络中弧的状态发生变化,网络中的流量也因此变化。当一定数量的设备进行维护时,需要有计划的调度不同的维护作业,从而使整个网络中煤炭的输出量达到最大。同时该问题也是一个由网络流问题和调度问题相结合的组合优化问题,具有较强的NP难特性。对MaxTFFAO问题算法研究过程中使用到了大量的精确式算法和元启发式算法。精确式的算法如分解算法,混合整数线性规划等,使用这类算法虽然能够获得该问题的最优解,但是当问题规模较大时,求解耗时较长,应用成本较高。使用元启发算法求解该问题的过程中,虽然能够在一定的时间范围内获得问题的解,但是由于算法中参数设置的不合理性,所获得的问题的解不一定是该问题的较优解。而元启发式算法发挥其算法性能的关键很大程度上取决于算法本身的参数设置,因此有必要对元启发式算法应用于求解MaxTFFAO问题过程中的参数设置问题展开研究。本文利用参数分析工具irace,对求解MaxTFFAO问题的元启发式算法中的参数进行优化,提升了元启发式算法应用于实际问题求解中的算法的性能。本文主要的研究内容和创新点如下:(1)首先本文对所研究的问题的背景和研究意义进行阐述,介绍了带边中断动态网络最大流问题以及求解优化问题常用的元启发式算法,以及国内外对含参数的元启发式算法参数分析方法的研究现状,并对在本课题研究过程中所使用到的算法理论,以及最新的参数分析方法进行了介绍。(2)以MaxTFFAO问题为研究目标,对已有求解该问题的随机贪婪自适应搜索算法和混合禁忌搜索算法进行参数分析,获得两种算法最优的参数设置,并通过了实验验证。在混合禁忌搜索算法获得优化参数设置的基础上,对其从积极作业个数,搜索策略,初始解三个方面进行改进,提升混合禁忌搜索算法的性能。(3)设计了禁忌搜索和迭代邻域搜索算法相结合的混合元启发算法,对其中的关键参数进行参数分析,获得该混合元启发算法求解此问题最优的参数设置,同时也获得了混合元启发式算法求解该问题到目前为止的较优解。所有的分析与改进均通过实验的方式对比验证。本文创新性的将irace应用于MaxTFFAO问题的求解过程,使得参数优化设置之后的混合元启发算法更加符合该问题的背景及算法的运行情况,从而提升了算法在实际应用中的求解性能。

论文目录

• 摘要
• Abstract
• 第1章 绪论
•   1.1 课题研究背景及意义
•     1.1.1 课题研究背景
•     1.1.2 课题研究意义
•   1.2 课题来源
•   1.3 国内外研究现状
•     1.3.1 带边中断动态网络最大流问题
•     1.3.2 常用的含参数的元启发式算法
•     1.3.3 元启发式算法的参数分析方法
•   1.4 研究内容及篇章结构安排
•   1.5 本章小结
• 第2章 相关理论及参数分析方法介绍
•   2.1 网络最大流问题及算法
•   2.2 混合整数线性规划
•     2.2.1 线性规划
•     2.2.2 对偶理论
•     2.2.3 整数线性规划
•   2.3 禁忌搜索算法介绍
•     2.3.1 原理及基本内容
•     2.3.2 算法中关键参数
•     2.3.3 搜索策略
•   2.4 参数分析工具
•     2.4.1 irace参数分析原理
•     2.4.2 irace内置关键参数
•     2.4.3 irace参数分析步骤
•   2.5 本章小结
• 第3章 带边中断动态网络最大流问题模型
•   3.1 问题描述
•     3.1.1 带边中断动态网络最大流问题描述
•   3.2 带边中断动态网络最大流问题模型
•     3.2.1 模型的基本假设
•     3.2.2 符号说明
•     3.2.3 模型目标函数
•     3.2.4 模型的约束条件
•   3.3 模型分析
•   3.4 可变因素分析
•   3.5 本章小结
• 第4章 基于参数分析的Max TFFAO问题求解
•   4.1 元启发式算法求解前期准备
•     4.1.1 计算初始目标函数值
•     4.1.2 计算净目标函数值
•     4.1.3 寻找积极维护作业
•     4.1.4 更新时间片段
•   4.2 随机贪婪自适应搜索算法
•     4.2.1 算法中的关键参数
•     4.2.2 参数分析实验设计
•   4.3 混合禁忌搜索算法
•     4.3.1 算法中关键参数的设置
•     4.3.2参数分析实验
•   4.4 改进的混合禁忌搜索算法
•     4.4.1 算法改进
•   4.5 混合元启发式算法
•     4.5.1 算法设计
•     4.5.2 算法中的关键参数
•     4.5.3参数分析实验
•   4.6 本章小结
• 第5章 算法对比分析实验
•   5.1 实验数据来源及说明
•   5.2 实验环境
•   5.3 实验设计与分析
•     5.3.1 随机贪婪自适应搜索算法
•     5.3.2 混合禁忌搜索算法
•     5.3.3 改进后的混合禁忌搜索算法
•     5.3.4 混合元启发算法
•   5.4 实验总结
•   5.5 本章小结
• 第6章 总结与展望
•   6.1 全文总结
•   6.2 研究展望
• 致谢
• 参考文献
• 攻读硕士期间研究成果和参与项目

文章来源

类型: 硕士论文

作者: 夏振喜

导师: 郑澜波

关键词: 动态网络流,元启发式算法,禁忌搜索,参数分析

来源: 武汉理工大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,自动化技术

单位: 武汉理工大学

基金: 国家青年自然科学基金项目(71501152):多时间粒度下端到端煤炭供应链增效研究

分类号: TP18;O224

DOI: 10.27381/d.cnki.gwlgu.2019.001829

总页数: 78

文件大小: 1553K

下载量: 11