分配算法范文-盘古文库

分配算法范文

来源：漫步者

作者：开心麻花

2025-09-19

分配算法范文（精选11篇）

分配算法第1篇

人工蜂群算法(artificial bee colony ABC) 自2005年土耳其学者Karaboga[1]提出以来, 得到了学术界的广泛关注。人工蜂群通过对蜂群内部分工机制及其觅食行为的模拟, 产生群体智能行为。与遗传算法(GA)、差分进化算法(differential evolution,DE) 和粒子群优化算法(particle swarm optimization,PSO) 相比较,ABC算法的求解质量相对较好, 具有操作简单、控制参数少、搜索精度较高和鲁棒性较强的特点[2], 对目标函数和约束几乎没有要求, 在搜索过程中基本不利用外部信息,仅以适应度函数作为进化的依据[3]等优点。ABC算法已经成功应用于人工神经网络训练、网络优化、机器人路径规划、滤波器设计、生产调度等多个领域。

ABC算法主要存在以下问题:1)ABC算法存在“早熟”的收敛性缺陷[4];2)ABC算法具有较好的探索能力, 但开发能力不足;3) 局部搜索能力较弱, 收敛速度相对较慢[5]。针对ABC算法的不足, 国内外的学者提出了较多的改进方法, 研究成果可归纳为算法参数调整、混合算法和设计新的学习策略3 个方面。Akey和Karaboga[6]系统研究了参数设置对ABC算法性能的影响, 在基本ABC算法的基础上增加了修改率(modification rate,MR) 的参数, 其用于控制搜索的扰动维数[7]方法。肖剑等[8]改进人工蜜蜂群全局搜索能力,引入Levy飞行策略, 对原始人工蜜蜂群算法进行改进。易正俊[9]等针对人工蜂群算法易陷入局部最优问题, 将蜂群算法中的跟随蜂数量翻倍, 用其一半采用轮盘赌选择机制更新, 增加的一半跟随蜂采用反向的轮盘赌选择机制, 用以维持种群的多样性。

本文为了提高算法的前期收敛速度和后期的探索能力, 主要做了两方面的改进工作:(1) 讨论了引领蜂数量对算法收敛速度和全局开采能力的影响, 在优化过程中动态调整引领蜂在种群中的比例。(2) 针对算法后期收敛速度慢, 易陷入局部最优的不足, 利用被抛弃蜜源信息和随机蜜源两种方式,产生优质潜在侦查蜂位置信息,有效提高搜索效率。

论文的结构如下: 在第二部分中对人工蜂群算法模型进行了描述, 第三部分论述了引领蜂和侦查蜂动态调整的策略, 提出动态种群分配人工蜂群算法(OS-ABC),第四部分进行了仿真验证, 并对结果进行了分析。

2 人工蜂群算法描述

ABC算法是模拟蜜蜂以协同的方式高效完成采集蜂蜜的工作过程而提出来的群体智能算法。蜂群中的蜜蜂根据分工可划分为引领蜂、跟随蜂和侦察蜂3 种。蜂群实现群体智能的模型包括蜜源、引领蜂、跟随蜂和侦察蜂共4 个组成要素, 以及引领蜂探索、招募跟随蜂和放弃蜜源并派出侦查蜂3 种基本的行为。蜂群通过引领蜂、跟随蜂和侦察蜂3 类不同角色的转换, 从而共同协作寻找高质量的蜜源[7]。

ABC算法中, 食物源的位置代表空间中的一个潜在解, 每个食物源的蜂蜜量代表着潜在解的质量, 即适应度值(Fit), 设定初始蜜源和引领蜂个数为EB, 跟随蜂的个数为OB,OB=EB, 则种群总数NP=EB+OB, 蜂群算法首先按照(1) 式随机生成含有EB个蜜源的初始种群。

被抽象成解空间中的点, 式中Xi,max和Xi,min分别代表解的上下限,i(i=1,2,…EB) 代表蜜源的编号,D代表解的取值空间,n代表问题的维数。蜜源Xi的质量对应于解的适应度值Fiti。

每个蜜源与一个引领蜂对应, 将引领蜂按照式(2)对蜜源位置进行更新

式中:xij(1<=i<=EB,1<=j<=n) 为蜜源Xi的第j个分量位置。vij(1<=i<=EB,1<=j<=n) 为第i个引领蜂在蜜源Xi基础上产生新蜜源Vi∈D的第j个分量位置。rij是[-1,1] 上的一个随机数。Xkj为在群体EB个蜂源中随机选择的另一个蜜源。

所有的引领蜂完成式(2) 的运算后, 飞回信息交流区共享蜜源信息。跟随蜂根据引领蜂分享的蜜源信息,按式(3) 计算蜜源的选择概率

人工蜂群算法的软件实现框架如图(1) 所示。

3 基于增强跟随蜂和侦查蜂的改进人工蜂群算法

3.1 基于引领蜂比例调整的改进

在ABC算法中, 引领蜂的作用是用来维持优良解的个数, 跟随蜂用来增强收敛速度, 侦查蜂用来跳出局部最优解。在基本的ABC算法中, 引领蜂和跟随蜂都采用相同的方式进行探索来寻找更优的解。所不同的是引领蜂是对所有蜜源都进行一次随机搜索,寻找更优解;而跟随蜂是在一定的概率引导下选择蜜源进行搜索, 这样当跟随蜂进行搜索时,并不一定每个蜜源都进行了搜索,而有的进行了不止一次的搜索, 跟随蜂能够对种群中相对优质解进行优先探索, 从而尽快找到质量较高的蜜源。

搜索过程中,引领蜂和跟随蜂进行搜索都是按照(式2) 进行, 对某一维随机的与其他引领蜂进行交叉。这样如果引领蜂太少, 由于参考系过少, 即使有很多跟随蜂也只是在相对较少的区域内搜索,容易陷入局部最优解,使算法进化停滞, 空耗计算时间, 影响进化速度。如果在后期增加引领蜂的比例, 可以使蜂群能够有更多的参考空间进行探索。

本文中, 在算法前期, 将跟随蜂的比例相对调高,能够增强优先探索相对优质解和跳出局部最优解的速度, 使算法的收敛速度增加。即使此点为局部最优解,也能够尽快跳出。在运算过程当中, 再逐渐对引领蜂比例进行增加, 能够使跟随蜂有更多选择和进化空间, 加强后期的探索能力。

由图中可以看出, 当引领蜂个数大于等于5 以后函数优化过程会比较平滑, 甚少出现早熟收敛现象。

通过大量实验比较, 当引领蜂处在种群总数的1/6至1/3, 但最少不能少于5 只时,ABC算法相对稳定,较少出现陷入局部最优解的情况。

将ABC算法中引领蜂在初始阶段采用NP/6, 再依据当前循环次数r按照式(4) 逐渐增加引领蜂, 当到Max Cycle/2 时增加到NP/3, 提高前期收敛速度和后期探索能力。

3.2 基于已抛弃蜜源的改进

在蜂群进行探索时, 各引领蜂是逐渐逼近全局最优解的, 所以即使是对于由于进化停滞被抛弃的蜜源也带有一定的解的信息。当有侦查蜂Xs出现时, 对已抛弃蜜源进行记录并计数(number of Scout bees,NS), 将所有已抛弃蜜源按照适应度值进行加权平均式(5), 这样可以直接将引领蜂带到全局最优解附近。为了消除局部最优解的影响, 对侦查蜂采用间隔使用加权平均的已抛弃蜜源和全局随机蜜源, 增强蜂群的开发能力。

式中:Xs代表侦查蜂位置,NS代表现在已经出现的已抛弃蜜源的个数,Xi代表各已抛弃蜜源,fiti代表各已抛弃蜜源的适应度值

综合上面2 方面的改进, 本文提出提出自适应调整跟随蜂和引领蜂比例的动态种群分配人工蜂群算法(OS-ABC)。

3.3 OS-ABC算法步骤

本文提出的OS-ABC算法步骤如图4。

4 实验仿真

下面为验证本文改进蜂群算法侦查蜂个数设置的效果, 选用单峰函数Sphere、Schwefel和具有多个局部最小点的多峰函数Rosenbrock、Griewank、Rastrigin、Akley做仿真实验, 实验采用EB=15,EB=45,soaABC[9],OS-ABC四种算法进行比较, 每个函数每个算法都独立运行30 次。实验仿真中参数具体设置为: 种群大小取90, 测试函数都取30 维, 控制参数limit为1000, 最大循环迭代次数Max Cycle取为5000 次, 仿真结果如表(1) 所示, 函数的进化过程曲线如图(5) 所示。

以上实验表明, 改进的人工蜂群算法OS-ABC具有较好的前期收敛速度和后期探索开发能力, 当函数优化后期初始ABC算法已经停止进化的时候,OS-ABC仍能够继续进化, 得到更精确的全局最优解。

5 结束语

针对蜂群算法前期收敛慢,后期探索能力差的问题,本文通过理论分析和仿真验证, 采用调整引领蜂的比例和改变侦查蜂的生成方式, 使算法能够尽快收敛, 且在后期有较强的探索能力, 有效避免早熟收敛。本文进行了仿真验证, 结果表明此方法有较好的改进效果。

