贪婪算法的基本原理范文

导语：如何才能写好一篇贪婪算法的基本原理，这就需要搜集整理更多的资料和文献，欢迎阅读由公务员之家整理的十篇范文，供你借鉴。

篇1

关键词：遗传算法；贪婪思想；进化逆转；旅行商问题

中图分类号： TP18 文献标识码： A

0引言

遗传算法（GA）是一种进化算法，其基本原理是仿效生物界中的“物竞天择、适者生存”的演化法则。最早是由美国密歇根大学Holland教授提出，在20世纪80年代左右得到了进一步发展。遗传算法是把问题参数编码为染色体，再利用迭代的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息，最终生成符合优化目标的染色体。目前遗传算法主要多用于优化问题[1]、图像处理[2]、通讯工程[3]等领域。

旅行商问题（TSP）是典型的组合优化问题，求解TSP问题传统的算法有：穷举法、分支限界法、动态规划法[4-5]等。高海昌等[6] 对蚁群算法、遗传算法、模拟退火算法、禁忌搜索、神经网络、粒子群优化算法、免疫算法等进行了论述。随着研究的深入，许多改进的算法不断涌现，李玮[7]采用矩阵编码、交叉、变异的遗传算法来解决TSP问题，雷玉梅[8]提出了一种分而治之的遗传算法思想，姚明海[9]采用遗传算法与其他智能算法结合的思想来解决问题。遗传算法因其高效的搜索能力成为了解决TSP问题的有效方法之一。虽然遗传算法能够较为成功地求解TSP问题，但也存在搜索较慢的问题，特别是遗传算法在解决TSP问题时容易出现早熟的问题。因此本文在交叉操作之前，将一半的当前种群替换成随机种群来防止早熟，再融合贪婪思想产生的初始群体[10]和贪婪思想引导的交叉算子[11]来加快收敛速度，用改进的变异算子[12]进行操作，由此而得到最优解。

5 结束语

文章在基本的遗传算法基础上提出一定改进，引用贪婪思想产生质量相对较好的初始种群，同时又在贪婪思想引导的交叉操作操作之前，把当前较差的一半种群替换成随机种群，二者结合来提升收敛速度又防止了陷入局部最优。实验证明，本文研发的改进遗传算法较好地解决了TSP问题中收敛速度和早熟的问题，且具有较强的鲁棒性，通用于类似的组合优化问题。

参考文献：

[1]袁满，刘耀林.基于多智能体遗传算法的土地利用优化配置[J].农业工程学报， 2014，30（1）： 191-199.

[2]门慧勇.基于遗传算法的图像分割优化研究[D].长春：东北师范大学，2012.

[3]陈侠.基于改进的遗传算法的网络编码优化方法研究[D].武汉：华中科技大学，2012.

[4]周康，强小利，同小军，等.求解TSP算法[J].计算机工程与应用，2007，43（29）：43-47，85.

[5]赵颂华.城市公共资源监管设计新思维[J].科技资讯，2015（15）：31-32.

[6]高海昌，冯博琴，朱利.智能优化算法求解TSP问题[J].控制与决策，2006，21（3）：241-247，252.

[7]李玮.关于旅行商问题的改进遗传算法[D].重庆：重庆大学，2004.

[8]雷玉梅.基于改进遗传算法的大规模TSP问题求解方案[J].计算机与现代化，2015（2）：34-39.

[9]姚明海，王娜，赵连朋.改进的模拟退火和遗传算法求解TSP问题[J].计算机工程与应用，2013， 49（14）：60-65.

[10]于莹莹，陈燕，李桃迎.改进的遗传算法求解旅行商问题[J].控制与决策，2014，29（8）： 1483-1488.

[11]谢胜利，唐敏，董金祥.求解TSP问题的一种改进的遗传算法[J].计算机工程与应用，2002， 38（8）： 58-60，245.

篇2

【关键词】压缩感知；贪婪算法；线性规划；随机投影

1.引言

当前大部分数据采集系统都是基于传统的香农采样定理来设计，按照这种方式采集的数据能够充分表示原始信号，但是它们存在较大的冗余。因此，这些方法往往导致采集数据的泛滥和传感器的浪费。研究如何根据信号的一些特征来实现低于乃奎斯特采样频率的采集，以减少所需采集的数据量具有重要的意义。在过去的30年里，从噪声中提取正弦信号的方法吸引了许多科学家的关注，但是利用信号的可压缩性进行数据采样却是一个新兴的课题。其起源于对具有有限信息率信号（finite-rate-of-innovation signal，即单位时间内具有有限自由度的信号）进行采集的研究，利用固定的结构性基函数（structured fixed deterministic sampling kernels）以两倍于新息率而不是两倍于奈奎斯特采样频率对连续信号进行采集。Donoho等人提出的压缩感知方法是一种可以广泛应用于可压缩信号的采集方法。该方法所需要的传感器数目大大减少，采集到的数据也具有更小的冗余度。因此，该理论提出后立即吸引了众多科学家的关注，目前我国关于压缩感知方法的研究也已开始起步，相信不久将有更多的人加入到关于压缩感知的研究行列。

压缩感知采集方法并不是对数据直接进行采集，而是通过一组特定波形去感知信号，即将信号投影到给定波形上面（衡量与给定波形的相关度），感知到一组压缩数据，最后利用最优化的方法实现对压缩数据解密，估计出原始信号的重要信息。压缩感知关键的问题是如何给定用来感知信号的波形才能有效地恢复出原始信号的重要信息。涉及的关键因素在于给定的波形要与可以用来压缩原始信号的波形组均不相干，并且不相干程度越高，感知数据包含的信息量越大，为准确获取重建原始信号所需的感知数据量就越少。Tao等人提出的受限等距性（Restricted Isometry Property，RIP）[2，3]、一致不确定性原理（Uniform Uncertainty Principle，UUP）和准确重构原理（Exact Reconstruction Principle，ERP）[4，5]进一步回答了如何从压缩数据中方便地提取信号有用信息的充分条件。

