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

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

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

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

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