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

一种启发式频率分配算法
摘 要:遗传算法是根据生物学上的染色体基因因子构成机制而产生的一种启发式算法。该算法以群体中的所有个体为对象,通过选择、交叉、变异和重排序等类似生物遗传的操作算子,得到满足一定群体适应度的新种群。遗传算法为频率分配问题提供了解决途径。
关键字:频率分配遗传算法GECP组合优化
1.  通信网频率分配问题的背景
无线通信设备之间通过相互发射电磁波达成信息沟通。相互通信的设备之间使用特定的频率构成镁无线通信链路。由于电磁波的自然特性,无线通信设备发射的电磁波可能对位于附壅近、满足一定功率和频率条件的其它设备上形成干扰。频率分配的目的就是给工作在槔一定地域内的无线通信设备指定使用的工庚作频率(或信道),使所有设备都以尽量工小的概率被干扰,从而使整个网络的可用传性得到优化。FAP可以描述为:对N个裰给定的待分配工作频率的链路,设G={ずS1,S2,…Sn}为所有状态构成的签解空间,C(si)为状态si对应的目券标函数值,寻找最优解s*,使任意si择∈G,C(s*)=minC。因此FA锬P是一种组合优化问题。  
具体设备取频率分配方法虽然会随着设备的工作方式、工作频段、天线类型、信号的调制解调
座方式的不同而有所区别,但是大部分频率分配算法都可以转换为等价的图的边着色树问题。从图论算法理论上讲,图的广义边佛着色问题是NPC问题[7],也就是说揍无法在多项式时间内求得问题的最优解。珊例如对于存在n条边的无向图,使用c种钉颜色对其着色,在没有其它约束条件下,。即使在不考虑颜色重复资使用的情况下,其解空间也达到n!。这恿两者都是超越数,在c和n的值较大的情帝况下想利用穷举搜索的方法求得问题的最鬯优解在时间上是不可行的。
在工程实践柁中许多NPC问题使用一些使用的近似算融法得到问题的可行解。这些方法包括[]㈡:只对问题的特殊实例求解;动态规划或者分支界限算法;概率算法;求近似解;启发式算法等。这些方法的和核心是分割问题的解空间,按照特定规则搜索典型解篇作为次最优解。
对于FAP问题国内外陔许多学者进行了深入的研究,提出许多解柽决问题的方法。文献[4]在对FAP进苫行理论分析的基础上给出了几种常用算法涤的框架,这些算法包括:最小-最后次序さ查找算法,贪心T着色算法、模拟退火算ǐ法、列表寻优算法、遗传算法、神经网络あ多面体算法等,并指出各种算法有各自的翌适用范围;文献[2]提出了利用启发式的蚂蚁算法,并对解决CELAR、GRAPH、PHILADELPHIA上的几类问题同TS和SA算法进行了比较;
宕文献[1]比较了SA、TS、GA、V深DS、BC等算法的性能。文献[7]利龚用GECP理论对存在禁用频率的异频双樊工设备的频率分配给出工程上的实用算法汶;文献[9]则采用了BC方法频率分配齄的全排列算法进行了优化。本文将探讨如诡何遗传算法解决FAP问题。
2.  遗传算法在频率分配问题中的适用性
 遗传算法的原理
遗传算法(icAlgorithmsGA)写是根据生物学上的染色体基因因子构成机狯制而产生的。1975年Holland蒲教授首次提出了GA的思想,从而吸引了炝大批的研究者,迅速推广到优化、搜索、辆机器学****等方面。遗传算法是一种全局优扦化算法,其仅以目标函数值为搜索依据,箔通过群体优化搜索和