基于模擬退火算法的地面電視頻率指配方法研究

　　3.2.3應用舉例

　　問題：

　　已知現(xiàn)有20個臺站(如圖1示)，每個臺站有20個可選頻道(編號為DS-13～DS-32)。要求給每個臺站指配一個頻道，使得相鄰發(fā)射臺站的頻率指配滿足同頻復用約束條件，同時
　　使用的頻道數(shù)量最少，且盡可能使用低頻段。

 　　分析：

　　給20個臺站分別指配一個頻道，共有2020種可能的覆蓋組網(wǎng)方案。

　　如果采用世界最快的超級計算機進行"窮舉"，運算速度按每秒約280，6萬億次計算，需要t=2020／(280.6×1012)秒≈11849年?？梢姡捎么朔椒ú豢赡茉谟猩暧嬎惚容^所有方案，從中找出絕對的最佳方案。因此，只能采用某些優(yōu)化算法如模擬退火算法等找到滿足規(guī)劃要求的"近似最佳"方案。

　　為了便于計算，可以用一個鄰接矩陣N來表示上述發(fā)射臺站之間的頻率約束關系，發(fā)射臺站之間頻率約束關系對應的鄰接矩陣見圖2。

 　　0表示臺站間的距離大于或等于最小同頻復用距離。

　　1表示臺站間的距離小于最小同頻復用距離。

　　一旦用于頻率指配的鄰接矩陣生成，接下來的問題是怎樣用盡可能少的頻道來指配。在實際頻率指配中，可以采用數(shù)學中的模擬退火方法逼近最優(yōu)解。

 　　模擬退火算法的具體實現(xiàn)步驟：

　　(1)初始化：初始溫度T1=500，T2=0.01

　　初始解狀態(tài)S(是算法迭代的起點)

　　Freq[20]={13，14，15，16，17，18，19，20，21，22，23，24，25，26，27，28，29，30，31，32}；

　　(2)從Freq領域中產(chǎn)生滿足約束條件的新解Freq′；

　　(3)計算增量△E=E(Freq′)-E(Freq)，其中E(Freq)為目標函數(shù)

　　E(Freq)=sum(Freq)+span(Freq)×μ(μ為加權值，span為所指配的最高頻道與最低頻道之差)；

　　(4)若△E<0則接受Freq′作為新的當前解，否則以概率exp(-△E／)接受Freq′作為新的當前解；

　　(5) 如果滿足終止條件則輸出當前解作為最優(yōu)解，結束程序； (6) T1逐漸減少(T1=0.998T1)，且T1>T2，然后轉第2步。

　　結果

　　應用模擬退火算法程序產(chǎn)生的一組頻率指配結果如表1。

　　此時目標函數(shù)E(Freq)=313，迭代次數(shù)k為5751次。

　　測試結果表明，只要計算時間足夠長，模擬退火算法就可以保證以概率1.0收斂于全局最優(yōu)解。在實際應用中，由于計算速度和時間的限制，優(yōu)化效果和計算時間二者之間存在矛盾，計算結果可能會陷入局部最優(yōu)解。

　　4小結

　　近年來，根據(jù)"科學發(fā)展觀要求"，為使頻率規(guī)劃決策更具科學性，我國在多次地面電視頻率規(guī)劃工程中，均使用了覆蓋面積、人口，可用場增量等統(tǒng)計指標，取得了良好的收效。由于指標數(shù)據(jù)的獲得需考慮復雜的臺站地理關系和統(tǒng)計模型，耗時費力，在時間來不及時，不得已還要借助經(jīng)驗進行頻率規(guī)劃決策。分析表明，上述指標的統(tǒng)計方法具備一定規(guī)律，經(jīng)過適當?shù)挠嬎銠C標準化處理后可降低人工依賴，自動獲得，如采用模擬退火算法等進行優(yōu)化處理，可極大提高頻率使用效率，降低覆蓋網(wǎng)綜合干擾水平，加快我國地面數(shù)字電視頻率規(guī)劃進程。