摘 要：遗传算法是根据生物学上的染色体基因因子构成机制而产生的一种启发式算法。该算法以群体中的所有个体为对象，通过选择、交叉、变异和重排序等类似生物遗传的操作算子，得到满足一定群体适应度的新种群。遗传算法为频率分配问题提供了解决途径。
关键字：频率分配 遗传算法 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 变异算子
变异算子对后代个体的某些基因进行变异，起局部搜索的作用.生物界
