代数算法

代数算法（精选3篇）

代数算法 篇1

1、引言

最短路径算法使得网络中从源节点到接收节点的所选路径的链路权重之和最小，网络路由只要求从源节点到目的节点的最短路径。Dijkstra算法是图论中寻找最短路径的算法，把它应用到网络路由中，虽然能得出最短路径的最优解，但由于它遍历计算的节点很多，效率低。Bellman Ford算法是寻找最短路径的分布式算法，适合网络路由，但是各节点在不同步的情况下就可能得不到最优解。并且这两种算法都无法获得网络存在的全部可用路由。本文介绍的逻辑代数运算规则用来解决路由算法问题，可以计算出网络两节点间存在的全部路由，能够快速收敛且易于进行高速并行计算，避免闭环的出现。同时考虑QoS度量，可以得到满足度量标准的结果。

2、服务质量（QoS）度量

通常情况下，通过分析到达目的节点的所有路由并按度量标准的最小值来选择路由的方法确定网络之间最短路径。重要参数QoS度量根据性质的不同可以分为相加性度量、相乘性度量和最小性度量3类。对于路径P= (v1, v2, ..., vs) ，若eij∈P，将eij的第j个属性记为m (vi, vj) ，整个路径P的属性记为m (vi, vs) ，则以上3类度量的定义如下：

(1) 相加性度量。对任意路径P= (v1, v2, ..., vs) ，若m (v1, vs) =m (v1, v2) +m (v2, v3) +...+m (vk, vs)

则称路径P的这个属性为相加性度量。相加性度量包括延迟、抖动、成本等。例如，一条路径P的延迟为从源到目的地的所有链路延迟的总和。

(2) 相乘性度量。对任意路径P= (v1, v2, ..., vs) , 若m (v1, vs) =m (v1, v2) ×m (v2, v3) ×...×m (vk, vs)

则称路径P的这个属性为相乘度量。例如，分组丢失率为相乘性度量。

(3) 最小性度量，对任意路径P= (v1, v2, ..., vs) ，若m (v1, vs) =min[m (v1, v2) , m (v2, v3) , ..., m (vk, vs) ]

则称路径P的这个属性为最小度量。例如，带宽为最小性度量，即路径带宽为路径上瓶颈链路的带宽。

3、逻辑代数规则路由算法

逻辑代数运算规则路由算法利用节点之间的直接连接进行逻辑代数规则运算来求出两个节点之间所有路由。对于具有n个节点的网络只需n-2次运算，就可以找到全部路由，且结果中不会出现闭环路由。具体计算步骤、方法与规则如下：

(1) 建立关联分组并确定元素的初始表达式。

设网络有n节点，序号为1, 2，...，n。设1为源节点、n为目的节点。建立除节点n以外的n-1个节点的关联组M1=[m12, m13, …, m1n]M2=[m22, m23, …, m2n], Mn-1=[m (n-1) 2, m (n-1) 3, …, m (n-1) n]。其中，Mi表示节点i的关联分组，mij为该分组中的元素，代表i和j两节点的连接关系。i和j的取值范围为：i=1, 2, …，n-1;j=2, 3, …，n。分组中元素nij的初始表达式按照如下定义得到：

当i=j时，表示节点本身，则元素初始表达式为：mij=1;

当节点i到j方向无直接连接链路时，则元素初始表达式为：mij=0;

当Xij为节点i到j方向的直接连接链路时，则元素初始表达式为：mij=Xij;

当Xij1, Xij2, …, Xijn等为节点i到j方向存在的多条并联直接连接链路时，则元素初始表达式为：mij=Xij1+Xij2+…+Xijn。

(2) 关联分组间的变换与整合运算。算法进行一次变换与整合运算所采取的方法、遵循的规则为：

假设准备要删除编号为k (k≠1) 的中间节点分组Mk，则应以Mk分组为参考，对其它分组Mi (i=1, 2，…，n-1, i≠k) 中的元素进行变换运算。分组中除了元素mik之外，组中的其它元素均需要进行变换与整合运算。当Mk与其它关联分组逐一完成变换与整合运算后，删除关联分组Mk以及其它组中带有k脚标的元素实现此次整合。完成一次整合后所剩余的关联分组，不仅分组的数量减少一组，而且每组中元素的个数也减少一个。通过以上介绍可总结出进行一次变换与整合运算，各分组中元素的变换、整合计算公式为

