不确定随机网络下的度约束最小生成树问题

摘要

最小生成树问题是网络优化中的基本问题之一，在通信网络、交通网络、物流网络等领域中有广泛的应用。电路设计中为了减小节点的脆弱性，Narula和Ho在1980年提出度约束最小生成树问题。该问题旨在寻找最小权重的生成树，且每个节点的度满足给定的约束的要求。在经典网络中，所有权重都是已知的常数，因此可以利用经典的算法求解。
　　然而在现实网络中，由于非决定性因素的存在，导致网络中盼权重是非决定性的。为了描述非决定性的网络，Frank和Hakimi在1965年首先提出了随机网络的概念，目的是描述通信网络的随机现象。在2010年，Knowles和David首先把度约束最小生成树问题引入到随机网络中，但该方法对权重的估计十分依赖历史数据。然而在现实网络中，很多网络是没有历史数据的，因此Liu在2010年提出了不确定网络的概念。本文主要研究了不确定网络下的度约束最小生成树问题。基于不确定变量的不同的比较原则，我提出了三种不确定规划模型:不确定期望值度约束最小生成树模型，不确定α-度约束最小生成树模型和不确定最大机会度约束最小生成树模型。论文运用改进的遗传求解模型，并给出数值算例。
　　在实际生活的网络中，有的权重没有历史数据，有的权重有历史数据，因此不确定性和随机性往往同时出现在一个复杂的网络。最近，Liu在不确定网络的基础上进一步提出了不确定随机网络的概念。本文首次研究了不确定随机网络下的度约束最小生成树问题，提出了一个理想机会分布的概念。为了寻找与理想机会分布最接近的度约束生成树作为度约束最小生成树，建立了一个不确定随机规划模型，最后论文给出了数值算法求解该模型。

目录

声明

摘要

第1章 绪论

1．1 课题研究背景与意义

1．2 国内外研究现状

1．3 本文内容和结构

1．4 本章小结

第2章 预备知识

2．1 不确定理论基础

2．2 机会理论基础

2．3 不确定网络简介

2．4 不确定随机网络简介

2．5 本章小结

第3章 不确定网络下的度约束最小生成树问题

3．1 经典的度约束最小生成树问题介绍

3．2 不确定网络下的度约束最小生成树问题介绍

3．3 度约束最小生成树问题的不确定规划模型

3．4 改进的遗传算法

3．4．1 树的编码和解码过程

3．4．2 种群的初始化及适应度函数

3．4．3 选择过程

3．4．4 遗传操作

3．4．5 算法的流程图

3．5 数值算例

3．6 本章小结

第4章 不确定随机网络下的度约束最小生成树问题

4．1 不确定随机网络下的度约束最小生成树问题介绍

4．2 不确定随机规划模型及算法介绍

4．3 数值实例

4．4 本章小结

第5章 结论与展望

参考文献

攻读硕士学位期间发表的论文及成果

致谢