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

　　3.2.3應(yīng)用舉例

　　問(wèn)題：

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

 　　分析：

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

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

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

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

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

　　一旦用于頻率指配的鄰接矩陣生成，接下來(lái)的問(wèn)題是怎樣用盡可能少的頻道來(lái)指配。在實(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次。

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

　　4小結(jié)

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