【作者】 王会婷；

【导师】 何中市；

【作者基本信息】 重庆大学 ， 计算机软件与理论， 2008， 硕士

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

【Abstract】 The network routing problem is one of fundamental problems encounted in modern communication service. The network routing problem contains dynamic problem and static problem. We only consider about the static network routing problem. The static network routing problem can be formulated as a constraint Steiner tree, but as we all know the Steiner tree is a NP(Nondeterministic Polynomical) hard problem, the network routing problem can’t be resolved to achieve the perfect outcome. So based on the analysis for the existing heuristics for the network routing problem, the two typical computational intelligence methods– neural network and genetic algorithm is considered by this paper, in solving the network routing problem show that these two algorithms are effective and efficient. For solving the problem by neural network, we formulate the problem as a quadratic 0-1 planning problem that have a equality constraints, then we transfer the problem as a unconstrained quadratic energy function by function method,we give out concrete Hopfield neural network algorithm.We find the computing speed is quick, and the perfect outcome can be found for the middle scale、small scale problem after a series of numerical simulation experiments. In this paper,to apply the genetic algorithm for solving problems,the counter measures bellow will be put into our practice:First and foremost,the original problems have to be alter into a so-called complete form in distance;Last,a new feasible solution(that is,so called the chromosome coding of the solution) will be designed to express and set an efficient adjusting weight and generate an concrete genetic processing.It is found that the genetic algorithm can convergence the excellent result, and the computing effection is stable after a series of numerical simulation experiments.This paper contributes to the research of the research of the network routing problem in four aspects:(1) Discuss the mathematics model of the network routing and the research methods. After that this paper establishes the mathematics model and then puts its own research method.(2) Study the neural network, and we establish the mathematics model and the solving algorithm of the network routing problem that can be solved by the neural network.(3) Study the genetic algorithm, and we establish the mathematics model and solving algorithm of the network routing problem that can be solved by the genetic algorithm.(4) This paper uses neural network and genetic algorithm for many different scales of network to do numerical simulation,it is showed that the effectivity and feasibility of the models and the algorithms of solving the network routing problem that be proposed in this paper.In this paper there is still some difference between the academic research and the real life using. The two algorithms in this paper are suit for the single source-multiple destination network routing problem. Our next step is to invent new algorithms to resolve the real problems in logistics, and justify them by testing in experiment or the application of real life.更多还原