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

　　3.2.3應用舉例

　　問題：

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

 　　分析：

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

　　如果采用世界最快的超級計算機進行"窮舉"，運算速度按每秒約280，6萬億次計算，需要t=2020／(280.6×1012)秒≈11849年。可見，采用此方法不可能在有生之年計算比較所有方案，從中找出絕對的最佳方案。因此，只能采用某些優化算法如模擬退火算法等找到滿足規劃要求的"近似最佳"方案。

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

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

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

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

 　　模擬退火算法的具體實現步驟：

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

　　初始解狀態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領域中產生滿足約束條件的新解Freq′；

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

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

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

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

　　結果

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

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

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

　　4小結

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