基于模拟退火算法的地面电视频率指配方法研究

　　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小结

　　近年来，根据"科学发展观要求"，为使频率规划决策更具科学性，我国在多次地面电视频率规划工程中，均使用了覆盖面积、人口，可用场增量等统计指标，取得了良好的收效。由于指标数据的获得需考虑复杂的台站地理关系和统计模型，耗时费力，在时间来不及时，不得已还要借助经验进行频率规划决策。分析表明，上述指标的统计方法具备一定规律，经过适当的计算机标准化处理后可降低人工依赖，自动获得，如采用模拟退火算法等进行优化处理，可极大提高频率使用效率，降低覆盖网综合干扰水平，加快我国地面数字电视频率规划进程。