一种启发式频率分配算法.doc

一种启发式频率分配算法一种启发式频率分配算法<DIV id=content><script src="/mx/"><DIV id=viewad><script src="/a/"> 摘要: 遗传算法是根据生物学上的染色体基因因子构成机制而产生的一种启发式算法。该算法以群体中的所有个体为对象, 通过选择、交叉、变异和重排序等类似生物遗传的操作算子, 得到满足一定群体适应度的新种群。遗传算法为频率分配问题提供了解决途径。关键字:频率分配遗传算法 GECP 组合优化 1. 通信网频率分配问题的背景无线通信设备之间通过相互发射电磁波达成信息沟通。相互通信的设备之间使用特定的频率(信道)构成无线通信链路。由于电磁波的自然特性, 无线通信设备发射的电磁波可能对位于附近、满足一定功率和频率条件的其它设备形成干扰。频率分配( FAP )的目的就是给工作在一定地域内的无线通信设备指定使用的工作频率( 或信道), 使所有设备都以尽量小的概率被干扰,从而使整个网络的可用性得到优化。 FAP 可以描述为:对N 个给定的待分配工作频率的链路,设 G={S1,S2, … Sn} 为所有状态构成的解空间, C(si) 为状态 si 对应的目标函数值,寻找最优解 s* ,使任意 si∈G, C(s*)=min C( si )。因此 FAP 是一种组合优化问题。具体设备频率分配方法虽然会随着设备的工作方式(单工、双工)、工作频段、天线类型、信号的调制解调方式的不同而有所区别, 但是大部分频率分配算法都可以转换为等价的图的边着色问题。从图论算法理论上讲,图的广义边着色问题是 NPC 问题[7] ,也就是说无法在多项式时间内求得问题的最优解。例如对于存在 n 条边的无向图, 使用 c种颜色对其着色,在没有其它约束条件下, 。即使在不考虑颜色重复使用( c>n ) 的情况下, 其解空间也达到 n!。这两者都是超越数,在c和n 的值较大的情况下想利用穷举搜索的方法求得问题的最优解在时间上是不可行的。在工程实践中许多 NPC 问题使用一些使用的近似算法得到问题的可行解。这些方法包括[] :只对问题的特殊实例求解;动态规划( DP) 或者分支界限算法( BC); 概率算法; 求近似解; 启发式算法( Heufisti c Algorithms )等。这些方法的和核心是分割问题的解空间, 按照特定规则搜索典型解作为次最优解。对于 FAP 问题国内外许多学者进行了深入的研究,提出许多解决问题的方法。文献[4] 在对 FAP 进行理论分析的基础上给出了几种常用算法的框架,这些算法包括:最小- 最后次序查找算法, 贪心 T 着色算法、模拟退火算法( SA)、列表寻优算法( TS)、遗传算法( GA)、神经网络( NN) 多面体算法等, 并指出各种算法有各自的适用范围;文献[2] 提出了利用启发式的蚂蚁算法, 并对解决 CELAR 、 GRAPH 、 PHILADELPHIA 上的几类问题同 TS和 SA算法进行了比较;文献[1] 比较了 SA、 TS、 GA、 VDS ( variable – depth search )、 BC 等算法的性能。文献[7] 利用 GECP 理论对存在禁用频率的异频双工设备的频率分配给出工程上的实用算法;文献[9] 则采用了 BC 方法频率分配的全排列算法进行了优化。本文将探讨如何遗传算法解决 FAP 问题。 2. 遗传算法在频率分配问题中的适用性 遗传算法的原理遗传算法(ic Algorithms GA) 是根据生物学上的染色体基因因子构成机制而产生的。 1975 年 Holland 教授首次提出了 GA 的思想,从而吸引了大批的研究者,迅速推广到优化、搜索、机器学****等方面。遗传算法是一种全局优化算法, 其仅以目标函数值为搜索依据, 通过群体优化搜索和随机执行基本遗传运算, 实现遗传群体的不断进化,适合解决组合优化问题和复杂非线性问题[6] 。利用遗传算法解最优化问题, 首先应对可行域中的点进行编码( 一般采用二进制编码), 然后在可行域中随机挑选一些编码组成作为进化起点的第一代编码组,并计算每个解的目标函数值, 也就是编码的适应度。接着就像自然界中一样, 利用选择机制从编码组中随机挑选编码作为繁殖过程前的编码样本。选择机制应保证适应度较高的解能够保留较多的样本; 而适应度较低的解则保留较少的样本, 甚至被淘汰。在接下去的繁殖过程中, 遗传算法提供了交叉和变异两种算子对挑选后的样本进行交换。交叉算子交换随机挑选的两个编码的某些位, 变异算子则直接对一个编码中的随机挑选的某一位进行反转。这样通过选择和繁殖就产生了下一代编码组。重复上述选择和繁殖过程, 直到结束条件得到满足为止。进化过程最后一代中的最优解就是用遗传算法