基于模擬退火算法的頻率指配并行計算研究.pdf

1、隨著廣播電視數字化技術的發(fā)展與應用，新型數字地面業(yè)務如高清晰度電視、移動電視、數據廣播、手機電視正逐步走進千家萬戶。新型業(yè)務的引入使得頻率資源越來越緊張。頻率指配是廣播電視頻率規(guī)劃中的一項重要任務，是解決頻率資源匱乏的有效途徑。使用優(yōu)化算法來解決大規(guī)模的頻率指配問題是當前頻率規(guī)劃問題中的一個研究重點和方向，本文依托國家質量監(jiān)督檢驗檢疫總局科技公益專項基金項目數字電視國家標準推廣實施關鍵技術及優(yōu)化標準研制（200910245），對模擬退火

2、算法在頻率指配問題中的應用及其并行優(yōu)化做了深入的研究。
　　 本文首先分析了我國廣播電視頻率的劃分及其發(fā)展歷史和幾種常見的廣播電視頻率干擾情況，在已知發(fā)射機坐標和可用頻率表，并考慮同、鄰頻約束和人口覆蓋的基礎上，建立了頻率指配的數學模型。然后，根據模擬退火算法的基本思想及其與優(yōu)化組合問題的相似性，著重探討了Metropolis重要性抽樣準則和Markov鏈理論。在此基礎上，設計了求解頻率指配問題的模擬退火算法，并研究了各個關鍵環(huán)

3、節(jié)的參數設置及功能實現。然后，以局部搜索算法為參考，驗證了模擬退火算法在求解頻率指配問題上的優(yōu)越性。接著從頻率指配的可視化與地理信息輔助的角度出發(fā)，設計了基于MFC的頻率指配模塊，并實現了發(fā)射機坐標數據、人口數據、頻率表數據的導入，同、鄰頻干擾圖的顯示查詢以及基本的地圖操作功能。因為在求解頻率指配問題時，隨著問題規(guī)模的增大和要求的指配方案質量的提高，模擬退火算法計算所需時間也隨之增長，而冷卻進度表不能從根本上提高算法運行的效率。所以，提

4、出了模擬退火算法并行計算的思路，在分析并行計算的常見平臺與相關的并行庫基礎上，探討了并行算法的設計與性能評價指標，研究了模擬退火算法的三種并行方案，并提出了隨機選擇溫度表的并行指配方案。最后，根據軟件優(yōu)化的相關理論，在多核平臺下使用OpenMP對約束檢測代碼中的循環(huán)進行并行優(yōu)化。實驗表明，在求解較大規(guī)模的頻率指配問題中有明顯的加速效果。本文建立了一個簡易的頻率指配數學模型，提出了解決頻率指配問題的一般思路，實現了頻率指配的可視化與地理信