摘要：针对人工蜂群算法中前期收敛慢,后期探索能力差的问题,本文通过分析引领蜂数量对算法寻优能力的影响,提出自适应调整跟随蜂和引领蜂比例的动态种群分配人工蜂群算法。在侦查蜂阶段,利用已抛弃蜜源信息进行加权平均,生成优质潜在解,该策略能够提高算法后期探索效率和搜索精度。实验表明动态种群分配人工蜂群算法具有收敛速度快、后期探索开发能力强,有效避免早熟收敛。

关键词：人工蜂群算法,动态调整,种群分配,已抛弃蜜源,优质潜在解

参考文献

[1]B.BASTURK,DERVIS KARABOGA.An Artificial Bee Colony(ABC)Algorithm for Numeric function Optimization[J].IEEE Swarm Intelligence Symposium2006Indianapolis,Indiana,USA.(5):12-14.

[2]D.KARABOGA,B.BASTURK.On The Performance Of Artificial Bee Colony(ABC)Algorithm[J].Applied Soft Computing,January 2008,8,(1):687-697.

[3]D.KARABOGA,B.AKAY,A Comparative Study of Artificial Bee Colony Algorithm[J].Applied Mathematics and Computation,2009,(214):108-132.

[4]秦全德,程适,李丽,史玉回.人工蜂群算法研究综述[J].智能系统学报,2014.4,9(2):377-385.

[5]ZHU,G.,KWONG,S.,Gbest-guided artificial be ecolony algorithm for numerical function optimization[J],Applied Mathematics and Computation,2010,217(7):3166-3173.

[6]B.AKAY,D.KARABOGA,Parameter Tuning for the Artificial Bee Colony Algorithm[C],1st International Conference on Computational Collective Intelligence-Semantic Web,Social Networks&Multiagent Systems[C],2009,5-7,Wrocław(Poland).

[7]D.KARABOGA,B.BASTURK,A powerful and Efficient Algorithm for Numerical Function Optimization:Artificial Bee Colony(ABC)Algorithm[J],Journal of Global Optimization,2007,Volume:39,Issue(3):459-171.

[8]肖剑,周建中,张孝远等.基于Levy-ABC优化SVM的水电机组故障诊断方法[J].振动、测试与诊断,2013,(5):839-844.

[9]易正俊,韩晓晶.增强寻优能力的改进人工蜂群算法[J].数据采集与处理,2013,(6):761-769.

基于拍卖算法的目标分配问题优化第2篇

基于偶图理论对目标分配问题进行数学描述,提出设立虚拟火力点和目标的方法对拍卖算法进行适当改进来解决目标分配问题.基于拍卖算法建立的目标分配模型,采用C语言编程实现,最后通过算例验证模型的正确性.该算法计算量小、优化性好,应用范围广,具有极大的.实用价值.

作者：柳鹏高杰刘扬 LIU Peng GAO Jie LIU Yang 作者单位：柳鹏,LIU Peng(军械工程学院,河北,石家庄,050003)

高杰,GAO Jie(军械工程学院,63961部队,北京,100000)

刘扬,LIU Yang(中国电子科技集团第54研究所,河北,石家庄,050002)

分配算法第3篇

关键词:量子遗传算法;多目标分配;最优化

中图分类号:TP18 文献标识码:A 文章编号:1674-7712 (2012) 12-0176-01

一、引言

遗传算法不同于传统寻优算法的特点在于:遗传算法在寻优过程中,仅需要得到适应度函数的值作为寻优的依据;同时使用概率性的变换规则,而不是确定性的变换规则;遗传算法适应度函数的计算相对于寻优过程是独立的;算法面对的是参数的编码集合,而并非参数集合本身,通用性强。它尤其适用于处理传统优化算法难于解决的复杂和非线性问题。[1]

目前,GA已经在很多领域得到成功应用,但随着问题规模的不断扩大和搜索空间的更加复杂,GA在求解很多具体问题时往往并不能表现出其优越性。于是,近年来便出现了遗传算法与其它理论相结合的实践,其中遗传算法与量子理论的结合是一个崭新的、极富前景和创意的尝试。

量子遗传算法QGA是量子计算特性与遗传算法相结合的产物。基于量子比特的叠加性和相干性,在遗传算法中借鉴量子比特的概念,引入了量子比特染色体。由于量子比特染色体能够表征叠加态,比传统GA具有更好的种群多样性,同时QGA也会具有更好的收敛性,因此在求解优化问题时,QGA在收敛速度、寻优能力方面比GA都将有较大的提高。QGA的出现结合了量子计算和遗传算法各自的优势,具有很高的理论价值和发展潜力。

本论文提出用量子遗传算法处理和解决多目标分配问题,为多目标问题的解决提供一种新的思路。

二、量子遗传算法

在传统计算机中,信息存储是以二进制来表示,不是“0”就是“1”态,但是在量子计算机中,充当信息存储单元的物质是一个双态量子系统,称为量子比特(qubit),量子比特与比特不同之就在于它可以同时处在两个量子态的叠加态,量子进化算法建立在量子的态矢量表述基础上,将量子比几率幅表示应用于染色体的编码,使得一条染色体可以表示个态的叠加,并利用量子旋转门更新染色体,从而使个体进达到优化目标的目的。

一个位的量子位染色体就是一个量子位串,其表示如下:

其中。在多目标优化中,一个量子染色体代表一个决策向量,在量子态中一个位的量子染色体可以表达个态,采用这种编码方式使得一个染色体可以同时表达多个态的叠加,使得量子进化算法比传统遗传算法拥有更好的多样性特征。

为了实现个体的进化,经典进化算法中通过染色体的交叉、变异操作推进种群的演化,而对量子进化算法而言,量子染色体的调整主要是通过量子旋转门实现的,算法流程如下:

(1)进化代数初始化: ;

(2)初始化种群 ,生成并评价 ;

(3)保存中的最优解 ;

(4) ;

(5)由生成 ;

(6)个体交叉、变异等操作,生成新的 (此步可省评价);

(7)评价 ,得到当前代的最优解 ;

(8)比较与得到量子概率门 ,保存最优解于 ;

(9)停机条件当满足停机条件时,输出当前最优个体,算法结束,否则继续;

(10)以更新 ,转到4)。

三、基于量子遗传算法的多目标分配应用

如今为了满足市场的需要,很多工厂的生产种类多、生产量大,从而设置了不同的生产车间,根据产品的性质分配生产车间合理与否直接影响工厂的经济收益,这同样可采用遗传算法的目标分配方法进行分配。

模型构建:设工厂有i个生产车间。为在第i个车间生产第j种产品的收益, 为第j种产品的需求量;如果第j种产品被选中,则为在第i个车间生产该产品的总收益。由题意知为求解最大问题。

仿真实例:设有10个生产车间,要生产15种产品,用Matlab程序编程,设定40个粒子,迭代200次,代沟0.9。运行结果如下:

此图表明经200次迭代后的目标分配方案为:第1种产品由第3个车间生产,以此类推,车间5生产第2种产品,车间8生产第3种产品,……。次方案对应的车间总收益值为2.7030e+003,成功进行了多目标分配问题的解决。

四、结论

基于量子遗传算法的多目标分配,为多目标分配突破传统寻优模式找到了一个可行的解决方法。根据这种方法实验,仿真结果可以看出,基本符合要求,并且能够在一定的时间内得到最优的分配方案,因此,本文在探索多目标分配问题上找到了一种新的解决思路。

参考文献:

[1]吉根林.遗传算法研究综述[J].计算机应用与软件,2004,21(2):69-73

[2]肖晓伟,肖迪.多目标优化问题的研究概述[J].计算机应用研究,2011,3,28(3):805-808

[3]原银忠,韩传久.用遗传算法实现防空导弹体系的目标分配[J].火力与指挥控制,2008,3,33(3):80-83

[4]郭张龙,李为民,王刚.基于遗传算法的目标分配问题的研究[J].现代防御技术,2002,6:0172-0180

[5]孙祥,徐流美.matlab7.0基础教程[M].北京:清华大学出版社,2005

一种动态频谱分配算法第4篇

本文主要研究如何合理规划与优化分配资源提高频谱复用效率问题。模拟退火算法 (SA) 作为局部搜索算法的扩展, 在每一次修改模型的过程中, 随机产生一个新的状态模型, 然后以一定的概率选择邻域中能量值的状态。这种采用新模型的方式使其成为一种全局最优算法, 并得到理论证明和实际应用的验证。

1 模拟退火算法

模拟退火的概念是根据熔融金属中粒子的统计力学与复杂的组合最优化问题的求解过程的相似性而提出来的。统计力学的研究表明, 在温度T, 粒子停留在状态r满足波兹曼 (Boltzmann) 概率分布

式 (1) 中E (r) 为r状态的能量;kb>0, 为Boltzmann常数;T为绝对温度, 量纲为1;Z (T) 为概率分布的标准化因子

