一种启发式频率分配算法
摘 要：遗传算法是根据生物学上的染色体基因因子构成机制而产生的一种启发式算法。该算法以群体中的所有个体为对象，通过选择、交叉、变异和重排序等类似生物遗传的操作算子，得到满足一定群体适应度的新种群。遗传算法为频率分配问题提供了解决途径。
关键字：频率分配 遗传算法 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种颜色对其着色，在没有其它约束条件下，其解空间是cn。即使在不考虑颜色重复使用（c>n）的情况下，其解空间也达到n!。这两者都是超越数，在c和n的值较大的情况下想利用穷举搜索的方法求得问题的最优解在时间上是不可行的。
在工程实践中许多npc问题使用一些使用的近似算法得到问题的可行解。这些方法包括[]：只对问题的特殊实例求解；动态规划（dp）或者分支界限算法（bc）；概率算法；求近似解；启发式算法（heufistic 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. 遗传算法在频率分配问题中的适用性
2．1 遗传算法的原理
遗传算法(genetic algorithms ga)是根据生物学上的染色体基因因子构成机制而产生的。1975年holland教授首次提出了ga的思想，从而吸引了大批的研究者，迅速推广到优化、搜索、机器学习等方面。遗传算法是一种全局优化算法，其仅以目标函数值为搜索依据，通过群体优化搜索和随机执行基本遗传运算，实现遗传群体的不断进化，适合解决组合优化问题和复杂非线性问题[6]。
利用遗传算法解最优化问题，首先应对可行域中的点进行编码（一般采用二进制编码），然后在可行域中随机挑选一些编码组成作为进化起点的第一代编码组，并计算每个解的目标函数值，也就是编码的适应度。接着就像自然界中一样，利用选择机制从编码组中随机挑选编码作为繁殖过程前的编码样本。选择机制应保证适应度较高的解能够保留较多的样本；而适应度较低的解则保留较少的样本，甚至被淘汰。在接下去的繁殖过程中，遗传算法提供了交叉和变异两种算子对挑选后的样本进行交换。交叉算子交换随机挑选的两个编码的某些位，变异算子则直接对一个编码中的随机挑选的某一位进行反转。这样通过选择和繁殖就产生了下一代编码组。重复上述选择和繁殖过程，直到结束条件得到满足为止。进化过程最后一代中的最优解就是用遗传算法解最优化问题所得到的最终结果。
实践表明，遗传算法解最优化问题的计算效率比较高、适用范围相当广。为了解释这一现象，holland给出了模式定理。所谓模式，就是某些码位取相同值的编码的集合。模式定理说明在进化过程的各代码中，属于适应度高、阶数低且长度短的图式的编码数量将随代数以指数形式增长[6]。最近的研究则表明，上述遗传算法经适当改进后对任意优化问题以概率1收敛于全局最优解[5]。
2．2 遗传算法的基本结构
在遗传算法中，将问题的求解的过程，看成一个在候选解空间寻找满足问题要求的解或近似解的搜索过程。遗传算法的重点在适应规划和适应度量方面。遗传算法的适应规划用于指导算法怎么样在空间进行搜索，一般采用遗传算子(或称遗传操作)诸如交配(crossover)和变异(mutation)等，以及模拟自然过程的选择机制，采用计算适应值的方法来评估一个候选解的优劣。
遗传算法求解问题的基本步骤可以描述如下：
1. 首先生成一组初始的候选解群体(假设为n个候选解个体)，称为第0代；
2. 计算群体中各个候选解的适应值；
3. 如果有候选解满足算法终止条件， 算法终止，否则继续4；
4. 根据交配概率，将候选解群体中的个体随机两两配对，进行交配操作以生成新的候选解；
5. 根据变异概率，对4中生成的候选解群中的每个个体进行变异操作；
6. 使用选择机制形成新一代候选解；转2。
ga算法具有下述特点： ga是对问题参数的编码组进行，而不是直接对参数本身；ga的搜索是从问题解的编码组开始搜索，而不是从单个解开始；ga使用目标函数值（适应度）这一信息进行搜索，而不需导数等其他信息；ga算法使用的选择、交叉、变异这三个算子都是随机操作，而不是确定规则。
遗传算法通过编码和遗传操作，达到了处理的并行性，可以同时处理群体中的多个个体，即同时对搜索空间内的多个解进行评估，具有较好的全局搜索性能，减少了限于局部最优解的风险。
3. 遗传算法用于频率分配
3．1 算法的基本流程
采用遗传算法的fap基本流程
3．2 遗传算子的选择
3．2．1 选择算子
选择算子在父代群体中选出父体和母体。生物界中，父母亲素质比较高的其后代素质高的概率也大。模拟这种现象，在fap中选择算子采用轮赌算法实现。
轮赌算法流程如下：
sum=0; i=0;
wheelpos=rand()*sumfitness;
for(sum<wheelpos && i<pop-size)
｛
i++;
if(i≥pop-size)
｛
sum=0; i=0
wheelpos=rand()*sumfitness;
｝
j=rand()*pop-size;
sum+=fitness［j］;
｝
return j;
3．2．2 交叉算子
交叉算子让父体和母体互相交换某部分基因而产生下一代个体的雏形，起全局搜索的作用。交叉算子通常有单点交叉、双点交叉、多点交叉等等。在频率自动分配的算法中，为了不破坏基因段内部频点间的关系，采用单点交叉和双点交叉比较合适。此外，在生物界中并不是两个个体相遇了就一定会结合，模拟此现象，引入交叉因子pc。
其基本流程如下：
//flip函数中，产生一个0到1的随机数，若小于pc，则返回1，否则返回0
if(flip(pc))
crossover1(mother,father);
else if(flip(pc))
crossover2(mother,father);
else
copy(mother);
copy(father);
3．2．3 变异算子
变异算子对后代个体的某些基因进行变异，起局部搜索的作用.生物界中，父母的染色体交叉后产生后代个体的染色体雏形，这个雏形在成长过程中会发生基因的变异，正是这种变异使得下一代的群体中会出现各种特征的个体.另外，生物界中并非每个基因都会变异，模拟此现象，引入变异因子pm，使用方法与交叉因子类似。
其基本流程如下：
while(all frequentpoint)
{
if(flip(pm)) mutate(frequentpoint)；}
4. 工程上需要注意的问题
4．1 初始候选种群
由于遗传算法和其它启发式算法一样，不对全部解空间进行穷举搜索，因此初始的候选解群体的选择会对得到最终解的速度和质量有影响。初始的候选解群体在解空间内分布得越均匀，它们拥有的遗传基因就越有代表性。实践中采用文献[7]的gecp得到以各个顶点为主顶点的可行解作为初始候选种群。
4．2 编码方案
编码就是用一种数字排列方案来表示问题的解的方法，利用编码将问题的解空间映射到ga算法的编码空间。编码方案的选择依赖于问题的性质，并影响到算法内操作的设计，是影响算法性能的重要因素。常见的编码方案有二进制编码、十进制编码、实数编码等。频率分配问题适合采用十进制编码方案，每个码表示一条通信链路，码值表示分配的信道编号。
4．3 适配值函数
适配值函数对个体（频率分配方案）进行评价，也是优化过程发展的依据。可以采用如下方式来计算适应度：
fitness=1000 / σ (pri×seperate(freq))。
其中：
pri 是节点的加权值；
函数seperate(freq)是节点中各条链路发频率同其它链路的收频率间隔的和；
参考文献：
[1] robert y, panos m. pardalos etc, frequency assignment problems, handbook of combinatorial optimization, kluwer academic publishers,1999
[2] vittorio m., antonella c., an ants heuristic for the frequency assignment problem, /china/">中国科学技术大学硕士学位论文 1998
[8] 王晓东：《计算机算法设计与分析》 电子工业出版社 2001
[9] 高建文，李单镝： 通信网频率分配算法设计 无线电通信技术 vol25（5）1999