神经网络与遗传算法在网络通信路由问题中的应用研究

摘要

网络通信路由问题是现代通信网络与服务中的基本问题之一。网络通信路由问题通常分为动态和静态两个类型。在本文中我们只考虑静态网络通信路由问题。静态网络通信路由问题通常可描述为一个约束Steiner树,而已知Steiner树本身是一个NP(Nondeterministic Polynomical)困难的问题,求得最优解相当困难,所以本论文在总结已有求解该问题的传统方法优、缺点的基础上,分别应用神经网络算法与遗传算法这两类典型的智能算法对其进行求解,获得了较满意的效果。为了应用神经网络算法求解,我们将原问题用一个带等式约束的二次0-1规划问题加以模型化,然后将该问题运用函数法转化到一个无约束二次能量函数,并给出求解网络通信路由问题的具体的Hopfield神经网络算法。在进行了一系列的数值模拟实验后我们发现,其计算速度快,而且对中、小规模问题,通常总能以非常快的速度找到问题的局部最优解。在本文,为了应用遗传算法求解,本文采取将原问题转换到一个所谓的“距离完备形”问题考虑,然后依据这一转换,设计一个新的可行解表示(即所谓解的染色体编码)和设置一个有效的适应性度量,并给出具体的遗传操作和求解网络通信路由问题的遗传算法。在进行了一系列的数值模拟实验后我们发现:遗传算法通常总能收敛到问题的全局最优解,而且计算效果稳定。该文对网络通信路由问题进行了研究,其主要工作有以下几个方面:(1)对网络通信路由问题的数学模型以及研究方法进行了探讨,构造出了数学模型,并对不同的研究方法进行了归纳总结,并提出了自己的研究方法。(2)对神经网络算法进行了研究,并给出了能够用神经网络算法求解网络通信路由问题的数学模型及相应求解算法。(3)对遗传算法进行了研究,并给出了能够用遗传算法求解网络通信路由问题的数学模型及相应求解算法。(4)对不同规模的网络分别应用求解网络通信路由问题的神经网络算法与遗传算法进行数值模拟,体现了本文提出的以上求解网络通信路由问题的模型与算法的可行性与有效性。本文研究的网络通信路由问题与实际问题有一定的差距,求解网络通信路由问题的神经网络算法和遗传算法只适用于单源多目的地网络通信路由问题,则下一步工作目标是设计更能符合实际网络通信路由的算法,即分别用神经网络算法和遗传算法求解动态的多源多目的地网络通信路由问题的算法,通过实验和实际运用验证其有效性和实用性。

目录

摘要

ABSTRACT

1 引言

1.1 研究背景及意义

1.2 研究现状

1.3 论文所做工作及结构

2 网络通信路由问题及数学模型

2.1 网络通信路由问题

2.2 用神经网络求解网络通信路由问题的数学模型

2.3 用遗传算法求解网络通信路由问题的数学模型

3 神经网络在网络通信路由问题求解中的应用研究

3.1 HOPFIELD 神经网络算法简介

3.1.1 神经网络应用的研究

3.1.2 人工神经网络理论概述

3.1.3 神经网络基本概念

3.2 问题求解主要过程

4 遗传算法在网络通信路由问题求解中的应用研究

4.1 遗传算法简介

4.2 遗传算法过程描述

4.3 主要算子设计

4.3.1 染色体编码

4.3.2 染色体适应值度量的确定

4.3.3 染色体遗传操作的确定

4.3.4 遗传算法中各种控制参数的确定

4.4 问题的求解过程设计

5 实验结果及分析

5.1 用神经网络求解网络通信路由问题的实验及其分析

5.2 用遗传算法求解网络通信路由问题的实验及其分析

6 总结与展望

6.1 本文研究工作总结

6.2 展望

致谢

参考文献

附录