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

一种启发式频率分配算法.doc一种启发式频率分配算法
摘要:遗传算法是根据生物学上的染色体基因因子构成机制而产生的一种启发式算法。该算法以群体中的所有个体为对象,通过选择、交叉、变异和重排序等类似生物遗传的操作算子,得到满足一定群体适应度的新种群。遗传算法为频率分配问题提供了解决途径。
关键字:频率分配遗传算法 GECP 组合优化
1. 通信X频率分配问题的背景
无线通信设备之间通过相互发射电磁波达成信息沟通。相互通信的设备之间使用特定的频率(信道)构成无线通信链路。由于电磁波的自然特性,无线通信设备发射的电磁波可能对位于附近、满足一定功率和频率条件的其它设备形成干扰。频率分配(FAP)的目的就是给工作在一定地域内的无线通信设备指定使用的工作频率(或信道),使所有设备都以尽量小的概率被干扰,从而使整个X络的可用性得到优化。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);概率算法;求近似解;启发式算法(Heufistic Algorithms)等。这些方法的和核心是分割问题的解空间,按照特定规则搜索典型解作为次最优解。
对于FAP问题国内外许多学者进行了深入的研究,提出许多解决问题的方法。文献[4]在对FAP进行理论分析的基础上给出了几种常用算法的框架,这些算法包括:最小-最后次序查找算法,贪心T着色算法、模拟退火算法(SA)、列表寻优算法(TS)、遗传算法(GA)、神经X络(NN)多面体算法等,并指出各种算法有各自的适用范围;文献[2]提出了利用启发式的蚂蚁算法,并对解决CELAR、GRAPH、PHILADELPHIA上的几类问题同TS和SA算法进行了比较;文献[1]比较了SA、TS、GA、VDS(variable
–depth search)、BC等算法的性能。文献[7]利用GECP理论对存在禁用频率的异频双工设备的频率分配给出工程上的实用算法;文献[9]则采用了BC方法频率分配的全排列算法进行了优化。本文将探讨如何遗传算法解决FAP问题。
2. 遗传算法在频率分配问题中的适用性
遗传算法的原理
遗传算法(Geic Algorithms GA)是根据生物学上的染色体基因因子构成机制而产生的。1975年Holland教授首次提出了GA的思想,从而吸引了大批的研究者,迅速推广到优化、搜索、机器学****等