導語：如何才能寫好一篇貪婪算法的基本原理，這就需要搜集整理更多的資料和文獻，歡迎閱讀由公務員之家整理的十篇范文，供你借鑒。

篇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.