式中，mij, mik, mkj表示整合前分组中的元素表达式，m′ij代表整合之后分组中的新元素表达式，其中i=1, 2，…，n-1;j=2, 3，…，n, 且i、j≠k。需要说明的是，变换运算及整合过程中必须利用逻辑化简公式及规则简化每一个元素表达式，使之始终保持为最简“与或”逻辑表达式。

(3) 求得两节点间全部路由。

对于有n个节点的网络，除了源节点和目的节点以外，将有n-2个中间节点。算法需要按照第 (2) 步介绍的方法，逐一删除所有中间节点的关联分组，最终只剩下源节点的关联分组，且该组也仅剩下一个元素。此时元素表示的就是源节点和目的节点连接关系，其“与或”逻辑表达式的每一个逻辑乘积项就是一条路由，所有逻辑乘积项的集合就是要寻找的源节点到目的节点间全部路由。

删除n-2个中间节点分组的先后顺序可以任意，并不会影响最终计算结果。而在求解出全部路由以后，可以根据QoS度量结合目标函数来分析可行路径，从而最终找到满足QoS度量需求的最佳路径。

4、算法示例

若网络链接如图1所示，求源节点 (1) 到目的节点 (5) 之间所有存在的路由。设链路状态属性=（延迟，带宽，花费），求服务质量较优的可行路径P。

其中X1=（1, 5, 7）, X2=（2, 4, 2）, X3=（3, 2, 3）, X4=（6, 2, 2）, X5= (4, 2, 3) , X6= (1, 4, 5) , X7= (5, 3, 3) , X8= (1, 1, 3) 。

求解过程：

(1) 因为有5个节点，因此需要建立4个关联分组，各关联分组为

我们根据前面介绍得知5个节点需要进行3次关联分组间的变换与整合运算，运算过程为

首先，取节点 (2) 关联分组进行处理，经过变换与整合运算并删除M2后得到：

然后，取节点 (3) 关联分组进行处理，删除M′3后得到整合结果：

最后，取节点 (4) 关联分组进行处理，删除M'4'后得到整合结果：

于是得到源节点 (1) 到目的节点 (5) 可能的9条路由