在温度T时, 根据金属内部粒子的状态选择规律, Metropolis等提出了以下准则:设初始状态i为当前状态, 该状态的能量为Ei, 然后对该状态作随机微扰, 得到一个新状态j, 新状态的能量为Ej。如果Ej<Ei, j就为重要状态;如果Ej>Ei, 考虑到热运动的影响, j是否为重要状态要根据固体处于该状态的概率来判断。固体处于状态i和j的概率的比值等于相应Boltmann因子的比值, 即

用随机数据发生器产生一个[0, 1]区间的随机数ε, 若r>ε, 则新状态j为重要状态, 就以j取代i成为当前状态, 否则仍以i为当前状态。再重复以上新状态的产生过程。在大量固体状态变换后, 系统趋于能量较低平衡状态, 固体状态的概率分布趋于Boltmann概率分布。

以上接受新状态的准则称为Metropolis准则, 相应的算法则称为Metropolis算法。SA中采用上述准则, 故成为全局寻优算法。

2 基于改进模拟退火算法的频率分配

2.1 模拟退火算法模型扰动

SA中新模型的产生是对当前模型进行扰动得到的, 常规用的是高斯分布法, 而快速模拟退火计划采用依赖于温度的似Cauchy分布法, 即

式 (4) 中:mi为当前模型中第i个变量;u为[0, 1]内均匀分布的随机数;[Ai, Bi]为mi的取值范围;m'i为扰动后的模型中第i个变量, 且m'i∈[Ai, Bi]。

Cauchy分布产生新模型的优点是:在高温情况下搜索范围大, 在低温搜索时, 仅在当前模型附近有一平坦的“尾巴”, 使其易于迅速跳出局部极值。这一改进加快了SA的收敛速度。

2.2 改进接收概率

由广义Boltmann-Gibbs分布, 可给出新的接收概率计算公式

式中:ΔE=E (m1) -E (m0) 。h为实数。当h→1时,

这是常规SA的接受概率公式, 为式 (6) 的特例。

2.3 基于改进算法的频率分配

基于改进模拟退火算法的频率分配算法步骤如下:

(1) 给定初温t0, 随机产生解Fold, 计算代价函数Cold;

(2) for k=1 to NUM loop

(3) 结束, 输出最优结果。

为证明频率分配方法的有效性和普遍性, 初始解在可用频率资源中随机生成。

通常SA算法应用于频率分配时, 新状态采取随机产生的方法, 这确保了全局收敛性能, 但也导致后期搜索速度慢;因此根据破坏约束的已有信息建立新状态, 有利于加速SA算法的收敛速度。新状态按如下步骤进行创建:

(1) 在计算代价函数的同时, 记录每个违反约束条件中任意一个频点, 已记录过的就不重复记录;

(2) 在以上违反约束频率记录的基础上, 从每个频率集Fi中随机抽取两个频率 (对应于频率表长度为32和64时) ;

(3) 从频域Φ未分配的频率中随机选择步骤 (1) 和步骤 (2) 中记录的数目一样多的频点数;

(4) 将步骤 (3) 中选择的频点随机替换步骤 (1) 和步骤 (2) 中记录的频点, 即完成新状态的建立。

可以看出, 新方法采用一定程度上的确定性转移规则, 同时保证一定的随机性, 可比普通SA算法更有时间效率。

当算法运行中满足下列任何一个条件时终止算法:

(1) 温度tk降低到指定的tmin。

(2) 循环次数超过最大迭代次数 (设为50次) 。

(3) 代价函数C=0。

3 实例验证

在某网络规划软件中, 需要进行频率分配, 跳频组网的参数由用户自行决定, 并在Visual Studio2010应用程序控制台上进行手动输入, 这也造成每次算法运行所得结果本身具有一定的随机性。

初始频率分配方案跳频同步干扰概率:

为验证频率分配方法的性能, 对频率表长度为32、跳频子网数量分别为4、6和8的情况下频率表进行频率分配求解。跳频电台处于发射状态的概率α=0.1, 电台中频频率为70MHz, 跳频频段为30MHz~90MHz, 跳频间隔为25k Hz, 共2400个频率点。假定每个跳频频率表的第6位为同步信号频率;射频跳频滤波器30d B带宽为中心频率的6%。

仿真中, SA算法初温t0=100, 冷却参数δ=0.98, 终止温度tmin=1, 循环最大迭代次数为50次。为分析跳频同步信号特殊约束对跳频通信同步性能的作用, 对跳频同步信号频率未采取特殊约束的情况也进行了求解。跳频通信系统频率分配优化前后干扰概率的求解结果如表1所示。

通过上表能够看出, 对跳频同步信号采取特殊约束, 可以明显减小跳频同步信号受干扰的概率。即使是在同址干扰最严重的情况下, 即8个子网均采取全频段跳频方式, 采用跳频同步信号特殊约束后, 同步信号被干扰的概率也只有0.0012%, 远远优于未采取特殊约束时0.0653%的同步信号被干扰概率。采用跳频同步信号特殊约束可以在基本不影响频率分配总代价函数的基础上显著减小跳频同步信号受干扰的概率, 其实质是在同样破坏约束的情况下, 尽可能避免该被破坏约束中的被干扰信号为同步信号, 这样就能提高同址跳频通信系统的同步性能。

4 结语

在无线通信领域中, 网络的合理规划和优化是十分重要的现实问题。在电磁环境相当复杂的无线通信中, 这一问题尤为突出。频谱分配的前提和基础是场强预测、电波覆盖是否合理、正确, 这关系到通信间干扰分析、频率指配的可靠性, 最终决定有限频率资源利用的高效性、科学性。

摘要：针对机动通信网络, 提出一种效能评估算法, 研究了效能评估指标体系, 包括基本通信能力、通信保障能力、互连互通能力、安全保密能力、抗毁顽存能力、机动快反能力、动态变化能力、快速自适应能力。首先明确任务需求, 确定效能参数, 构建效能评估模型, 获取数据, 研究效能评估方法, 选择合适的评估算法, 估算模型参数得出评估结果;最后通过实例说明频谱分配在特定应用场景下的效能评估。

关键词：模拟退火,效能指标,模型参数,权重系数,层次分析法

参考文献

[1]Bo Lennselius and Rydstrom.Software Fault Content and Reliability Estimations for Telecommunications System[J].IEEE Trans.Selected Areas in Communications, 1990, 8 (2) :262-271

分配算法第5篇

依据火电机组的实时煤耗特性曲线,针对目前较实用的负荷优化分配方法--动态规划法的弊端,即在机组数目较多时运算量过大、难以满足实时要求,提出了改进的.遗传算法,在加快搜索速度、提高寻优精度、保证群体多样性等方面采取了新的措施.改进后的遗传算法在搜索结果接近全局最优解的前提下,大大提高了寻优速率,具有较高的实用价值.

作者：倪敏陈彦桥刘吉臻魏向国 NI Min CHEN Yan-qiao LIU Ji-zhen WEI Xiang-guo 作者单位：倪敏,陈彦桥,刘吉臻,NI Min,CHEN Yan-qiao,LIU Ji-zhen(华北电力大学,控制科学与工程学院,河北,保定,071003)

魏向国,WEI Xiang-guo(国华定洲电厂,河北,定州,073000)

分配算法第6篇

关键词：矢量量化；码率分配；带死区的格型矢量量化器

中图分类号：TN919.8 文献标识码：A文章编号：1007-9599 (2011) 08-0000-01

Fast Bit allocation Algorithm of Wavelet Image on DZLVQ

Tie Feng

(Haerbin University of Commerce,Haerbin150028,China)

Abstract:Dead zone of the lattice vector quantization(DZLVQ)give a new rate-distortion function close rate allocation method.Can be obtained by fitting the exponential function with a dead zone lattice vector quantization(DZLVQ)the rate-distortion function(RD).

Keywords:VQ;Bit allocation;DZLVQ

一、引言

压缩算法要求权衡视觉质量、压缩比和计算复杂度之间的关系。对于一幅静态数字图像，变换编码特别是多分辨率离散小波变换是当前最流行的压缩方法。实际上，小波系数可以在率失真函数的指导下进行有效的量化和编码，离散小波变换被应用于著名的SPIHT算法和JPEG2000标准。单独考虑多分辨率分解后的各小波子带，就必须解决各小波子带的码率分配问题。在本文中，我们提供一个完整的量化过程，图像经过多分辨率小波变换之后，采用带死区的格型矢量量化（DZLVQ）[1]对小波系数进行量化。DZLVQ方法有较好的性能，由于它允许忽略不重要的小波系数块，从而达到分配给重要的小波系数块较多码率的目的。本文提出一个简单的指数模型用于拟合DZLVQ率失真曲线，基于此模型可以采用解析的方法解决码率分配问题。此方法相对于实际数据多次调用迭代得到率失真曲线计算复杂度大大降低。

二、带死区的格型矢量量化（DZLVQ）

带死区的格型矢量量化（DZLVQ）的死区半径如图1所示。因此，任何一个输入矢量如果小于那么它被零矢量替代，如果它大于则用快速格型矢量量化算法进行量化[2]。在失真一定的条件下，较多的码率被用于重要矢量，因此DZLVQ被应用于低码率矢量量化。带死区的格型矢量化器要求对每一个小波子带确定两个参数：伸缩因子γ和死区半径。调整这两个参数使得在最小是失真的条件下，达到分配给每一子带的码率达到目标码率。

