3.2.3應(yīng)用舉例

　　問題：

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

 　　分析：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　結(jié)果

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

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

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

　　4小結(jié)

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