模拟退火算法的地面电视频率指配方法研究
2008-8-8 11:28:21 DVBCN数字电视中文网 人气() 作者：李薰春 史虹湘 杨明 李栋 来源: 电子产品世界
的液态，系统能量也随温度提高不断增大，冷却时，液体粒子的热运动渐渐减弱，温度降至结晶温度时，粒子运动变为围绕晶体格点的微小震动，液体开始凝固成固体的晶态，这个过程称为"退火"，退火过程必须徐徐进行，以使系统在每一温度下都达到平衡态，最终达到固体的基态，此时系统能量最小。冷却时若急剧降低温度，将引起淬火效应，固体将冷凝为非均匀的亚稳态，系统能量无法达到最小值。根据Boltzmann有序性原理，退火过程遵循热平衡封闭系统的热力学过程--自由能减少定律：
"对于与周围环境交换热量而温度保持不变的封闭系统，系统状态的自发变化总是朝着自由能减少的方向进行，当自由能达到最小值时，系统达到平衡态"。
通过对固体退火过程的研究，于1982年首先意识到固体退火过程与离散系统模型中的组合优化问题之间存在着某种相似性，同时，受到Metropolis等对固体在常温下达到热平衡过程所做的模拟中的启发，Kirkpatrick提出把Metropolis准则引入到优化过程中，建立一种对Metropolis算法进行迭代的组合优化算法，由于该算法模拟固体退火的过程，因此经常称之为"模拟退火算法"。
3.2频率指配中的模拟退火算法
3.2.1实现步骤
3.2.2目标函数
在频率指配过程中，目标函数E可包含以下几项：
目标函数E可用于评估频率指配方案的优劣。其中(i=1，2，…，6)是加权系数，用来反映上述各因子的相对重要程度。除上述指标外，其他指标如覆盖及干扰的人口和面积等也可以作为加权因子。
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。