函数用于计算在γ和的情况下的失真。可以证明，可以简化为单变量函数。为了简化码率分配过程，本文提出了一个简单、精确的指数模型用于拟合率失真曲线。

图1

三、率失真函数的逼近及相应码率分配

码率分配方法可以被分为两大类：一种是拉格朗日方法动态分配、另一种是基于率失真函数的模式化分配。第一种算法的复杂度仅仅取决于优化算法的收敛速度，每一次迭代取得的R-D的值，都需要大量的计算[3]。为了降低复杂度，我们采用的率失真模型从而降低计算R-D的值的复杂度。下面，我们给出带死区的格型矢量量化的率失真函数的性质，凭借这些性质我们可以设计出有效快速的码率分配方法。我们首先根据指数模型给出近似值，然后根据相应的码率分配问题，给出简单的、可解析的算法。

（一）指数模型

指数率失真模型：

为输入矢量的方差，R为目标码率，，g（0）=1。带死区的矢量量化器拟合R-D曲线的指数模型：

参数C和a可以通过使用一个对数线性回归得到，=，k=1，...，L，是码率下的失真。

图2给出在实验得到的lena图像子带率失真函数同我们所给模型逼近的比较。正如所看到的，给出的模型是精确的。

图2

（二）码率分配的复杂度

我们需要计算三个率失真的值来确定小波子带模型的参数，可以通过上式计算出整幅图像的码率分配的复杂度。

表示基本操作（加法、乘法、除法）表示搜索到最小失真的平均迭代次数，例如图像Boat的码率就可以达到0.25 bpp，C值可以下降到63 operations/pixel。

四、实验结果

实验表明，对于不同小波子带FA-DZLVQ与LA-DZLVQ码率分配方法非常接近目标码率，并且非常近似实验所得率失真曲线。FA-DZLVQ与LA-DZLVQ在视觉上产生了很好的效果。此外，拉格朗日算子法需要进行大量的数据计算，它的收敛速度取决于初始值，因此FA-DZLVQ比LA-DZLVQ节省45%的计算量。对于Boat图像，当码率为0.125 bpp时，FA-DZLVQ的PSNR接近SPIHT并且优于JPEG2000。

参考文献：

[1]A.Said and W.Pearlman."A new fast and efﬁcient image code based on set partitioning in hierarchical trees",IEEE Transactions Circuits Syst.Video Technol.vol.6,pp.243-250,June 1996

[2]郑莉,董渊,张瑞丰.C++语言程序设计(第3版)[M].北京:清华大学出版社,2007

[3]陈化.浅谈C++语言的教学改革与课程实践[J].电脑知识与技术,2008,31:917-918

基于排队理论的信道分配算法研究第7篇

移动通信用户的持续增长以及用户对各种业务的需求不断增加, 导致频谱资源日益紧缺。信道分配技术作为解决该问题的有效措施之一, 得到了十分广泛的深入研究。

在蜂窝移动通信中, 小区逐渐由宏蜂窝向微蜂窝、微微蜂窝发展。这就导致了面临切换的用户数增多, 切换变得更加频繁。在切换过程中, 掉话所带来的影响要远远大于阻塞一个新增呼叫。目前, 国内外对切换的准则、切换控制以及切换时的信道分配进行了许多研究, 提出了多种对切换呼叫进行优先处理的方案。其中, 具有代表性的有:① 引入了保护信道的概念[1], 即专门预留出一些信道供切换呼叫使用;② 无保护方式, 没有专门的保护信道, 而是引入了各种排队方法, 如文献[2][3]便是此类方法。

针对蜂窝移动通信中的信道分配问题, 本文提出了一种基于排队理论的信道分配方案。该方案主要思想是预留数据保护信道, 切换呼叫引入排队机制。仿真结果表明, 与专门为切换提供保护信道的方式相比, 算法改善了话音业务的各项性能, 为数据业务预留保护信道的措施对提高数据业务传输掉包率也有一定的实际工程参考价值。

1 系统模型

设系统中每个小区的信道分配情况如下图1所示。一个小区里有C个下行信道, 并且被分为2部分:语音信道和数据保护信道。其中Cg个信道作为保护信道预留给数据业务, 用于补偿数据丢包率, C～Cg个信道则作为语音信道。当语音信道空闲时, 数据业务可以借用进行数据传输, 一旦有语音呼叫请求到来, 且发现可用语音信道集合为空, 数据业务应立即释放借用的语音信道, 停止在语音信道中的传输, 继续在数据缓冲器中排队等待。另外, 对语音业务设置FIFO排队缓冲器, 让切换呼叫优先占用语音缓冲器以确保切换优先权。

至此, 对该系统建模完成。进一步考虑语音队列缓冲器的门限, 设置为Bv。当缓冲器内队列数超过Bv时, 系统将无条件阻塞一个新增呼叫。对于切换呼叫排队, 设置门限为Bh (Bh<Bv) , 若缓冲器内切换呼叫队列数超过Bh, 系统将拒绝接纳新的切换呼叫。

2性能分析

设无线蜂窝通信系统中各个小区特性完全相同, 即各小区信道总数相同、业务类型相同。新增呼叫到达率和数据包到达率分别符合参数为λv和λd的泊松分布;语音呼叫时长, 数据包传输时间和语音呼叫小区驻留时间的数学期望分别为1/μv、1/μd和1/η。则切换到达率λh为[4]:

$λ_{h} = \frac{η (1 - Ρ_{v b})}{μ_{v} + η Ρ_{f t}} λ_{v}$ 。 (1)

式 (1) 中, Pvb表示新增呼叫被阻塞的概率;Pft表示切换呼叫的掉话概率。

为了从理论上探讨问题, 还需要引入一个状态变量集合S (x, y, bn, bh, bd) , 并用P (x, y, bn, bh, bd) 表示某个时刻系统处于S (x, y, bn, bh, bd) 状态集合里某一状态的稳态概率。系统的状态空间S (x, y, bn, bh, bd) 可以描述如下:

S={ (x, y, bn, bh, bd) |0xC-Cg+Nv,

0y*CmaxC, 0bnBv,

0bdBd}。

式中, x为系统中语音用户数, 包括缓冲器的新增呼叫和切换呼叫;y为数据用户数, 并假设单个数据用户最多使用信道数为Camx;bn为新增语音呼叫缓冲队列个数;bh为切换呼叫缓冲队列个数;bd为数据用户缓冲队列个数;bv为语音队列缓冲器的门限;Bd为数据缓冲器的门限。

系统总的状态转移概率为:

$\sum_{(x, y, b_{n}, b_{h}, b_{d}) \in S} Ρ (x, y, b_{n}, b_{h}, b_{d}) = 1$ 。 (2)

2.1语音业务性能分析

语音业务性能的2个主要参量是新增呼叫阻塞概率和切换掉话率。在这里, 用p $_{b k}^{h d}$ 表示切换掉话率, 用p $_{b k}^{n}$ 表示新增呼叫阻塞概率。

(1) 切换掉话率

在式 (2) 中, 状态集合G1、G2∈S, 分别可表示为:

G1={ (x, y, bn, bh, bd) |y*Cmax<Cg,

C-Cg<x<C-Cg+Bv},

G2{ (x, y, bn, bh, bd) |Cgy*CmaxC,

C-Cg<x<C-Cg+Bv}。

(2) 新增呼叫阻塞概率p $_{b k}^{h d}$

当计算新增呼叫阻塞率时, 有如下2种情况需要考虑:

① bn+bh=Bv。表示当整个语音缓冲队列已满, 此时新增呼叫会被无条件阻塞。设此种情况下新增呼叫阻塞率为p $_{b k, f}^{n}$ 。

在式 (3) 中, 状态集合G3、G4∈S, 分别可表示为:

G3={ (x, y, bn, bh, bd) |y*Cmax<Cg,

x=C-Cg+Bv},

G4{ (x, y, bn, bh, bd) |Cgy*CmaxC,

x+y*Cmax=C+Bv}。

② bn+bh=Bv, bh<Bh。表示整个语音缓冲队列已满, 但切换队列数目未达到门限Bh。根据切换优先原则, 所以若有新切换请求到来, 会发生新切换呼叫替代一个正在排队的新增呼叫的情形。相应的新增呼叫阻塞率设为p $_{b k, t}^{n}$ :

$p_{b k, t}^{n} = \frac{λ_{h} p_{b k, f}^{n}}{λ_{v} (x - p_{b k, f}^{n})}$ 。 (5)

由此, 考虑上面2种情况后的新增呼叫的总的新增呼叫阻塞概率应为p $_{b k}^{n}$ :

p $_{b k}^{n}$ =1- (1-p $_{b k, f}^{n}$ ) (1-p $_{b k, t}^{n}$ ) 。 (6)

2.2数据业务掉包率分析

设pdd表示数据业务的掉包率, 则

在式 (6) 中, 状态集合, 分别可表示为:

G5={ (x, y, bn, bh, bd) |Cgy*Cmax<C,

0bn+bhBv, bd=Bd},

G6{ (x, y, bn, bh, bd) |Cx+y*CmaxC+Bv,

0bn+bhBv, bd=Bd}。

3 仿真结果