(2）若链路状态属性=（延迟，带宽，花费），由QoS相加性度量、最小性度量有

使用Matlab7.0来显示的运算结果如图2所示。

根据图2看出服务质量较优的可行路径P有：延迟最小的路径为L1、L4，带宽最大的路径为L1，花费最小的路径为L9，服务质量从链路状态属性=（延迟，带宽，花费）考虑较优的可行路径P为L1。

5、结束语

本文介绍的基于QoS度量和逻辑代数运算规则的路由算法，是用逻辑代数运算规则计算出网络两节点间存在的全部路由后，再根据QoS度量计算出最佳路径。由于算法只涉及逻辑代数运算，而且规律性和目标性强、收敛速度快，所以非常容易编写计算机程序，程序运行一次即可得出网络两节点间的所有路由。算法还具有兼容性强、适用范围广等特点，只要对路由结果进行简单的代数运算处理，该算法的独立性又适合并行运算，可实现对大型复杂网络计算的高速处理。在以后的工作中可以根据QoS度量具体设计目标函数以及约束函数，从而更好地应用到各种类型的网络路由计算中。

摘要：基于服务质量QoS的路由的主要目标是为接入的业务选择满足服务质量要求的传输路径, 同时保证整个网络资源的有效利用。逻辑代数运算规则路由算法是利用节点之间的直接连接进行逻辑代数运算来求出两个节点之间的所有路由。本文总结出了基于服务质量度量和逻辑代数运算规则的路由算法, 并给出了算法示例。

关键词：路由算法,服务质量,逻辑代数

参考文献

[1].刘荣慧.基于覆盖网的QoS问题研究综述[J].信息技术, 2009.2

[2].潘锦.Internet服务质量路由算法研究[J].贵阳金筑大学学报, 2005.59 (3)

[3].包学才.服务质量路由算法仿真平台的设计与实现[J].计算机与现代化, 2009.1

[4].戴伏生, 宋立众.通信网络路由新算法[J].南京邮电学院学报, 2005.25 (2)

代数算法 篇2

转炉终点控制技术一般包含静态模型和动态模型。静态模型是在吹炼前根据冶炼初始条件和终点目标,基于物料平衡和热平衡原理,运用数据统计、增量模型和人工智能等方法,确定吹炼、加料模式以指导生产操作。动态模型是在静态模型的基础上,直接或者间接测定吹炼过程中特别是吹炼后期的熔池成分、温度以及炉渣状况等动态信息,对吹炼参数进行修正,以达到预定的吹炼目标。静态模型是动态模型的基础,动态模型则是对静态模型控制精度的提升,是转炉终点控制的发展方向。

有副枪转炉炼钢工艺应用十分广泛,其主要特点是使用副枪在转炉冶炼后期测定结晶碳质量分数和钢液温度,并启动动态模型计算后续吹氧量和温控剂投入量,以保证吹炼终点达到目标温度和结晶碳质量分数。以副枪检测信息为基础的动态控制模型,对提高冶炼效率、改善生产环境和降低生产成本具有重要的作用[1,2]。

现在采用的有副枪转炉动态模型大多为代数模型。代数模型使用线性和指数函数来描述转炉吹炼后期的复杂非线性过程,结合参数自学习算法,可以有效地提高结晶碳质量分数和钢液温度终点命中率。而对于不能实现碳、温终点双命中的情况,需要根据工艺需求调整目标为舍碳保温或者舍温保碳。为此,研究合适的算法用于转炉后期的目标调整十分重要。近年来,一些人工智能技术特别是神经网络算法逐渐应用到转炉生产过程的控制和优化中[3,4],而对于传统代数模型存在的问题缺乏持续的研究。特别是当工艺条件受限,无法实现碳、温度双命中时,如何进一步地优化算法以保障关键目标,还未见相关的文献。

本文以基于副枪检测的转炉代数动态模型为研究对象,提出基于代数模型的碳温目标调整算法,不仅可以根据工艺的具体要求,权衡目标碳和温度的关系,而且可以灵活地实现舍温保碳和舍碳保温,以确保关键目标。该算法于2011年10月在广东某厂130 t转炉中投入应用,取得了良好的效果。

1代数动态模型及动态控制

代数动态模型主要通过实验研究以及实际经验得到。代数模型往往与生产厂家和设备情况密切相关,不同厂家的代数动态模型的结构和形式可能存在较大的差异。但是这类模型的共性就是通过解析式来表示生产过程中各个工艺参数之间的数学关系。基于代数模型的转炉副枪动态控制就是利用这些解析式,根据副枪测定的结晶碳质量分数和钢液温度,计算要达到目标所需要的吹氧量和温控剂投入量,以实现动态调整。

1.1脱碳升温解析式及参数自学习

1.1.1 脱碳解析式

脱碳解析式以副枪检测碳质量分数为基点,建立吹炼后期的结晶碳质量分数与吹氧量、温控剂加入量之间的关系。目前脱碳解析式大都采用钢液脱碳过程的动力学经验公式[5]:

undefined

式中,C(t)为t时刻钢液中碳的预测质量分数,%;C0为极限碳质量分数,达到此值后,继续供氧也不再发生脱碳反应,%;β为系数;CM为副枪检测时刻的结晶碳质量分数,%;α为理论最大脱碳速度,理论值为1.07,t/m3;VO(t)为t时刻的吹氧量,m3;VOM为副枪测量时刻的吹氧量,m3;hi为第i种类型温控剂供氧系数,m3/t;ri(t)为第i种类型动态温控剂投入量,t;WST为钢水量,t。

1.1.2 升温解析式

升温解析式以副枪检测温度为基点,建立吹炼后期的温度与吹氧量、温控剂加入量之间的关系。一般认为转炉冶炼后期,温度的变化与供氧量成线性关系。目前升温解析式大都采用钢液升温过程的经验公式[5]:

undefined

式中,T(t)为t时刻钢液的预测温度,℃;TM为副枪检测时刻的钢液温度,℃;γ为吹氧升温系数,(℃·t)/m3;δ为升温系数,℃;ki为第i种温控剂的冷却能力,℃/t;ε为碳降温度系数,℃。

1.1.3 参数自学习

为了提高代数模型的精度和命中率,需要对其中的参数进行自学习优化。具体而言,就是将达到吹炼要求并且命中合格的炉次在生产过程中采用的碳、温各项指标带入公式(1)和(2)中, 通过参数自学习确定常系数α,β,γ,δ,ε的较佳取值,并将这些参数运用于后续炉次动态控制量的计算中。自学习时,采用高斯-牛顿算法对公式(1)中的脱碳参数α,β进行回归分析,采用线性回归算法对公式(2)中的升温参数γ,δ,ε进行回归分析。

通过对参数分类标准的严格划分和自学习算法的优化,可以有效提高转炉冶炼终点碳、温度双命中率。

1.2动态控制原理

如前所述,动态模型以静态模型为基础,应用副枪、自动测温装置等检测吹炼过程中的熔池成分、温度以及炉渣状况等动态信息,对吹炼过程进行修正,以达到预定的吹炼目标,两者之间既相对独立又相互关联[6]。静态控制和动态控制的基本原理如图1所示。

转炉冶炼的前期和中期仍按静态模型吹炼。在吹炼末期到达终点前2～3 min时,下副枪检测结晶碳质量分数和钢液温度,进入动态控制阶段。从动态检测点到冶炼终点之间的动态控制阶段,碳温变化规律可以通过公式(1)和(2)来描述。

如图1所示,转炉终点控制目标是以目标碳质量分数和钢液温度为中心的动态目标窗口。只要让终点碳、温度进入该窗口内,则冶炼结果满足工艺要求。不同的厂家对窗口的定义不同。表1为对广东某厂130 t转炉终点碳、温度命中窗口的定义。

当工艺条件受限,在无法实现碳、温度双命中的情况下,通过调整动态控制量(温控剂、吹氧量等),可以让碳、温中的某一个关键指标命中目标范围。

2碳温目标调整算法

转炉冶炼后期的吹氧降碳是一个加热升温过程,在降低结晶碳质量分数的同时会导致温度的升高,因此结晶碳质量分数和温度是两个相互关联而又相互制约的目标。在动态控制中,如果升温超过了目标温度,则可以添加温控剂降温;如果脱碳吹氧达不到温度目标要求,有的工厂则添加升温剂,有的工厂则认定为事故,也有很多工厂不添加升温剂,而是继续吹氧以提高温度。因此,在冶炼后期可能出现碳质量分数已经进入范围边界而温度仍然没有达到要求,或者温度达到要求而碳质量分数超出目标范围的情况。此时,应根据工艺需求对目标进行调整,以保证关键目标。为此,研究代数模型中的碳、温度目标调整算法,在无法实现双命中时将冶炼目标调整为舍碳保温或者舍温保碳是十分必要的。

该算法引入碳命中权重W[c]和温度命中权重W[temp]的概念,且W[c]+W[temp]=1。权重描述碳和温度在整体评价中的重要程度。W[c]=W[temp]表示碳与温度的命中同样重要,W[c]>W[temp]表示目标倾向保碳,W[c]

undefined

由于绝对权值φ的偏向性很高,容易偏向温度和碳其中的一个,因此计算最小φ可以减小预测值与目标值的偏差。代数模型优化算法流程图如图2所示,其中体现了权重的调整规律。

上述流程中,在确定了碳温权重W[c]和W[temp]之后,搜索可行结果的具体步骤是:

(1)已知脱碳系数α,β,升温系数γ,δ,ε,碳温目标设定值Caim,Taim,设置吹氧量调节步长为Vup和Vdown(Vup为增加一个步长的吹氧量,Vdown为减小一个步长的吹氧量),温控剂调节步长为rup和rdown(rup为增加一个步长的温控剂,rdown为减小一个步长的温控剂)。

(2)在求解式(1)和(2)之后,得到补吹氧量和温控剂量,以此为基础,先按一个步长分别增加或减小吹氧量和温控剂量并分别预测终点碳质量分数和温度,按式(3)求得φ1,φ2,φ3,φ4及Min(φ1,φ2,φ3,φ4)=φmin 1,令φhis_min=φmin 1(φhis_min为循环过程中记录的上一轮修正后的φmin),若此时碳温已到目标窗口以内,则转向第(5)步;否则执行第(3)步。

(3)将吹氧量和温控剂步长减小为当前步长的一半,即Vup=Vup/2,Vdown=Vdown/2,rup=rup/2,rdown=rdown/2。

(4)按式(3)找到第2个极小值φmin 2,如果φmin 2<φhis_min,则令φhis_min=φmin 2,此时碳温若已到目标窗口以内,则转向第(5)步,否则转向第(3)步。

(5)按调整后的吹氧量和温控剂量进行碳温控制。

在偏差的绝对权值φ中可以体现碳、温在目标中的权值。在实际生产中,当由于现实原因,无法做到碳、温度双命中时,需要人工选择命中其中的一个指标:对于无法双命中的炉次,或者首先保温,再通过后续操作继续微调碳质量分数;或者首先保碳,再通过后续操作继续微调温度。这样,通过调整碳、温命中权重系数W[c]和W[temp],灵活实现了舍温保碳或者舍碳保温。

3结束语

2011年5月广东某厂130 t转炉自动炼钢系统投入使用,并取得了较高的碳温双命中率,但是对没有实现双命中的炉次,系统却没有偏向性地命中关键目标。为此,该算法于2011年10月上线,经过一年多的实践,整体运行情况良好。

我们对该系统的碳、温双命中率进行统计分析,进而对未能实现双命中的炉次进行分析。选取该厂的200炉实绩数据,其中100炉作为学习炉次,另外100炉用于精度校验,其中碳和温度的命中权重系数设置为W[c]=0.5,W[temp]=0.5。终点碳、温命中率如表2所示。

我们对无法实现碳、温度双命中的炉次进行调整,并对终点结晶碳质量分数和温度的命中情况进行统计分析。选取160炉未实现双命中的实测数据,其中80炉设置为舍温保碳,80炉设置为舍碳保温。目标调整算法效果如表3所示。

表3显示,在无法实现碳质量分数和钢液温度双命中的情况下,通过优化算法,可以灵活地实现舍温保碳或者舍碳保温,满足了生产需要。

参考文献

[1]Galloway S M,Green M J,Balajee S R,et al.Improvementin furnace performance at Inland Steel Company’s No.2BOF shop through models utilization and standardization ofoperation practices[C]//Steelmaking Conference Pro-ceedings.Pittsburgh:American Iron and Steel Society,1991:389-396.

[2]Andersion D,Barnes C M,Whittaker H J.Fully dynamicprocess control of the BOS in British’s Steel[C]//Steel-making Conference Proceedings.Pittsburgh:American Ironand Steel Society,1991:379-387.

[3]杜斌,郑贻裕,钱卫东.有副枪转炉模型的研究与应用[C]//2001年中国钢铁年会论文集[下卷].北京:冶金工业出版社,2001:479-484.

[4]郭亚芬,杜斌,陈军鹏.宝钢转炉过程控制模型研究应用新进展[C]//2005年中国钢铁年会论文集[下卷].北京:冶金工业出版社,2005:714-716.

[5]王连华,李江.转炉炼钢动态过程控制量算法的改进[J].江苏冶金,2003,31(1):45-47.

代数算法 篇3

关键词：近世代数,代数思想,渗透

一、近世代数的重要作用

近世代数是大学数学与应用数学专业以及信息与计算机专业的基础课程之一,是以研究抽象代数系统的性质与构造为主的一门课程,故也称之为抽象代数,近世代数也是现代数学各个分支的基础。随着科技的不断发展与实际应用的需要,近世代数的基本理论与基本思想越来越渗透到各个学科领域,特别是电子计算机、信息与编码等领域。因此,近世代数教学中一些基本的代数思想的渗透不论对学生今后的数学学习还是从事其他学科的研究工作都有着重要的指导意义。

二、近世代数中的几种重要基本代数思想

(一)同态与同构思想。

近世代数主要是研究带有运算的集合,也即代数系统。因此,近世代数一般很少考察一般的映射,而是重点考察和运算有关的映射,也就是同态映射和同构映射。同态映射和同构映射主要是研究代数系统之间的关系,由已知的代数系统的性质推得未知的代数系统的性质,特别地,同构映射是比较两个代数系统最有力的工具,因为互相同构的代数系统的运算性质是完全一样的。因此,同态与同构思想是研究代数系统有效的代数思想方法之一。

(二)等价分类思想。

研究代数系统除了同态与同构思想之外,另外一种常用方法就是把代数系统分成若干个子集来加以讨论,也就是集合的分类。所谓集合的分类是把集合的全体元素分成若干互不相交的子集。通常是给出所研究的代数系统上的一个等价关系,利用此等价关系来对代数系统分类。集合的分类与集合的等价关系之间密切相连,即集合的一个分类决定集合上的一个等价关系,反过来,集合上的一个等价关系也决定一个集合的分类。正因为如此,等价分类思想的地位显得尤其重要。

(三)子代数(系统)思想。

研究代数系统另外一种常用方法就是用其子代数系统来研究原代数系统,特别地,要根据子代数系统的特征对原代数系统进行分类,一般是利用子代数系统建立集合上的等价关系,再利用等价等价关系对代数系统进行分类。如群论的全部内容都在不同程度上和子群有联系。

三、如何在教学中渗透上述几种代数思想

(一)同态与同构思想的渗透。

在介绍同态映射与同构映射的定义时,强调:同态映射的本质是保持运算的满射,类似地,同构映射的本质是保持运算的双射(一一映射)。虽然课本中同态映射与同构映射的定义是以带有一个代数运算的代数系统为例给出来的,但经过上述强调后,学生很自然而然地给出带有多个代数运算的代数系统的同态映射的定义与同构映射的定义。如,群是带有一个代数运算的代数结构,学习了群同态与群同构之后,在学习带有两个代数运算的代数结构——环与域的时候,学生便很容易理解环(域)同态与环(域)同构的概念,在介绍定义之前,可以让学生先自己给出环同态与环同构的定义,以加深对同态映射与同构映射概念的理解。

(二)等价分类思想的渗透。

此代数思想的重点是理解等价关系和分类的联系,在介绍等价关系和分类间的联系的定理时,强调:互相等价的元素同在一类,不再同一类的元素是不等价的。特别在后面介绍群的左(右)陪集时,要给学生强调就是利用子群建立群上的等价关系并对群进行分类,这些类就是子群的左(右)陪集。进一步可得到著名的拉格朗日定理,体现了等价分类思想重要应用的一个方面。另外,利用正规子群建立群上的一个等价关系对群进行分类,这些类就是子群的陪集,再与群同态及同构结合起来,得到了群的三大同构定理。类似地,在研究环的时候,利用理想(与不变子群地位相当)建立环上的等价关系并对环进行分类,得到相应的环同构定理。

(三)子代数(系统)思想的渗透。

子代数系统简称为子代数,在近世代数教材中没有提及子代数(系统)这一概念。实际上,在介绍群、环时所涉及到的子群、正规子群、子环、理想等都属于子代数。虽然教材中没有提及,但在介绍子群概念的时候就要把这一代数思想给学生介绍一下。强调:所谓子代数就是代数系统的非空子集关于该代数系统的运算也作成相同的代数系统。这样学生便能理解子群的本质就是群的非空子集关于该群的乘法运算也做成一个群。类似地,在学习后面的代数系统环时便很容易理解子环的概念。进而可以更好地理解特殊的子代数的概念,如正规子群、理想等相关概念。