摘 要：遗传算法是根据生物学上的染色体基因因子构成机制而产生的一种启发式算法。该算法以群体中的所有个体为对象，通过选择、交叉、变异和重排序等类似生物遗传的操作算子，得到满足一定群体适应度的新种群。遗传算法为频率分配问题提供了解决途径。
关键字：频率分配 遗传算法 GECP 组合优化
1. 通信网频率分配问题的背景
无线通信设备之间通过相互发射电磁波达成信息沟通。相互通信的设备之间使用特定的频率（信道）构成无线通信链路。由于电磁波的自然特性，无线通信设备发射的电磁波可能对位于附近、满足一定功率和频率条件的其它设备形成干扰。频率分配（FAP）的目的就是给工作在一定地域内的无线通信设备指定使用的工作频率(或信道)，使所有设备都以尽量小的概率被干扰，从而使整个网络的可用性得到优化。FAP可以描述为：对N个给定的待分配工作频率的链路，设G={S1,S2,…Sn}为所有状态构成的解空间，C(si)为状态si对应的目标函数值，寻找最优解s*，使任意si∈G，C(s*)=min C（si）。因此FAP是一种组合优化问题。
在工程实践中许多NPC问题使用一些使用的近似算法得到问题的可行解。这些方法包括[]：只对问题的特殊实例求解；动态规划（DP）或者分支界限算法（BC）；概率算法；求近似解；启发式算法（Heufistic Algorithms）等。这些方法的和核心是分割问题的解空间，按照特定规则搜索典型解作为次最优解。