基于OPNET仿真平台, 对上述方案进行了性能仿真。系统中有一个语音业务源和数据业务源, 二者产生的业务分别用来模拟所到达的语音业务和数据业务。在业务产生后, 分别由语音业务服务模块和数据业务服务模块进行处理, 再由信道发射出去。对典型的GSM/GPRS网络, 仿真参数取C=7, Bv=4, Bh=2, Bd=14, Cmax=1, Cg={1, 2}。限于篇幅, 下面仅给出了当Cg=1时的仿真。语音业务性能的仿真如图2和图3所示, 数据传输掉包率仿真如表1所示。图中固定信道分配 (FCA) 对应于预留切换保护信道的方式, 即专门预留出一些信道供切换呼叫使用的情况。

4 结束语

本文提出了一种基于排队策略的动态信道分配方案, 其目的是分析和解决无线蜂窝通信系统中语音业务和数据业务共享系统资源的问题, 经仿真证明具有较好的性能。大量仿真结果表明, 数据保护信道的个数设置和语音呼叫等待队列容量的大小对语音业务性能存在一定的影响, 因此进一步的研究是利用仿真结果合理选择保护信道的个数和设置FIFO语音呼叫等待队列的容量, 以保证系统整体性能最优。另外, 对系统的分析和仿真没有考虑数据用户的切换问题, 这也需要更深入的研究。

参考文献

[1] TEKINAR S, JABBARI B.Handover and Channel Assignment in Mobile Cellular Networks[J].IEEE Communication Magazine, 1991, 2 (11) :42-46.

[2] SHIN Haw-yun, WU Jean-lien C.The study of dynamic multi-channel scheme with channel de-allocation in wireless networks[J].Computer Networks, 2004, 45 (4) :463-482.

[3] FERNG Huei-wen, TSAI Yi-chou.Using priority, Buffering, Threshold control, and Reservation Techniques to Improve Channel-Allocation Schemes for GPRS System[J].IEEE Transactions on Vehicular technology, 2005, 54 (1) :286-306.

基于频谱感知的卫星信道分配算法第8篇

已有的信道分配方法主要集中在信道分配策略上, 包括固定信道分配策略、动态信道分配策略和混合型信道分配策略。文献[1 -4]中的方法包括基于位置信息的信道预留策略和保护信道预留策略。文献[5 -7]的方法包括波束内策略、基于业务量的策略和时间预留策略。这些方法都没有区分频带内的信道与环境的适应性, 频谱感知技术可以对不同频谱的时空特性进行感知, 获得频谱的时空特性。文献[8 -10]论述了软件无线电的思想, 把软件无线电的思想延伸到感知无线点。文献[11 -14]中介绍了频谱感知技术、策略及其应用。本文把频谱感知技术引入卫星通信的信道分配, 以解决传统的信道分配策略不区分频带内的信道与环境的匹配性的问题, 挖掘信道与环境的匹配性信息, 为稀缺的信道资源分配提供一种新的思路, 这种方法能够很好地提高系统的通信容量, 增加系统吞吐率。

1 基于频谱感知的卫星信道分配

1. 1 问题描述

目前的卫星信道分配方法是从可用的信道中按顺序或者随机取用信道, 当信道质量下降到一定程度时再切换到别的可用信道, 切换的目的、信道的选用也是从可用的信道中按顺序或者随机取用信道。这种分配方法不考虑信道与通信环境的适应性, 在环境适方面对频带内的信道不做区分, 所有信道在卫星波束覆盖的区域都有均等的可用概率。

卫星通信中, 卫星轨道高度高, 链路的路径损耗大, 信号强度小, 尤其是地球静止轨道卫星, 这种卫星在通信卫星中占有很大的比例。在这种情况下, 较小的干扰就会对信号产生严重的影响, 甚至会导致地面设备无法正确解调卫星信号。随着地面无线应用的不断增多, 地面干扰对卫星和地面终端的接收性能的影响越来越严重, 传统的方法实际上对所有信道在地域上是一种等概的分配方法。地面的干扰信号在不同的地理位置和时间段上有不同的特征, 并不是所有地域的无线干扰都一样, 所以传统的不加地域区分的信道选择方法并没有有效利用不同地理位置干扰特征信息。本文对地理区分信息进行挖掘, 以增加所选择信道的可用性, 减少因为信道与环境失配, 使得信道质量变坏而带来的速率下降和切换概率, 降低系统开销。

位置特性在卫星通信中是一种很重要的信息, 目前的研究没有考虑按照位置特性来辅助信道分配。本文考虑不同覆盖位置中不同频段的信道在时空二维空间的统计特性, 感知这种信息, 辅助信道分配, 在初始信道分配和信道切换时, 候选信道根据不同信道在不同位置上的可用度信息来排序, 这样可以提高信道分配对不同覆盖位置的适应性, 最终达到提高通信质量, 减少频繁切换, 降低系统开销的效果。本文以地球静止轨道卫星为例, 结论可以推广到其他通信卫星。

卫星以多波束天线覆盖地面, 每个波束覆盖一定的地域, 所有波束覆盖的区域称为卫星服务区。相隔一定距离的波束间频率资源可以复用, 相邻波束间不能复用频率资源, 当一个波束下的负载过重时可以从相邻波束借用信道, 本文中的信道指的是频率资源。卫星服务区的每个地面终端都处在一个波束中, 由所在的波束为其分配上行和下行信道, 本文中提到的上行和下行信道统称为信道。

在传统的信道分配方法下, 整个卫星的信道先在波束之间进行复用方案的分配。完成信道的波束间复用分配后, 每个波束都获得了自己的资源, 将分配到的信道放入信道资源池中, 当有用户接入时从信道池中取用一个信道, 因为信道质量下降进行信道切换时, 也从信道池中取用一个信道, 当用户使用完成时将信道放回信道池。这里所述的用户接入包括新到的用户的接入和切换用户的接入。

卫星信道资源的分配涉及两个层面的问题:1将全部信道资源在波束间进行分配; 2在波束内用户到来时, 从波束的信道池中选用信道资源给用户, 这也包括了波束内用户信道切换时切换信道的选用。在不同的地理位置, 不同信道受到的干扰和衰落等特性是不同的, 存在信道特性和地理位置的匹配度问题, 在某个位置表现出信道质量好的信道定义为与该位置匹配度高的信道, 信道所表现出的质量好坏程度的统计特性定义为信道与地理位置的匹配度, 在一个位置上质量越好的信道匹配度的值越大, 质量越差的匹配度的值越小。一般在不同的位置, 优先选用在该位置上匹配度高的信道能够提高信道利用率, 减少系统开销。本文在利用了位置信息的基础上, 将信道与位置结合起来考虑, 在两个层面的信道分配时都考虑信道与地理位置的匹配度来优化信道分配。

1. 2 数学模型

将卫星所覆盖的区域进行分区, 每一分区的大小根据具体实现确定。分区大小根据信道在地理位置上的敏感程度确定, 信道对地理位置敏感的区域也可以采用精细的分块, 不敏感的位置可以采用较粗的分块。本文以相等大小的分区来示意, 这种方法包括其他的分区方法, 不同大小的分区可以出现在一种信道分配方法中。卫星覆盖域分区示意图如图1所示, 将卫星的覆盖域分成n×m块, 每一块用ai, j表示, 通过对每一块上各个信道与该块位置的匹配度进行统计和估计, 在每一块上将得到一个所有信道在本块上的匹配度排序。

匹配度值包括上行信道和下行信道与位置匹配度的值。上行信道的匹配度可以由星上处理单元或者地面信关站对使用各个信道时的信道质量指示数据, 如BER数据的统计和估计得到; 下行信道的匹配度由地面终端对使用各个信道时的信道质量指示数据的统计和估计得到, 并将该信息反馈给卫星或者信关站, 也可以由卫星或信关站根据使用不同信道时的切换情况对下行信道的匹配度进行估计。这里指出, 计算信道匹配度的方法和参数不限于此, 可以包含其他参数和其他方法。

假设卫星共有N个信道、M个波束, 每个波束所覆盖的块的集合用Mi表示, Mi= { ai, j| ai, j在波束i中} , 信道n在ai, j上作为上行信道时匹配度的值为nui, j, 作为下行信道时匹配度的值为ndi, j。每个波束需要2mi个信道 ( mi个上行信道、mi个下行信道) , 信道总数满足约束式 ( 1) 。这里说明, 每个波束需要的信道数量是随业务量变化的, 这里为了表述方便, 按照固定的mi来表示。

卫星为Mi分配的上行信道的集合为:

卫星为Mi分配的下行信道的集合为:

用Dui表示Mui内所有上行信道的匹配度的和, 用Ddi表示Mdi内所有下行信道的匹配度的和。卫星信道在波束间的分配方案是使得卫星信道的总体匹配值最大, 可以表示为:

这种分配使得整个卫星的信道在总体上与位置的匹配度最高, 从而以最优的方式适应整个覆盖域。

在一个波束内, 为某个位置的用户分配信道时, 根据用户的位置所对应的信道的匹配度的排序, 从该波束的可用信道中选用匹配度的值最高的信道作为该用户的信道, 波束内的位置分区示意图如图2所示。

