多约束QoS路由算法综述_李敏
第2期71
[收稿日期] 2008-04-10
[基金项目] 广东省自然科学基金项目(7008733)
[作者简介] 李敏(1984-)，男(汉)，湖南省涟源市人，硕士，huan314@https://www.wendangku.net/doc/d710674131.html,
第6卷 第2期2008年6月深圳信息职业技术学院学报
Journal of Shenzhen Institute of Information Technology Vol.6 No.2Jun. 2008服务质量(QoS)是计算机网络研究领域的一个热点问题，目前的QoS研究主要通过两种方法提供服务质量保证: ①通过节点的控制为用户的业务预留资源，如RSVP; ②在网络中搜索出满足QoS要求的路径，即QoS路由。因为QoS路由有很好的可扩展性和适应性，还可以避免预留造成的资源浪费，所以QoS 路由成为解决QoS的关键技术。QoS路由是一种基于数据流QoS请求和网络可用资源进行路由的机制。QoS路径要能满足用户对某些度量参数的要求。QoS路由的度量参数包括带宽、代价、延迟、延迟抖动、丢失率和跳数等。根据运算规则，这些度量参数可分为加性度量参数、乘性度量参数和凹性度量参数。QoS度量参数中，代价、延迟等属于加性度量参数，丢失率属于乘性参数，带宽属于凹性参数。搜索QoS路径过程中，可以删除不满足凹性参数的链路，而乘性参数可通过取对数变为加性，所以QoS路由算法主要是搜索到满足一个或多个加性度量参数的路径。寻找同时满足多个独立的QoS约束的路径是一个NP完全问题。
按照业务对路由度量参数的约束要求，可以把基于度量参数的选路问题分为：参数受限和参数最优两种类型。参数受限是指业务要求某度量参数必须达到某个数值要求，如链路延迟不得大于100ms 等；参数最优是指业务并不对度量参数提出某最
小，最大的数值要求，而是期望得到目前网络能够提供的一条基于某度量参数的最好性能的路径，如要求该路径具有最大带宽或最小延迟等。
当前的研究主要集中在搜索出满足多个约束的QoS路径，以及信息不准确条件下的路由算法。
1 多约束QoS路由模型
一个网络可以用一个无向全赋图G=(V，E)表示，其中：图中顶点表示网络节点，边表示网络中连接节点的通信链路(1ink)。V表示网络的节点集合。E表示节点间的链路集合。为简化问题，假设该网络中每对节点之间至多只有一条链路，并且由于节点和链路的QoS具有等价性，只考虑链路上的QoS问题。
对于无向图G=(V，E)，e∈E。P表示从源节点s 到目的节点d的路径集合。对几个常用的QoS指标数学表示如下：
1）延时：delay(p)=()e p D e ∈∑
，D(e)为链路e上
的延时；
2）成本：cos ()()e p
t p C e ∈=∑
；C(e)为链路e上
的成本；3）瓶颈带宽：width(p)=min{ B(e)}，e p ∈ B(e)为EP链路e上的瓶颈带宽；
4）丢包率：()1(1())e p
loss p L e ∈=?
?∏，L(e)
多约束QoS路由算法综述
李敏1，陆芸婷2
（1.深圳大学信息工程学院，广东 深圳 518060
2.深圳信息职业技术学院信息技术研究所，广东 深圳518029）
摘 要：保证服务质量的QoS 路由（Quality of Service Routing ）是网络中解决QoS 问题的一项关键技术。QoS 路由的主要目标是为接入的业务选择满足服务质量要求的传输路径，同时保证整个网络资源的有效利用。度量参数选择问题、寻路问题和路由信息不准确问题是QoS 路由中的几个主要研究内容。多约束QoS 路由算法通常是NPC 问题，本文先对QoS 路由中的问题进行分类，再对当前研究的一些多约束QoS 路由算法进行了归纳与分析。这些算法对于在Internet 中实现QoS 有着重要的指导意义。
关键词：服务质量路由(QoSR);多约束路由;NP(Non-deterministic Polynomial)完全问题;多约束路由算法中图分类号：TP393 文献标识码：A 文章编号：1672-6332（2008）02-0071-06
72深圳信息职业技术学院学报第6卷
为链路上的丢包率。
多约束QoS问题是找一条路径p=(s，d)，使它满足以下条件：时延约束：delay(p)≤D，D表示时延约束；丢包率约束：loss(p)≤L，L表示丢包率约束；瓶颈带宽：1／width(p)≤1／B，B表示瓶颈带宽。
对于多约束路由问题，由于各个目标之间缺少统一的度量尺度，往往不能使每个指标都达到最优。所以，通常是尽可能兼顾多个目标，求其满意解。
2 多约束QoS路由算法
由于基于多个约束条件建立的网络模型可以更准确地反映实际的QoS路由选择问题，随着人们对网络服务质量要求的提高和网络规模的不断扩大，研究基于多约束条件的QoS路由算法，以获得良好的网络服务质量和高的网络资源利用率具有十分重要的研究意义。
QoS路由主要有单播、组播、广播、选播等，QoS的单播、组播路由算法研究已经进行多年，也取得了很多的研究成果，目前的主要研究集中在两个算法中NP难问题的启发式或近似算法。广播路由算法相对简单，主要考虑网络开销和信息扩散程度之间的关系。选播路由算法的研究才刚刚起步，相关研究成果不多。目前的网络中单播路由仍然占主导地位，因此，本文主要研究了多约束条件下的单播路由法。当然，组播路由是下一步的发展方向。
在研究多约束QoS路由算法之前，有必要对现有的路由算法进行介绍和归类。
2.1 基本路由算法简介
在这里将路由算法中解决最基础最常见的路由问题的一类算法统称为基本路由算法。
2.1.1 QoS单播路由算法
从许多算法中大致归纳出以下几种QoS单播路由算法[3] 。
1）最短路径算法
最短路径算法使得网络中从源节点到接收节点的所选路径的链路权重之和最小。Dijkstra 算法和Bellman-Ford算法是两个最著名的最短路径算法。最短路径算法可用来解决路径约束问题。
2）多路路由算法
当网络流量很小，网络资源总有剩余时，多路路由的首要任务是平衡网络负载以更好地利用网络资源，平衡的流量分布将增加未来连接请求的连通率。
3）启发式路由算法
启发式路由算法用于解决多限制条件下的QoS 路由问题。该算法可以降低算法的时间复杂度，但不能保证在即使存在传输路径的条件下发现一条可行的传输路径。
4）基于某种调度策略的路由算法
基于某种调度策略的路由算法是把分组调度算法引入路由算法的度量值计算中，可使路由计算得到简化，能较好地解决多受限QoS路由问题。
2.1.2 QoS多播路由算法
QoS多播路由问题基本上可分：单链路约束问题、多链路约束问题、单树约束问题、多树约束问题、链路最优化问题、树最优化问题。解决QoS多播路由问题的算法主要有最小生成树、Steiner树、约束Steiner树及最大带宽树等四种算法。
2.2 多约束QoS单播路由算法分类介绍
多约束QoS单播路由算法根据不同的角度可以分为不同的类，按照不同算法的不同特性以及相互之间的共性，本文分为以下几类：多项式非启发类，探测法，基于花费函数法，随机化求解，路径子空间搜索，归类印射(QoS度量简化算法)，伪多项式算法(受限最小约束)，仿生类。下面将一一加以介绍。
2.2.1 多项式非启发类
多项式非启发类算法本质上针对的是多项式可解的问题，而并不是典型的QoS路由问题，然而多项式可解这类问题及对其进行的求解思路却是QoS 路由算法的基础。
赵海雁和陈立潮使用Dijkstra最短路径树算法实现了时延、成本受限的路由求解[4] 。先通过修剪不满足QoS需求的所有链路，瓶颈约束条件可作为预处理步骤来处理，这样就可以仅考虑可加约束条件时延和成本。为了更准确地模型化一个网络，他们仅用两个约束条件来简化NPC问题，这个就是“最短度量约束路径”的NPC的简单问题。在非线性路径的情况下， 线性路径的度量与路径中所有链路度量的和不相等， 即最优路径的一部分不一定是最短路径。 在这种最短路径与最小度量不相
第2期73
李敏，陆芸婷：多约束QoS路由算法综述
符的非线性能量函数的情况下，应用k最短路径算法来有效地寻找受时延、成本约束的路径，并把路径的多个约束条件(时延、成本)转化为单一的路径度量( D= kDc+ Dd )约束，因而易于实现。此方法的优点是对于不能同时满足时延、成本约束的路径全部被修剪，所以搜索空间得到了降低， 优化了搜索空间，提高了运行速度。他们还在此思想上提出了层次Dijkstra最短路径算法。
Wang和Crowroft用Dijksrta最短路径树算法实现了基于延迟、带宽约束的源路由求解[5] 。
2.2.2 探测法
探测法的思想是从源节点开始，通过向邻节点发送探测包或查询信息逐步逼近并到达目标节点。
shin和chou提出了一种基于延迟受限的算法[6] ，这个算法是分布式的。在这个算法中，各个节点并不要求保存全局状态，而是从源节点向目的节点广播路由信息，并且在这路由信息中累加了延迟。中间的各个节点在收到路由信息时，首先累加自己的延迟，如果依然小于规定的延迟，则再转发给其他邻居节点。由此一步一步探测下去，直到到达目的地为止。
2.2.3 基于花费函数法
通过研究花费函数，可以降低QoS路由算法的复杂度并提供更好的QoS支持，这样就能够保证所计算的最小花费路径能够满足QoS需求。此类算法应用广泛，涉及面广，以下提及的几种算法都可以归于此类。
1) J.M.Jaffe算法[7]
J.M.J a f f e设计了一个非线性花费函数：f(P)=max{w1(P)，L1}+max{w2(P)，L2}，要是可行路径存在的话，则f(P)函数取最小值时可以保证找到可行路径。但由于不存在简单的基于非线性函数f(P)的最短路径选择算法，为此，J.M.Jaffe提出了基于链路属性线性组合
w(u，v)=d1*w1(u，v)+d2*w2(u，v)
的近似算法。此算法先将两重约束转化为单重约束，从而通过最短路径算法求出最短路径。然后检查此路径是否满足约束条件，即wi<=Li(i=1，2)。
2) H-MCOP算法[8]
Korkmaz和Krunz提出了启发式多约束最优路由选择算法(H-MCOP)。H-MCOP算法是一种寻找满足多约束条件并尽可能理想的路径的算法。该算法分两个部分分别从正反两个方向使用了两次扩展Dijkstra算法。首先，是一个反向寻路过程，基于线性花费函数，从目的节点d出发，使用扩展Dijkstra 算法求出到达每个节点的最短路径，并对每个节点进行标号；然后，基于非线性花费函数，做一个正向寻路过程，再次使用扩展Dijkstra算法，对之前逆向搜索得到的节点和标号进行评估，最后求出多约束最优路径。
3) TAMCRA/SAMCRA算法[9]
H.De Neve和P.Van Mieghem提出了多约束路由算法TAMCRA，此算法的性能可调。然后他们又进一步提出了自适应多约束路由算法SAMCRA，TAMCRA算法中涉及到了通过非线性花费函数计算最短路径这个概念。
2.2.4 随机化求解
随机化指在搜索过程中搜索方向是随机的，这种思想可以避免在搜索可行路径的过程中，算法陷入未知的僵局。
Korkmaz和Krunz提出了一种解决多约束路由问题的随机化算法[10] 。首先，在初始化阶段，该算法先计算出每一个节点u到目的节点的所有最短路径；然后算法进入随机性搜索阶段，即从源节点开始，采用随机化的广度优先策略展开搜索。该算法充分利用了在初始化阶段得到的信息，选择有可能到达目的节点的下一跳进行搜索，同时有预见地避开可能陷入僵局的下一跳。如果第一次尝试不成功，则随机性地选择另一节点进行搜索，周而复始，直到成功到达目的节点。
2.2.5 QoS度量简化算法
把QoS的度量分类并通过映射的方法来解决多约束路由问题，称为QoS度量简化算法，有的论文也将其称为归类映射法。
Yuna和Liu设计了粒度受限的启发式算法[11] ，通过限制PATH(u)中最优路径的数目达到减小复杂度的目的。此算法是在基于EBFA的基础上做出的设计与改进。
Chen和Nahrstedt设计了多重路径受约束的源路由算法[12] 。该算法将QoS度量参数的取值范围R或Z 映射到一个有限集合C，以保证多项式可解。
2.2.6 伪多项式算法(受限最小约束法)
多约束路由问题通常以两个约束条件的路由问
74
深圳信息职业技术学院学报第6卷
题为具体的研究对象，将两个约束条件的路由问题转化成一个约束受限，另一个约束最小的问题来解决。这种方法称为受限最小约束法。对于延迟受限的最小花费问题(DCLC)，存在一些伪多项式时间的近似算法。对于任意e>0，存在一个多项式时间的算法能够找到一条路径，在满足延迟受限的同时，其花费不超过最小花费的(l+e)倍。由于这些算法的计算复杂度与e有关，因此又被称为伪多项式算法。
此类算法应该也比较广泛，下面提及的几种算法都可以归于此类。
1）Juttner基于拉格朗日松弛算法[13]
Juttner等基于拉格朗日松弛法设计了基于延迟受限的最小花费问题(DCLC)的源路由求解算法。算法首先构造路径花费函数()()()g p c p d p λλ=+?，其中c为原来的花费，d(p)为路径p的延迟，0λ≥。然后以()g p λ为关键字使用Dijkstra算法计算最短路径P，如果0λ=且同时p满足延迟要求，则P为原DCLC问题的最优解；如果p不能满足要求则可通过增大λ而加大对()g p λ的惩罚力度，求得满足延迟要求的路径。
令{{
}}
()min
()(,)
L g p p p s t D λ
λλ=?∈?其中D为延迟要求，则对0λ?≥有()L λ为原
DCLC问题的花费下界。算法通过计算特定的λ从而最大化()L λ得到花费下界，并给出一条可行路径。
2）A*剪除算法[14]
Liu和Ramakrishnan提出了A*剪除算法，这种算法考虑同时寻找满足多约束条件的单条或多条可行路径。对于每个QoS度量，首先分别从源节点和目的节点出发使用最短路径算法计算出所有最短路径，并在所有节点中保留其权值，权值将用来估测子路径是否将成为最终的可行路径。接着，从源节点开始使用基于端到端花费函数逐跳检测其邻居节点，如果邻居节点产生回路或不满足给定的约束条件，则此邻居节点将被剪除。检测和剪除得过程不断反复，直到多条最短路径形成或所有节点检查完毕。2.2.7 仿生类算法
有一类算法常常仿照自然界各种生物现象，本文将之形象地称为仿生类算法。遗传算法，蚁群算法等都可归于此类。
1）遗传算法
遗传算法(Genetic Algorithm，GA)是模拟生物群体进化过程，通过“优胜劣汰”法则保留优秀后代的一种新型优化算法。作为一种自适应、启发式的全局意义上的搜索算法，遗传算法具有很强的鲁棒性，并具有并行搜索，群体寻优的特点，已广泛用于解决具有NP难度的问题。运用遗传算法解决路由选择问题已有很多研究，如解决基于负载均衡的路由问题、QoS路由问题和时延费用最小问题等。
可以看出，同其他优化算法相比，利用遗传算法解决此类问题显得更为简单、有效。但采用一般的遗传算法解决QoS路由问题，容易收敛于局部解且在进行遗传算子(如交叉和变异)操作时染色体中会产生死遗传子，形成根本不存在的链路或造成循环链路，并且遗传算法本身还存在收敛速度和全局收敛性之间的矛盾。
针对这些问题，宋乃斌，高随祥，王营昌对传统遗传算法进行了一些改进[15] ，将遗传算法本身还存在收敛速度和全局收敛性之间的矛盾降低到可以忽略的程度，并利用该算法解决多约束的QoS路由问题，取得了较好的效果。
量子遗传算法(Quantumgenetic Algorithm，QGA)是新发展起来的一种基于量子计算原理的遗传算法，它采用多状态基因比特编码方式使一个量子染色体同时表征多个状态的信息，通过量子坍塌策略带来丰富的种群，采用动态调整旋转角机制引入量子变异，避免了早熟收敛。
孟维嘉，庞伟正设计了一个QoS路由的网络模型[16] ，针对这个模型，提出了一种基于量子遗传算法的多约束QoS路由的解决算法，详细讨论了该算法用于解决包含带宽，延时，丢包率和最小花费等约束条件在内的多约束QoS路由问题，给出了算法实现的方法和具体流程，再通过实验证明了该算法不但满足QoS约束要求，同时也可以均衡链路负载，很好地优化了网络资源。
2）蚁群算法
蚁群算法是M．Dorigo 1992年提出的一种优化方法。其主要特点就是：通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法。它充分利用了生物蚁群能通过个体间简单的信息传递，搜索从蚁巢至食物间最短路径的集体寻优特征。它不依赖于具体问题的数学描述，具有很强的全局优化能力和本质上的并行性；同时，
第2期75
李敏，陆芸婷：多约束QoS路由算法综述
具有更强的鲁棒性、求解时间短、易于计算机实现等优点。
马立肖，郭秀敏，赵占芳等设计了MQRAM模型[17] ，利用了蚁群系统，具有设计简洁性、鲁棒性、收敛性、灵活性的特点，该模型不仅可以保证多约束QoS路由的有效搜索，有效地解决了QoS路由在计算开销、鲁棒性等方面问题，具有一定的通用性和可扩展性。
陈岩，杨华江，沈林成首先建立了多约束QoS 路由模型[18] ，在该模型中通过引入模糊评判，消除了由于量纲导致的参数屏蔽现象，实现了多约束下的综合优化。然后提出了再励学习蚁群算法对该问题进行求解，算法针对基本蚁群算法容易陷入局部极值的情况，引入再励学习机制，通过对蚂蚁搜索路径的评价产生再励信号，根据再励信号采取不同的信息素更新策略，提高了收敛速度，减小了陷入局部极值的可能性，增强了寻优能力。
Fanjin Mai，Yezhang Liang提出了一种基于蚁群算法并考虑多个路由限制的优化QoS路由问题的方法[19] ，它选取带宽作为约束条件，把时延和丢失率作为QoS优化的目标，建立了QoS路由选择的多目标整数优化模型，并且，对蚁群算法的信息素更新策略进行了改进，并将其应用到QoS路由优化中。算法经过NC次循环，整个算法复杂度为O(NC*m*n2)。一般情况下，m取与n同一数量级，大致相等的情况下，效果最好，最终复杂度是O(NC*n3)。该方法收敛速度快，求解全局最优解的性能较高，具有一定的有效性。
本文涉及到的几种主要的单播多约束QoS路由算法性能比较如表1所示。
表1 单播多约束QoS路由算法比较
Tab.1 Comparisons among Qos algorithms with single broadcast
multi-constrained routing
算法时间复杂度空间复杂度
Jaffe算法O(NlogN+mM)O(N)
H-MCOP算法O(NlogN+mM)O(kmN)
TAMCRA/
SAMCRA算法
O(N m M)O(N)随机化算法O(mNlogN+mM)O(mN)
Chen近似算法O(mNlogN+mM)O(N)
A*剪除算法O(N!(m=N=NlogN))O(mN!)
3 结语
目前对QoS路由的研究主要集中于:高效率NP完全路由算法的搜索性算法、多QoS度量参数的状态聚合问题、不精确信息下的层次路由、QoS数据和尽力而为数据的融合问题等。随着网络日趋一日的复杂与庞大，客户对网络的要求也越来越高。如何满足多种需求的网络多约束QoS问题已经成为当下急需解决的问题。对多约束QoS路由算法的研究也具有特别重要的意义。
参考文献(References)
[1] 张世辉. 多约束QoS路由算法研究[D] . 沈阳：沈阳工业大学 2006.
ZHANG Shihui. Research on multi-constraint quality of service routing algorithm[D] . Shenyang:Shenyang University of Technology 2006. (in Chinese)
[2] 刘萍. IP QoS路由算法的研究[D] . 扬州：扬州大学 2006.
LIU Ping. Research on IP quality of service routing algorithm[D] . Yangzhou:Yangzhou University 2006. (in Chinese)
[3] 冀鑫泉，桂志波. Internet中QoS路由算法研究现状及其展望[J] . 江苏通信技术，2003，19(1)：13-16.
JI Xinquan，GUI Zhibo. Research on IP QoS routing algorithm[J] . Jiangsu Communication Technology，2003，19(1)：13-16. (in Chinese)
[4] 赵海雁，陈立潮. 多约束条件下最短路径QoS路由算法[J] . 华北工学院学报，2004，25(1)：49-51.
ZHAO Haiyan，CHEN Lichao. Algorithm for the shortest route on multi-constrained QoS routing[J]. J North China Institute of Technology，2004，25(1)：49-51. (in Chinese)
[5] Wang Z，Crowroft J. QoS routing for supporting resource reservation. IEEE Journal on Selected Areas in Communications，1996，
14(7):1228-1234.
[6] Shin K G，Chou C. A distributed route-selection scheme for establishing real-time channel. Sixth IFIP Int’s l Conf. On High
performance Networking Conf(HPN’95), 1995:319-329.
[7] J M Jaffe. Algorithms for finding paths with multiple constraints[J] . Networks，1984，(14): 95-116.
[8] T Korkmaz，M Krunz. Multi-constrained optimal path selection[A] . IEEE INFCOCO-M[C] ，2001.
[9] H De Neve，P Van Mieghem. TAMCRA: a tunable accuracy multiple constraints routing algorithm[J] . Computer Communications，
2000，23:667-679.
[10] T Korkmaz，M Krunz. A randomized algorithm for finding a path subject to multiple qos requirements[J] . Computer Networks,
76深圳信息职业技术学院学报第6卷
2001:251-268.
[11] Yuan X，Liu X. Heuristic Algorithms for Multi-Constrained Quality of Service Routing[A] . Proceedings of the IEEE
INFOCOM2001[C] . IEEE Communication Society，2001:844-853.
[12] Chen S，Nahrstedt K. On Finding Multi- Constrained Paths[A] . Proceedings of the IEEE International Conference on
Communications(ICC’98)[C] . IEEE Communication Society，2001:874~879.
[13] Juttner A. Szviatiovski Mecs B. Lagrange relaxation based method for the QoS routing problem[A] . Proceedings of the IEEE
INFOCOM2001[C] . IEEE Communication Society，2001:859-868.
[14] G Liu，K G Ramakrishnan. A*Prune: an algorithm for finding K shortest paths subject to multiple constraints[C] . ICC’03[C] ，
Anchorage，AK，USA，2003:1718-1722.
[15] 宋乃斌，高随祥，王营昌. 一种基于改进遗传算法的多约束QoS路由选择方法[J] . 微型机与应用, 2005，3:30-31.
SONG Naibin，GAO Suixiang，WANG Yingchang. QoS routing algorithm based on an ameliorative genetic algorithm[J] .
Microcomputer and application, 2005, 3:30-31. (in Chinese)
[16] 孟维嘉，庞伟正. 基于量子遗传算法的多约束QoS路由算法[J] . 应用科技, 2007，34(3):11-14.
MENG Weijia，PANG Weizheng. QoS routing algorithm based on quantum genetic algorithm[J]. Applied Science and Technology, 2007，34(3):11-14. (in Chinese)
[17] 马立肖，郭秀敏，赵占芳等. 基于蚁群系统的多约束QoS路由模型设计[J] . 现代计算机, 2007，255:4-6.
MA Lixiao，GUO Xiumin，ZHAO Zhanfang，et al. Design of an ant colony system based an model of multi-constraints QoS routing[J]. Morden Computer, 2007，255:4-6. (in Chinese)
[18] 陈岩，杨华江，沈林成. 基于再励学习蚁群算法的多约束QoS路由方法[J] . 计算机科学, 2007，34(5):25-44.
CHEN Yan，YANG Huajiang，SHEN Lincheng. A reinforcement learning based ant algorithm for multiple constrained QoS routing problem[J] . Computer Science, 2007，34(5):25-44. (in Chinese)
[19] Fanjin Mai，Yezhang Liang. Study Multiple Constrained QoS Routing Optimization Based on Modified Ant Colony Algorithm [J].
Journal of Communication and Computer, 2005，8.
[20] 胡永良. 启发式多约束路由算法研究[J] . 计算机工程与应用, 2005，30:155-157.
HU Yongliang. Research on heuristic multi-constrained routing algorithms[J]. Computer Project and Application, 2005，30:155-157. (in Chinese)
Multiple constraints-based QoS routing algorithm
LI Min1，LU Yunting2
（1. College of Information Engineering, Shenzhen University，Shenzhen 518060，P. R. China
2. Research of Information Technology, Shenzhen Institute of Information Technology,
Shenzhen 518029，P. R. China）
Abstract：The insurance of quality of service routing is a key technique of resolving problems of QoS in network. The primary target of QoS routing is to choose a path which satisfying the quality of service for the connected operation, and to ensure the effectiveness of using the resources of the whole network. The multiple constraint QoS routing algorithm is a NPC problem commonly. In this paper, the summary and analysis are made based on investigating typical algorithms on multi-constrained routing. These algorithms are very important for the purpose of realizing QoS in the internet.
Keywords: quality of service routing(QoSR); multiple constraint routing; NP-complete problem; multiple constraint QoS routing algorithms
（责任编辑：周学才）
基本差分进化算法
基本差分进化算法 基本模拟退火算法概述 DE 算法是一种基于群体进化的算法，其本质是一种基于实数编码的具有保优思想的贪婪遗传算法。由于DE 算法操作简单，寻优能力强，自提出以来引起了国内外学者的高度关注，目前已在电力系统优化调度、配网重构等领域得到了应用。 1、算法原理 DE 算法首先在N 维可行解空间随机生成初始种群P 0001[,,]N =X x x L ，其中000T 1[,,]i i iN x x =x L ，p N 为DE 种群规模。DE 算法的核心思想在于采取变异和交叉操 作生成试验种群，然后对试验种群进行适应度评估，再通过贪婪思想的选择机制，将原种群和试验种群进行一对一比较，择优进入下一代。 基本DE 算法主要包括变异、交叉和选择三个操作。首先，在种群中随机选取三个个体，进行变异操作： 1123()t t t t i r r r F +=+-v x x x 其中1t i +v 表示变异后得到的种群，t 表示种群代数，F 为缩放因子，一般取(0,2]，它的大小可以决定种群分布情况，使种群在全局范围内进行搜索；1t r x 、2t r x 、3t r x 为从种群中随机抽取的三个不同的个体。 然后，将变异种群和原种群进行交叉操作： 1,R 1 ,,R () or () () and ()t i j t i j t i j v rand j C j randn i u x rand j C j randn i ++?≤=?=?>≠?? 其中t 1,i j u +表示交叉后得到的种群，()rand j 为[0,1]之间的随机数，j 表示个体的第j 个分量，R C 为交叉概率，()randn i 为[1,,]N L 之间的随机量，用于保证新个体至少有一维分量由变异个体贡献。 最后，DE 算法通过贪婪选择模式，从原种群和试验种群中选择适应度更高的个体进入下一代： 11t 11 ()() ()()t t t i i i i t t t i i i f f f f ++++?<=?≥?u u x x x u x 1()t i f +u 、()t i f x 分别为1t i +u 和t i x 的适应度。当试验个体1t i +u 的适应度优于t i x 时，
多级反馈队列调度算法的实现
学生实习报告 课程名称_ 数据结构与数据处理应用训练 题目名称多级反馈队列调度算法的实现 学生学院计算机与计算科学 专业班级 学号 学生姓名 指导教师 2012年 2月 16 日 多级反馈队列调度算法的实现 【摘要】 多级反馈队列调度算法是操作系统中CPU处理机调度算法之一，该算法既能使高优先级的进程（任务）得到响应又能使短进程（任务）迅速完成。UNIX操作系统便采取这种算法，而本次试验就是试用C语言模拟某多级反馈队列调度算法。本次试验中前三级就绪队列采用时间片轮转法，时间片大小分别为2、4和8，最后一级就绪队列采用FIFO调度，将任务进入多级队列进行模拟，任务从优先级高的队列到优先级地的队列的顺序逐一进入，还用了算法支持抢占式，最后完成模拟，得到各个任务先后完成的顺序，还有得到各个任务的响应时间、离开时间、周转时间。 【关键词】队列优先级任务时间 1 内容与要求 【内容】 多级反馈队列调度算法是操作系统中CPU处理机调度算法之一，该算法既能使高优先级的进程（任务）得到响应又能使短进程（任务）迅速完成。UNIX操作系统便采取这种算法，本次试验就是试用C语言模拟某多级反馈队列调度算法，通过输入任务号、到达时间、运行时间，求出任务完成的先后顺序以及各个任务
的响应时间、离开时间、周转时间。 【要求】 多级反馈队列调度算法描述： 1、该调度算法设置四级就绪队列：前三级就绪队列采用时间片轮转法，时间片大小分别为 2、4和8；最后一级就绪队列采用FIFO调度。 2、任务在进入待调度的队列等待时，首先进入优先级最高的队列等待。 3、首先调度优先级高的队列中的任务。若高优先级中队列中已没有调度的任务，则调度次优先级队列中的任务，依次类推。 4、对于同一个队列中的各个任务，按照队列指定调度方法调度。每次任务调度执行后，若没有完成任务，就被降到下一个低优先级队列中。 5、在低优先级的队列中的任务在运行时，又有新到达的任务，CPU马上分配给新到达的任务。（注：与原来的题目不同，原题是在低优先级的队列中的任务在运行时，又有新到达的任务时，要在运行完这个时间片后，CPU马上分配给新到达的任务，而本题不需要在运行完这个时间片，即正在进行的任务立刻停止，CPU 马上分配给新到达的任务） 6、为方便实现，时间以1为单位，用整数数据表示；且每个时间点，最多只有一个任务请求服务（即输入）。 2 总体设计 算法总体思路： 这是建立在一个时间轴上的，即时刻，一个一个时刻（时间点）进行。 2.1.1 主函数思路：
进化计算综述
进化计算综述 1.什么是进化计算 在计算机科学领域，进化计算（Evolutionary Computation）是人工智能（Artificial Intelligence），进一步说是智能计算（Computational Intelligence）中涉及到组合优化问题的一个子域。其算法是受生物进化过程中“优胜劣汰”的自然选择机制和遗传信息的传递规律的影响，通过程序迭代模拟这一过程，把要解决的问题看作环境，在一些可能的解组成的种群中，通过自然演化寻求最优解。 2.进化计算的起源 运用达尔文理论解决问题的思想起源于20世纪50年代。 20世纪60年代，这一想法在三个地方分别被发展起来。美国的Lawrence J. Fogel提出了进化编程（Evolutionary programming），而来自美国Michigan 大学的John Henry Holland则借鉴了达尔文的生物进化论和孟德尔的遗传定律的基本思想，并将其进行提取、简化与抽象提出了遗传算法（Genetic algorithms）。在德国，Ingo Rechenberg 和Hans-Paul Schwefel提出了进化策略（Evolution strategies）。 这些理论大约独自发展了15年。在80年代之前，并没有引起人们太大的关注，因为它本身还不够成熟，而且受到了当时计算机容量小、运算速度慢的限制，并没有发展出实际的应用成果。
到了20世纪90年代初，遗传编程（Genetic programming）这一分支也被提出，进化计算作为一个学科开始正式出现。四个分支交流频繁，取长补短，并融合出了新的进化算法，促进了进化计算的巨大发展。 Nils Aall Barricelli在20世纪六十年代开始进行用进化算法和人工生命模拟进化的工作。Alex Fraser发表的一系列关于模拟人工选择的论文大大发展了这一工作。 [1]Ingo Rechenberg在上世纪60 年代和70 年代初用进化策略来解决复杂的工程问题的工作使人工进化成为广泛认可的优化方法。[2]特别是John Holland的作品让遗传算法变得流行起来。[3]随着学术研究兴趣的增长，计算机能力的急剧增加使包括自动演化的计算机程序等实际的应用程序成为现实。[4]比起人类设计的软件，进化算法可以更有效地解决多维的问题，优化系统的设计。[5] 3.进化计算的分支 进化计算的主要分支有：遗传算法GA ，遗传编程GP、进化策略ES、进化编程EP。下面将对这4个分支依次做简要的介绍。 1遗传算法（Genetic Algorithms）： 遗传算法是一类通过模拟生物界自然选择和自然遗传机制的随机化搜索算法，由美国John HenryHoland教授于1975年在他的专著《Adaptation in Natural and Artificial Systems》中首次提出。[6]它是利用某种编码技术作用于称为染色体的二进制数串，其基本思想是模拟由这些串组成的种群的进化过程，通过有组织地然而是随机地信息交换来重新组合那些适应性好的串。遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染
多目标进化算法总结
MOGA i x 是第t 代种群中个体，其rank 值定义为： () (,)1t i i rank x t p =+ ()t i p 为第t 代种群中所有支配i x 的个体数目 适应值（fitness value ）分配算法： 1、 将所有个体依照rank 值大小排序分类； 2、 利用插值函数给所有个体分配适应值（从rank1到 rank * n N ≤），一般采用线性函数 3、 适应值共享：rank 值相同的个体拥有相同的适应值， 保证后期选择时同一rank 值的个体概率相同 最后采用共享适应值随机选取的方法选择个体进入下一代 一种改进的排序机制（ranking scheme ）： 向量,1,(,,)a a a q y y y =???和,1,(,,)b b b q y y y =???比较 goal vector ：() 1,,q g g g =??? 分为以下三种情况：
1、 ()() ,,1,,1; 1,,; 1,,; a i i a j j k q i k j k q y g y g ?=???-?=????=+???>∧≤ 2、() ,1,,; a i i i q y g ?=???> 当a y 支配b y 时，选择a y 3、() ,1,,; a j j j q y g ?=???≤ 当b y 支配a y 时，选择b y 优点：算法思想容易，效率优良 缺点：算法容易受到小生境的大小影响 理论上给出了参数share σ的计算方法
NPGA 基本思想： 1、初始化种群Pop 2、锦标赛选择机制：随机选取两个个体1x 和2x 和一个Pop 的 子集CS(Comparison Set)做参照系。若1x 被CS 中不少于一 个个体支配，而2x 没有被CS 中任一个体支配，则选择2x 。 3、其他情况一律称为死结（Tie ），采用适应度共享机制选择。 个体适应度：i f 小生境计数（Niche Count ）：(),i j Pop m Sh d i j ∈= ????∑ 共享函数：1-,()0,share share share d d Sh d d σσσ? ≤?=??>? 共享适应度（the shared fitness ）： i i f m 选择共享适应度较大的个体进入下一代 优点：能够快速找到一些好的非支配最优解域 能够维持一个较长的种群更新期 缺点：需要设置共享参数
用于约束多目标优化问题的双群体差分进化算法
用于约束多目标优化问题的双群体差分进化算法 孟红云１ 张小华２ 刘三阳1 (1.西安电子科技大学 应用数学系，西安，71007１; 2.西安电子科技大学 智能信息处理研究所，西安,7１0０７1） 摘 要:首先给出一种改进的差分进化算法,然后提出一种基于双群体搜索机制的求解约束多目标优化问题的差分进化算法．该算法同时使用两个群体，其中一个用于保存搜索过程中找到的可行解，另一个用于记录在搜索过程中得到的部分具有某些优良特性的不可行解，避免了构造罚函数和直接删除不可行解.此外,将本文算法、N ＳGA-Ⅱ和SPEA 的时间复杂度进行比较表明，ＮS ＧA-Ⅱ最优,本文算法与SPE Ａ相当.对经典测试函数的仿真结果表明,与ＮＳGA-Ⅱ相比较，本文算法在均匀性及逼近性方面均具有一定的优势. 关键字: 差分进化算法；约束优化问题；多目标优化问题； 中图分类号：TP18 1 引言 达尔文的自然选择机理和个体的学习能力推动进化算法的出现和发展,用进化算法求解优化问题已成为一个研究的热点[1-3].但目前研究最多的却是无约束优化问题.然而，在科学研究和工程实践中,许多实际问题最终都归结为求解一个带有约束条件的函数优化问题,因此研究基于进化算法求解约束优化问题是非常有必要的.不失一般性，以最小化问题为例,约束优化问题（Constrai ｎｅd Opti ｍｉｚａtio ｎ Prob ｌｅm ，COP )可定义如下： )(COP ()()()()q j x h p i x g t s x f x f x f x F j i k R x n ,,1,0)( ,,1,0)( ..,,,)(min 21 ===≤=∈ (1) 其中)(x F 为目标函数,)(),(x h x g j i 称为约束条件,n n R x x x x ∈=),,,(21 称为n 维决策 向量．将满足所有约束条件的解空间S 称为（1)的可行域.特别的，当1=k 时,（1)为单目标优化问题;当1>k 时，（1）为多目标优化问题.)(x g i 为第i 个不等式约束,)(x h j 是第j 个等式约束.另一方面,对于等式约束0)(=x h j 可通过容许误差（也称容忍度）0>δ将它转化为两个不等式约束: ?????≤--≤-0 )(0)(δδx h x h j j （2） 故在以后讨论问题时,仅考虑带不等式约束的优化问题．进一步，如果x 使得不等式约束0)(=x g i ，则称约束()x g i 在x 处是积极的.在搜索空间S 中,满足约束条件的决策变量x 称为可行解，否则称为不可行解. 定义1(全局最优解）() **2*1*,,,n x x x x =是COP 的全局最优解,是指S x ∈*且)(*x F 不劣于可行域内任意解y 所对应的目标函数)(y F ，表示为)( )(* y F x F ． 对于单目标优化问题,)( )(*y F x F 等价为)()(*y F x F ≤，而对于多目标优化问题是指不存在y ,使得)(y F Pa ｒe ｔo 优于)(*x F . 目前,进化算法用于无约束优化问题的文献居多，与之比较,对约束优化问题的研究相对
Pareto最优概念的多目标进化算法综述
Pareto最优概念的多目标进化算法综述 作者：唐云岚， 赵青松， 高妍方， 陈英武， TANG Yun-lan， ZHAO Qing-song， GAO Yan-fang ， CHEN Ying-wu 作者单位：唐云岚,TANG Yun-lan(国防科学技术大学信息系统与管理学院 长沙 410073;武警工程学院通信工程系,西安710086)， 赵青松,高妍方,陈英武,ZHAO Qing-song,GAO Yan-fang,CHEN Ying-wu(国防科学技术大学信息系统与管理学院 长沙 410073) 刊名： 计算机科学 英文刊名：COMPUTER SCIENCE 年，卷(期)：2008,35(10) 被引用次数：1次 参考文献(23条) 1.Zitzler E;Thiele L Multiobjective Evolutionary Algorithms:A Comparative Case Study and the Strength Pareto Approach[外文期刊] 1999(04) 2.Srinivas N;Deb K Muhiobjective Optimization Using Nondomi-nated Sorting in Genetic Algorithms[外文期刊] 1995(03) 3.Hans A E Multicriteria optimization for highly accurate syste-ms 1988 4.Chankong V;Haimes Y Y Multiobjective decision making theo-ry and methodology 1983 5.Knowles J;Come D查看详情 1999 6.Horn J;Nafpliotis N查看详情 1994 7.Fonseca C M;Fleming P J Genetic Algorithm 1993 8.Richardson J T;Palmer M R;Liepins G查看详情[外文期刊] 1989 9.Schaffer J D Some experiments in machine learning using vector evaluated genetic algorithms 1984 10.Rosenberg R S Simulation of Genetic Populations with Bio-chemical Properties 1967 11.Zitzler E Evolutionary algorithms for multiobjeetive optimiza-tion:Methods and applications 1999 12.Deb K Muhiobjeetive Optimization using Evolutionary Algo-rithms 2001 https://www.wendangku.net/doc/d710674131.html,umanns M;Thiele L;Deb K Combining Convergence and Diversity in Evolutionary Multi-Objective Optimization[外文期刊] 2002(03) 14.Mann J W;Smith G D A Comparison of Heuristics for Tele-communications Traffic Routing 1996 15.Deb K Genetic algorithms in multimodal function optimization 1989 16.Srinivas N Multiobjective optimization using nondominated sor-ting in genetic algorithms 1994 17.Goldberg D E;Deb K A Comparison of Selsction Schemes used in Genetic Algorithms 1991 18.Goldberg D E;Richardson J查看详情 1987 19.Deb K;Goldberg D E查看详情 1989 20.Osman M S;Abo-Sinna M A;Mousa A A IT-CEMOP:An iter-ative co-evolutionary algorithm for muhiobjeetive optimization problem with nonlinear constraints[外文期刊] 2006(1) 21.Shin S-Y;Lee I-H;Kim D Multiobjeetive Evolutionary O-ptimization of DNA Sequences for Reliable DNA Computing[外文期刊] 2005(02) 22.Deb K;Prata PA;Agatwal S A Fast and Elitist Muhiob-jective Genetic Algorithm:NSGA-II 2002 23.Zitzler E;Laumanns M;Thiele L SPEA2:ImprovingtheS-trength Pareto Evolutionary Algorithm 2001
加权公平队列调度算法
2008年2月 February 2008 —28— 计 算 机 工 程Computer Engineering 第34卷 第4期 Vol.34 No.4 ·博士论文· 文章编号：1000—3428(2008)04—0028—03 文献标识码：A 中图分类号：TP391 一种新的加权公平队列调度算法 尹德斌，谢剑英 (上海交通大学自动化系，上海 200240) 摘 要：传统公平队列调度算法(WFQ 、WRR 等)普遍存在基于数据包的权重参数计算问题，由此产生的高复杂度使其难以获得广泛应用。该文提出一种新的加权公平队列调度算法，使用服务概率和随机数实现加权公平调度，显著降低了算法的复杂度。同时使用自适应服务概率计算解决了数据包变长度带来的不公平性。通过队列管理技术有效地提高了交换机的缓冲区利用率，并减小了排队延迟抖动。仿真结果证明了算法的有效性和实用性。 关键词: 队列调度；加权公平排队；自适应队列管理；分组交换网络 New Weighted Fair Queue Scheduling Algorithm YIN De-bin, XIE Jian-ying (Department of Automation, Shanghai Jiaotong University, Shanghai 200240) 【Abstract 】Traditional weighted fair queue algorithms have the main drawback: the calculation of the weight parameters according to each packet.The paper proposes a new weighted fair queueing algorithm(SPFQ), which uses service probability to schedule packets and a random number to decide which packet to be served next. In addition, a novel adaptive service probability parameter calculation method is used to solve the unfair problem induced by the variable packet length and an adaptive queue management technology to improve the utilization of the server's queue buffer and reduce the delay burstiness. Simulation results demonstrate the validity and practicability of SPFQ. 【Key words 】queue scheduling; weighted fair queueing; adaptive queue management; packet switching network 1 概述 队列调度是当前互联网技术领域的一个研究热点。其中，加权公平队列调度算法由于能够根据各业务流的权重进行区分服务而受到广大研究者的广泛关注[1-9]。其中最著名的是加权公平WFQ [1]和加权轮询WRR [6]两类算法。WFQ 及其改进算法[3,5,7]都基于通用处理机共享模型[2]，使用虚时间(virtual time)进行数据包转发。WFQ 算法在业务流受漏斗约束的情况下可以提供精确的带宽保证和最大时延上限，并且数据包的转发不受其他业务流特性影响。但是它的计算复杂度太高。WRR [2,6]是另一类复杂度相对较低的常用加权队列调度算法；各业务流在一次轮询中所允许发送的数据包个数由队列权重决定。DRR [4]引入了差额计数器(dificit conter)，记录由数据包长度不同引起的服务量差。轮询类算法复杂度较低，但无法提供确定的带宽保证和时延上限。 国内的研究者近年来也提出了许多队列调度算法。文 献[8]针对SS 和BF 两种业务流，提出了一种对数自适应调度算法，但该算法对类内各业务流之间如何调度并没有说明，且不能提供公平服务和隔离特性。文献[9]提出了一种用于区分服务网络的虚时钟核心无状态队列调度算法，各数据包自身携带虚时钟状态信息，中心服务器根据虚时钟进行转发，但需要根据虚时钟将入队列数据包插入到转发队列中，这无疑是一项沉重的计算负担。另外，该算法并未考虑虚时钟清零问题。本文提出了一种新的加权队列调度算法SPFQ 。由于采用了指数移动平均算法和阀值触发的平均数据包长度更新，使得服务概率计算频度大大降低，从而显著降低了算法的复杂度。 2 SPFQ 队列调度算法 2.1 SPFQ 的基本原理 SPFQ 算法依据各业务流的平均数据包长度将它们的权重转换成归一化服务概率，通过该参数实现加权服务。为了降低算法的复杂度，系统采用事件触发方式计算队列的平均长度。在算法实现中，使用单独模块计算服务概率，以减轻调度器的负荷。 2.2 SPFQ 的结构 数据包分类器图1 SPFQ 算法结构 基金项目：国家自然科学基金资助项目(60572157)；国家“863”计划基金资助项目(2003AA123310) 作者简介：尹德斌(1978－)，男，博士，主研方向：包交换网络的队列调度和管理；谢剑英，教授、博士生导师 收稿日期：2007-03-10 E-mail ：yin_db@https://www.wendangku.net/doc/d710674131.html,
多级反馈队列调度算法
#include
void input() {int i; printf("请输入进程数："); scanf("%d",&J); for(i=0;i
差分进化算法综述概况
差分进化算法（DE）[1]是Storn 和Price 在1995 年提出的一种基于种群差异的进化算法，DE是一种随机的并行搜索算法。差分进化计算和其他进化计算算法一样，都是基于群体智能理论的优化算法，利用群体内个体之间的合作与竞争产生的群体智能模式来指导优化搜索的进行。与其他进化计算不同的是，差分进化计算保留了基于种群的全局搜索策略，采用实数编码、基于差分的简单变异操作和一对一的竞争生存策略，降低了进化操作的复杂性。差分进化计算特有的进化操作使得其具有较强的全局收敛能力和鲁棒性，非常适合求解一些复杂环境中的优化问题。 最初试图使用向量差进行向量种群的混洗，以此来解决切比雪夫多项式适应性问题。DE 通过种群内个体间的合作与竞争来实现对优化问题的求解，其本质上是一种基于实数编码的具有保优思想的进化算法。该算法实现技术简单，在对各种测试问题的实验中表现优异，已经成为近年来进化算法研究中的热点之一。 差分进化算法基本原理 基本的差分进化算法是基于候选方案种群的算法，在整个搜索空间内进行方案的搜索，通过使用简单的数学公式对种群中的现有方案进行组合实现的。如果新的方案有所改进，则被接受，否则被丢弃，重复这一过程直到找到满意的方案。 设 f 是最小化适应度函数，适应度函数以实数向量的形式取一个候选方案作为参数，给出一个实数数值作为候选方案的输出适应值。其目的是在搜索空间的所有方案p 中找到m 使得f(m) ≤f(p)。最大化是找到一个m 使得f(m) ≥f(p)。 设X=(x1, x2,…, xn)∈?n是种群中一个个体，基本的差分进化算法如下所述： ?在搜索空间中随机地初始化所有的个体。 ?重复如下操作直到满足终止条件（最大迭代数或者找到满足适应值的个体） o 对于种群中的每个个体： ●随机地从种群中选择三个彼此不同的个体a，b 和c。 ●选择一个随机索引R ∈{1, ..., n}，n 是被优化问题的维数。 ●通过对每个i ∈{1, ..., n}进行如下的迭代计算可能的新个体Y = [y1, ..., yn] 生成一 个随机数ri~U(0,1)； ●如果(i=R)或者(ri
用于约束多目标优化问题的双群体差分进化算法精编
用于约束多目标优化问题的双群体差分进化算 法精编 Document number：WTT-LKK-GBB-08921-EIGG-22986
用于约束多目标优化问题的双群体差分进化算法 孟红云 1 张小华2刘三阳1 (1.西安电子科技大学应用数学系，西安，710071； 2.西安电子科技大学智能信息处理研究所，西安，710071)摘要：首先给出一种改进的差分进化算法，然后提出一 种基于双群体搜索机制的求解约束多目标优化问题的差分 进化算法．该算法同时使用两个群体，其中一个用于保存 搜索过程中找到的可行解，另一个用于记录在搜索过程中 得到的部分具有某些优良特性的不可行解，避免了构造罚 函数和直接删除不可行解．此外，将本文算法、NSGA-Ⅱ和SPEA的时间复杂度进行比较表明，NSGA-Ⅱ最优，本文算法与SPEA相当.对经典测试函数的仿真结果表明，与NSGA-Ⅱ相比较，本文算法在均匀性及逼近性方面均具有一定的优势. 关键字：差分进化算法；约束优化问题；多目标优化问题； 中图分类号：TP18 1 引言 达尔文的自然选择机理和个体的学习能力推动进化算 法的出现和发展，用进化算法求解优化问题已成为一个研 究的热点[1-3]．但目前研究最多的却是无约束优化问题．然而，在科学研究和工程实践中，许多实际问题最终都归结 为求解一个带有约束条件的函数优化问题，因此研究基于 进化算法求解约束优化问题是非常有必要的．不失一般
性，以最小化问题为例，约束优化问题（Constrained Optimization Problem ，COP ）可定义如下： )(COP ()()()()q j x h p i x g t s x f x f x f x F j i k R x n ,,1,0)( ,,1,0)( ..,,,)(min 21 ===≤=∈ （1） 其中)(x F 为目标函数，)(),(x h x g j i 称为约束条件， n n R x x x x ∈=),,,(21 称为n 维决策向量．将满足所有约束条件的 解空间S 称为(1)的可行域．特别的，当1=k 时，(1)为单目 标优化问题；当1>k 时，（1）为多目标优化问题．)(x g i 为 第i 个不等式约束，)(x h j 是第j 个等式约束．另一方面，对于等式约束0)(=x h j 可通过容许误差（也称容忍度）0>δ将它转 化为两个不等式约束： ?????≤--≤-0)(0)(δδx h x h j j （2） 故在以后讨论问题时，仅考虑带不等式约束的优化问题．进一步，如果x 使得不等式约束0)(=x g i ，则称约束() x g i 在x 处是积极的．在搜索空间S 中，满足约束条件的决策变量x 称为可行解，否则称为不可行解． 定义1（全局最优解）()**2 *1*,,,n x x x x =是COP 的全局最优解，是指S x ∈*且)(*x F 不劣于可行域内任意解y 所对应的目标 函数)(y F ，表示为)( )(*y F x F ． 对于单目标优化问题， )( )(*y F x F 等价为)()(*y F x F ≤，而对于多目标优化问题是指不 存在y ，使得)(y F Pareto 优于)(*x F ． 目前，进化算法用于无约束优化问题的文献居多，与 之比较，对约束优化问题的研究相对较少[4-6]。文[7] 对当前基于进化算法的各种约束处理方法进行了较为详细的综述. 对于约束优化问题的约束处理方法基本上分为两类：基于 罚函数的约束处理技术和基于多目标优化技术的约束处理
差分进化算法-入门
基本差分进化算法 1基本差分进化算法的基本思想 DE 算法是一种基于实数编码的用于优化函数最小值的进化算法，是在求解有关切比雪夫多项式的问题时提出来的，是基于群体差异的进化计算方法。它的整体结构类似于遗传算法，一样都存在变异、交叉和选择操作，但是它又不同于遗传算法。与基本遗传算法的主要区别在于变异操作上，如： 1、传统的遗传算法采用二进制编码，而差分进化算法采用实数编码。 2、在遗传算法过两个父代个体的交叉产生两个子个体，而在差分进化算法过第两个或几个个体的差分矢量做扰动来产生新个体。 3、在传统的遗传算法中，子代个体以一定概率取代其父代个体，而在差分进化中新产生的个体只有当它比种群中的个体优良时才替换种群中的个体。 变异是DE 算法的主要操作，它是基于群体的差异向量来修正各个体的值，其基本原理是通过把种群中两个个体的向量差加权后，按一定的规划与第三个个体求和来产生新个体，然后将新个体与当代种群中某个预先决定的个体相比较，如果新个体的目标值优于与之相比较的个体的目标值，则在下一代中就用新个体取代，否则，旧个体仍保存下来。 差分进化算法其基本思想是：首先由父代个体间的变异操作构成变异个体；接着按一定的概率，父代个体与变异个体之间进行交叉操作，生成一试验个体；然后在父代个体与试验个体之间根据适应度的大小进行贪婪选择操作，保留较优者，实现种群的进化。 2 差分进化算法的基本操作 设当前进化代数为t ，群体规模为NP ，空间维数为D ，当前种群为 {}12(),, ,t t t NP X t x x x =，()12,, ,T t t t t i i i iD x x x x =为种群中的第i 个个体。在进化过程 中，对于每个个体t i x 依次进行下面三种操作。 2.1 变异操作 对于每个个体t i x 按下式产生变异个体12(,, ,)t t t t T i i i iD v v v v =，则 123() 1,2, ,D t t t t ij r j r j r j v x F x x j =+-= (1) 其中111112(,,,)t t t t T r r r r D x x x x =，222212(,,,)t t t t T r r r r D x x x x =和333312(,, ,)t t t t T r r r r D x x x x =是群 体中随机选择的三个个体，并且123r r r i ≠≠≠；1t r j x ，2t r j x 和3t r j x 分别为个体1r ，2r 和3r 的第j 维分量；F 为变异因子，一般取值于[0,2]。这样就得到了变异个体t i v 。
操作系统论文-----多级反馈队列调度算法
在多道程序环境下，主存中有着多个进程，其数目往往多过于处理机数目。这就要求系统能按某种算法，动态的把处理机分配给就绪队列中的一个进程，使之执行。 在OS中的调度的实质是一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法。对于不同的系统和系统目标，通常采用不同的调度算法，目前存在的多种调度算法中，有的算法适用于作业电镀，有的算法适用于进程调度；但也有些调度算法即可用于作业调度，也可用于进程调度。 多级反馈队列调度算法是一种CPU处理机调度算法，它不必事先知道各种进程所需的执行时间，而且还可以满足各种类型进程的需要，因而它是目前被公认的一种较好的进程调度算法。 多级反馈队列调度算法的思想 设置多个就绪队列，并为各个队列赋予不同的优先级和不同长度的时间片；第一个队列的优先级最高，进程所执行时间片最小。 新创建的进程挂到第一优先级的队列后，然后按FCFS 原则排队等待调度。当轮到其执行时，如它能在时间片内完成，便撤离系统；如果不能完成，便被挂入第二级队列后，……； 仅当第一级队列空闲时，调度程序才调度第二级队列中的进程运行，依次类推……；新进程可抢占低级进程的处理机。 多级(假设为N级)反馈队列调度算法可以如下原理： 1、设有N个队列（Q1,Q2....QN），其中各个队列对于处理机的优先级是不一样的，也就是说位于各个队列中的作业(进程)的优先级也是不一
样的。一般来说，优先级Priority(Q1) > Priority(Q2) > ... > Priority(QN)。怎么讲，位于Q1中的任何一个作业(进程)都要比Q2中的任何一个作业(进程)相对于CPU的优先级要高（也就是说，Q1中的作业一定要比Q2中的作业先被处理机调度），依次类推其它的队列。 2、对于某个特定的队列来说，里面是遵循时间片轮转法。也就是说，位于队列Q2中有N个作业，它们的运行时间是通过Q2这个队列所设定的时间片来确定的（为了便于理解，我们也可以认为特定队列中的作业的优先级是按照FCFS来调度的）。 3、各个队列的时间片是一样的吗？不一样，这就是该算法设计的精妙之处。各个队列的时间片是随着优先级的增加而减少的，也就是说，优先级越高的队列中它的时间片就越短。同时，为了便于那些超大作业的完成，最后一个队列QN(优先级最低的队列)的时间片一般很大(不需要考虑这个 问题)。 多级反馈队列调度算法描述： 1、进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。 2、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。 3、对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1 队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。 4、在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。 我们来看一下该算法是如何运作的： 假设系统中有3个反馈队列Q1,Q2,Q3，时间片分别为2，4，8。 现在有3个作业J1,J2,J3分别在时间 0 ，1，3时刻到达。而它们所需要的CPU时间分别是3，2，1个时间片。 1、时刻0 J1到达。于是进入到队列1 ，运行1个时间片，时间片还未到，此时J2到达。 2、时刻1 J2到达。由于时间片仍然由J1掌控，于是等待。 J1在运行了1个时间片后，已经完成了在Q1中的 2个时间片的限制，于是J1置于Q2等待被调度。现在处理机分配给 J2。 3、时刻2 J1进入Q2等待调度，J2获得CPU开始运行。 4、时刻3 J3到达，由于J2的时间片未到，故J3在Q1等待调度，J1也在Q2等待调度。
多级反馈队列_实验_操作系统
实验名称：多级反馈队列调度 09091201丁奎荣 一、实验目的： 1、综合应用下列知识点设计并实现操作系统的进程调度，进程状态转换，多组级反馈队列进程调度算法。 2、加深理解操作系统进程调度的过程。 3、加深理解多级反馈队列进程调度算法。 二、实验内容： 1、采用一种熟悉的语言，编制程序，最好采用C/C++，界面设计可采用其它自己喜欢的语言。 2、采用多级反馈队列进程调度算法进行进程调度。 3、每个进程对应一个PCB。在PCB中包括进程标识符pid、进程的状态标志status、进程优先级priority、进程的队列指针next和表示进程生命周期的数据项life（在实际系统中不包括该项）。 4、创建进程时即创建一个PCB，各个进程的pid都是唯一的，pid时在1到100范围的一个整数。可以创建一个下标为1到100的布尔数组，“真”表示下标对应的进程号是空闲的，“假”表示下标对应的进程号已分配给某个进程。 5、进程状态status的取值为“就绪ready”或“运行run”，刚创建时，状态为“ready”。被进程调度程序选中后变为“run”。 6、进程优先级priority是0到49范围内的一个随机整数。 7、生命周期life是1到5范围内的一个随机整数。 8、初始化时，创建一个邻接表，包含50各就绪队列，各就绪队列的进程优先级priority分别是0到49。 9、为了模拟用户动态提交任务的过程，要求动态创建进程。进入进程调度循环后，每次按ctrl+f即动态创建一个过程，然后将该PCB插入就绪队列中。按ctrl+q 退出进程调度循环。 10、在进程调度循环中，每次选择优先级最大的就绪进程来执行。将其状态从就绪变为运行，通过延时一段时间来模拟该进程执行一个时间片的过程，然后优先级减半，生命周期减一。设计图形用户界面GUI，在窗口中显示该进程和其他所
遗传算法综述
遗传算法综述 史俊杰 摘要：遗传算法来源于进化论和群体遗传学，是计算智能的重要组成部分，正受到众多学科的高度重视。本文主要回顾了遗传算法的起源和发展历程，并对遗传算法的基本原理及特点作了简要阐述。进一步指出了遗传算法存在的问题及相应的改进措施，讨论了遗传算法在实际中的应用，并对遗传算法的未来的发展进行了探讨。 关键字：遗传算法，适应度函数，神经网络 1.遗传算法的起源 遗传算法(Genetic Algorithm，GA)是模拟自然界生物进化机制的一种算法，即遵循适者生存、优胜劣汰的法则，也就是寻优过程中有用的保留，无用的则去除。在科学和生产实践中表现为，在所有可能的解决方法中找出最符合该问题所要求的条件的解决方法，即找出一个最优解。这种算法是1960年由Holland提出来的，其最初的目的是研究自然系统的自适应行为，并设计具有自适应功能的软件系统。 2.遗传算法的发展过程 从二十世纪六十年代开始，密切根大学教授Holland开始研究自然和人工系统的自适应行为，在这些研究中，他试图发展一种用于创造通用程序和机器的理论。在六十年代中期至七十年代末期，Bagly发明“遗传算法”一词并发表了第一篇有关遗传算法应用的论文。1975年竖立了遗传算法发展史上的两块里程碑，一是Holland出版了经典著作“Adaptation in Nature and Artifieial System”，二是Dejong完成了具有指导意义的博士论文“An Analysis of the Behavior of a Class of Genetie Adaptive System”。进入八十年代，随着以符号系统模仿人类智能的传统人工智能暂时陷入困境，神经网络、机器学习和遗传算法等从生物系统底层模拟智能的研究重新复活并获得繁荣。进入九十年代，以不确定性、非线性、时间不可逆为内涵，以复杂问题为对象的科学新范式得到学术界普遍认同，如广义进化综合理论。由于遗传算法能有效地求解属于、NPC类型的组合优化问题及非线性多模型、多目标的函数优化问题，从而得到了多学科的广泛重视。3.遗传算法特点 遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。遗传算法具有进化计算的所有特征，同时又具有自身的特点： （1）搜索过程既不受优化函数的连续性约束，也没有优化函数导数必须存在的要