2.压缩感知中的信息获取方法

本节我们将讨论从感知到的数据中估计原始信号的几种常见实用方法：基追踪算法（Basis Pursuit，BP）、贪婪算法（Matching Pursuit，MP）、迭代阈值算法（iterative threshholding methods，iterative shrinkage algorithm）等。

2.1 基追踪算法

首先需要指出的是基追踪算法并不是一个最优化原则，其原理是上述讨论的给定一些限制条件后，通过极小化z，范数町以获得最稀疏的解。与之问题等价的标准线性规划问题为

极小化Z范数的方法能够有效解决压缩感知中的恢复问题，但是当结合其它的一些先验知识后，该问题可以被更加有效地解决。在此，我们仅简单介绍贝叶斯压缩感知方法（Bayesian compressed Sensing，BCS）和基于模型的压缩感知方法（model based compressed sensing）。Ji等人提出的BCS借助传统的贝叶斯方法和机器学习中的主动学习方法（active learning），通过将关于稀疏性的先验信息用垂直先验分布（hierarchical prior）来建模，提出了自适应的感知方法以及相应的恢复方法。而Baraniuk等人提出的针对基于模型可压缩信号（model compressible signals）的压缩感知方法中利用小波树模型和块稀疏模型，仅需要与稀疏程度相当的测度数即可实现信号的鲁棒性恢复。

2.2 矩阵填充问题

矩阵填充理论与压缩感知理论相比，压缩感知理论利用的是信号在一组基下的稀疏性，而矩阵填充理论利用的是利用矩阵特征值的稀疏性（即低秩性）。假设一个秩为r的低秩矩阵X，坩硒是一个将矩阵中位于支撑域以外的元素投影成零的正交投影。即：

那么，x能够通过如下的最优化方法从部分观测y中准确的重构出来：

该问题的求解同样是一个NP难问题。当部分观测是从矩阵X中随机选取的元素时，Candes指出该问题可以通过如下的凸规划问题加以求解：

实际上，部分观测矩阵l，是矩阵X在一些随机矩阵上的随机投影时，矩阵X同样可以从观测矩阵l中准确地重构出来。Ma等人进一步指出，当一个低秩的矩阵被稀疏噪声污染的时候，利用噪声的稀疏性和矩阵的低秩特性，同样能够把原始矩阵准确地重构出来，该理论被成功地用于人脸识别和视频跟踪中。

篇3

Abstract:The paper comment on digital image fusion what it researched maily,and introduce some typical technique of image fusion.

关键词:数字图像融合;主成分分析;演化计算;神经网络;小波变换;模糊算法

Key words: digital image fusion;principal components analysis;evolutionary computation;neural network;wavelet transform;fuzzy algorithm

中图分类号:TP399 文献标识码:A文章编号:1006-4311(2010)20-0099-01

0引言

二十世纪九十年代以来,图像融合技术的研究呈不断上升的趋势,应用领域也遍及遥感图像处理,可见光图像处理,红外图像处理,医学图像处理等。尤其是近几年来,多传感器图像融合技术已成为机器人,智能制造,智能交通,医疗诊断,遥感,保安,军事应用等领域的研究热点问题。

1数字图像融合的主要研究内容

数字图像融合是将两个或者两个以上的传感器在同一时间(或不同时间)获取的关于某个具体场景的图像或者图像序列信息加以综合,以生成一个新的有关此场景的解释,而这个解释是从单一传感器获取的信息中无法得到的。图像融合的目的是减少不确定性,其作用包括:①图像增强。通过综合来自多传感器(或者单一传感器在不同时间)的图像,获得比原始图像清晰度更高的新图像。②特征提取。通过融合来自多传感器的图像更好地提取图像的特征,如线段,边缘等。③去噪。④目标识别与跟踪。⑤三维重构。

2图像融合研究的发展现状和研究热点

多传感器图像融合是一个正在兴起的,并有着广泛应用前景的研究领域。当前图像融合在特征级的研究重点在于提高融合图像的空间分辨率的同时,尽量保持原图像的光谱特征,从而保证后续分析理解的有效性。另外,图像序列以及视频信息的融合问题也是非常有意义的研究课题。

3几类典型的数字图像融合理论与方法

3.1 主成分分析法主成分分析法的几何意义是把原始特征空间的特征轴旋转到平行于混合集群结构轴的方向去,得到新的特征轴。实际操作是将原来的各个因素指标重新组合,组合后的新指标是互不相关的。在由这些新指标组成的新特征轴中,只用前几个分量图像就能完全表征原始集群的有效信息,图像中彼此相关的数据被压缩,而特征得到了突出。

3.2 演化计算法演化计算是模拟自然界生物演化过程产生的随机优化策略与技术。它具有稳健性,通用性等优点和自组织,自适应,自学习等职能特征,下面是几种常用的演化计算方法:

3.2.1 遗传算法GA(genetic algorithm)遗传算法的基本思想是基于达尔文进化论和孟德尔遗传学说的。所以在算法中要用到进化和遗传学的概念,比如串(在算法中为二进制串,对应于遗传学中的染色体);群体(个体的集合,串是群体的元素);基因(串中的元素,如有一个串S=1001,其中1,0,0,1这四个元素分别成为基因);基因位置;串结构空间;参数空间;非线性;适应度等。遗传算法的原理可以简要给出如下:

Choose an initial population;Determine the fitness of each individual;Perform selection.

Repeat:Perform crossover;Perform mutation;Determine the fitness of each individual;Perform selection;

Until some stopping criterion applies.

这儿所指的某种结束准则一般是指个体的适应度达到给定的阈值,或者个体的适应度的变化率为零。

3.2.2 粒子群算法(PSO)粒子群优化算法是一种进化计算技术,源于对鸟群捕食的行为研究。设想有这样一个场景:一群鸟在随机搜索食物,在这个区域里只有一块食物,所有的鸟都不知道食物在哪里,但是他们知道当前的位置离食物还有多远,那么找到食物的最优策略是什么呢?最简单有效的方法就是搜寻目前离食物最近的鸟的周围区域。PSO算法从这种模型中得到启示并用于解决优化问题。PSO中,每个优化问题的解都是搜索空间中的一只鸟,我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值,每个粒子还有一个速度决定他们飞翔的方向和距离,然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子(随机解),然后通过迭代找到最优解。

3.2.3 蚁群算法蚁群算法(ant colony optimization,ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种求解组合最优化问题的新型通用启发式方法,该方法具有正反馈、分布式计算和富于建设性的贪婪启发式搜索的特点。

3.3 神经网络法神经网络法是在现代神经生物学和认知科学对人类信息处理研究成果的基础上提出的,它有大规模并行处理、连续时间动力学和网络全局作用等特点,将存储体和操作合二为一。现实世界中图像噪声总是不可避免地存在,甚至有时信息会有缺失,在这种情况下,神经网络融合法也能以合理的方式进行推理。

3.4 小波变换法自从1989年Mallat提出了二维小波分解方法后,小波变换在图像处理中迅速得到了广泛的应用。在图像融合领域,小波变换方法也是一种重要的方法。对于图像融合,在频率域进行比在时间域进行更为有效,融合算法的设计必须把融合的技术目的和图像的频率域表现结合起来考虑。

3.5 模糊图像融合所谓模糊性是指客观事物在形态及类属方面的不分明性,其根源是在类似事物间存在一系列过渡状态,它们互相渗透,互相贯通,使得彼此之间没有明显的分界线。图像融合模糊算法的基本原理是利用模糊隶属度函数量化不同目标类型和相应像素值之间的关系。

4结束语

图像融合是一个众多学科感兴趣的十分活跃的研究领域。图像融合也还有许多问题急需解决。首先,图像融合技术缺乏理论指导。虽然关于图像融合技术的公开报道很多,但每篇文章都是针对一个具体的应用问题,对图像融合技术还没有一个统一的理论框架。所以,建立图像融合的理论框架是目前的一个发展方向。再者由于图像的特殊性,在设计图像融合算法时一定要考虑到计算速度和所需的存储量,如何得到实时、可靠、稳定、实用的融合算法和硬件电路是目前研究的一个热点。另外,建立客观的图像融合技术评价标准也是急需解决的问题。

参考文献:

[1]覃征等.数字图像融合[M].西安交通大学出版社,2004.

篇4

关键词：蚁群算法；参数选择；人工设置；自适应调整

中图分类号：TP312文献标识码：A文章编号：1009-3044(2010)20-5588-03

Study on Parameter Selection of Ant Colony Algorithm

HUANG Shao-rong

(Department of Information Management, Guangdong Justice Police Vocational College, Guangzhou 510520, China)

Abstract: Ant colony algorithm (ACA) is a new stochastic optimization algorithm which shows many excellent characters and has succeeded in solving many difficult optimization problems and NP-hard problems. The parameters have an important role in the result of ant colony algorithm. This paper introduces the theory of ACA based on Traveling Salesman Problem (TSP), analyses the function and influence of parameters in ACA, and then introduces the methods of parameters selection in two ways: set the parameters manually and adjust the parameters adaptively. At last, it has compares and summarizes each method.

Key words: ant colony algorithm; parameter selection; manually set; adaptively adjust

如何为元启发式算法设置合理的参数是启发式算法理论和应用研究的一个重要方向。蚁群算法作为最成功的元启发式算法之一，优化性能很大程度上依赖于参数的设置，但要对其参数进行最优设置是一项复杂的工作，往往需要经过大量的测试，这成为蚁群算法进一步推广应用的一个瓶颈。

1 基本蚁群算法

蚁群算法是由Colorni、Dorigo和Maniezzo于20世纪90年代初通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于种群的启发式仿生进化算法[1]。由于蚁群算法具有分布性、并行性、全局性、鲁棒性强等特点，已经在求解NP-难问题和众多应用问题中显示出良好的优化性能和发展潜力。

以TSP问题为例，采用常用的any-cycle模型，简单阐述蚁群算法的基本原理：

设有m只蚂蚁，每只蚂蚁访问n个城市，规定蚂蚁走合法路线，除非周游完成，不允许转到已访问城市。初始时刻，各路径的信息量τij(0)相等，m只蚂蚁被放置到不同的城市上。蚂蚁k（k=1,2...,m）在运动过程中，根据各条路径上信息量和前方路径的长短决定转移方向，Pkij (t)表示在t时刻蚂蚁k由城市i转移到j的概率：

(1)

其中：

allowed k―蚂蚁k下一步允许转移到的城市集合，随k的行进而改变；

τij(t)―t时刻路径（i,j）上的信息量；

α―信息启发式因子；

β―期望启发式因子；

ηij(t)―城市i转到j的期望程度，一般取：ηij(t)=1/dij（dij表示相邻两个城市的距离）；

当蚂蚁k完成周游后，根据式(2)-(4)更新蚂蚁访问过的每一条边上的信息素：

τij(t+n)=(1-ρ)・τij(t)+ Δτij(t) (2)

(3)

(4)

其中：

ρ―信息素挥发系数；

Δτij(t)―本次循环中路径(i,j)上的信息量增量；

Δτkij(t)―蚂蚁k本次循环中在路径(i,j)上留下的信息素数量；

Lk―蚂蚁k环游一周的路径长度；

Q―信息素强度因子，常量。

众多的研究已经表明蚁群算法具有很强的发现较好解的能力，但作为启发式概率型优化算法，蚁群算法存在着早熟收敛，对参数依赖性强的缺点。对于不同版本的蚁群算法或具体的应用问题，甚至不同的具体实例，算法需要不同的参数设置来获取最优的性能。传统对参数的设置是根据应用者有限的经验习惯人为地调整，往往需要做大量的数据测试，不仅耗费时间而且影响了算法最优性能的发挥，成为蚁群算法应用的一大缺陷。

2 控制参数对算法性能的影响[2]

蚁群算法含有一系列对算法性能有重要影响的控制参数，包括：

1）启发式因子α和β：α表示信息素的重要性，反映了蚁群在运动过程中所残留的信息量在指导蚁群搜索中的相对重要程度。α越大，信息素在路径选择上所起作用越大，蚂蚁选择以前走过路径的可能性就越大，搜索的随机性减弱；α越小，易使蚁群算法过早陷入局部最优。当α=0时，将不会利用信息素信息，搜索降为贪婪搜索。

β表示能见度的重要性，反映了启发式信息在指导蚁群搜索过程中的相对重要程度。这些启发式信息表现为寻优过程中先验性、确定性因素。β越大，城市之间距离对路径选择所起作用越大，蚂蚁在局部点上选择局部最短路径的可能性越大，虽然加快了收敛速度，但减弱了随机性，易于陷入局部最优。当β=0时，将忽略对有吸引力的解的显式倾向，算法等同于性能较差的简单蚁群优化（SACO）。

α和β决定了以往的搜索经验和问题的固有启发信息之间的相对重要性，出现在绝大部分的蚁群算法中，对算法性能的影响至关重要，是最重要的两个参数。由于α和β是在信息素浓度和启发式信息之间取得平衡的转移概率Pkij的两大决定因子，通过调节α和β可以很好地处理探索--开发之间的关系。

2）信息素挥发系数ρ：模仿人类记忆特点，随着新信息的增加，旧的信息将逐步忘却、削弱，故引入ρ表示信息素的挥发率，为了防止信息的无限积累，ρ的取值范围设定为[0,1]。

ρ的大小直接关系到蚁群算法的全局搜索能力及其收敛速度；ρ增大，则信息素挥发加快，对过去的历史经验不太敏感，突出最近路径上留下的信息对选择的影响。

相应地，用1-ρ表示信息的残留系数。1-ρ反映了蚂蚁个体之间相互影响的强弱，其大小对蚁群算法的收敛性能影响非常大。在0.1-0.99范围内，1-ρ与迭代次数近似成正比，这是由于1-ρ很大，路径上的残留信息占主导地位，信息正反馈作用相对较弱，搜索的随机性增强，因而蚁群算法的收敛速度慢。若1-ρ较小时，正反馈作用占主导地位，搜索的随机性减弱，导致收敛速度快，但易陷于局部最优。

3）信息素强度因子Q：Q表示蚂蚁循环一周或一个过程释放在所经路径上的信息素总量。在一定程度上影响处算法的收敛速度，Q越大，则每次蚂蚁经过所留下的信息素越多，在已遍历路径上信息素的累积越快，加强蚁群搜索时的正反馈性，有助于算法的快速收敛。

4）蚂蚁数量m：蚁群算法成功在于多只蚂蚁的共同协作行为，通过释放信息素，蚂蚁之间相互传递有关搜索空间的经验与知识。对同一规模的处理问题，m越大，即蚂蚁数量多，会提高蚁群算法的全局搜索能力和稳定性，但数量过多会导致大量曾被搜索过的路径上的信息量变化趋于平均，信息正反馈作用减弱，随机性增强，收敛速度变慢。反之，如果m越小，即蚂蚁数目太少，会使从来未被搜索到的解上的信息量减小到接近于0，全局搜索的随机性减弱，虽然提高了收敛速度，但算法稳定性差，出现早熟现象。另一个就是对计算复杂度的影响，使用的蚂蚁越多，需要建立的路径就越多，对信息素释放的计算也就越多。

3 参数选择

控制参数直接影响算法的性能，包括找到的解的质量及其计算开销。参数选择在算法应用中显得尤其重要，为了提高算法的性能，必须优化相关的控制参数。自从Dorigo等对AS系统中的参数下选取进行了初步研究[3]以来，很多学者在实验基础上进行了深入研究并提供了一些参数设置参考值和优化参数值的启发式方法。

1）人工设置参数：叶志伟等对α、β和ρ这三个对算法的影响较大的参数的最优配置进行了研究，得出：在any-cycle模型中，α=1，β=5，ρ=0.5时，算法性能最优；ant-density模型中，α=1，β=10，ρ=0.1时，算法性能最优；ant-quantity模型中，α=1，β=5，ρ=0.001时，算法性能最优[4]；而蒋玲艳等在分析了这三个参数不同组合对算法性能的影响基础上，总结出参数设置规则：当α∈[0.1,0.3]，β∈[3,6]，ρ∈[0.01,0.3]时，算法总体上有较好的性能，不易早熟，而且所需的迭代次数较少[5]。

对于所有参数（α、β、ρ、Q、m），段海滨提出了调整步骤[6]：首先根据“城市规模/蚂蚁数目≈1.5”的原则确定蚂蚁数目m；然后粗调取值范围较大的α、β和Q；最后微调取值范围较小的ρ。詹士昌等指出当α∈[1,5]，β∈[1,5]，ρ=0.3，Q=100， （n为城市规模）时基本蚁群算法能较快地求得最优解[7]。张毅等则提出了最优的算法参数组合为：α=1、β=5、ρ=0.6、Q=1000、m=城市规模。在该算法参数设置原则下，基本蚁群算法对任意TSP问题总能比较快速地求得全局最优解[8]。

人工设置参数需要大量的数据测试，蚁群中的所有蚂蚁均采用相同的参数，而且只能为算法设定一个合适的初始参数，而不能在执行过程中随时调整参数，影响了算法的性能。

2）自适应调整参数：针对人工设置参数的局限，学者们提出了自适应地调整参数的改进算法，主要是利用蚁群算法具有容易与其它优化算法或局部搜索算法结合的优点，在蚁群算法中混合其它启发式算法以对其参数进行训练和优化，主要有：

① 运用遗传算法优化蚁群算法的控制参数[9]：利用遗传算法快速性、随机性、全局收敛性的特点，每条染色体代表蚁群算法的一个参数值集合，通过选择、交叉和变异等操作不断优化蚁群算法参数。

② 运用粒子群优化算法优化蚁群算法的控制参数[10]：粒子群优化算法具有非常快地逼迫最优解的速度，可以有效对蚁群算法的控制参数进行优化。粒子被表示成一个多维的实数编码串，代表蚁群算法的一个参数值集合，再引入适应度函数并结合粒子群算法得到各参数的最优组合。

③ 运用差分演化算法优化蚁群算法的控制参数：将蚁群算法的参数作为差分演化算法解空间的向量元素，自适应地寻找蚁群算法最优参数组合的同时求解问题的最优解。

在蚁群算法中引入其它启发式算法的混合算法，不仅使蚁群算法有效摆脱了对参数设置的依赖，而且克服了早熟收敛的缺点，大大提高了算法发现最优解的能力，具有更好的全局优化性能。

此外，研究者还提出了根据蚁群算法的不同进化阶段或当连续几代进化后的最优解没有明显变化时，自适应调整参数，以提高最优解的求解质量的改进方案[11]。这类改进算法能够有效提高算法的优化性能，但这些方法并不是通用的，只能使用于特定的算法模型或针对特定的问题。

4 小结

蚁群算法作为一种随机算法，其性能很大程度上受算法参数的影响，好的参数可以使算法快速收敛于优质解，而参数设置不当，将导致算法找到的解质量差，容易陷于局部最优，并且收敛速度慢甚至不收敛。由于蚁群算法参数空间的庞大性和各参数之间的关联性，很难设置最优参数组合以使蚁群算法优化性能最佳，至今还没有完善的理论依据，没有参数选择方面的公式可循，通常根据经验而定。因此，对蚁群算法的参数进行深入分析，了解参数之间的关联，提出好的参数设置方案，以便更合理地设置参数或者自适应地调整参数是非常有意义的，不仅能有效地提高算法的优化性能，而且完善了算法的理论研究，进一步推广蚁群算法在优化领域上的应用。

参考文献：

[1] Colorni A,Dorigo M,Maniezzo V.Distributed Optimization by Ant Colonies[C]//The First European Conference on Artificial Life.France: Elsevier,1991:134-142.

[2] 汪定伟.智能优化方法[M].北京:高等教育出版社,2007.

[3] Dorigo M,Maniezzo V,Colorni A.Ant system: optimization by a Colony of Cooperating Agents[J].IEEE Transactions on System,Man and Cybernetics,1996,26(1):29-41.

[4] 叶志伟,郑肇葆.蚁群算法中参数α,β,ρ设置的研究-以TSP问题为例[J].武汉大学学报,2004,29(7):597-601.

[5] 蒋玲艳,张军,钟树鸿.蚁群算法的参数分析[J].计算机工程与应用,2007,43(20):31-36.

[6] 段海滨.蚁群算法原理及应用[M].北京:科学出版社,2005.

[7] 詹士昌,徐婕,吴俊.蚁群算法中关键参数的选择[J].科技通报,2003,19(5):381-386.

[8] 张毅,梁艳春.蚁群算法中求解参数最优选择[J].分析计算机应用研究,2007(8).

[9] Botee H,Bonabeau E.Evolving Ant Colony Optimization[J].Complex Systems,1998,1(2):149-159.

篇5

基金项目:国家自然科学基金资助项目（61075013）;电子科技大学青年科技基金资助项目（TX0706）。

作者简介:李晓峰（1963-）, 男, 四川成都人，教授, 主要研究方向：多媒体图像传输、无线通信系统； 刘洪盛（1966-）, 男，吉林吉林人，博士，主要研究方向：通信信号处理、多媒体传输； 任通菊（1964-）, 女,四川成都人, 硕士, 主要研究方向：通信技术。

文章编号:1001-9081（2011）07-1956-03doi:10.3724/SP.J.1087.2011.01956

（电子科技大学 通信与信息工程学院， 成都 611731）

（; ; ）

摘 要:为了应对H.264可伸缩视频编码（SVC）应用中网络特性的波动，提出了一种预测播放中断与缓冲区溢出风险进行及早调节的自适应媒体播放（AMP）算法。该算法估算网络流量与视频图像组（GOP）结构中各帧长度用于风险预测，通过K步调节过程实现良好的调节平滑性与速度，并利用SVC的可伸缩性尽量减少溢出带来的质量损失。仿真结果表明，该算法在抑制播放中断、处理缓冲区溢出与抖动性能等方面，优于现行的平滑AMP与常规AMP算法。

关键词:自适应媒体播放；可伸缩视频编码；视频流；多媒体通信

中图分类号:TN919.8文献标志码:A

Adaptive media playout algorithm for H.264 scalable video streaming

LI Xiao-feng, LIU Hong-sheng, RENG Tong-ju

（School of Communication and Information Engineering, University of Electronic Science and Technology of China, Chengdu Sichuan 611731,China）

Abstract: To cope with the variation of network conditions in scalable video streaming, a new Adaptive Media Playout （AMP） algorithm was proposed which predicates the risk of playout outage and buffer overflow and adjusts the frame rate in advance. The algorithm estimated the throughput of network and the lengths of frames in the video’s GOP structure for risk predication, realized adjustments in K steps for good smoothness and speed, and reduced quality loss of the video by exploiting the scalability of SVC stream. The simulation results show that the proposed algorithm outperforms the existing smooth and conventional AMP algorithms in outage suppressing, overflow processing and jitter performance.

Key words: Adaptive Media Playout （AMP）; Scalable Video Coding （SVC）; video streaming; multimedia communication

0 引言

视频压缩与网络技术的发展促进了各种视频流媒体的广泛应用，典型的例子如：数字视频广播、视频点播、可视会议与网络视频等。视频序列以流的形式传输时，先到达终端的部分数据立即被解码播放，让用户及时收看内容，而不必等待全部数据接收完毕。但是，网络的传输特性是时变的，端到端的数据速率与时延总不稳定。通过网络传输的视频数据包在到达收端时可能发生突发的延迟，甚至出现短期中断。为此，收端必须使用接收缓冲区应付传输特性的变化。缓冲区太小难于应付网络变化，太大会引入过多的时延并耗费存储资源。如何有效利用接收缓冲区提高视频传输可靠性是人们研究的热点之一。

自适应媒体播放（Adaptive Media Playout，AMP）技术是其中的重要方法之一。运用AMP技术，终端根据接收缓冲区的状况调整媒体播放速率。当网络流量低时，缓冲区存量减少，终端适量减慢播放速率，从而降低数据消耗，减少播放中断风险。研究表明: 在基本不影响用户感受的条件下，音视频流的播放速率可以变化约±25%［1］。调节音频流的速度时需要通过特殊的信号处理保持音调等声音特征的稳定，而调节视频流的速度可简单地通过改变帧间间隔来实现。本文只讨论视频流的相关问题。

文献［1-3］主要研究了基于缓冲区数据量实施调节的AMP方法。其基本原理是设置调节门限，当缓冲区数据量低于门限时，增大播放视频的帧间间隔s（s>1）倍，以降低缓冲区下溢出的概率。这类方法中要根据应用合理地选择门限。文献［4-6］探讨了以最佳视频质量为目标，通过动态设置门限降低缓冲区中断概率与起始等待时间的方法。其中文献［5］以无线视频流的应用为背景提出了缓冲区下溢出的统计模型，通过动态建立模型参数来计算最佳门限。文献［6］采用马尔可夫模型研究中断间隔、启动预时延、视频质量与无线网络信道状况彼此之间的关系，进而求出优化的AMP策略。文献［7］对发端的数据包调度策略与收端的播放速度进行联合优化，并将视频内容特征纳入考虑，通过复杂的贪婪算法进行求解。文献［8］采用G/G/1/∞与G/G/1/N统计模型对接收缓冲区进行建模，推导了多种主要参数公式，提出了最佳视频质量函数，并通过复杂的优化算法解出最佳策略。上述动态门限与统计模型等方法常常用到复杂的算法。文献［9］不同于常规的门限调节方式，提出了一种基于缓冲区变化幅度的调节方法，结合较长的调节进程实现了十分平滑的调节。但这种方法有时调节速度过于平缓，造成跟踪信道变化的速度不够。

近年来国际标准化组织提出一种能适应异构网络与终端特性的有效方法――可伸缩视频编码（Scalable Video Coding，SVC）［10］。不同于常规的H.264，SVC编码器生成的比特流由一个基础层（Base Layer,BL）与多个增强层（Enhancement Layer,EL）构成，在空间、时间与质量方面具有可伸缩性。

本文针对SVC码流的传输应用，提出了一种通过预测接收缓冲区的上下溢出风险，进行平滑调节的方法。预测中基于SVC的图像组（Grope Of Pictures，GOP）结构中不同帧的长度估算提高预测准确性，并在溢出处理中利用SVC的可伸缩性来避免BL丢失，减少质量损失。

1 系统模型与典型算法

SVC视频流传输系统如图1所示。它包括源端、差错信道与用户端。视频源与流媒体服务器按固定的标称帧率Rf（相应的标称帧间间隔记为Tf 0）发送以H.264可伸缩压缩编码的NAL数据包，经信道传输到用户终端，存入接收缓冲区中。播放器基于AMP策略按间隔Tf（t）从缓冲区中提取数据，播放画面。这里t为系统时间，采用离散值（时隙长为δ）。记s（t）为t时刻后播放画面的时间基准，n（t）是t时隙中播放器应从缓冲区中提取的帧数，有

s（t） （1）

与 n（t）「［δ－s（t－1）］/Tf（t）S（2）

式中「S为取整数运算。

图1 SVC视频流传输系统

传输系统采用自动重传请求（Automatic Repeat reQuest, ARQ）策略，如果出现传输错误，收端通过反馈信道发送重传请求。本文参照文献［1］的方法作合理的简化，假定系统允许足够次数的重传，保证进入缓冲区的数据包都是正确的与严格按顺序到达的。在这种情况下，网络的错误与丢包可以等效为数据速率的下降。记网络端到端的原始数据率为R0，当前丢包率为Pe（j），则等效的数据率为R（t）R0［1－Pe（j）］，其中， j为当前信道状态。不同状态的信道具有不同的丢包率。本文采用Gilbert-Eilliott的两状态马尔可夫丢包模型。信道在好状态与坏状态下以不同的概率随机丢包。坏信道对应信道出现突发错误时的情况，而突发长度对应信道处于坏状态的平均滞留时间。记信道状态为j∈{g,b}，g与b分别指好状态与坏状态。两状态的平均滞留时间分别记为Tg与Tb，相应的丢包概率记为pgPe（g）与pbPe（b）。

视频流中每帧对应的字节数各不相同，而且可以相差很大，比如，I帧与B帧可能相差十倍以上，因此，不宜采用文献［9］的观点取各帧字节长度一样并对应于单个数据包。本文将区别不同帧的长度，帧长信息从NAL包头参数求取。设缓冲区尺寸为B0字节，可容纳的平均帧数大约为L。数据存入缓冲区时以数据包为单位，而播出时以帧为单位。分别记B1（字节）为缓冲区的上溢出警戒线、L0（帧）为下溢出警戒线；ML/2为起始等待帧数。并记t时刻缓冲区的数据量为b（t）,包含的完整帧数为l（t）。缓冲区结构如图2所示。

播放过程中，如果t时刻出现l（t）

图2 接收缓冲区结构示意图

常规AMP算法［1］的基本规则为:

Tf（t） （3）

平滑AMP算法［9］ 的基本规则为：

1）如果l（t）－lR（t）>τ则发出调节请求（lR（t）为动态参考点，τ为某常数），计算调节期长度如下：

TC－ln－1（4）

其中：T 0f与T1f分别是当前与目标间隔，T1f通过输入数据速率估算；C称为调节量，如下计算（以l（t）向下波动为例）：

C （5）

2）在调节期中，

Tf（t）T0f+（T1f－T0f）（t－t0）/T（6）

其中t0是调节期的起始时刻。

3）在非调节期中，保持Tf（t）Tf（t－1）。

平滑AMP算法只检查缓冲区中帧数的波动，而不需直接对数据量设定门限，该算法通过调节期使调节过程十分平滑。但其调节幅度没有控制，有时远大于±25%的范围，使收视感觉不好。而且，其调节过程有时过于缓慢，来不及应付信道变化。

2 基于预测的自适应播放算法

本文提出的AMP方案对网络流量与视频参数进行估算，并基于这两项估算预测缓冲区的溢出与播放中断风险。具体策略如下。

1）收端统计当前时隙中的接收数据包及其字节量，记当前接收字节量为x（t）。估算信道流量为

R^ （t）λcR^ （t－1）+（1－λc）x（t）（7）

其中λc为正常数，0≤λc≤1。

由接收数据包分析NAL包头，重组视频帧，记成功重组的完整帧长度为y（t），其在GOP中的帧编号为i1,2,…,Ngop（其中，整数Ngop为SVC的GOP长度）。记视频帧长度为{fi（t）,i1,2，…,Ngop}，并如下估算，

fi（t）λvfi（t－1）+（1－λv）y（t）（8）

其中λv为正常数，0≤λv≤1。

2）预测未来K帧期间的风险（K为常数）。

a）播出中断风险：计算lKnl（KR^ （t）,i），其中i是当前接收帧的GOP编号；nl（z,i）给出从编号i开始用z字节可组装的完整视频帧数。

令ΔlKlK+l（t）－K－L0。若ΔlK

ΔTf－2ΔlKTf（t）/[（K+ΔlK）（K+ΔlK+1）]（9）

若Tf（t）+K×ΔTf>1.25，改用ΔTf［1.25－Tf（t）］/K1，其中:

K1「+S（10）

b） 缓冲区溢出风险：计算lKnl（b（t）+KR^ （t）－B0,i），其中i是当前播放帧的GOP编号。

令ΔlKlK－K。若ΔlK>0，则存在溢出风险。这时启动调节，以ΔlK代入式（9）计算参数ΔTf。若Tf（t）+K×ΔTf

K1「+S（11）

3）在K步调节期中，Tf（t）Tf（t－1）+ΔTf ；在非调节期中，保持Tf（t）Tf（t－1） 。

算法中，计算nl（z,i）时利用{fi（t）}可以准确估算帧数；式（9）按K步平滑调节原则计算间隔增量；而式（10）与（11）是为了确保在±25%的调节范围内完成平滑调节。当到达数据量超过缓冲区容量，本文基于SVC的可伸缩性进行如下处理：由缓冲区中的NAL包头提取SVC空间、时间与质量层次编号D、T与Q，如下计算该NAL包的重要性，

SI （12）

其中，a,b,c∈（0,1）为权系数；β是使SI的范围为0至1的归一化因子。在缓冲区中依次删除SI最小的数据包，直到缓冲区能够容纳新到达的数据包为止。由于基础层（BL）的数据量比总的数据量小许多，通过这样的处理可以完全避免BL的丢失，而且，删除的数据包对应的质量损失是最小的。

3 仿真结果及分析

仿真实验采用四个长约10min的视频测试序列，它们由标准序列经重复生成。相应的标准序列分别是：Mobile、Football、Foreman与Bus，基本长度为256、288、288与144，重复次数为72、64、64与128。视频编解码采用联合可伸缩视频模型（JSVM）参考软件7.10版本，帧率为30fps，输出码流为单一的空间分辨率，含一个基础层与三个增强层。设定GOP＝8，Intra＝16，基础层量化参数QP＝36。

信道采用两状态马尔可夫丢包模型。主要参数为：Tg18.5s，Tb1.5s，pg0.01与pb0.80。网络原始数据率R0设定为视频流平均码率的1.5倍。系统时隙取为1/30s。缓冲区大小B0为128B的倍数，相当于约5s时间（L150）。令B10.75B0与L036。

为了评估本文所提方案的性能，本算法与常规AMP［1］、平滑AMP算法［9］与“25%约束的平滑AMP算法”相比较。“25%约束的平滑AMP算法”指帧间隔调节范围限制在±25%以内的平滑AMP算法方案，通过限制便于在可接受的变速条件下进行比较。三种参考算法以及本文算法分别简记为AMP、SAMP（Smooth AMP）、SAMP25与PAMP（Predicative AMP）。SAMP算法中取τ7，PAMP算法中取K49。性能指标为：播出中断次数、帧间隔的归一化范围（Tf/Tf 0）、相对抖动dTf，以及溢出造成的平均峰值信噪比（PSNR）损失与BL丢失计数。相对抖动dTf可以衡量调节的平滑度，定义为（设序列总帧数为n）

dTf∑ni2Tf（t）－Tf（t－1）/Tf 0×100%（13）

表1给出了四种算法针对各测试序列的仿真实验结果，所有数据为运行100次的平均值。可以看到：本文算法与SAMP的播出中断次数基本一样（大约0.6次），都明显优于常规AMP算法；调节平滑程度也比常规AMP好许多。本文算法的帧间隔变化幅度控制在±25%以内，而SAMP的变化幅度可能超过600%，后者的视觉感受会明显降低。SAMP调节较缓慢，如果对其调节幅度进行约束，从SAMP25的数据可见，SAMP的中断次数会明显上升。

表1 四种算法的性能参数对比

另一方面，SAMP算法依靠大幅度的调节使其溢出概率与BL丢失概率较低。本文PAMP算法采用基于SVC可伸缩性的溢出处理，避免了BL丢失，有效减少了视频质量损失。这种溢出处理方法同样适用于其他几种算法。表2给出了PAMP算法中溢出处理前后的数据比较，还给出了AMP与SAMP25的相应数据。可见，几种算法经过处理后BL不再丢失,这对于视频的收视质量有很好的改善。溢出处理无助于播出中断与调节范围的控制，所以，本文算法比其他算法在综合性能上有明显的优势。

表2 启用基于SVC的溢出处理前后比较

4 结语

面对网络传输特性与流量的波动，自适应媒体播放技术是有效利用接收缓冲区保障用户视觉感受的一项重要技术。本文为SVC视频流提出一种预测播放中断与缓冲区溢出风险进行及早调节的AMP方法，通过对SVC视频数据GOP结构中各种帧长度的估算，使风险预测更加准确。通过K步调节过程使帧间隔的调节既比较平滑又有良好的速度；适度的调节范围使视频播放的主观感受保持良好；而基于SVC可伸缩性的溢出处理最大限度地减少了溢出带来的质量损失。仿真实验表明，本方法相对于现行的平滑AMP与常规AMP算法在抑制播放中断、维持用户视觉感受、处理缓冲区溢出与控制调节的平滑度等方面有较大的优势。

参考文献:

［1］ KALMAN M, STEINBACH E, GIROD B. Adaptive media playout for low-delay streaming over error-prone channels ［J］. IEEE Transactions on Circuits and Systems for Video Technology, 2004, 14（6）: 841-851.

［2］ STEINBACH E, FARBER N, GIROD B. Adptive playout for low latency video streaming［C］// Proceedings of 2001 International Conference on Image Processing. New York:IEEE, 2001:962-965.

［3］ CHUAN H C, HUANG C Y, CHIANG T. On the buffer dynamics of scalable video streaming over wireless network［C］// Proceedings of IEEE 60th Vehicular Technology Conference. New York:IEEE, 2004:2582-2586.

［4］ YANG Y H, LU MENGTING, CHEN H H. Smooth playout control for video streaming over error-prone channels［C］// Proceedings of the 8th IEEE International Symposium on Multimedia. Washington, DC: IEEE Computer Society, 2006:415-418.

［5］ CHUANG H C, HUANG C Y, CHIANG T H. Content-aware adaptive media playout controls for wireless video streaming［J］. IEEE Transactions on Multimedia,2007, 9（6）:1273-1283.

［6］ PARK S, KIM J. An adaptive media playout for intra-media synchronization of networked-video applications［J］. Journal of Visual Communication and Image Representation, 2008, 19（2）:106-120.

［7］ LI Y, MARKOPOULOU A, APOSTOLOPOULOS J, et al. Content-aware playout and packet scheduling for video streaming over wireless links［J］. IEEE Transactions on Multimedia, 2008, 10（8）:885-895.

［8］ LUAN T H, CAI L X,SHEN X. Impact of network dynamics on user's video quality: Analytical framework and QoS provision［J］. IEEE Transactions on Multimedia, 2010,12（1）:64-78.