卫星通信设备很容易和GPS、北斗等定位单元结合, 有些卫星通信设备本身就集成了定位装置, 位置信息在卫星通信系统中普遍存在, 利用好位置信息来进行信道分配, 将提高整个卫星服务域的信道利用率。

1. 3 算法实施步骤

本文所述的基于频谱感知的卫星信道分配方法的实施分为3个阶段:

1生成每个分区的信道匹配度信息。获得每个分区的匹配度值是一个学习和更新的过程, 在地面终端辅助下, 信关站和卫星对每个分区的历史信道好坏程度进行统计, 使用参数估计的方法将每个分区上所有信道的匹配度的值估计出来, 生成信道与地理位置匹配度表。在有新的历史数据的增加时, 匹配度的值根据新增数据值进行更新。

2波束信道分配。根据卫星所有波束下的负载情况, 确定每个波束所能分配的信道数量。根据信道与地理位置匹配度表, 按照式 ( 4) 将卫星信道分配到每个波束中。

3为用户分配信道。当有用户接入时, 在用户所在的波束内, 在可用信道中按照匹配度的排序选用匹配度值最大的信道分配给用户。

信道分配执行过程如图3所示。

2 仿真分析

仿真数据设置, 系统的总信道数量N, 信道质量在每个分区上所表现的质量服从一定的分布, 将对均匀分布和正态分布进行比较。本文将从系统归一化的吞吐率和切换率两方面来比较基于频谱感知的卫星信道分配和传统的信道分配。

系统吞吐率的比较, 以信道数量N为变量, 仿真两种分布下的吞吐率, 仿真结果如图4所示。“传统 -1”代表信道质量在各分区为均匀分布时传统算法所产生的系统吞吐率, “感知 -1”代表在同样的分布下基于频谱感知的算法所产生的系统吞吐率。“传统 -2”代表信道质量在各分区为正态分布时传统算法所产生的系统吞吐率, “感知 -2”代表在同样的分布下基于频谱感知的算法所产生的系统吞吐率。仿真结果表明, 基于频谱感知的算法能够很好地提高系统的吞吐率。

系统因信道分配不当会导致信道切换, 这里只考虑一次切换的概率, 对于一次通信发生多次因信道质量差所导致的切换可以类推, 结果如图5所示。仿真以信道质量为0.5为切换门限, 结果表明, 基于频谱感知的分配方法基本上能够避免因信道与还击不匹配所引起的信道切换问题, 从而减小切换开销, 提高信道利用率。

3 结束语

基于遗传算法的电力负荷分配方法第9篇

关键词：MD电费,最大需求负荷,电力负荷分配

引言

企业用电电费由基本电费及实际用量电费两部分组成。基本电费主要由契约 (最大) 用电负荷 (MD) 决定。用电企业的每月用电量的峰值决定了当月MD电费。按照定义, 有功电表以连续15 分钟稳定最大负荷记录作为本月实际负荷的最大值, 且只进不退, 按此值对照MD进行收费。文章以某钢铁厂用电数据为例, 下文简称冷轧薄板厂, 做如下分析。按照供电合同电力公司对冷轧薄板厂T1、T2两路供电线路分别收取MD费用。如图1 所示, 其中N1 至N13 共13 个用电单元的电力负荷可以在T1 线路及T2 线路之间自由切换。其中13 个用电单元的电力负荷具有完全不同的负荷特性。冷轧薄板厂供电线路系统如图1 所示。如何最优化分配电力负荷, 如何尽可能的让负荷平稳, 这是文章研究的方向。

1 数学描述

记第n个用电单元电力负荷为LOADn (t) , t为时间变量, 代表当月的第t分钟。

记T1 线路电力总负荷为LOADT1 (t) , T1 线路电力总负荷为LOADT2 (t)

记持续15 分钟平均值函数为:下一代。在遗传算法中, 用一组染色体的集合模拟解的集合, 用评价函数来模拟自然筛选。通过评价函数而筛选存活下来的解可以进行“产生突变的繁殖”, 产生不同的下一代解集, 然后再对下一代解集用评价函数进行筛选, 选出下一代最优解, 并与上一代最优解进行比较, 看哪一个更合适, 合适的那个解再用来繁殖下一代, 如此反复, 直到得出符合要求的最优解。其实现方法如下: (1) 根据具体问题确定可行解域, 确定一种编码方法, 能用数值串或字符串表示可行解域的每一解。 (2) 对每一解应有一个度量好坏的依据, 它用一函数表示, 叫做适应度函数, 适应度函数应为非负函数。 (3) 确定进化参数群体规模、交叉概率、变异概率、进化终止条件。

记变量an∈ (0, 1) , 1≤n≤13, 当an=1为第n个用电单元选择T1线路, 当an=0为第n个用电单元选择T2线路。

记MDT1为1#主变当月最大契约负荷, MDT2为2#主变当月最大契约负荷。

2遗传算法简介

众所周知, 在进化过程中, 每个种群将会面临一系列复杂的变异和环境选择, 只有能适应环境变化的变异体才能继续生存下去, 同时, 对于生存有利的突变会随着存活下来的个体的染色体传给其下一代。在遗传算法中, 用一组染色体的集合模拟解的集合, 用评价函数来模拟自然筛选。通过评价函数而筛选存活下来的解可以进行“产生突变的繁殖”, 产生不同的下一代解集, 然后再对下一代解集用评价函数进行筛选, 选出下一代最优解, 并与上一代最优解进行比较, 看哪一个更合适, 合适的那个解再用来繁殖下一代, 如此反复, 直到得出符合要求的最优解。其实现方法如下: (1) 根据具体问题确定可行解域, 确定一种编码方法, 能用数值串或字符串表示可行解域的每一解。 (2) 对每一解应有一个度量好坏的依据, 它用一函数表示, 叫做适应度函数, 适应度函数应为非负函数。 (3) 确定进化参数群体规模、交叉概率、变异概率、进化终止条件。

3 遗传算法在电力负荷分配中的应用

3.1 收集历史数据

本案例收集了2013 年4 月冷轧薄板厂的13 个用电单元的每分钟用电数据用以模拟历史工单模型。

3.2 参数设置

求解的遗传算法的参数设定如下:

种群大小:M=40

最大代数:G=15

交叉率=1, 交叉概率为1 能保证种群的充分进化。

变异率=0.1, 一般而言, 变异发生的可能性较小。

3.3 实验结果

采用matlab编程, 计算机代入历史数据, 运行15 代, 历时约100 分钟, 运行结果如下。 (1) 如图2 所示种群MD平均值及最优值均处于下降趋势, 其中种群MD平均值由24.47MW下降至24.16MW。种群最优值由23.98MW下降至23.86MW。 (2) 从第15 代运行结果可以得出, 排列在前11 位的最优排列, 对应两种排列组合方式, 如下:

1# 主变下安排负荷:N1, N2, N3, N5, N8, N11

22## 主变下安排负荷:NN44, NN66, NN77, NN99, NN1100, NN1122, NN1133

4结束语

以太无源光网络带宽分配算法研究第10篇

以太无源光网络 (EPON) [1]是目前有希望进行大规模部署的下一代超宽带接入网技术之一, 利用光纤的海量带宽和低成本可以为用户提供高速且价格低廉的宽带接入服务。作为一种新型的接入网技术, 它同时支持语音、图象和数据的接入, 因而EPON也是一个多业务综合接入平台。EPON技术虽然采用了以太网技术, 但其与传统的以太网有所不同。在其下行方向是点到多点传输;而在上行方向, 是多点到点。这就势必造成在上行接入时出现带宽竞争以及下行方向资源调度和带宽合理分配的问题。

1、EPON结构与MPCP协议

1.1 EPON结构

EPON是一种点到多点的无源光网络。EPON主要由三部分组成：光线路终端（OLT）、无源分路器和网络单元（ONU）。OLT是本地交换节点，将光接入网与IP, ATM或者SDH的骨干网连接起来。而ONU是FTTC中的控制节点或FTTH、FTTB中的用户终端，提供宽带语音、数据和视频的服务。EPON下行方向为点对多点的数据传输，采用802.3广播工作方式[2]。在信道上，以太帧由OLT经过1:N光分路器 (分路比在1:4到1:64之间) 到达各个ONU，接收端ONU由MAC层地址解析提取自己的数据包，丢弃其他数据。上行方向为多点对点的数据传输，多个ONU复用上行1310nm信道，完成数据的传输。

1.2 MPCP协议

为了在EPON中支持DBA，完成上行信道的动态带宽分配，EFM小组在EPON的网络框架中添加了MPCP协议支持。

MPCP (Multi-point Control Protocol多点控制协议) 是MAC Control子层的一项功能。它不是特指某一种带宽分配或ONU调度算法，而是一种支持EPON多种带宽分配算法实行的机制。协议定义了五条Ethernet消息：GATE, REPORT, REGISTER＿RE-QUEST, REGESTER和REGISTER＿ACK。其中后三条用于ONU登录OLT。通信过程中，依靠GATE和REPORT消息传递控制信息。GATE消息由OLT发向ONU，实现传输开窗。REPORT消息携带ONU的本地信息，如服务需求，缓冲区占用情况等，由ONU发向OLT。OLT则依据REPORT信息进行信息更新并智能决定带宽分配。GATE和REPORT消息为MAC控制帧，其生成和处理都在MAC控制子层完成。

