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

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

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

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

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