用蚁群算法求解最小极大流问题

摘要

网络流问题是近几十年来运筹学、网络分析等学科研究的热点问题。1997年, Shi-Yamamoto提出了最小极大流问题,现已有的算法均是通过理论证明在多维空间中得到网络的最小极大流,却没有基于蚁群算法研究最小极大流问题。因此,鉴于该问题的网络特性和蚁群算法求解网络问题的优越性,针对最小极大流问题,可以采用以蚁群算法为基础进行算法设计从而求解最小极大流问题。
　　首先,对最小极大流问题进行了理论分析,提出结合蚁群算法求解问题的思想,设计程序求解最小极大流问题。接着,通过定理证明可知,最小极大流问题可转换为一个线性优化问题,构造了适于蚁群算法的模型,运用蚁群算法寻找该线性优化方程的价值向量,并运用MATLAB求解线性方程最优解,该最优解即为网络的一个极大流,继而得到最小极大流。
　　文章对一个复杂的交通模拟图利用MATLAB编程求解最小极大流问题。数值实验表明,基于蚁群算法的方法在最小极大流问题上得到了较好的结果,分析的结果验证了该算法的可行性。通过数值实验得到了蚁群算法中参数的范围,各个参数的范围是05,0.10.99,0.5 Q10????????,在该参数范围内,问题可以得到最优解,而且该算法丰富了最小极大流问题的求解方法,推广了蚁群算法的应用范围。

目录

封面

声明

致谢

中文摘要

英文摘要

目录

1 引言

1.1 选题背景和研究意义

1.2国内外研究现状

1.3 本文的主要内容

2 最小极大流问题及其性质

2.1 最小极大流问题概述

2.2最小极大流问题的求解算法及其性质

2.2.1 最小极大流的性质

2.2.2 最小极大流问题的算法

3 蚁群算法

3.1 蚁群算法的起源

3.2 蚁群算法的基本原理

3.2.1 生物学实例

3.2.2 人工蚂蚁和真实蚂蚁的联系

3.2.3 蚁群算法的基本原理

3.2.4 蚁群算法的意义及其应用

3.3 蚁群算法的模型

3.3.1 带精英策略的蚁群算法

3.3.2 基于优化排序的蚁群算法

3.3.3 Ant-Colony System

3.3.4 最大最小蚁群算法（Max-Min Ant System，MMAS）

3.3.5 最优最差蚁群算法(Best-Worst Ant System，BWAS)

3.4 蚁群算法特点分析

4 蚁群算法求解最小极大流

4.1 基本定理

4.2 蚁群算法设计

4.2.1 算法思想

4.2.2 路径信息素更新模型

4.2.3 蚂蚁路径选择规则

4.2.4 算法步骤及其流程图

4.3 算例与数值分析

5 结论与展望

5.1 结论

5.2 展望

参考文献

作者简历

学位论文数据集