2、带宽分配算法分析

2.1 静态带宽分配算法

好的带宽分配算法需要OTL公平地分配带宽，并且保证不同业务的QSo和高带宽利用率。在带宽分配算法的研究中，不少学者和专家已经做了很多研究工作。最先提出的算法是静态带宽分配[3]，即在一个轮询时间内给每个ONU都分配同样大小的时隙。

2.2 动态带宽分配算法

2.2.1 IPACT算法

基于授权 (Gate) 和请求 (Report) 的有自适应循环周期时间的交织轮询方案 (IPACT) ，IPACT以OLT为控制中心，根据一个周期内网络的实时情况来改变时隙安排，并考虑了系统中OLT与不同ONU之间由实际距离所带来的传输时延。

现以4个ONU组成的EPON系统为例，如图1所示。假设某时刻t0, OLT知道每个ONU的缓存队列数据大小和数据往返时间，OLT将这些信息保存在一张实时轮询表中。考虑该算法每个ONU实时的需求，尽量满足每个ONU实际要求的传输带宽。但在保证每个ONU公平性时却造成轮循周期过长，数据传输时延过大，因此在OLT端要限制ONU传输窗口，使得每个ONU分配的带宽不会大于"最大传输窗口"。

G:Gate帧;R:Report帧;MTW:最大传输窗口

2.2.2 BGP算法

BGP算法[4]允许上行带宽在每个用户和操作器之间基于服务等级协议（SLA) 共享。这个算法能根据SAL提供给高级用户保证带宽而对其他用户提供相应服务。在BGP算法中，ONU分为两组:带宽保证ONU (BGONU) 和非带宽保证ONU (non-BG ONU) 。整个上行带宽被分割成相等的带宽单元，OTL保存一张"入口登记表"，每个入口拥有一个带宽单元，该单元或者分配给BG ONU，或者动态分配给non-BG ONU。每个BG ONU根据带宽需求和SLA占用一个或多个入口，即获得一个或多个带宽单元。占用多个入口的ONU在一个轮询周期中获得多个带宽单元。没有被BG ONU占用的入口可动态地分配给non-BG ONU。另外，一个被BG ONU占用但没有完全使用的入口中剩余带宽可动态的分配给non-BG ONU。

2.3 带宽分配算法存在问题

静态带宽分配虽然简单，但负载较小的ONU不能充分利用带宽，造成其他ONU时延增大，系统吞吐量减小，造成了带宽的浪费。好的带宽分配算法需要能够根据ONU突发业务的要求实时地改变ONU的上行带宽分配方案。

IPACT机制有一个缺点，它将所有的ONU同等对待，而且，在每轮循环中对每个ONU的带宽授权按其自身的带宽需求来分配，导致其他ONU业务流量时延和抖动增大或者根本无法正常工作，这使得IPACT机制难以支持SLA。

BGP算法并不适合未来网络的发展，未来网络的发展必须是能根据不同用户的需求提供不同的服务，而BGP算法并不适合这种变化的趋势。

3、动态带宽分配发展方向

3.1 自适应上行带宽的DBA算法

在PON网络中，DBA算法是实现流控最简洁的途径。现有的DBA算法通常假设上行带宽是恒定的，但是在实际的应用中，通常是多个OLT和一个10GbE交换机相连，交换机为一个OLT提供的上行带宽往往是变化的。如果采用现有的DBA算法, OLT中的缓存很可能会出现溢出。一种解决方案就是OLT从交换机提供的流控信息来灵活决定上行带宽的大小, 这个带宽同时成为DBA算法可用带宽的上限, 这样就很方便地实现了OLT对ONU的流量控制。

3.2 有流量预测功能的DBA算法

在本地调度算法中，调度器对队列状态信息的获取是即时的。而远程调度则不同，因为调度器和队列的物理位置上相去甚远，等待时间已经大到不可忽略的地步。

当等待时间内到达的分组未被DBA算法考虑时，可能出现以下情况：1）上行带宽出现了不应有的空闲时隙，导致上行带宽的利用率降低；2）平均分组时延增大。由于远程调度系统的特点，等待时间不可避免，一个合理的解决方法是对等待时间内到达的流量进行预测，但是现有的算法过于简单。理想的算法应该是一种基于自相似流量的、简洁的预测算法，这有待进一步研究。

4、小结

要提高EPON系统性能的，DBA算法的改进非常重要，它是EPON发展道路上的障碍，但是同时也为研究者提供了丰富的论题。

摘要：以太无源光网络综合了PON技术和以太网技术的优点, 成为目前光接入网的优选方案。本文通过分析现有以太无源光网络带宽分配算法存在的问题, 提出DBA的两个发展方向:自适应上行带宽的DBA算法, 有流量预测功能的DBA算法。

关键词：以太无源光网络,动态带宽分配,上行接入

参考文献

[1].IEEE std 802.3ah, Carrier sense multiple access with col2lision detection (CSMA/CD) access method and physical layer specifications, amendment:Media access control parameters, physical layers, and management parame-ters for subscriber access network[S].

[2].Seong-Ho Jang, Jin-Min Kim, Jong-Wook Jang.A new DBA algorithmsupporting priority queues and fairness for EPON[J].Proceedings of Asia-pacific Optical Communications, 2004, 12 (07) :56-63.

[3].G.Krame, B.Mukherjee, G.Pesvaento, EthernetPON (EPON) :Design and Analysis of an Optical Access Network, Photonic Network Communica-tions, Vol.3, no.3, Jul2001, 307-319

分配算法第11篇

随着移动通信的迅速发展,飞速增长的用户数量与有限的频率资源这二者之间的矛盾越来越突出,提高现有资源利用率已成为移动通信领域关注的重要课题。所谓“信道分配”,也称频率分配,即在采用信道利用技术的蜂窝移动通信系统中,在多信道共用的情况下,使通信过程中的相互干扰减到最小,以最有效的频谱利用方式,为每个小区的移动通信设备提供尽可能多的可用信道[1]。

在本文中我们针对蜂窝网络中的固定信道分配进行研究,考虑移动通信中主要的几种干扰对信道分配附加一些约束条件:

(1) 同频约束(cochannel constraint,CCC):两小区除非在距离上足够远,否则不能分配相同的频率;

(2) 邻频约束(adjacent channel constraint,ACC):当相邻小区使用相近频率时,仍然存在干扰的可能性;

(3) 同小区频率间隔约束(cosite constraint,CSC):分配给同一小区的频率之间应有一定的间隔,比如250 kHz或5个频点的间隔。

目前已有多种算法被应用到信道分配中,早期主要是用着色算法进行信道分配,近些年用神经网络算法,模拟退火算法和遗传算法也被广泛应用到信道分配中。本文用一种改进的混合遗传算法对信道分配问题进行研究。常规的遗传算法存在搜索空间太大,收敛速度慢以及易于陷入局部最优解的缺点,针对这些缺点通过模拟退火与遗传算法的结合引入父代与子代之间的竞争,既加快了算法的收敛速度又能适当避免算法陷入局部最优解。同时加入了“寻优式爬山”与大规模基因突变两种优化方法,前者在加快算法收敛速度方面具有明显的效果,而后者则可以很好地防止算法陷入局部最优解情况的发生。

2 问题建模

为了在数学上构建信道分配问题的模型,引入兼容矩阵C与需求向量D的概念[2]:对于拥有n个小区的蜂窝网络,我们用nn的对称矩阵C来描述小区之间的频率兼容性,矩阵C中非对角线上的元素cij表示分配给小区i与小区j之间的频率的最小间隔,代表小区之间同频与邻频限制。对角线上的元素cii表示分配给小区i的任意两个频率之间的最小间隔,代表同小区的频率间隔限制。用n1的向量来描述小区的频率需求关系,n为蜂窝系统中小区的总数,D中的元素di(1in)表示第i个小区所需的频率数。兼容矩阵用数学表达式描述如下:

undefined

式中fik是分配给第i个小区的第k个频点,文中的频率用正整数表示。

