基于网络单纯形的虚拟网络映射算法
第45卷第4期Vol.45 No.4计算机工程
Computer Engineering
2019年4月
April2019
?体系结构与软件技术?文章编号：1000-3428(2019)04-0013-05 文献标志码：A中图分类号：TP393
基于网络单纯形的虚拟网络映射算法
王志臻1!郑焓1，陈晨1!田洪亮2
(1.中国科学技术大学自动化系，合肥230027; 2.中兴通讯股份有限公司，广东深圳518057)
摘要：在软件定义网络（SDN)架构中，虚拟网络映射是实现网络虚拟化的关键技术。针对虚拟网络映射算法映
射成本高、执行时间长的问题，提出一种虚拟网络映射算法Simplex-VNM。在节点映射阶段，对虚拟节点按照资源
需求进行排序，综合考虑节点连通性和映射成本选择映射节点。在链路映射阶段，采用网络单纯形算法求解最小
费用流问题。实验结果表明，相比于NA-PVNM和Improved-vnmFlib算法，该算法具有更低的映射成本和更短的
运行时间。
关键词：软件定义网络；虚拟网络映射；节点连通性；网络单纯形；效用函数;性能指标
中文引用格式：王志臻，郑铨，陈晨，等.基于网络单纯形的虚拟网络映射算法[6.计算机工程，2019,45(4):13-17,24.
英文引用格式：VANG Zhizhen%ZHENG Quan%CHEN Chen%et al. Virtual network mapping algorithm based on network simplex[J]. Computer Engineering，2019，45 (4) *13-17，24.
Virtual Network Mapping Algorithm Based on Network Simplex
WANG Zhizhen1，ZHENG Quan1，CHEN Chen1，TIAN Hongliang2
(1. Department of Automation，University of Science and Technology of China，Hefei 230027，China;
2. Zhongxing Telecommunication Equipment Corporation，Shenzhen，Guangdong 518057，China)
[Abstract]I n theSoftware Defined Network(SDN)architecture，virual n etwork mapping is the key achieve network virualization.To solve the problems of high cost of mapping and long rnning time,a v mapping algorithm named Simplex-VNM is proposed.I n the stage of node mapping，virual nodes are ranked according to resources requirements and search order，then the mapping node is chosen according to the node c costs.I n the stage of link mapping，the process is equivalent to the minimum cost flow problem which can be solved by
the network simplex algorithm.Experimental results show that，compared with NA-PVNM and I mproved-vnmFlib algorithms，the proposed algorithm has lower mapping cost and shorter rnning time.
[Key words]S oftware Defined Network(SDN); virual network mapping;node connectivity;network simplex;utility function；performance index
DOI:10.19678/j.issn.1000-3428.0050008
0概述
随着互联网的发展，网络架构“僵化”问题日益 严重，软件定义网络（Software Defined Network，S D N)与网络虚拟化技术的出现为该问题的解决提
供了新的契机。SDN将网络设备的控制面与数据面 分离，实现网络流量的灵活控制，是一种可靠的网络 虚拟化实现方式。网络虚拟化技术允许多个虚拟网 络运行在同一个底层物理网络中，是构建新一代网 络体系架构的重要支撑性技术[1]。虚拟网络映射是 网络虚拟化研究的基础内容之一[2]，其主要目标是 在满足节点和链路资源约束的基础上，将虚拟网络映射到物理网络上，实现底层资源的高效利用。
虚拟网络映射目前面临3大难题：资源约束，拓 扑多样化，在线请求的即时性[3]。这些难题导致在 多项式时间内很难求出它的最优解。虚拟网络映射 是NP-Hard问题，一般通过设计启发式算法求出近 似解，目前大部分研究主要以提高物理网络收益和 减少映射时间为目标。
虚拟网络映射可以分解成节点映射和链路映 射[4]。一般采用启发式算法求解节点映射问题，然 后在已知源节点和目的节点的基础上，将链路映射 转换成最小费用流问题[5]，再使用最短路径算法或 消圈算法完成链路映射。文献[6-7]提出基于同构
基金项目：中兴通讯科研项目“接人网面向内容服务网络的研究项目”（2017ZTE04-09)。
作者简介：王志臻（1993—），男，硕士研究生，主研方向为未来网络、虚拟网络映射；郑拴（通信作者），副教授；陈晨，硕士研究生; 田洪亮，博士。
收稿日期：2018-01-08 修回日期：2018-03-01 E-ma i l：qzheng@ ustc. edu. cn
数值稳定性验证实验报告
实验课程：数值计算方法专业：数学与应用数学班级：08070141 学号：37 姓名：汪鹏飞 中北大学理学院
实验1 赛德尔迭代法 【实验目的】 熟悉用塞德尔迭代法解线性方程组 【实验内容】 1.了解MATLAB 语言的用法 2.用塞德尔迭代法解下列线性方程组 1234123412341234 54 1012581034 x x x x x x x x x x x x x x x x ---=-??-+--=?? --+-=??---+=? 【实验所使用的仪器设备与软件平台】 计算机，MATLAB7.0 【实验方法与步骤】 1.先找出系数矩阵A ，将前面没有算过的x j 分别和矩阵的(,)A i j 相乘,然后将累加的和赋值给sum ，即(),j s u m s u m A i j x =+?.算 出()/(,) i i x b sum A i i =-,依次循环,算出所有的i x 。 2.若i x 前后两次之差的绝对值小于所给的误差限ε，则输出i x .否则重复以上过程，直到满足误差条件为止. 【实验结果】 (A 是系数矩阵，b 是右边向量，x 是迭代初值，ep 是误差限) function y=seidel(A,b,x,ep) n=length(b); er=1; k=0; while er>=ep
k=k+1; for i=[1:1:n] q=x(i); sum=0; for j=[1:1:n] if j~=i sum=sum+A(i,j)*x(j); end end x(i)=(b(i)-sum)/A(i,i); er=abs(q-x(i)); end end fprintf('迭代次数k=%d\n',k) disp(x') 【结果分析与讨论】 >> A=[5 -1 -1 -1;-1 10 -1 -1;-1 -1 5 -1;-1 -1 -1 10]; b=[-4 12 8 34]; seidel(A,b,[0 0 0 0],1e-3) 迭代次数k=6 0.99897849430002 1.99958456867649 2.99953139743435 3.99980944604109
Linux 上虚拟网络与真实网络的映射
Linux 上虚拟网络与真实网络的映射 虚拟化环境中的网络问题 在提供IaaS 服务的云计算环境中，每个用户都能得到一个虚拟的计算机，而这些虚拟机器以密集的方式运行在后台服务器集群中。虚拟机的一个特点是提供给用户类似于物理机器的体验，而现实世界中的物理机器能通过各种网络拓扑结构组网。如何在虚拟环境中方便快捷地创建和现实中一样的网络，成为一个新的挑战。 图 1.物理网络映射问题例子 图1 为一个网络映射问题的例子。图中左边是现实世界中一个常见的网络环境：四台PC 通过各自的物理网卡组成了两个子网，两个子网中的PC 默认情况下是不能通讯的，也就是说他们被物理隔离了。图 1 的右边显示了虚拟化环境下的情景，四个虚拟机同时运行在一个物理主机上，并且需要象图 1 左边的真实环境一样划分出两个子网并隔离。如何才能做到这一点，或者说如何简单方便的创建出和图1 左边部分类似的网络环境，成为虚拟化里必须要解决的一个问题。 回页首虚拟化环境中模拟网络的主要方法 为方便理解，本文把虚拟化环境中模拟现实网络的方法分为两种：使用传统网络技术，或使用虚拟化网络扩展技术。传统网络技术主要指在虚拟化技术流行以前，现实世界中已经存在的以太网络，包括传统IP 网络、802.1Q VLAN 网络，对它们Linux 已经有良好支持，用户可以配置这些Linux 设备以完成对现实网络的模拟。虚拟化网络扩展技术主要指为应对云计算与虚拟化环境带来的挑战而新出现的网络技术，包括802.1Qbg 和802.1Qbh 网络。 回页首虚拟化环境中网络模型说明 图 2 本文使用的网络模型说明
点击查看大图 为方便阅读，上图列出了本文将使用的网络元素。图中左列表示现实世界中存在的网络元素，分别为电脑终端、二层交换机、路由器、网关、支持802.1Q VLAN 的交换机、三层交换机、物理网卡、支持Hairpin 模式的交换机。图中中列为虚拟化环境中的元素，分别为虚拟机，Linux Bridge、Linux 路由表、Linux iptables、Host 主机。棕色虚线框表示以太网广播域，黑色虚线框表示物理捆绑关系。图中右列为Linux 系统里的网络设备模型，分别为TAP 设备、VETH 设备、工作在VEPA 模式的MACVLAN 设备、工作在Bridge 模式的MACVLAN 设备、工作在Passthrough 模式的MACVLAN 设备、SRIOV 的虚拟VF 设备、VLAN 设备，下文将有对它们的简介。 回页首使用传统网络技术模拟现实网络 Linux Host 侧使用的网络元素简介
数值分析—龙贝格算法
数值分析 实 验 报 告 专业：信息与计算科学 班级： 10***班 学号： 1008060**** 姓名： ******
实验目的： 用龙贝格积分算法进行积分计算。 算法要求： 龙贝格积分利用外推方法，提高了计算精度，加快了收敛速度。 1--4R R R R 1-j 1-j 1-k 1-j k 1-j k j k ，，，，+= ，k=2，3，… 对每一个k ，j 从2做到k ，一直做到|R R 1-k 1-k k k -，，| 小于给定控制精 度时停止计算。 其中： T R h k 1k =，（复化梯形求积公式），2h 1-k k a -b = 程序代码： #include
while(t!=n) { t*=2; ++i; } return i; } float t(int n) { float g,h,q=0; if(1==n) { h = (float)fabs(b-a); q = (f(a)+f(b))*h/2; } else { float x = a; g = 0; h = (float)fabs(b-a)*2/n; x = x+h/2; while(x B P神经网络算法步骤 SANY GROUP system office room 【SANYUA16H- 传统的BP 算法简述 BP 算法是一种有监督式的学习算法，其主要思想是：输入学习样本，使用反向传播算法对网络的权值和偏差进行反复的调整训练，使输出的向量与期望向量尽可能地接近，当网络输出层的误差平方和小于指定的误差时训练完成，保存网络的权值和偏差。具体步骤如下： （1）初始化，随机给定各连接权[w],[v]及阀值θi ，rt 。 （2）由给定的输入输出模式对计算隐层、输出层各单元输出 （3）计算新的连接权及阀值，计算公式如下： （4）选取下一个输入模式对返回第2步反复训练直到网络设输出误差达到要求结束训练。 第一步，网络初始化 给各连接权值分别赋一个区间（-1，1）内的随机数，设定误差函数e ，给定计 算精度值 和最大学习次数M 。 第二步,随机选取第k 个输入样本及对应期望输出 ()12()(),(),,()q k d k d k d k =o d ()12()(),(),,()n k x k x k x k =x 第三步，计算隐含层各神经元的输入和输出 第四步，利用网络期望输出和实际输出，计算误差函数对输出层的各神经元的偏导数()o k a δ 第五步，利用隐含层到输出层的连接权值、输出层的()o k δ和隐含层的输出计算误差函数对隐含层各神经元的偏导数()h k δ 第六步，利用输出层各神经元的()o k δ和隐含层各神经元的输出来修正连接权值()ho w k 第七步，利用隐含层各神经元的()h k δ和输入层各神经元的输入修正连接权。 第八步，计算全局误差211 1(()())2q m o o k o E d k y k m ===-∑∑ ε 实验三 龙贝格方法 【实验类型】 验证性 【实验学时】 2学时 【实验内容】 1.理解龙贝格方法的基本思路 2.用龙贝格方法设计算法，编程求解一个数值积分的问题。 【实验前的预备知识】 1．计算机基础知识2．熟悉编程基本思想3．熟悉常见数学函数； 【实验方法或步骤】 龙贝格方法的基本思路龙贝格方法是在积分区间逐次二分的过程中，通过 对梯形之值进行加速处理，从而获得高精度的积分值。 1． 龙贝格方法的算法 步骤1 准备初值()f a 和()f b ，用梯形计算公式计算出积分近似值 ()()12b a T f a f b -=+??? ? 步骤2 按区间逐次分半计算梯形公式的积分近似值令 2i b a h -=，0,1,2,...i =计算12102122n n n i i h T T f x -+=??=+ ??? ∑，2i n = 步骤3 按下面的公式积分梯形公式：()223n n n n T T S T -=+ 辛普生公式：()2215n n n n S S C S -=+ 龙贝格公式：()2263n n n n C C R C -=+ 步骤4 精度控制 当2n n R R ε-<，（ε为精度）时，终止计算，并取2n R 为近似值否则将步长折 半，转步骤2。 [实验程序] #include 单纯形法求最优解问题 题目（老师布置的那道作业题）：2153m ax x x f +=，其中 ??? ??? ?=≥=++=+=+5,4,3,2,1,0182312245214 231j x x x x x x x x j ，求2153m ax x x f +=的最大值。 这张表是根据题目画的，Cj （行向量）为5432100053m ax x x x x x f ++++=中各个变量的系数，Ci （列向量）为与X B （列向量）相对应的各项的系数，X B 称为基变量（3列，由题目中的方程个数决定），起初的基变量由构造的变量x3、x4、x5组成，b 为对应三个方程等式右边的常数，z j 为Ci 各列与xj 各列乘积的和，如z1=0*1+0*0+0*3=0。i θ为判别将哪个基变量换出的依据，根据c j -z j 为正，要先将x2换入XB 中，关键是判断x3、x4、x5哪个跟x2换，这就要根据各列各列除以2x B i X =θ，与所得的最小的i θ对应的XB 换，如上表可知x2跟x4换，换完之后注意原来x4所对应的列向量为[0 1 0]T ,故要将x2所对应的列向量变换为为[0 1 0]T ，注意b 也要跟着变化，于是得下表. 由上表知c 1-z 1=3>0，故仍需将x1换入XB 中，用各列各列除以2x B i X =θ，与所得的最小的i θ对应的XB 换，结合i θ可知，x1跟x5换，于是得下表。 由上表可知c j -z j 均非正，故5432100053m ax x x x x x f ++++=取最大值时，????? ?? ?????????=00662x ， 对应的最大值36max =f . 系统工程导论知识点整理： 系统是由相互作用和相互依赖的若干组成部分(要素)结合的具有特定功能的有机整体。 系统的特征：整体性、相关性、目的性、环境适应性。 系统的功能是指系统与外部环境相互作用所反映的能力。 结构是功能的内在根据，功能是结构的外在表现。 系统功能的特性：易变性、相关性。 系统工程就是用科学的方法规划和组织人力、物力、财力，通过最优途径的选择，使人们的工作在一定期限内收到最合理、最经济、最有效的效果。 科学的方法：从整体观念出发，通盘筹划，合理安排整体中的每一个局部，以求得整体的最优规划、最优管理和最优控制，使每个局部都服从一个整体目标，力求避免资源的损失和浪费。 https://www.wendangku.net/doc/646698670.html,/s/blog_5bbd6ec00100b5nk.html 人工神经网络算法(2008-11-20 17:24:22) 标签：杂谈 人工神经网络算法的作用机理还是比较难理解，现在以一个例子来说明其原理。这个例子是关于人的识别技术的，在门禁系统，逃犯识别，各种验证码破译，银行预留印鉴签名比对,机器人设计等领域都有比较好的应用前景，当然也可以用来做客户数据的挖掘工作，比如建立一个能筛选满足某种要求的客户群的模型。 机器识别人和我们人类识别人的机理大体相似，看到一个人也就是识别对象以后，我们首先提取其关键的外部特征比如身高，体形，面部特征，声音等等。根据这些信息大脑迅速在内部寻找相关的记忆区间，有这个人的信息的话，这个人就是熟人，否则就是陌生人。 人工神经网络就是这种机理。假设上图中X(1)代表我们为电脑输入的人的面部特征，X(2)代表人的身高特征X(3)代表人的体形特征X(4)代表人的声音特征W(1)W(2)W(3)W(4)分别代表四种特征的链接权重，这个权重非常重要，也是人工神经网络起作用的核心变量。 现在我们随便找一个人阿猫站在电脑面前，电脑根据预设变量提取这个人的信息，阿猫面部怎么样，身高多少，体形胖瘦，声音有什么特征，链接权重初始值是随机的，假设每一个W均是0.25,这时候电脑按这个公式自动计 算,Y=X(1)*W(1)+X(2)*W(2)+X(3)*W(3)+X(4)*W(4)得出一个结果Y,这个Y要和一个门槛值（设为Q）进行比较，如果Y>Q,那么电脑就判定这个人是阿猫,否则判定不是阿猫.由于第一次计算电脑没有经验,所以结果是随机的.一般我们设定是正确的,因为我们输入的就是阿猫的身体数据啊. 现在还是阿猫站在电脑面前,不过阿猫怕被电脑认出来,所以换了一件衣服,这个行为会影响阿猫的体形,也就是X(3)变了,那么最后计算的Y值也就变了,它和Q比较的结果随即发生变化,这时候电脑的判断失误,它的结论是这个人不是阿猫.但是我们告诉它这个人就是阿猫,电脑就会追溯自己的判断过程,到底是哪一步出错了,结果发现原来阿猫体形X(3)这个 体征的变化导致了其判断失误,很显然,体形X(3)欺骗了它,这个属性在人的识别中不是那 么重要,电脑自动修改其权重W(3),第一次我对你是0.25的相信,现在我降低信任值,我0.10的相信你.修改了这个权重就意味着电脑通过学习认为体形在判断一个人是否是自己认识的人的时候并不是那么重要.这就是机器学习的一个循环.我们可以要求阿猫再穿一双高跟皮鞋改变一下身高这个属性,让电脑再一次进行学习,通过变换所有可能变换的外部特征,轮换让电脑学习记忆,它就会记住阿猫这个人比较关键的特征,也就是没有经过修改的特征.也就是电脑通过学习会总结出识别阿猫甚至任何一个人所依赖的关键特征.经过阿猫的训练电脑,电脑已经非常聪明了,这时你在让阿猫换身衣服或者换双鞋站在电脑前面,电脑都可以迅速的判断这个人就是阿猫.因为电脑已经不主要依据这些特征识别人了,通过改变衣服,身高骗不了它.当然,有时候如果电脑赖以判断的阿猫关键特征发生变化,它也会判断失误.我们就 Romberg龙贝格算法实验报告 2017-08-09 课程实验报告 课程名称： 专业班级： CS1306班学号： U201314967 姓名：段沛云指导教师：报 告日期： 计算机科学与技术学院 目录 1 实验目的 (1) 2 实验原理 (1) 3 算法设计与流程框图 (2) 4 源程序 (4) 5 程序运行 (7) 6 结果分析 (7) 7 实验体会 (7) 1 实验目的 掌握Romberg公式的用法，适用范围及精度，熟悉Romberg算法的流程，并能够设计算法计算积分 31 得到结果并输出。 1x 2 实验原理 2.1 取k=0,h=b-a,求T0= 数)。 2.2 求梯形值T0( b-a ),即按递推公式（4.1）计算T0。 k 2 h [f(a)+f(b)]，令1→k,(k记区间[a，b]的二分次2 2.3 求加速值，按公式(4.12)逐个求出T表的第k行其余各元素Tj(k-j) (j=1,2,….k)。 2.4 若|Tk+1-Tk| n-1 11T2n=[Tn+hn∑f(xi+)] 22i=0 1 Sn=T2n+(T2n-Tn) 31 Cn=S2n+(S2n-Sn) 151 Rn=C2n+(C2n-Cn) 63 3 算法设计与流程框图 算法设计：(先假定所求积分二分最大次数次数为20) 3.1 先求T[k][0] 3.2 再由公式T (k)m 4m(k+1)1)=mTm-1-mTm(k-1(k=1,2,) 求T[i][j] 4-14-1 3.3 在求出的同时比较T[k][k]与T[k-1][k-1]的大小，如果二者之差的绝对 值小于1e-5，就停止求T[k][k]；此时的k就是所求的二分次数，而此时的T[k][k]就是最终的结果 3.4 打印出所有的T[i][j]；程序流程图 三、单纯形法的解题步骤 第一步：作单纯形表. ）（1）把原线性规划问题化为标准形式； ）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵； ）（3）目标函数非基化； ）（4）作初始单纯形表. 第二步：最优解的判定. (1) 若所有检验数都是非正数，即，则此时线性规划问题已取 得最优解. (2) 若存在某个检验数是正数，即，而所对应的列向量无正分量，则线性规划 问题无最优解. 如果以上两条都不满足，则进行下一步. 第三步：换基迭代. ，并确定所在列的非基变量为进基变量. （1）找到最大正检验数，设为 （2）对最大正检验数所在列实施最小比值法，确定出主元，并把主元加上小括号. 主元是最大正检验数 所在列，用常数项与进基变量所对应的列向 量中正分量的比值最小者； 替换出基变量，从而得到新的基变量.也就是主元所在 （3）换基：用进基变量 （4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表； （5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止. 例3 求. 解（1）化标准型：令 ，引进松弛变量 ，其标准型为 求 （2）作单纯形表：在约束方程组系数矩阵中 的系数构成单位矩阵，故取 为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）.表 6.8 （3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为 目标函数取得最优值. 原线性规划问题的最优解为：.目标函数的最优值为14，即. 例4 用单纯形方法解线性规划问题. 求. 解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出 ，, 代入目标函数 , 经整理后，目标函数非基化了. 作单纯形表，并进行换基迭代（见表6.9）. 最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变出基，非基变量进基. 换，基变量 深度学习 卷积神经网络算法简介 李宗贤 北京信息科技大学智能科学与技术系 卷积神经网络是近年来广泛应用在模式识别、图像处理领域的一种高效识别算法，具有简单结构、训练参数少和适应性强的特点。它的权值共享网络结构使之更类似与生物神经网络，降低了网络的复杂度，减少了权值的数量。以二维图像直接作为网络的输入，避免了传统是被算法中复杂的特征提取和数据重建过程。卷积神经网络是为识别二维形状特殊设计的一个多层感知器，这种网络结构对于平移、比例缩放、倾斜和其他形式的变形有着高度的不变形。 ?卷积神经网络的结构 卷积神经网络是一种多层的感知器，每层由二维平面组成，而每个平面由多个独立的神经元组成，网络中包含一些简单元和复杂元，分别记为C元和S元。C元聚合在一起构成卷积层，S元聚合在一起构成下采样层。输入图像通过和滤波器和可加偏置进行卷积，在C层产生N个特征图（N值可人为设定），然后特征映射图经过求和、加权值和偏置，再通过一个激活函数（通常选用Sigmoid函数）得到S层的特征映射图。根据人为设定C层和S层的数量，以上工作依次循环进行。最终，对最尾部的下采样和输出层进行全连接，得到最后的输出。 卷积的过程：用一个可训练的滤波器fx去卷积一个输入的图像（在C1层是输入图像，之后的卷积层输入则是前一层的卷积特征图），通过一个激活函数(一般使用的是Sigmoid函数)，然后加一个偏置bx，得到卷积层Cx。具体运算如下式，式中Mj是输入特征图的值： X j l=f?(∑X i l?1?k ij l+b j l i∈Mj) 子采样的过程包括：每邻域的m个像素（m是人为设定）求和变为一个像素，然后通过标量Wx+1加权，再增加偏置bx+1，然后通过激活函数Sigmoid产生特征映射图。从一个平面到下一个平面的映射可以看作是作卷积运算，S层可看作是模糊滤波器，起到了二次特征提取的作用。隐层与隐层之间的空间分辨率递减，而每层所含的平面数递增，这样可用于检测更多的特征信息。对于子采样层来说，有N 个输入特征图，就有N个输出特征图，只是每个特征图的的尺寸得到了相应的改变，具体运算如下式，式中down（）表示下采样函数。 X j l=f?(βj l down (X j l?1) +b j l)X j l) ?卷积神经网络的训练过程 卷积神经网络在本质上是一种输入到输出的映射，它能够学习大量的输入和输出之间的映射关系，而不需要任何输入和输出之间的精确数学表达式。用已知的模式对卷积网络加以训练，网络就具有了输 二、Romberg 积分法 1.变步长Romberg 积分法的原理 复化求积方法对于提高精度是行之有效的方法，但复化公式的一个主要缺点在于要事先估计出部长。若步长过大，则精度难于保证；若步长过小，则计算量又不会太大。而用复化公式的截断误差来估计步长，其结果是步长往往过小，而且''()f x 和(4)()f x 在区间[,]a b 上的上界M 的估计是较为困难的。在实际计算中通常采用变步长的方法，即把步长逐次分半（也就是把步长二等分），直到达到某种精度为止，这种方法就是Romberg 积分法的思想。 在步长的逐步分半过程中，要解决两个问题： 1. 在计算出N T 后，如何计算2N T ,即导出2N T 和N T 之间的递推公式； 2. 在计算出N T 后，如何估计其误差，即算法的终止的准则是什么。 首先推导梯形值的递推公式，在计算N T 时，需要计算1N +个点处的函数值在计算出N T 后，在计算2N T 时，需将每个子区间再做二等分，共新增N 个节点。为了避免重复计算，计算2N T 时，将已计算的1N +个点的数值保留下来，只计算新增N 个节点处的值。为此，把2N T 表示成两部分之和，即 由此得到梯形值递推公式 因此 由复化梯形公式的截断误差有 若''()f x 变化不大时，即''''12()()f f ηη≈，则有 式（2）表明，用2N T 作为定积分I 的近似值，其误差大致为21 ()3 N N T T -， 因此其终止条件为 其中ε是预先给定的精度。 积分公式 将上述方法不断推广下去，可以得到一个求积分的序列，而且这个序列很快收敛到所求的定积分。记 (0)N N T T =，将区间N 等分的梯形值。(1)N N T S =，将区间N 等分的Simpson 第４５卷 第１２期２０１８年１２月 计算机科学COM PU T ER SCIENCE Vol ．４５No ．１２Dec ．２０１８ 到稿日期：２０１７-１１-０３ 返修日期：２０１８-０２-３１ 本文受国家９７３计划（２０１２CB ３１５９０１），国家自然科学基金（６１３７９０７９）资助。 王 明（１９９２－），男，硕士，主要研究方向为下一代互联网；庄 雷（１９６３－），女，博士，教授，博士生导师，CCF 高级会员，主要研究方向为形式语言与自动机理论、模型检测、下一代互联网，E -mail ：ielzhuang ＠zzu ．edu ．cn （通信作者）；王国卿（１９８９－），男，博士，主要研究方向为模型检测、 虚拟网络映射；张坤丽（１９７７－），女，博士，讲师，主要研究方向为机器学习、自然语言处理。 基于元胞遗传机制的虚拟网络映射算法 王 明 庄 雷 王国卿 张坤丽（郑州大学信息工程学院 郑州４５００００） 摘 要 满足节点和链路约束条件的虚拟网络请求最优映射问题是NP -难问题，粒子群算法和遗传算法等启发式算法是解决这类问题的主要手段。这类启发式算法从数学模型优化的角度来求解问题，但未考虑虚拟网络映射节点本身的变化对最优解的影响，存在收敛速度较慢和容易陷入局部最优解的问题。文中将元胞遗传机制引入虚拟网络映射问题中，提出了虚拟网络映射算法VNE -CGA 。该算法利用元胞自动机对节点建模，使用“B ４５６７／S １２３４”规则来替代传统遗传算法中的交叉操作；通过对邻居的学习来指导个体的寻优过程，弥补了传统遗传算法的固有缺陷，最终提高了虚拟网络请求的接受率以及底层物理网络的运营收益。关键词 虚拟网络映射，元胞自动机，遗传算法，元胞遗传算法 中图法分类号 T P ３９３ 文献标识码 A ＤＯＩ １０．１１８９６／j ．issn ．１００２-１３７X ．２０１８．１２．００９ ＶｉｒｔｕａｌＮｅｔｗｏｒｋＭａｐｐｉｎｇＡｌｇｏｒｉｔｈｍＢａｓｅｄｏｎＣｅｌｌｕｌａｒＧｅｎｅｔｉｃＭｅｃｈａｎｉｓｍ WANG Ming ZHUANG Lei WANG Guo -q ing ZHANG Kun -li （School of Information Engineering ，Zhengzhou U niversity ，Zhengzhou ４５００００，China ） Ａｂｓｔｒａｃｔ The optimal mapping problem of virtual network requests which satisfies the constraints of nodes and links is an NP -hard problem ．Heuristic algorithms ，such as particle swarm algorithm and genetic algorithm ，can solve those p roblems ． They solve the problem from the perspective of mathematical model optimization ，but fail to consider the in -fluence of the change of virtual network mapping node itself on the optimal solution ，and they also have the problems of slow convergence speed and being easy to fall into local optimal solution ．This paper introduced the cellular genetic mechanism into the problem of virtual network mapping ，and proposed the virtual network mapping algorithm （VNE -CGA ）．This algorithm uses the cellular automata to model the nodes ，and replaces the cross operator in the traditional g enetic algorithm with the “B ４５６７／S １２３４”rule ． Besides ，the individual ’s optimization process is guided through lear -ning from neighbors ，making up for the inherent defects of traditional genetic algorithms ．Finally it improves the request acceptance rate of virtual network and the operating income of underlying physical network ．Ｋｅｙｗｏｒｄｓ Virtual network mapping ，Cellular automata ，Genetic algorithm ，Cellular genetic algorithm 1 引言 随着互联网规模的扩大及新型业务的增多，传统网络结构趋于“僵化”，而网络虚拟化为网络的创新和可持续发展提供了有力的支持［１-２］。网络虚拟化的核心思想是在同一个物理网络之上，为不同的业务构建各自的虚拟网［３］。其关键是将底层物理网络资源按需提供给虚拟网络请求，它是NP -难问题［４］，启发式算法是求解这类问题的主要手段。文献［５］在粒子群算法的基础上提出了一种负载均衡算法，以提高底层网络的长期平均运营收益。文献［６］设计了一种基于蚁群算法的虚拟网络映射算法，利用蚁群的迭代和智能求解此优化问题。文献［７］初次使用遗传算法（Genetic Algorithm ，GA ）解决此映射优化问题，但收敛速度较慢，并且容易陷入局部最优。文献［８］融合遗传算法与粒子群算法提出了一种迭代优 化映射方案，改善了局部最优问题。文献［９］在遗传算法的基础上加入单纯性算法，一定程度上改差了早熟收敛问题。 以上研究多从数学模型的角度来解决和优化问题，较少考虑到虚拟网映射中节点和链路本身的变化对最终映射结果的影响。元胞自动机依靠局部的简单规则来研究整体的复杂性，被广泛应用于信息传递［１０］、图像加密［１１］、复杂函数优化［１２］及生物仿真［１３］等领域。特别是对于许多单目标优化问题，元胞遗传算法作为一种成熟且高效的方案，已经取得了很好的效果［１４-１５］。本文利用元胞自动机对物理节点和链路进行建模，使用元胞遗传算法来解决虚拟网映射问题，提出了Virtual Network Embedding -Cellular Genetic Algorithm （VNE -CGA ）算法。据我们所知，目前所能查询检索到的文 献中尚未有学者结合元胞自动机来求解虚拟网络映射问题。根据仿真实验分析，相较于传统遗传算法和文献［８-９］中提出 万方数据 计算方法实验报告(5) 学生姓名杨贤邦学号指导教师吴明芬实验时间2014.4.16地点综合实验大楼203 实验题目数值积分方法 实验目的●利用复化梯形、辛普森公式和龙贝格数值积分公式计算定积分的 近似植。 实验内容●梯形、辛普森、柯特斯法及其Matlab实现； ●变步长的梯形、辛普森、柯特斯法及其Matlab实现。 ●题目由同学从学习材料中任意选两题 算法分析梯形：function y=jifeng_tixing(a,b,n,fun) fa=feval(fun,a); fb=feval(fun,b); s=0; h=(b-a)/n; for k=1:n-1 xk=a+k*h; s=feval(fun,xk)+s; end y=(h/2)*(fa+fb+2*s); 辛普生：function y=jifeng_xingpu(a,b,n,fun) fa=feval(fun,a); fb=feval(fun,b); h=(b-a)/n; s=0; s2=feval(fun,a+0.5*h); for k=1:n-1 xk=a+k*h; s=feval(fun,xk)+s; s2=feval(fun,xk+(h/2))+s2; end 与源程序y=(h/6)*(fa+fb+2*s+4*s2); 龙贝格：function r2=jifeng_long(fun,a,b,e) h=b-a; t1=(h/2)*(feval(fun,a)+feval(fun,b)); k=1; r1=10; r2=0; c2=0; while abs(r2-r1)>e; s=0; x=a+h/2; while x=3 r1=r2; c2=s2+(1/15)*(s2-s1); r2=c2+(1/63)*(c2-c1); k=k+1;h=h/2; t1=t2;s1=s2; c1=c2; end end 科技信息 2011年第 3期 SCIENCE &TECHNOLOGY INFORMATION 人工神经网络是模仿生理神经网络的结构和功能而设计的一种信息处理系统。大量的人工神经元以一定的规则连接成神经网络 , 神经元之间的连接及各连接权值的分布用来表示特定的信息。神经网络分布式存储信息 , 具有很高的容错性。每个神经元都可以独立的运算和处理接收到的信息并输出结果 , 网络具有并行运算能力 , 实时性非常强。神经网络对信息的处理具有自组织、自学习的特点 , 便于联想、综合和推广。神经网络以其优越的性能应用在人工智能、计算机科学、模式识别、控制工程、信号处理、联想记忆等极其广泛的领域。 1986年 D.Rumelhart 和 J.McCelland [1]等发展了多层网络的 BP 算法 , 使BP 网络成为目前应用最广的神经网络。 1BP 网络原理及学习方法 BP(BackPropagation 网络是一种按照误差反向传播算法训练的多层前馈神经网络。基于 BP 算法的二层网络结构如图 1所示 , 包括输入层、一个隐层和输出层 , 三者都是由神经元组成的。输入层各神经元负责接收并传递外部信息 ; 中间层负责信息处理和变换 ; 输出层向 外界输出信息处理结果。神经网络工作时 , 信息从输入层经隐层流向输出层 (信息正向传播 , 若现行输出与期望相同 , 则训练结束 ; 否则 , 误差反向进入网络 (误差反向传播。将输出与期望的误差信号按照原连接通路反向计算 , 修改各层权值和阈值 , 逐次向输入层传播。信息正向传播与误差反向传播反复交替 , 网络得到了记忆训练 , 当网络的全局误差小于给定的误差值后学习终止 , 即可得到收敛的网络和相应稳定的权值。网络学习过程实际就是建立输入模式到输出模式的一个映射 , 也就是建立一个输入与输出关系的数学模型 : 虚拟网络映射问题 1网络虚拟化概述 网络虚拟化技术是指：通过抽象、分配、隔离机制，在一个公共物理网络(Substrate Network,SN)上支持多个虚拟网络，各个虚拟网络可以使用相互独立的协议体系，并能够根据动态变化的用户需求对整个网络中的节点资源和链路资源进行合理配。每一个虚拟网络是底层网络的一份资源片，它由虚拟节点(例如，虚拟路由器)和虚拟链路组成。网络虚拟化的优势之一是支持多个异构的网络架构共亨物理基础设施。 网络虚拟化环境与当前Internet的最大区别就在于：当前的Internet仅仅由互联网服务提供商(ISP)一个角色组成，而网络虚拟化环境由两个不同的角色组成，即基础设施提供商(Infrastrueture Providers,InP)和服务提供商(Service Providers,SP)。当前网络环境中ISP不仅提供物理的基础设施，而且直接为用户提供相应的网络服务来满足终端用户需求。然而在网络虚拟化环境中把服务提供从ISP中解耦出来,新增了服务提供商(SP)和虚拟网络提供商(VNP)两个角色，而原来的ISP只负责提供并管理底层网络设备成为网络基础设施提供商(InP)，由SP代替它负责网络服务的运营。其中VNP相当于中间商或经纪人(Broker)为SP代理构建虚拟网络的服务。 2网络虚拟化模型 图1展示了现有网络模型向网络虚拟化环境下的模型的转变：在网络虚拟化的环境中，基础设施层由各个基础设施提供商(InP)建造和部署的物理网络组成，这些底层的物理网络包括大量支持虚拟化的可编程节点，例如可重构的虚拟路由器、服务器及终端等。InP通过将底层网络资源虚拟化为多个“切片”的资源，然后对虚拟化的资源以统一描述方式将底层资源的细节屏蔽，为上层提供统一的虚拟资源抽象SP通过中间商Broker向InP申请和“租赁”物理资源，构建独立的虚拟网络，并在该虚拟网络上部署自己的网络架构，运行独立的定制协议，来为用户提供服务。 网络虚拟化环境中主要参与者的功能如下：基础设施提供商：网络虚拟化环境下，基础设施提供商部署并管理底层的物理网络资源，负责物理基础设施的运营及维护，并通过可编程的接口向不同的服务提供商提供资源。基础设施提供商 5.4 神经网络与遗传算法简介 在本节中，我们将着重讲述一些在网络设计、优化、性能分析、通信路由优化、选择、神经网络控制优化中有重要应用的常用的算法，包括神经网络算法、遗传算法、模拟退火算法等方法。用这些算法可以较容易地解决一些很复杂的，常规算法很难解决的问题。这些算法都有着很深的理论背景，本节不准备详细地讨论这些算法的理论，只对算法的原理和方法作简要的讨论。 5.4.1 神经网络 1. 神经网络的简单原理 人工神经网络（Artificial Neural Networks，简写为ANNs）也简称为神经网络（NNs）或称作连接模型（Connectionist Model），是对人脑或自然神经网络（Natural Neural Network）若干基本特性的抽象和模拟。人工神经网络以对大脑的生理研究成果为基础的，其目的在于模拟大脑的某些机理与机制，实现某个方面的功能。所以说, 人工神经网络是由人工建立的以有向图为拓扑结构的动态系统，它通过对连续或断续的输入作出状态相应而进行信息处理。它是根据人的认识过程而开发出的一种算法。假如我们现在只有一些输入和相应的输出，而对如何由输入得到输出的机理并不清楚，那么我们可以把输入与输出之间的未知过程看成是一个“网络”，通过不断地给这个网络输入和相应的输出来“训练”这个网络，网络根据输入和输出不断地调节自己的各节点之间的权值来满足输入和输出。这样，当训练结束后，我们给定一个输入，网络便会根据自己已调节好的权值计算出一个输出。这就是神经网络的简单原理。 2. 神经元和神经网络的结构 如上所述，神经网络的基本结构如图5.35所示： 隐层隐层2 1 图5.35 神经网络一般都有多层，分为输入层，输出层和隐含层，层数越多，计算结果越精确，但所需的时间也就越长，所以实际应用中要根据要求设计网络层数。神经网络中每一个节点叫做一个人工神经元，他对应于人脑中的神经元。人脑神经元由细胞体、树突和轴突三部分组成，是一种根须状蔓延物。神经元的中心有一闭点，称为细胞体，它能对接受到的信息进行处理，细胞体周围的纤维有两类，轴突是较长的神经纤维，是发出信息的。树突的神经纤维较短，而分支众多，是接收信息的。一个神经元的轴突末端与另一神经元的树突之间密 单纯形法求解线性规划的思路及重要参数 的推导 在求解线性规划问题的算法中，单纯形法是一种成熟、简便、有效的算法，在目前应用最为广泛。因此，我们组通过查阅资料以及小组讨论的形式，分工合作，共同探讨出单纯形法求解线性规划的思路。 一般线性规划问题有时具有线性方程组的变量数大于方程个数 的情况, 这时就使得方程有不定的解。这时就可以使用单纯形法来求解，从线性方程组中找出一个个的单纯形, 每一个单纯形可以求得一组解, 然后再判断该解使目标函数值是增大还是变小, 决定下一步 选择的单纯形。在这其中每一个单纯形所对应的解其实都相当于n维空间图形中的一个顶点，我们就是要一个顶点，一个顶点的找到使目标函数值更好的顶点, 直到目标函数实现最大值或最小值为止。这样问题就得到了最优解。 具体的求解步骤来说有6步：1：建立基本可行解。2：计算变量的检验数。3：判断是否最优。4：若不是最优解，则换基。5：计算新的基本可行解。6：迭代计算直到求的最优解或者可判断无最优解为止。 接下来，我们通过具体的事例来详细介绍具体的求解步骤，并列出重要参数以及定理的推导过程。 某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品, 已知生产单位产品所需的设备台时及A、B 两种原材料的消耗, 如下表所示。 该工厂每生产一件产品Ⅰ可获利2 元, 每生产一件产品Ⅱ可获利3元, 问应如何安排计划使该工厂获利最多? 解：根据题意建立其标准型： max z = 2x1 + 3x2 + 0x3 + 0x4 + 0x5 (1) x1 +2x2 +x3 = 8 4x1 + x4 = 16 (2) 4x2 +x5 = 12 x j ≥0 , j = 1 , 2 , ? , 5 一、建立基本可行解 在标准型中x3 , x4 , x5为转化为标准型时加入的松弛变量，从(2)式中可以看到x3, x4 , x5的系数列向量 1 0 0 P3 = 0 , P4 = 1 , P5 = 0 0 0 1 而这些列向量就可以看做一个初始可行基 1 0 0 B = ( P3 , P4 , P5 ) = 0 1 0 0 0 1BP神经网络算法步骤
数值分析龙贝格实验报告
单纯形法求最优解问题及一些知识点整理
人工神经网络算法
Romberg龙贝格算法实验报告.
单纯形法的解题步骤
(完整word版)深度学习-卷积神经网络算法简介
龙贝格积分实验报告
基于元胞遗传机制的虚拟网络映射算法
matlab计算方法实验报告5(数值积分)
人工神经网络BP算法简介及应用概要
虚拟网络映射算法
神经网络与遗传算法
单纯形法求解思路及重要参数的推导