问题编码:根据问题中分配给小区的频率为固定范围正整数的特点,在本文中采用整数编码与最小间隔编码[3]两种编码方法。整数编码用ndmax大小矩阵表示个体,其中dmax为需求向量D中最大值,fij=y(1yp,1jdi)表示频点y分配给第i个小区,fij=0(di

如果频率p已分配给小区i,则与p之间的距离小于cii的频率q不能分配给小区i,否则将产生CSC,用数学表达式描述如下:

undefined

如果频率p已分配给小区i,则与p之间的距离小于cij(cij>0)的频率q不能分配给小区j,否则将产生CCC(fip=fjq)或ACC,用数学表达式描述如下:

undefined

因此,代价函数可以表示成下面的形式:

undefined

从公式可以看出,违背约束的频点越少则代价函数越小,当所有分配的频点都满足约束条件时,代价函数取到最小值为零。因此我们要做的就是找到一种分配方案F使C(F)达到一定的标准,如果要求违约数为零则要找到一种分配方案使C(F)=0。

从文献[3]中我们知道采用最小间隔编码可以避免CSC违约,缩小频率搜索空间,从而代价函数可以变为:

undefined

3 算法实现

一般遗传算法主要包含初始化、选择、交叉、变异等算子,下面对适应度函数与各遗传算子进行设计。

(1) 适应度函数定义

针对此信道分配问题,适应度函数与代价函数密切相关,一般可取f(F)=1/C(F)作为分配方案F的适应度。在本文中采用f(F)=1/C(F)g作为分配方案F适应度函数,其中g为跟代数相关的变量。

(2) 产生初始种群

遗传算法初始种群的产生最基本也是最常用的方法是随机生成法,用这种方法生成初始种群简单快捷但平均适应度与最佳个体适应度都较差,需要较长时间与较多代数完成收敛。为了解决这个问题,在保证搜索空间完备性的基础上产生高适应度的初始群体,我们设计一种“寻优式爬山”算法。寻优式爬山算法的具体实现过程将在下面的章节中进行介绍。

(3) 选择

在本文中我们采用常用的轮盘赌选择法,其基本原理是根据个体适应度大小进行选择,适应度大的个体被选中的概率大,反之则小,轮盘赌的详细实现方法可参见文献[4]。为了防止在选择以及其后的交叉、变异过程中最佳个体意外丢失,我们在每代遗传操作前将最佳个体保留,操作结束后将其直接复制,替换子代种群中的最差个体。另外,为了防止优秀个体迅速繁殖,陷入局部最优解,在选择时要控制最优个体的数量。

(4) 交叉算子

交叉操作在最小间隔编码的种群中执行,为了保证在交叉的过程中,分配给第i个小区的频点个数始终等于di,我们采用文献[3]中的固定交叉算子。在本文中采用一种全新的交叉思想:个体交叉与小区交叉相结合。其基本方法如下:对个体进行交叉部分(将进行交叉的小区)选取,选取过程采用单点与两点相结合的选取方法,具体过程为生成两个随机点a,b(1a

(5) 变异算子

交叉算子只是对原有的基因进行重组来产生新的个体,通过交叉并不能产生初始种群以外的基因,而必须靠变异算子来生成新的基因,使遗传算法能够在整个解空间上进行全局搜索。在本文中基本的变异方式采用文献[3]中的对应变异。在此种变异方式的基础上,我们采用个体变异与小区变异相结合的变异思想。

通过以上算子的实现与组合即可完成一般遗传算法,但一般遗传算法存在收敛速度慢的缺点。通过将模拟退火算法与遗传算法结合可以适当克服遗传算法的缺点,具体的结合方法为在交叉与变异操作完成之后,由退火算法来决定是否用新产生的个体来代替父代个体。设父代个体的适应度为f1,子代个体的适应度为f2,则适应度改变量Δf=f2–f1如果满足exp{Δf/T}>rand(1),则用新个体代替父代个体,否则保持父代个体不变,这样引入了父代与子代的竞争,有利于加快算法的收敛速度。从判断条件exp{Δf /T}>rand(1) 可以看出,当新个体适应度大于父个体时,新个体必然被保留,而当新个体适应度小于父个体时仍以一定的概率被保留,这样可以适当避免种群迅速陷入局部极小值。关于退火算法的知识可参考文献[5]。

从后面的仿真结果可以看到混合算法的收敛速度较一般遗传算法有明显提高,且有很好的稳定性,但混合算法极易陷入局部最优解。为了进一步提高算法性能我们加入了“寻优式爬山”与大规模基因突变两种优化方法对混合算法进行改进。

寻优式爬山的基本思想很简单,就是找到一种分配方案中所有不满足条件的小区及小区中违背约束条件的频点,用可用的频点来代替违约频点,形成新分配方案。如果新分配方案适应度优于原分配方案,则保留,否则放弃。继续替换过程,直到所有的违约频点替换结束或无可用频点,则搜索过程结束。该过程可以描述如下:

(1) 找到一种分配方案中所有不满足条件的小区(设个数为r);

(2) 找出第i个小区中违背约束条件的频点和可以选择的频点(1ir);

(3) 随机选择违约频点a、可用频点b,将a用b代替;

(4) 对新个体进行适应度估计;

(5) 如果新生成个体适应度大于原个体,保留新个体,更新违约频点与可用频点;

(6) 如果小区中违约频点与可以选择的频点都不为零,重复步骤(3)～(5);

(7) 取下一个不满足条件的小区,重复步骤(2)～(6)。

基于以上原理我们进行初始种群生成,首先用随机生成方式产生适当规模的种群P0,然后对P0中所有的个体进行寻优式爬山处理,生成初始种群P。用这种方法生成的初始种群不仅满足上述的要求,且具有广泛的适用性。寻优式爬山算法在程序中的另一处应用为当遗传操作连续运行一定代数Ng(根据具体情况选取),仍未找到更高适应度的个体时,选取部分个体进行“寻优式爬山”搜索。但要注意Ng值不可以太小,否则容易造成过早收敛到局部极小值,不利于遗传算法搜索空间的展开,并且由于寻优式爬山算法需要较长时间,造成程序时间开销过大。

当算法运行很多代,适应度仍保持不变时,可能已陷入局部极小值,这时采取突然提高变异率的方法使大量个体进行变异,同时适当提高退火温度,并使用排序选择法进行选择操作,使新个体容易存活,帮助种群快速跳出局部极小值,这就是大规模基因突变的基本思想。经过以上改进的算法被称作改进混合算法。下面对3种算法进行仿真比较。

4 程序仿真及结果比较

我们选取文献[2]中有代表性的2,3,6三个问题对三种算法分别进行50代仿真,仿真参数如表1所示。表中G为程序运行的最大代数,N为种群大小,pc为交叉概率,pm为个体变异概率,pe为小区中元素的变异概率,K为触发“寻优式爬山”的计数器,T0为退火初始温度,k为退火系数,Te为终止温度,σ为初始种群中个体违约数的标准差。仿真结果见表2。仿真结束后,取每种算法的最佳收敛结果进行绘图比较,见图1～图3。

从图中可以看出,一般遗传算法的收敛速度最慢,收敛过程相对平稳,算法运行到最大代数时未完成收敛;混合遗传算法收敛速度快一些,但仍未完成收敛,这主要是由于常规退火方式后期的温度降到比较低,新产生的个体不易存活,所以算法很容易陷入局部极小值无法跳出。优化后的混合遗传算法收敛速度最快,且具有很好的稳定性,除问题6有一次陷入局部最优解,其余全部收敛。

由新初始化方式生成的初始种群的适应度明显提高,平均违约数只有一般初始化生成种群的25%～45%,这大大减小了算法的搜索空间,加快了算法的收敛速度。从表2可以看出,改进混合算法平均每代的运行时间大于前两种算法,这主要是由于执行“寻优式爬山”需要较长时间,但从完成收敛总体时间上看,改进算法较其他两种算法至少节省80%的时间。

我们针对6号问题,取G为40 000代,其他参数保持不变,进行仿真,一般遗传算法仿真结束时间为22 209 s,混合算法结束时间为8 868 s,结果如图4所示。可以看到一般遗传算法保持平稳收敛,但收敛速度慢,结束时最小违约数为12;混合算法收敛速度相对较快,但在13 000代后陷入局部极小值无法跳出,结束时最小违约数仍为16。

5 结语

改进混合算法通过将遗传算法与模拟退火算法的优点结合,并加入“寻优式爬山”与大规模基因突变两种改进,既克服了一般遗传算法收敛速度慢的缺点,又解决了遗传退火混合算法易于陷入局部最小的问题,从算法效率与稳定性两方面提高了算法的性能。目前该算法已应用到我们自己开发的频率管理软件中,并取得很好的效果,对其进行深入的研究,并应用于信道分配及管理领域将会起到更大的作用。

摘要：用遗传与模拟退火相结合的混合算法对信道分配问题进行研究,并通过加入“寻优式爬山”与大规模基因突变两种优化方法对混合算法进行改进,克服了一般遗传算法收敛速度慢以及易于陷入局部最优解的缺点。给出了算法的实现流程,并针对几个典型信道分配问题对一般遗传算法、遗传与退火混合算法、改进后的混合算法进行仿真。仿真结果证明改进算法较其他2种算法至少节省80%的时间,并具有更好的稳定性,是解决信道分配问题的一种很好的算法。

关键词：信道分配,遗传算法,模拟退火算法,寻优式爬山法,大规模基因突变

参考文献

[1]张业荣,竺南直,程勇.蜂窝移动通信网络规划与优化[M].北京:电子工业出版社,2003.

[2]Funabikin,Takefuji.A Neural Network Parallel Algorithmfor Channel Assignment Problems in Cellular Radio Net-works[J].IEEE Transactions on Vehicular Technology,1992,41(4):430-437.

[3]Chiu Y,NGO,Victor Li O K.Fixed Channel Assignment inCellular Radio Networks Using a Modified Genetic Algo-rithm[J].IEEE Transactions on Vehicular Technology,199847(1):163-172.

[4]王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社,2004.

[5]王凌.智能优化算法及其应用[M].北京:清华大学出版社,2004.